Library support for hierarchical multi-processor tasks

ABSTRACT

The paper considers the modular programming with hierarchically structured multi-processor tasks on top of SPMD tasks for distributed memory machines. The parallel execution requires a corresponding decomposition of the set of processors into a hierarchical group structure onto which the tasks are mapped. This results in a multi-level group SPMD computation model with varying processor group structures. The advantage of this kind of mixed task and data parallelism is a potential to reduce the communication overhead and to increase scalability. We present a runtime library to support the coordination of hierarchically structured multi-processor tasks. The library exploits an extended parallel group SPMD programming model and manages the entire task execution including the dynamic hierarchy of processor groups. The library is built on top of MPI, has an easy-to-use interface, and leads to only a marginal overhead while allowing static planning and dynamic restructuring.

REFERENCES

• 1: Scott B. Baden , Stephen J. Fink, A Programming Methodology for Dual-Tier Multicomputers, IEEE Transactions on Software Engineering, v.26 n.3, p.212-226, March 2000 [doi>10.1109/32.842948]
• 2: Henri E. Bal , Matthew Haines, Approaches for Integrating Task and Data Parallelism, IEEE Concurrency, v.6 n.3, p.74-84, July 1998 [doi>10.1109/4434.708258]
• 3: C.J. Beckmann and C. Polychronopoulos. Microarchitecture Support for Dynamic Scheduling of Acyclic Task Graphs. Technical Report CSRD Report 1207, University of Illinois, 1992.
• 4: Soumen Chakrabarti , James Demmel , Katherine Yelick, Modeling the benefits of mixed data and task parallelism, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.74-83, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215423]
• 5: F. Darema, D. A. George, V. A. Norton, and G. F. Pfis-ter. A single-program-multiple-data computational mode for EPEX/FORTRAN. Parallel Comput., 7(1):11--24, 1988.
• 6: Stephen Jason Fink , Scott B. Baden, A programming model for block-structured scientific calculations on smp clusters, 1998
• 7: 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]
• 8: I. Foster, M. Xu, B. Avalani, and A. Choudhary. A Compilation System That Integrates High Performance Fortran and Fortran M. In Proceedings 1994 Scalable High Performance Computing Conference, pages 293--300. IEEE Computer Society Press, 1994.
• 9: E. Hairer , S. P. Nørsett , G. Wanner, Solving ordinary differential equations I (2nd revised. ed.): nonstiff problems, Springer-Verlag New York, Inc., New York, NY, 1993
• 10: M. Hill, W. McColl, and D. Skillicorn. Questions and Answers about BSP. Scientific Programming, 6(3):249--274, 1997.
• 11: Pramod G. Joisha , Prithviraj Banerjee, PARADIGM (version 2.0): A New HPF Compilation System, Proceedings of the 13th International Symposium on Parallel Processing and the 10th Symposium on Parallel and Distributed Processing, p.609-615, April 12-16, 1999
• 12: Christoph W. Keßler, NestStep: Nested Parallelism and Virtual Shared Memory for the BSP Model, The Journal of Supercomputing, v.17 n.3, p.245-262, Nov. 2000 [doi>10.1023/A:1026511306490]
• 13: Scott R. Kohn , Scott B. Baden, Irregular coarse-grain data parallelism under LPARX, Scientific Programming, v.5 n.3, p.185-201, Fall 1996
• 14: M. Kühnemann, T. Rauber, and G. Rünger. Performance Modelling for Task-Parallel Programs. In Proc. of the Communication Networks and Distributed Systems Modeling and Simulation Conference (CNDS 2002), pages 148--154, San Antonio, USA, 2002.
• 15: Shankar Ramaswamy , Prithviraj Banerjee, Simultaneous exploitation of task and data parallelism in regular scientific applications, 1996
• 16: Thomas Rauber , Robert Reilein , Gudula Rünger, ORT: a communication library for orthogonal processor groups, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.27-27, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582061]
• 17: T. Rauber and G. Rünger. Load Balancing Schemes for Extrapolation Methods. Concurrency: Practice and Experience, 9(3):181--202, 1997.
• 18: T. Rauber and G. Rünger. Diagonal-Implicitly Iterated Runge-Kutta Methods on Distributed Memory Machines. Int. Journal of High Speed Computing, 10(2):185--207, 1999.
• 19: David B. Skillicorn , Domenico Talia, Models and languages for parallel computation, ACM Computing Surveys (CSUR), v.30 n.2, p.123-169, June 1998 [doi>10.1145/280277.280278]
• 20: Jaspal Subhlok , Bwolen Yang, A new model for integrated nested task and data parallel programming, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, June 18-21, 1997, Las Vegas, Nevada, United States
• 21: P.J. van der Houwen, B.P. Sommeijer, and W. Couzy. Embedded Diagonally Implicit Runge-Kutta Algorithms on Parallel Computers. Mathematics of Computation, 58(197):135--159, January 1992.
• 22: Zhiwei Xu , Kai Hwang, Early prediction of MPP performance: the SP2, T3D, and Paragon experiences, Parallel Computing, v.22 n.7, p.917-942, Oct. 1996 [doi>10.1016/0167-8191(96)00034-8]
• 23: G. Zhang, B. Carpenter, G. Fox, X. Li, and Y. Wen. A high level SPMD programming model: HPspmd and its Java language binding. Technical report, NPAC at Syracuse University, 1998.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

General Terms:
Standardization

Keywords:
distributed memory, hierarchical decomposition of processor sets, library support, mixed task and data parallelism, multilevel group SPMD, multiprocessor tasks