Double standards: bringing task parallelism to HPF via the message passing interface

ABSTRACT

High Performance Fortran (HPF) does not allow efficient expression of mixed task/data-parallel computations or the coupling of separately compiled data-parallel modules. In this paper, we show how a coordination library implementing the Message Passing Interface (MPI) can be used to represent these common parallel program structures. This library allows data-parallel tasks to exchange distributed data structures using calls to simple communication functions. We present microbenchmark results that characterize the performance of this library and that quantify the impact of optimizations that allow reuse of communication schedules in common situations. In addition, results from two-dimensional FFT, convolution, and multiblock programs demonstrate that the HPF/MPI library can provide performance superior to that of pure HPF. We conclude that this synergistic combination of two parallel programming standards represents a useful approach to task parallelism in a data-parallel framework, increasing the range of problems addressable in HPF without requiring complex compiler technology.

REFERENCES

• 1: D. Callahan and K. Kennedy. Compiling programs for distributed-memory multiprocessors. Journal of Supercomputing, 2:151-169, October 1988.
• 2: Nicholas Carriero , David Gelernter, Linda in context, Communications of the ACM, v.32 n.4, p.444-458, April 1989 [doi>10.1145/63334.63337]
• 3: G. Cheng, G. Fox, and K. Mills. Integrating multiple programming paradigms on Connection Machine CM5 in a dataflow-based software environment. Technical report, Northeast Parallel Architectures Center, Syracuse University, 1993.
• 4: A. N. Choudhary , B. Narahari , D. M. Nicol , R. Simha, Optimal Processor Assignment for a Class of Pipelined Computations, IEEE Transactions on Parallel and Distributed Systems, v.5 n.4, p.439-445, April 1994 [doi>10.1109/71.273050]
• 5: I. Foster, B. Avalani, A. Choudhary, and M. Xu. A compilation system that integrates High Performance Fortran and Fortran M. In Proceedings of the 1994 Scalable High-Performance Computing Conference, pages 293-300. IEEE Computer Society, 1994.
• 6: Ian Foster , Stephen Taylor, Strand: new concepts in parallel programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 7: K. S. Gatlin and S. B. Baden. Brick: A benchmark for irregular block structured applications. Technical report, University of California at San Diego, Department of Computer Science and Engineering, 1996.
• 8: M. Girkar , C. D. Polychronopoulos, Automatic Extraction of Functional Parallelism from Ordinary Programs, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.166-178, March 1992 [doi>10.1109/71.127258]
• 9: W. Gropp, E. Lusk, N. Doss, and A. Skjellum. A high-performance, portable implementation of the MPI message passing interface standard. Technical Report ANL/MCS-TM-213, Argonne National Laboratory, 1996.
• 10: William Gropp , Ewing Lusk , Anthony Skjellum, Using MPI: portable parallel programming with the message-passing interface, MIT Press, Cambridge, MA, 1994
• 11: Thomas Gross , David R. O'Hallaron , Jaspal Subhlok, Task Parallelism in a High Performance Fortran Framework, IEEE Parallel & Distributed Technology: Systems & Technology, v.2 n.3, p.16-26, September 1994 [doi>10.1109/M-PDT.1994.329791]
• 12: W. Daniel Hillis , Guy L. Steele, Jr., Data parallel algorithms, Communications of the ACM, v.29 n.12, p.1170-1183, Dec. 1986 [doi>10.1145/7902.7903]
• 13: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiling Fortran D for MIMD distributed-memory machines, Communications of the ACM, v.35 n.8, p.66-80, Aug. 1992 [doi>10.1145/135226.135230]
• 14: 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
• 15: Piyush Mehrotra , Matthew Haines, AN OVERVIEW OF THE OPUS LANGUAGE AND RUNTIME SYSTEM, Institute for Computer Applications in Science and Engineering (ICASE), 1994
• 16: S. Ramaswamy, S. Sapatnekar, and P. Banerjee. A framework for exploiting data and functional parallelism on distributed memory multicomputers. Technical Report CRHC-94-10, Center for Reliable and High-Performance Computing, University of Illinois, Urbana, IL, 1994.
• 17: S. Ramasulamy , P. Banerjee, Automatic generation of efficient array redistribution routines for distributed memory multicomputers, Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation (Frontiers'95), p.342, February 06-09, 1995
• 18: A. Rogers , K. Pingali, Process decomposition through locality of reference, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.69-80, June 19-23, 1989, Portland, Oregon, United States
• 19: Azriel Rosenfeld , Avinash C. Kak, Digital Picture Processing, Academic Press, Inc., Orlando, FL, 1982
• 20: Bradley K. Seevers , Michael J. Quinn , Philip J. Hatcher, A parallel programming environment supporting multiple data-parallel modules, International Journal of Parallel Programming, v.21 n.5, p.363-386, Oct. 1992 [doi>10.1007/BF01407837]
• 21: V. N. Vatsa, M. D. Sanetrik, and E. B. Parlette. Development of a flexible and efficient multigrid-based muliblock flow solver; AIAA-93-0677. In Proc. 31st Aerospace Sciences Meeting and Exhibit, January 1993.
• 22: H. Zima, H.-J. Bast, and M. Gerndt. SUPERB: A tool for semi-automatic MIMD/SIMD parallelization. Parallel Computing, 6:1-18, 1988.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
  D.4 OPERATING SYSTEMS

General Terms:
Design, Languages, Performance, Theory