Supporting dynamic parallel object arrays

ABSTRACT

We present efficient support for generalized arrays of parallel data driven objects. The “array elements” are scattered across a parallel machine. Each array element is an object that can be thought of as a virtual processor. The individual elements are addressed by their “index”, which can be an arbitrary object rather than a simple integer. For example, it can be a series of numbers, supporting multidimensional sparse arrays; a bit vector, supporting collections of quadtree nodes; or a string. Messages can be sent to any individual array element from any processor, and the elements can participate in reductions and broadcasts. Individual elements can be created or deleted dynamically at any time. Most importantly, the elements can migrate from processor to processor at any time. The paper discusses support for message delivery and collective operations in face of such dynamic behavior. The migration capabilities of array elements have proven extremely useful, for example, in implementing flexible load balancing strategies and for exploiting workstation clusters adaptively.

REFERENCES

• 1: L.V. Kal6 and S. Krishnan. "Charm++: Parallel Programming with Message-Driven Objects", Gregory V. Wilson and Paul Lu, editors, Parallel Programming using C++, pages 175-213. MIT Press, 1996
• 2: Robert K. Brunner , Laxmikant V. Kalé, Adapting to Load on Workstation Clusters, Proceedings of the The 7th Symposium on the Frontiers of Massively Parallel Computation, p.106, February 21-25, 1999
• 3: S. Krishnan and L.V. Kalr. "A parallel array abstraction for data-driven objects", Proc. Parallel Object-Oriented Methods and Applications Conference, February 1996
• 4: L.V. Kal6 and others. Charm++ Programmer's Manual, http : //charm. cs. uiuc. edu/, 2000
• 5: L. V. Kalr, S. Kumar, J. DeSouza. An Adaptive Job Scheduler for Timeshared Parallel Machines, PPL Technical Report 00-02, University of Illinois at Urbana- Champaign, Sept. 2000
• 6: M. Bhandarkar, L.V. Kal6, E. Sturler, J. Hoeflinger. Object-Based Adaptive Load Balancing for MPI Programs, PPL Technical report 00-03, University of Illinois at Urbana-Champaign, Sept. 2000
• 7: Sudhir Ahuja , Nicholas Carriero , David Gelernter, Linda and friends, Computer, v.19 n.8, p.26-34, Aug. 1986 [doi>10.1109/MC.1986.1663305]
• 8: F. Bodin, P. Beckman, D. Gannon, and others. "Distributed pC++: Basic Ideas for an Object Parallel Language", Scientific Programming, Volume 2/Number 3 Fall 1993
• 9: Andrew A. Chien , Willaim J. Dally, Concurrent aggregates (CA), Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.187-196, March 14-16, 1990, Seattle, Washington, United States
• 10: H. Bal, R. Bhoedjang, R. Hofman, and others. Orca: a Portable User-Level Shared Object System, Technical Report IR-408, Vrije Universiteit, Amsterdam, June 1996
• 11: Mike Barnett , Lance Shuler , Satya Gupta , David G. Payne , Robert van de Geijn , Jerrell Watts, Building a high-performance collective communication library, Proceedings of the 1994 conference on Supercomputing, p.107-116, December 1994, Washington, D.C., United States
• 12: Jaroslaw Nieplocha , Robert J. Harrison , Richard J. Littlefield, Global arrays: a nonuniform memory access programming model for high-performance computers, The Journal of Supercomputing, v.10 n.2, p.169-189, June 1996
• 13: S. Atlas, S. Banerjee, J. C. Cummings, and others (presented by J. Reynders). "POOMA: A high performance distributed simulation environment for scientific applications," Supercomputing 1995, Nov. 1995
• 14: M. Lemke, D. Quinlan. "P++, a Parallel C++ Array Class Library for Architecture-Independent Development of Structured Grid Applications", ACM SIGPLAN Workshop 1992. pp 21-23
• 15: José M. Piquer, Indirect distributed garbage collection: handling object migration, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.5, p.615-647, Sept. 1996 [doi>10.1145/232706.232711]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Methodologies (e.g., object-oriented, structured)

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Parallel and vector implementations

General Terms:
Design, Experimentation, Languages, Performance

Keywords:
object migration, parallel runtime, parallel tree