Obtaining sequential efficiency for concurrent object-oriented languages

ABSTRACT

Concurrent object-oriented programming (COOP) languages focus the abstraction and encapsulation power of abstract data types on the problem of concurrency control. In particular, pure fine-grained concurrent object-oriented languages (as opposed to hybrid or data parallel) provides the programmer with a simple, uniform, and flexible model while exposing maximum concurrency. While such languages promise to greatly reduce the complexity of large-scale concurrent programming, the popularity of these languages has been hampered by efficiency which is often many orders of magnitude less than that of comparable sequential code. We present a sufficiency set of techniques which enables the efficiency of fine-grained concurrent object-oriented languages to equal that of traditional sequential languages (like C) when the required data is available. These techniques are empirically validated by the application to a COOP implementation of the Livermore Loops.

REFERENCES

• 1: Gul Agha, Actors: a model of concurrent computation in distributed systems, MIT Press, Cambridge, MA, 1986
• 2: R. Allen , S. Johnson, Compiling C for vectorization, parallelization, and inline expansion, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.241-249, June 20-24, 1988, Atlanta, Georgia, United States
• 3: J. K. Bennett , J. B. Carter , W. Zwaenepoel, Munin: distributed shared memory based on type-specific memory coherence, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.168-176, March 14-16, 1990, Seattle, Washington, United States
• 4: Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, PRESTO: a system for object-oriented parallel programming, Software—Practice & Experience, v.18 n.8, p.713-732, August 1988 [doi>10.1002/spe.4380180802]
• 5: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 6: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
• 7: Craig Chambers , David Ungar, Interactive type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.150-164, June 1990, White Plains, New York, United States
• 8: K. Mani Chandy , Carl Kesselman, Compositional C++: Compositional Parallel Programming, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.124-144, August 03-05, 1992
• 9: 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
• 10: Andrew A. Chien, Vijay Karamcheti, John Plevyak, and X#ngbin Zhang. Concurrent aggregates language :#eport 2.0. Available via anonymous ftp from Ics.uiuc.edu in /pub/csag or from http://www-csa#.cs.uiuc.edu/, September 1993.
• 11: Fred C. Chow , John L. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.501-536, Oct. 1990 [doi>10.1145/88616.88621]
• 12: William D Clinger, Foundations of Actor Semantics, Massachusetts Institute of Technology, Cambridge, MA, 1981
• 13: Cray Research, Inc., Eagan, Minnesota 55121. CRAY T3D So}-tware Overwew Technical Note, 1992. /
• 14: 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
• 15: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 16: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 17: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 18: Andrew S. Grimshaw, Easy-to-Use Object-Oriented Parallel Processing with Mentat, Computer, v.26 n.5, p.39-51, May 1993 [doi>10.1109/2.211896]
• 19: Mary W. Hall , Ken Kennedy , Kathryn S. McKinley, Interprocedural transformations for parallel code generation, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.424-434, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126055]
• 20: Per Brinch Hansen, Structured multiprogramming, Communications of the ACM, v.15 n.7, p.574-578, July 1972 [doi>10.1145/361454.361473]
• 21: C. Hewitt and H. Baker. Actors and continuous functionals. In Proceedings of the IFIP Working Conference on Formal Description of Programming Concepts, pages 367-87, August 1977.
• 22: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiling Fortran D for MIMD distributed-memory machines, Communications of the ACM, v.35 n.8, p.66-80, Aug. 1992 [doi>10.1145/135226.135230]
• 23: Richard C. Holt, Some Deadlock Properties of Computer Systems, ACM Computing Surveys (CSUR), v.4 n.3, p.179-196, Sept. 1972 [doi>10.1145/356603.356607]
• 24: Urs Hölzle , David Ungar, Optimizing dynamically-dispatched calls with run-time type feedback, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.326-336, June 20-24, 1994, Orlando, Florida, United States
• 25: W. Horwat , A. A. Chien , W. J. Dally, Experience with CST: programming and implementation, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.101-109, June 19-23, 1989, Portland, Oregon, United States
• 26: Waldemar Horwat. Concurrent Smalltalk on the message-driven processor. Master's thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, June 1989.
• 27: A. S. Huang , G. Slavenburg , J. P. Shen, Speculative disambiguation: a compilation technique for dynamic memory disambiguation, Proceedings of the 21ST annual international symposium on Computer architecture, p.200-210, April 18-21, 1994, Chicago, Illinois, United States
• 28: P. P. Chang , W.-W. Hwu, Inline function expansion for compiling C programs, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.246-257, June 19-23, 1989, Portland, Oregon, United States
• 29: 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
• 30: 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]
• 31: B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
• 32: J. K. Lee , D. Gannon, Object oriented parallel programming: experiments and results, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.273-282, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.105186]
• 33: Henry Lieberman, Concurrent object-oriented programming in Act 1, Object-oriented concurrent programming, MIT Press, Cambridge, MA, 1987
• 34: Scott McFarling, Procedure merging with instruction caches, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.71-79, June 24-28, 1991, Toronto, Ontario, Canada
• 35: F. H. McMahon. The Livermore Fortran kernels: a computer test of the numerical performance range. Technical report UCRL-53745, Lawerence Livermore National Laboratory, Liverraore, California, 1986.
• 36: Stephan Murer, Jerome A. Feldman, Chu-Cheow Lira, and Martina-Maria Seidel. pSather: Layered extensions to an object-oriented language for efficient parallel computation. Technical Report TR- 93-028, International Computer Science institute, Berkeley, Calif., December 1993. (2nd revised edition).
• 37: Alexandru Nicolau, Run-time disambiguation: coping with statically unpredictable dependencies, IEEE Transactions on Computers, v.38 n.5, p.633-678, May 1989
• 38: John Plevyak , Andrew A. Chien, Precise concrete type inference for object-oriented languages, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.324-340, October 23-28, 1994, Portland, Oregon, United States
• 39: John Plevyak , Andrew A. Chien , Vijay Karamcheti, Analysis of Dynamic Structures for Efficient Parallel Execution, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.37-56, August 12-14, 1993
• 40: R. J. Smith, II. Experimental systems kit final project report. Technical Report ACT-ESP-077-91, Micro electronics and Computer Technology Corporation (MCC), Austin, Texas., 1991.
• 41: S. Sakai , y. Yamaguchi , K. Hiraki , Y. Kodama , T. Yuba, An architecture of a dataflow single chip processor, Proceedings of the 16th annual international symposium on Computer architecture, p.46-53, April 1989, Jerusalem, Israel
• 42: Thinking Machines Corporation, 245 First Street, Cambridge, MA 02154-1264. The Connection Machine CM-5 Technical Summary, October 1991.
• 43: Kenneth R. Traub, Implementation of non-strict functional programming languages, MIT Press, Cambridge, MA, 1991
• 44: Tim A. Wagner , Vance Maverick , Susan L. Graham , Michael A. Harrison, Accurate static estimators for program optimization, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.85-96, June 20-24, 1994, Orlando, Florida, United States
• 45: Yasuhiko Yokote , Mario Tokoro, Concurrent programming in concurrent Smalltalk, Object-oriented concurrent programming, MIT Press, Cambridge, MA, 1987
• 46: Akinori Yonezawa, ABCL: an object-oriented concurrent system, MIT Press, Cambridge, MA, 1990
• 47: Akinori Yonezawa , Satoshi Matsuoka , Masahiro Yasugi , Kenjiro Taura, Implementing Concurrent Object-Oriented Languages on Multicomputers, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.2, p.49-61, May 1993 [doi>10.1109/88.218175]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages
      D.3.3 Language Constructs and Features
          Subjects: Abstract data types
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Design, Languages, Performance