Charisma: orchestrating migratable parallel objects

ABSTRACT

The parallel programming paradigm based on migratable objects, as embodied in Charm++, improves programmer productivity by automating resource management. The programmer decomposes an application into a large number of parallel objects, while an intelligent run-time system assigns those objects to processors. It migrates objects among processors to effect dynamic load balance and communication optimizations. In addition, having multiple sets of objects representing distinct computations leads to improved modularity and performance. However, for complex applications involving many sets of objects, Charm++'s programming model tends to obscure the global flow of control in a parallel program: One must look at the code of multiple objects to discern how the multiple sets of objects are orchestrated in a given application. In this paper, we present Charisma, an orchestration notation that allows expression of Charm++ functionality without fragmenting the expression of control flow. Charisma separates expression of parallelism, including control flow and macro data-flow, from sequential components of the program. The sequential components only consume and publish data. Charisma expression of multiple patterns of communication among message-driven objects. A compiler generates Charm++ communication and synchronization code via static dependence analysis. As Charisma out puts standard Charm++ code, the functionality and performance benefits of the adaptive run-time system, such as automatic load balancing, are retained. In the paper, we show that Charisma programs scale up to 1024 processors without introducing undue overhead.

REFERENCES

• 1: Vijay K. Naik , Sanjeev K. Setia , Mark S. Squillante, Processor allocation in multiprogrammed distributed-memory parallel computer systems, Journal of Parallel and Distributed Computing, v.46 n.1, p.28-47, Oct. 10, 1997 [doi>10.1006/jpdc.1997.1377]
• 2: D. L. Eager , E. D. Lazowska , J. Zahorjan, The limited performance benefits of migrating active processes for load sharing, Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.63-72, May 24-27, 1988, Santa Fe, New Mexico, United States
• 3: Kevin J. Barker , Nikos P. Chrisochoides, An Evaluation of a Framework for the Dynamic Load Balancing of Highly Adaptive and Irregular Parallel Applications, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.45, November 15-21, 2003
• 4: Hai Jiang , Vipin Chaudhary, Process/Thread Migration and Checkpointing in Heterogeneous Distributed Systems, Proceedings of the Proceedings of the 37th Annual Hawaii International Conference on System Sciences (HICSS'04) - Track 9, p.90282.2, January 05-08, 2004
• 5: Laxmikant V. Kalé, Sameer Kumar, Gengbin Zheng, and Chee Wai Lee. Scaling molecular dynamics to 3000 processors with projections: A performance analysis case study. In Terascale Performance Analysis Workshop, International Conference on Computational Science(ICCS) Melbourne, Australia, June 2003.
• 6: Ramkumar V. Vadali, Yan Shi, Sameer Kumar, L.V. Kale, Mark E. Tuckerman, and Glenn J. Martyna. Scalable ?ne-grained parallelization of plane-wave-based ab initio molecular dynamics for large supercomputers. Journal of Comptational Chemistry 25(16):2006--2022, Oct.2004.
• 7: L. V. Kale and Attila Gursoy. Modularity,reuse and efficiency with message-driven libraries.In Proc. 27th Conference on Parallel Processing for Scientific Computing pages 738--743,February 1995.
• 8: Leonardo Dagum , Ramesh Menon, OpenMP: An Industry-Standard API for Shared-Memory Programming, IEEE Computational Science & Engineering, v.5 n.1, p.46-55, January 1998 [doi>10.1109/99.660313]
• 9: CORPORATE The MPI Forum, MPI: a message passing interface, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.878-883, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169855]
• 10: James C. Phillips , Gengbin Zheng , Sameer Kumar , Laxmikant V. Kalé, NAMD: biomolecular simulation on thousands of processors, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-18, November 16, 2002, Baltimore, Maryland
• 11: T. A. Darden, D. M. York, and L. G. Pedersen. Particle mesh Ewald. An N¿log(N)method for Ewald sums in large systems. JCP 98: 10089--10092, 1993.
• 12: 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
• 13: J L Gaudiot , L T Lee, Multiprocessor systems programming in a high-level data-flow language, Volume I: Parallel architectures on PARLE: Parallel Architectures and Languages Europe, p.134-151, March 1987, Eindhoven, The Netherlands
• 14: G. R. Gao, An efficient hybrid dataflow architecture model, Journal of Parallel and Distributed Computing, v.19 n.4, p.293-307, Dec. 1993 [doi>10.1006/jpdc.1993.1113]
• 15: Charles H. Koelbel , David B. Loveman , Robert S. Schreiber , Guy L. Steele, Jr. , Mary E. Zosel, The high performance Fortran handbook, MIT Press, Cambridge, MA, 1994
• 16: Ian T. Foster , K. Mani Chandy, Fortran M: a language for modular parallel programming, Journal of Parallel and Distributed Computing, v.26 n.1, p.24-35, April 1, 1995 [doi>10.1006/jpdc.1995.1044]
• 17: 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
• 18: Chao Huang , Gengbin Zheng , Laxmikant Kalé , Sameer Kumar, Performance evaluation of adaptive MPI, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122976]
• 19: Jayant DeSouza and Laxmikant V.Kalé. MSA: Multiphase specifically shared arrays. In Proceedings of the 17th International Workshop on Languages and Compilers for Parallel Computing West Lafayette, Indiana,USA,September 2004.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Design, Languages

Keywords:
adaptivity, migratable objects, orchestration, parallel programming productivity