A flexible operation execution model for shared distributed objects

ABSTRACT

Many parallel and distributed programming models are based on some form of shared objects, which may be represented in various ways (e.g., single-copy, replicated, and partitioned objects). Also, many different operation execution strategies have been designed for each representation. In programming systems that use multiple representations integrated in a single object model, one way to provide multiple execution strategies is to implement each strategy independently from the others. However, this leads to rigid systems and provides little opportunity for code reuse. Instead, we propose a flexible operation execution model that allows the implementation of many different strategies, which can even be changed at runtime. We present the model and a distributed implementation of it. Also, we describe how various execution strategies can be expressed using the model, and we look at applications that benefit from its flexibility.

REFERENCES

• 1: Gul Agha, Actors: a model of concurrent computation in distributed systems, MIT Press, Cambridge, MA, 1986
• 2: Henri E. Bal, Programming distributed systems, Silicon Press, Summit, NJ, 1990
• 3: Henri E. Bal , M. Frans Kaashoek, Object distribution in Orca using Compile-Time and Run-Time techniques, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.162-177, September 26-October 01, 1993, Washington, D.C., United States
• 4: Henri E. Bal , M. Frans Kaashoek , Andrew S. Tanenbaum, Orca: A Language for Parallel Programming of Distributed Systems, IEEE Transactions on Software Engineering, v.18 n.3, p.190-205, March 1992 [doi>10.1109/32.126768]
• 5: Prithviraj Banerjee , John A. Chandy , Manish Gupta , Eugene W. Hodges IV , John G. Holm , Antonio Lain , Daniel J. Palermo , Shankar Ramaswamy , Ernesto Su, The Paradigm Compiler for Distributed-Memory Multicomputers, Computer, v.28 n.10, p.37-47, October 1995 [doi>10.1109/2.467577]
• 6: Andrew D. Birrell , Bruce Jay Nelson, Implementing remote procedure calls, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.39-59, February 1984 [doi>10.1145/2080.357392]
• 7: A. P. Black , Y. Artsy, Implementing Location Independent Invocation, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.107-119, January 1990 [doi>10.1109/71.80129]
• 8: P. Dinda, T. Gross, D. O'Hallaron, E. Segall, J. Stichnoth, J. Subhlock, J. Webb, and B. Yang. The CMU task parallel program suite. Technical Report CMU-CS-94-131, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, 1994.
• 9: Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , Ioannis Schoinas , Mark D. Hill , James R. Larus , Anne Rogers , David A. Wood, Application-specific protocols for user-level shared memory, Proceedings of the 1994 conference on Supercomputing, p.380-389, December 1994, Washington, D.C., United States
• 10: Graham Hamilton , Michael L. Powell , James G. Mitchell, Subcontract: a flexible base for distributed programming, ACM SIGOPS Operating Systems Review, v.27 n.5, p.69-79, Dec. 1993
• 11: Saniya Ben Hassen, Prefetching Strategies for Partitioned Shared Objets, Proceedings of the 29th Hawaii International Conference on System Sciences (HICSS'96) Volume 1: Software Technology and Architecture, p.261, January 03-06, 1996
• 12: Saniya Ben Hassen , Henri Bal, Integrating task and data parallelism using shared objects, Proceedings of the 10th international conference on Supercomputing, p.317-324, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237628]
• 13: K. L. Johnson , M. F. Kaashoek , D. A. Wallach, CRL: high-performance all-software distributed shared memory, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.213-226, December 03-06, 1995, Copper Mountain, Colorado, United States
• 14: Eric Jul , Henry Levy , Norman Hutchinson , Andrew Black, Fine-grained mobility in the Emerald system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.109-133, Feb. 1988 [doi>10.1145/35037.42182]
• 15: M.F. Kaashoek. Group Communication in Distributed Computer Systems. P hD thesis, Vrije Universiteit, Amsterdam, 1992.
• 16: G. Kiczales. Towards a new model of abstraction in the engineering of software. In IMSA '92 Workshop on Reflection and Metalevel Architectures, 1992.
• 17: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Wolf-Dietrich Weber , Anoop Gupta , John Hennessy , Mark Horowitz , Monica S. Lam, The Stanford Dash Multiprocessor, Computer, v.25 n.3, p.63-79, March 1992 [doi>10.1109/2.121510]
• 18: Barbara Liskov, Distributed programming in Argus, Communications of the ACM, v.31 n.3, p.300-312, March 1988 [doi>10.1145/42392.42399]
• 19: Pattie Maes, Concepts and experiments in computational reflection, Conference proceedings on Object-oriented programming systems, languages and applications, p.147-155, October 04-08, 1987, Orlando, Florida, United States
• 20: M. Makpangou, Y. Gourhant, J-P Le Narzul, and M. Shapiro. Fragmented objects for distributed abstractions. In T. L. Casavant and M. Singhal, editors, Readings in Distributed Computing Systems. IEEE Computer Society Press, July 1994.
• 21: F. Manola. Meta-object protocol concepts for a Risc object model. Technical Report TR-0244-12-93-165, GTE Laboratories, Inc, December 1993.
• 22: W.G. O'Farrell, F.Ch. Eigler, I. Kalas, and G.V. Wilson. ABC++ User Guide. Technical report, IBM Canada, Toronto, 1995.
• 23: P. Pardyak. Group communication in an object-based environment. In 2nd Intl. Workshop on Object Orientation in Operating Systems, pages 106-116, Dourdon, France, September 1992.
• 24: Martin C. Rinard , Daniel J. Scales , Monica S. Lam, Jade: A High-Level, Machine-Independent Language for Parallel Programming, Computer, v.26 n.6, p.28-38, June 1993 [doi>10.1109/2.214440]
• 25: D.J. Scales and M.S. Lam. The Design and Evaluation of a Shared Object System for Distributed Memory Machines. Proc. 1st Syrup. on Operating System Design and Implementation, pages 101-114, November 1994.
• 26: M. Shapiro. Structure and encapsulation in distributed systems: the Proxy principle. In Intl. Conference on Distributed Computing Systems, pages 198-204, Cambridge, MA, May 1986.
• 27: Shamik D. Sharma , Ravi Ponnusamy , Bongki Moon , Yuan-Shin Hwang , Raja Das , Joel Saltz, Run-time and compile-time support for adaptive irregular problems, Proceedings of the 1994 conference on Supercomputing, p.97-106, December 1994, Washington, D.C., United States
• 28: J. Stoer and R. Bulirsh. Introduction to Numerical Analysis. Springer-Verlag, New York, NY, 1983.
• 29: D.C. Sturman and G.A. Agha. A protocol description language for customizing failure semantics. In 13th Intl. Syrup. on Reliable Distributed Systems, 1994.
• 30: Andrew S. Tanenbaum , M. Frans Kaashoek , Robbert Van Renesse , Henri E. Bal, The Amoeba distributed operating system—a status report, Computer Communications, v.14 n.6, p.324-335, July/Aug. 1991 [doi>10.1016/0140-3664(91)90058-9]
• 31: Andrew S. Tanenbaum , Robbert van Renesse , Hans van Staveren , Gregory J. Sharp , Sape J. Mullender, Experiences with the Amoeba distributed operating system, Communications of the ACM, v.33 n.12, p.46-63, Dec. 1990 [doi>10.1145/96267.96281]
• 32: Takuo Watanabe , Akinori Yonezawa, Reflection in an object-oriented concurrent language, Conference proceedings on Object-oriented programming systems, languages and applications, p.306-315, September 25-30, 1988, San Diego, California, United States
• 33: E. A. West , A. S. Grimshaw, Braid: integrating task and data parallelism, Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation (Frontiers'95), p.211, February 06-09, 1995

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Orca
      D.3.4 Processors
          Subjects: Compilers

  E. Data

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computation of transforms (e.g., fast Fourier transform)

General Terms:
Algorithms, Languages, Performance