Efficient support of location transparency in concurrent object-oriented programming languages

ABSTRACT

We describe the design of a runtime system for a fine-grained concurrent object-oriented (actor) language and its performance. The runtime system provides considerable flexibility to users; specifically, it supports location transparency, actor creation and dynamic placement, and migration. The runtime system includes an efficient distributed name server, a latency hiding scheme for remote actor creation, and a compiler-controlled intra-node scheduling mechanism for local messages and dynamic load balancing. Our preliminary evaluation results suggest that the efficiency that is lost by the greater flexibility of actors can be restored by an efficient runtime system which provides an open interface that can be used by a compiler to allow optimizations. On several standard algorithms, the performance results for our system are comparable to efficient C implementations.

REFERENCES

• 1: Gul Agha, Actors: a model of concurrent computation in distributed systems, MIT Press, Cambridge, MA, 1986
• 2: Gul Agha , Svend Frølund , WooYoung Kim , Rajendra Panwar , Anna Patterson , Daniel Sturman, Abstraction and Modularity Mechanisms for Concurrent Computing, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.2, p.3-14, May 1993 [doi>10.1109/88.218170]
• 3: G. Agha, W. Kim, and R. Panwar. Actor Languages for Specification of Parallel Computations. In G. E. Blelloch, K. Mani Chandy, and S. Jagannathan, editors, DIMACS. Series in Discrete Mathematics and Theoretical Computer Science. vol 18. Specification of Parallel Algorithms, pages 239--258. American Mathematical Society, 1994. Proceedings of DIMACS '94 Workshop.
• 4: Thomas E. Anderson , David E. Culler , David A. Patterson , and the NOW team, A Case for NOW (Networks of Workstations), IEEE Micro, v.15 n.1, p.54-64, February 1995 [doi>10.1109/40.342018]
• 5: Arvind , Robert A. Iannucci, Two fundamental issues in multiprocessing, 4th International DFVLR Seminar on Foundations of Engineering Sciences on Parallel Computing in Science and Engineering, p.61-88, April 1988, Bonn, Germany
• 6: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
• 7: Rohit Chandra , Anoop Gupta , John L. Hennessy, COOL: An Object-Based Language for Parallel Programming, Computer, v.27 n.8, p.13-26, August 1994 [doi>10.1109/2.303616]
• 8: Andrew A. Chien , Vijay Karamcheti , John Plevyak, The concert system--compiler and runtime support for efficient, fine-grained concurrent object-oriented programs, University of Illinois at Urbana-Champaign, Champaign, IL, 1993
• 9: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• 10: David E. Culler , Anurag Sah , Klaus E. Schauser , Thorsten von Eicken , John Wawrzynek, Fine-grain parallelism with minimal hardware support: a compiler-controlled threaded abstract machine, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.164-175, April 08-11, 1991, Santa Clara, California, United States
• 11: A. Malony , B. Mohr , P. Beckman , D. Gannon , S. Yang , F. Bodin , S. Kesavan, Implementing a parallel C++ runtime system for scalable parallel systems, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.588-597, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169802]
• 12: Svend Frølund, Inheritance of Synchronization Constraints in Concurrent Object-Oriented Programming Languages, Proceedings of the European Conference on Object-Oriented Programming, p.185-196, June 29-July 03, 1992
• 13: Andrew S. Grimshaw , W. Timothy Strayer , Padmini Narayan, Dynamic, Object-Oriented Parallel Processing, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.2, p.33-47, May 1993 [doi>10.1109/88.218174]
• 14: W. Horwat. Concurrent Smalltalk on the Message Driven Processor. Master's thesis, MIT, May 1989.
• 15: C. Houck and G. Agha. HAL: A High-level Actor Language and Its Distributed Implementation. In Proceedings of th 21st International Conference on Parallel Processing (ICPP '92), volume II, pages 158--165, St. Charles, IL, August 1992.
• 16: Laxmikant V. Kale , Sanjeev Krishnan, CHARM++: a portable concurrent object oriented system based on C++, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.91-108, September 26-October 01, 1993, Washington, D.C., United States
• 17: V. Karamcheti. Private Communication, 1994.
• 18: V. Karamcheti , A. Chien, Concert-efficient runtime support for concurrent object-oriented programming languages on stock hardware, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.598-607, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169806]
• 19: Vijay Karamcheti , Andrew A. Chien, A comparison of architectural support for messaging in the TMC CM-5 and the Cray T3D, Proceedings of the 22nd annual international symposium on Computer architecture, p.298-307, June 22-24, 1995, S. Margherita Ligure, Italy
• 20: Klaus E. Schauser , Chris J. Scheiman, Experience with active messages on the Meiko CS-2, Proceedings of the 9th International Symposium on Parallel Processing, p.140-149, April 25-28, 1995
• 21: W. Kim , Gul Agha, Comilation of a Highly Parallel Actor-Based Language, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.1-15, August 03-05, 1992
• 22: W. Kim and G. Agha. A Scalable Implementation of Communication Abstractions in Actor Programming. in preparation, 1995.
• 23: Eric J. Koldinger , Jeffrey S. Chase , Susan J. Eggers, Architecture support for single address space operating systems, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.175-186, October 12-15, 1992, Boston, Massachusetts, United States
• 24: Vipin Kumar , Ananth Grama , Anshul Gupta , George Karypis, Introduction to parallel computing: design and analysis of algorithms, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994
• 25: V. Kumar, A. Y. Grama, and V. N. Rao. Scalable Load Balancing Techniques for Parallel Computers. Technical Report 91-55, CS Dept., University of Minnesota, 1991. available via ftp ftp.cs.umn.edu:/users/kumar/lb_MIMD.ps.Z.
• 26: C. Manning. ACORE: The Design of a Core Actor Language and its Compiler. Master's thesis, MIT, Artificial Intelligence Laboratory, August 1987.
• 27: Nicholas Oxhøj , Jens Palsberg , Michael I. Schwartzbach, Making Type Inference Practical, Proceedings of the European Conference on Object-Oriented Programming, p.329-349, June 29-July 03, 1992
• 28: Rajendra Panwar , Gul Agha, A methodology for programming scalable architectures, Journal of Parallel and Distributed Computing, v.22 n.3, p.479-487, Sept. 1994 [doi>10.1006/jpdc.1994.1105]
• 29: Kenjiro Taura , Satoshi Matsuoka , Akinori Yonezawa, An efficient implementation scheme of concurrent object-oriented languages on stock multicomputers, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.218-228, May 19-22, 1993, San Diego, California, United States
• 30: K. Taura, S. Matsuoka, and A. Yonezawa. ABCL/f: A Future-Based Polymorphic Typed Concurrent Object-Oriented Language - Its Design and Implementation. In G. E. Blelloch, K. Mani Chandy, and S. Jagannathan, editors, DIMACS. Series in Discrete Mathematics and Theoretical Computer Science. vol 18. Specification of Parallel Algorithms, pages 275--291. American Mathematical Society, 1994. Proceedings of DIMACS '94 Workshop.
• 31: Thinking Machine Corporation. Connection Machine CM-5 Technical Summary, revised edition edition, November 1992.
• 32: Thinking Machine Corporation. CMMD Reference Manual Version 3.0, May 1993.
• 33: Nalini Venkatasubramanian , Gul Agha , Carolyn L. Talcott, Scalable Distributed Garbage Collection for Systems of Active Objects, Proceedings of the International Workshop on Memory Management, p.134-147, September 17-19, 1992
• 34: Thorsten von Eicken , Anindya Basu , Vineet Buch, Low-Latency Communication Over ATM Networks Using Active Messages, IEEE Micro, v.15 n.1, p.46-53, February 1995 [doi>10.1109/40.342017]
• 35: Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia
• 36: Masahiro Yasugi , Satoshi Matsuoka , Akinori Yonezawa, ABCL/onEM-4: a new software/hardware architecture for object-oriented concurrent computing on an extended dataflow supercomputer, Proceedings of the 6th international conference on Supercomputing, p.93-103, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143392]
• 37: Akinori Yonezawa, ABCL: an object-oriented concurrent system, MIT Press, Cambridge, MA, 1990

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers
      C.5.3 Microcomputers

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Measurement, Performance

Keywords:
Concurrent Object-Oriented Programming, Actors, Location Transparency, Migration