Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Baude, Francoise
Publisher: University of Warwick. Department of Computer Science
Languages: English
Types: Other
Subjects: QA76
The more user-friendly tools for expressing data-parallelism are encompassed by the PRAM language mechanisms (mainly, global addressing space, implicit processes synchronization). In this paper, we evaluate the cost for implementing such mechanisms on the only class of parallel architectures that should prove to be really scalable as well as versatile, i.e. MIMD fine-grained multicomputers. Being massively parallel, these architectures are constrained to not exceed a given wire density and also to have fine-grained processing nodes. For these reasons, recent algorithmic and hardware technics for hidding communication latency of PRAM emulations by parallel slackness do not apply. We consider an abstraction of these machines by reasoning in terms of the actor model of concurrent computation. Given the architectural constraints raised by the chosen class of architectures, the idea for implementing any PRAM program is to transform it into an actor program such that it can be efficiently implemented on the target machine via mapping technics such as for exemple graph embedding. This requires the underlying communication graph of the actor program to be predictable and sparse. This transformation is grounded on probabilistic theoretical simulations of PRAMs on parallel machines based on sparse communication networks.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [ACS89] A. Aggarwal, A.K. Chandra, and M. Snir. Communication Latency in PRAM Computations. In Proc. of the 1989 ACM Syrnpos'iurn on Parallel Algorithms and Archi,tectures, pages 11-21-, 1989.
    • [AFL83] E. Arjomandi, M.J. Fischer, and N.A. Lynch. Efficiency of synchronous versus asynchronous distributed systerns. J. ACM,30:449-456, 1983.
    • [AghB6] G. Agha. ACTORS : A model of concurrent computation'in di,stributed, systerns. MIT Press, Cambridge Massachuseits, 1986.
    • [AghB9] G. Agha. Supporting Multiparadigm Programming on Actor Architectures. In E. Odjyk, M.Rem, and J.C. Syre, editors, Proceed,ings of PARLE 89, pages 1-19, Eindhoven, 1989. Springer Verlag.
    • [AthB7] W.C. Athas. Fine grain concurrent computation. CALTECH Technical Report 5242:TP;.87, 1987.
    • [Bau91] F. Baude. Utilisation du paradigme acteur pour le calcul parallile. PhD thesis, Universit6 Paris-Sud, Orsay, 1991.
    • [8H85] A. Borodin and J. Hopcroft. Routing merging and sorting on parallel rnodels of computatior. Journal of Comp. and SEstem Sciences, 30:130- 145, 1995.
    • [BVN91] F. Baude and G. Vidal-Naquet. Actors as a parallel programming model. h Proc. of the 8th Symposi,um of Theoret'ical Aspects of Computer Science, volume 480, pages 184-195. Ll{CS, 1"991.
    • [Cli81] W.D.C. Clinger. Found,ation of Actor Semantics. PhD thesis, MIT, Cambridge, Mass, 1981.
    • [DW89] W.J. Dally and D.S. Wills. Universai Mechanisms for Concurrency. In E. Odjyk, M.Rem, and J.C. Syre, editors, Proceed'ings of PARLE 89, pages 19 33, Eindhoven, 1989. Springer Verlag.
    • IGBES9O] C. Geunain, J.L B6chennec, D. Etiemble, and J.P Sansonnet. An interconnection network and a routing scheme for a rnassively parallel messagepassing multicomputer. h Proc. of the ?rd Symposium on Frontiers of Massiaely Parallel Computation, College Park, MD, 1990.
    • [Gib89] P.B. Gibbons. A More Practical PRAM Model. In Proc. of the 1989 ACM Symposium on Parallel Algorithms and Architectures, pages 158 168, 1989.
    • [GMT88] H. Gazit, G.L. Miller, and S.H. Teng. Concurrent computations, chapter Optimal tree contraction in the EREW PRAM model, pages 139-155. Plenurn Publishing Corporation, 1988.
    • [Gol82] L. M. Goldschlager. A lJniversal Interconnection Pattern for Parallel Cornputers. J. ACM, 29:7073-1086, 1982.
    • [GR88] A. Gibbons and W. Rytter. Efficient parallel alltorithms. Cambridge University Press, Cambridge, 1988.
    • fKR90] R.M. Karp and V. Ramachandran. Hand,book of theoretical computer sc'ience, volume B, chapter Parallel algorithms for shared-memory machines, pages 869-942. Elsevier, 1990.
    • [KU88] A.R. Karlin and E. Upfai. Parallel hashing : An efficient implementation of shared mernory. J. of ACM,35:876 892, 1988.
    • [N{evB6] F. Meyer:auf der Heide. Efficient simulations among several models of parallel conputers. SIAM J. Comput,15:106 119, 1986.
    • [MVB4] K. Melhorn and U. Vishkin. Randomized and Deterrninistic Sirnulations of PRAMs by Parallel Machines with Restricted Granularitv of Parallel Memories. Acta Inforrnatica, 2L:339 374, L984.
    • IPVB1] F.P Preparata and J. Vuillemin. The cube-connected cycles : A versatile network for parallel computatiot. Comm. of the ACM,24:300-30g, 1981.
    • [Ran87] A.G. Ranade. How to emulate shared memory. In Proc. of the 28th IEEE symp. on FOCS., pages 185-194, 1987.
    • [RosB1] A.L. Rosenberg. Issues in the study of graph embeddings. In Proc. of the International Workshop WG80, volume 100, pages 150 176. LNCS, 1981.
    • [SieB9] A. Siegel. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In Proc. of the 30th IEEE sEmp. on FOCS., pages 20 25, 1989.
    • [UpfB ] E. Upfal. Efficient schemes for parallei communication. .I. ACM,31:507- 577, L984.
    • [Va190a] L.G. Valiant. A bridging model for parallel computation. Communication-s of the ACM,33:103 111, 1990.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article