Run-time and compile-time support for adaptive irregular problems

ABSTRACT

In adaptive irregular problems, data arrays are accessed via indirection arrays, and data access patterns change during computation. Parallelizing such problems on distributed memory machines requires support for dynamic data partitioning, efficient preprocessing and fast data migration. This paper describes CHAOS, a library of efficient runtime primitives that provides such support. To demonstrate the effectiveness of the runtime support, two adaptive irregular applications have been parallelized using CHAOS primitives: a molecular dynamics code (CHARMM) and a code for simulating gas flows (DSMC). We have also proposed minor extensions to Fortran D which would enable compilers to parallelize irregular forall loops in such adaptive applications by embedding calls to primitives provided by a runtime library. We have implemented our proposed extensions in the Syracuse Fortran 90D/HPF prototype compiler, and have used the compiler to parallelize kernels from two adaptive applications.

REFERENCES

• 1: M. J. Berger , S. H. Bokhari, A partitioning strategy for nonuniform problems on multiprocessors, IEEE Transactions on Computers, v.36 n.5, p.570-580, May 1987 [doi>10.1109/TC.1987.1676942]
• 2: Zeki Bozkus , Alok Choudhary , Geoffrey Fox , Tomasz Haupt , Sanjay Ranka , Min-You Wu, Compiling Fortran 90D/HPF for distributed memory MIMD computers, Journal of Parallel and Distributed Computing, v.21 n.1, p.15-26, April 1994 [doi>10.1006/jpdc.1994.1039]
• 3: P. Brezany, M. Gerndt, V. Sipkova, and H.P. Zima. SUPERB support for irregular scientific computations. In Proceedings of the Scalable High Performance Computing Conference (SHPCC-92), pages 314-321. IEEE Computer Society Press, April 1992.
• 4: B. R. Brooks, R. E. Bruccoleri, B. D. Olafson, D. J. States, S. Swaminathan, and M. Karplus. Charmm: A program for macromolecular energy, minimization, and dynamics calculations. Journal of Computational Chemistry, 4:187, 1983.
• 5: B. R. Brooks and M. Hodoscek. Parallelization of charmm for mimd machines. Chemical Design Automation News, 7:16, 1992.
• 6: B. Chapman, P. Mehrotra, and H. Zima. Programming in Vienna Fortran. Scientific Programming, 1(1):31-50, Fall 1992.
• 7: Raja Das , Mustafa Uysal , Joel Saltz , Yuan-Shin Hwang, Communication optimizations for irregular scientific computations on distributed memory architectures, University of Maryland at College Park, College Park, MD, 1994
• 8: Joel Saltz , Ravi Ponnusamy , Shamik D. Sharma , Bongki Moon , Yuan-Shin Hwang , Mustafa Uysal , Raja Das, A manual for the CHAOS runtime library, University of Maryland at College Park, College Park, MD, 1995
• 9: G. Fox, S. Hiranandani, K. Kennedy, C. Koelbel, U. Kremer, C. Tseng, and M. Wu. Fortran D language specification. Department of Computer Science Rice COMP TR90-141, Rice University, December 1990.
• 10: Dennis Gannon, Shelby Yang, and Peter Beckman. User Guide for a Portable Parallel C++ Programming System, pC++. Department of Computer Science and CICA, Indiana University, January 1994.
• 11: S. Hiranandani, K. Kennedy, and C. Tseng. Compiler support for machine-independent parallel programming in Fortran D. In Compilers and Runtime Software for Scalable Multiprocessors, J. Saltz and P. Mehrotra Editors, Amsterdam, The Netherlands, To appear 1991. Elsevier.
• 12: 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
• 13: C. Koelbel , P. Mehrotra , J. Van Rosendale, Supporting shared data structures on distributed memory architectures, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.177-186, March 14-16, 1990, Seattle, Washington, United States
• 14: S.R. Kohn and S.B. Baden. A robust parallel programming model for dynamic non-uniform scientific computations. In Proceedings of the Scalable High Performance Computing Conference (SHPCC-94), pages 509-517. May 1994.
• 15: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• 16: Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
• 17: Lee-Chung Lu , Marina C. Chen, Parallelizing Loops with Indirect Array References of Pointers, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.201-217, August 07-09, 1991
• 18: R. Mirchandaney , J. H. Saltz , R. M. Smith , D. M. Nico , K. Crowley, Principles of runtime support for parallel processors, Proceedings of the 2nd international conference on Supercomputing, p.140-152, June 1988, St. Malo, France [doi>10.1145/55364.55378]
• 19: B. Moon and J. Saltz. Adaptive runtime support for direct simulation Monte Carlo methods on distributed memory architectures. In Proceedings of the Scalable High Performance Computing Conference (SHPCC-94), pages 176-183. IEEE Computer Society Press, May 1994.
• 20: David M. Nicol , David R. O'Hallaron, Improved Algorithms for Mapping Pipelined and Parallel Computations, IEEE Transactions on Computers, v.40 n.3, p.295-306, March 1991 [doi>10.1109/12.76406]
• 21: B. Nour-Omid, A. Raefsky, and G. Lyzenga. Solving finite element equations on concurrent computers. In Proc. of Symposium on Parallel Computations and theis Impact on Mechanics, Boston, December 1987.
• 22: R. Ponnusamy , J. Saltz , A. Choudhary, Runtime compilation techniques for data partitioning and communication schedule reuse, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.361-370, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169752]
• 23: Matthew Rosing , Robert B. Schnabel , Robert P. Weaver, The DINO parallel programming language, Journal of Parallel and Distributed Computing, v.13 n.1, p.30-42, Sept. 1991 [doi>10.1016/0743-7315(91)90107-K]
• 24: Joel Saltz, Harry Berryman, and Janet Wu. Multiprocessors and run-time compilation. Concurrency: Practice and Experience, 3(6):573-592, December 1991.
• 25: H. Simon. Partitioning of unstructured mesh problems for parallel processing. In Proceedings of the Conference on Parallel Methods on Large Scale Structural Analysis and Physics Applications, 1991.
• 26: Roy D. Williams, Performance of dynamic load balancing algorithms for unstructured mesh calculations, Concurrency: Practice and Experience, v.3 n.5, p.457-481, Oct. 1991 [doi>10.1002/cpe.4330030502]
• 27: Richard G. Wilmoth. Direct simulation Monte Carlo analysis of rarefied flows on paralle processors. AIAA Journal of Thermophysics and Heat Transfer, 5(3):292-300, July-Sept. 1991.
• 28: J. Wu, J. Saltz, S. Hiranandani, and H. Berryman. Runtime compilation methods for multicomputers. In Proceedings of the 1991 ICPP, volume 2, pages 26-30, 1991.
• 29: Tao Yang , Apostolos Gerasoulis, PYRROS: static task scheduling and code generation for message passing multiprocessors, Proceedings of the 6th international conference on Supercomputing, p.428-437, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143446]