Abstract
We study the implementation of an actor language, OAL, on a massively parallel message-passing architecture: MEGA. Motivations and implementation constraints are exposed. A simulator has been built to investigate resource consumption. First results show the feasibility of the implementation but indicates serious problems in memory usage. Load-balancing strategies are presented which partially solve the memory problem. Actors adequacy as a model for exploiting massive parallelism is discussed in conclusion.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Bibliography
G. Agha, "Actors: a model for concurrent computation in distributed systems", AI tech. rep. 844, MIT, 1985.
P. America, "POOL-T: A Parallel Object-Oriented Language", in Object-Oriented Concurrent Programming, eds. A. Yonezawa, M. Tokoro, MIT Press 1988.
J. Amsterdam, "Load Balancing Strategies for the Apiary", dissertation for the degree of Bachelor, Hardvard College, May 1984.
W.C. Athas, "Fine Grain Concurrent Computations", Tech. Rep 5242, Dep. of Computer Science, California Institute of Technology, May 1987.
W.C. Athas, C.L. Seitz, “Multicomputers: Message-Passing Concurrent Computers”, IEEE Computer, vol. 21, no 8, August 1988, pp 9–24
G. Attardi "Building Expert Systems with Omega", DELPHI, tech. rep. ESP/85/2, 1985.
M.J. Beckerle, K. Ekanadham, "Distributed Garbage Collection with no Global Synchronisation", IBM research report RC 11667 (#52377) january 1986.
J-L. Béchennec, “MegaPack: a 3D Packaging for Massively Parallel Computers”, LRI-Archi TR 89-07-1989
J-L. Béchennec, C. Chanussot, V. Neri and D. Etiemble, “VLSI Design of a 3-D Highly parallel message passing architecture”, International Workshop on VLSI design for Artificial Intelligence and Neural Networks, Septembre 90
D. I. Bevan, "Distributed Garbage Collection Algorithm using Reference Counts", ACM trans. on prog. lang. and syst., vol 2, no3, july 87.
W.F. Burton, M.R. Sleep, “Executing functional programms on a virtual tree of processors”, Proc. ACM Conference on Functional programming languages and computer Architecture — 1981 pp 187–194
F. Baude, G. Vidal-Naquet, "Actors as a parallel programming model", to appear in STACS91.
F. Carré, "Alog: acteurs et programation en logique" (Alog: actors and logic programming) Thèse de docteur ingénieur, juin 1984 (in french).
F. Cappello, J-L Bechennec, D. Etiemble “A RISC Central Processing Unit for a Massively Parallel Architecture”, EUROMICRO 90, Amsterdam, August 90
F. Cappello, C. Germain, J-P. Sansonnet, “Design of a reduced instruction set for massively parallel functional programming”, LRI-Archi TR 90-07, also submitted to publication.
W.D. Clinger, "Foundation of Actor Semantics", PhD thesis, MIT May 1987 (ai-tr-633).
R. Cornu-Emieux, G. Mazaré, P. Objois, “A VLSI asynchronous cellular array to accelerate logical simulations”, proc. of the 30th. Midwest International Symposium on Circuit and Systems, 1987.
A; Couvert, A. Maddi, R. Pédrono "Object Sharing in Distributed Systems — Principles of garbage collection", IRISA, INRIA report 963, January 1989 (in french)
W.J. Dally, “Wire-Efficient VLSI Multiprocessor Communication Networks”, 1987 Stanford Conference on Advanced Research in VLSI, 1987, pp 391–415
W.J. Dally, “Fine-Grain Message-Passing Concurrent Computers”, proc. of the Third Conference on Hypercubes Concurrent Computers and Applications, vol. 1, Pasadena, January 19–20, 1988
D. Eppstein, Z. Galil, "Parallel algorithmic Technic for Combinatorial Computation" Ann. rev. Compt. Sci., 3:233–283, 1988
Esprit Project P440, "Final Report", December 1989.
J. Fowler, "Studies of algorithms adapted to a network of dynamic processes", University of Edinburgh, M.Sc Report September 1990.
C. Germain, J-L. Béchennec, D. Etiemble, J-P. Sansonnet, “A New Communication Design for Massively Parallel Message-Passing Architectures”, IFIP Working Conf. on Decentralized Systems 1989, North-Holland ed.
C. Germain, J-L Béchennec, D. Etiemble, J-P. Sansonnet, “An Interconnection Network and a Routing Scheme for a Massively Parallel Message-Passing Multicomputer”, Third Symp. on Frontiers 90 conference on Massively Parallel Computation, October 8–10 College Park, MD
C. Germain, J-L. Giavitto, "A Comparaison of Two Routing strategy for Massively Parallel Computers", 5th International Symposium on Computer and Information Science, Capadoccia, Nov. 90.
C. Germain, J-L. Giavitto, J-P. Sansonnet, "Implementation d'un paradigme de progrmmation fonctionnelle sur une machine massivement parallele" (implementation of a paradigmatic functionnal programming style on a massively parallel computer), LRI-Archi TR 90-07, also submitted to publication (in french).
A. Gibbons, W. Rytter, "Efficient parallel algorithms" Cambridge University Press — 1988, (chap. 5)
D.C. Grunwald, D.A. Reed, “Benchmarking Hypercubes Hardware and Software”, Hypercube Multiprocessors 87, 1987, pp 169–177
C. Hewitt, B. Smith, "A PLASMA Primer", rough draft, 13:17 1975, MIT-AIL
Hewitt C., "Viewing Control Structure as Patterns of Passing Messages", MIT Artificial Intelligence Memo 410, December 1976
Hewitt C., "Apiary multiprocessor architecture knowledge system", prooc. of the joint SRC/Univ. of Newcastle upon Tyne Workshop on VLSI, Machine Architecture and Very High Level LAnguages, October 1980.
W.D. Hillis, “The Connection Machine”, The MIT Press, 1985
W.D. Hillis, G.L. Steele, “Data Parallel Algorithms”, CACM vol.29 no12, December 1986.
P. Hudak, R.M. Keller, "Garbage collection and task deletion in distributed applicative processing systems", proc. ACM conference on Lisp and Functional Programming, 1982 pp 168–178.
J. Hughes, "A Distributed Garbage Collection Algorithm" proc. ACM conference on Functional Programming Languages and Computer Architecture, Nancy 1985, LNCS 201.
INTEL Scientific Computers, “Intel iPSC System Overview”, Order no 310610-001, 1986
W. Kornfeld, "Using Parallel Processing for Problem Solving", AI Memo 561, MIT, december 1979.
F.T. Leighton, B. Maggs, S. Rao, “Universal Packet Routing Algorithms”,29 st IEEE Symp. on Foudations of Computer Science,1988, pp 256–269
H. Lieberman, "A preview of Act-1", AI Memo 625, MIT AI Laboratory, 1981.
H. Lieberman, C. Hewitt, "A real-time garbage collector based on the lifetimes of objects", CACM vol. 26 no6, pp 419–428 June 1983.
F.C.H. Lin, "Load Balancing and Fault Tolerance in Applicative Systems", Ph.D. Dissertation, Dep. of Computer Science, Univ. of Utah, 1985.
L. Litzler, M. Tréhel, "The kernel of an actor language for a multi-transputer system", ISMM Lugano, june 1990.
S.F. Nugent, “The iPSC/2 Direct-Connect Communications Technology”, 3° Conf. on Hypercube Concurrent Computers and Applications, 1988
A. Pnueli, "Application of temporal logic to the specification and verification of reactive systems: a survey of current trends", LNCS, 1986.
D.A. Reed, R.M. Fujimoto, “Multicomputer Networks — Message-Based Parallel Processing”, The MIT Press, 1987
J.-P. Sansonnet, “Concepts d'Architectures Avancées”, Tome 1, cours de DEA de l'Université d'Orsay, LRI 1990 (in french).
C.L. Seitz, “The Cosmic Cube”, Com. ACM, vol. 28, no 1, Jan. 1985, pp 22
W. Stallings Ed., “Reduced Instruction Set Computers Tutorial”, IEEE Computer Society Press — 1986
G.L. Steele Jr., G. Sussman, “Scheme: An interpreter for the extended lambda calculus”, MIT AI Lab memo 349–1975
B. Stroustrup, "The C++ Programming Language" Addison-Weslay, 1987.
D. G. Theriault, "Issues in the design and implementation of Act2", tech. rep. ai-tr èé!, MIT, June 1983.
P. Treleaven, D.R. Brownbridge, R.P. Hopkins, “Data driven and Demand Driven Architectures”, ACM Computing survey Vol 14 no 1 — 1982
L.G. Valiant, “A scheme for fast parallel communication”, SIAM Jour. on Computing, vol. 11, no 2, Mai 1982, pp 350–361
L.G. Valiant "Bulk-synchronous parallel computers" Prooc. of the A.I. and Message Passing Architecture Conference, p 15–22, London, 1989. J. Wiley.
P. Watson, I. Watson, "An efficient garbage collection scheme for parallel computer", proc. of PARLE II, LNCS 259.
A. Yonezawa, E. Shibayama, H. Matsuda, T. Takada, Y. Honda "Modelling and Programming in an Object Oriented Concurent Language ABCL/1", Research report C-75, Dept. of Information Science, Tokyo Institute of Technology, Nov. 86.
A. Yonezawa, H. Matsuda, E. Shibayama "An Approach to Object Oriented Concurrent Programming: a language ABCL", Proc. of the third Workshop on Object-Oriented Languages, Paris 1986.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Giavitto, JL., Germain, C., Fowler, J. (1991). OAL: An implementation of an actor language on a massively parallel message-passing architecture. In: Bode, A. (eds) Distributed Memory Computing. EDMCC 1991. Lecture Notes in Computer Science, vol 487. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0032951
Download citation
DOI: https://doi.org/10.1007/BFb0032951
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-53951-3
Online ISBN: 978-3-540-46478-5
eBook Packages: Springer Book Archive