Compilation techniques for block-cyclic distributions

ABSTRACT

Compilers for data-parallel languages such as Fortran D and High-Performance Fortran use data alignment and distribution specifications as the basis for translating programs for execution on MIMD distributed-memory machines. This paper describes techniques for generating efficient code for programs that use block-cyclic distributions. These techniques can be applied to programs with symbolic loop bounds, symbolic array dimensions, and loops with non-unit strides. We present algorithms for computing the data elements that need to be communicated among processors both for loops with unit and non-unit strides, a linear-time algorithm for computing the memory access sequence for loops with non-unit strides, and experimental results for a hand-compiled test case using block-cyclic distributions

REFERENCES

• 1: V.S. Adve, C. Koelbel, and J.Mellor-Crummey. Performance analysis of data parallel programs. Submitted to Supercomputing '94, April 1994.
• 2: F. Bodin, E.D. Granston, and T. Montaut. Experiences reducing false sharing in shared virtual memory systems (under preparation). Technical report, Center for Research on Parallel Computation, Rice University, 1994.
• 3: D. Callahan and K. Kennedy. Compiling programs for distributed-memory multiprocessors. Journal of Supercomputing, 2:151-169, October 1988.
• 4: Siddhartha Chatterjee , John R. Gilbert , Fred J. E. Long , Robert Schreiber , Shang-Hua Teng, Generating local addresses and communication sets for data-parallel programs, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.149-158, May 19-22, 1993, San Diego, California, United States
• 5: J. Dongarra, R. van de Geijn, and D. Walker. A look at scalable dense linear algebra libraries. In Proceedings of the 1992 Scalable High Performance Computing Conference, pages 372-379, Williamsburg, VA, April 1992.
• 6: M. Gerndt, Updating distributed variables in local computations, Concurrency: Practice and Experience, v.2 n.3, p.171-193, Sep. 1990 [doi>10.1002/cpe.4330020303]
• 7: S.K.S. Gupta, S.D. Kaushik, S. Mufti, S. Sharma, C.-H. Huang, and P. Sadayappan. On compiling array expressions for efficient execution on distributed-memory machines. In Proceedzngs of the i993 International Conference on Parallel Processing, volume II, pages 301-305, 1993.
• 8: S.K.S. Gupta, S.D. Kaushik, S. Mufti, S. Sharma, C.-H. Huang, and P. Sadayappan. On compiling array expressions for efficient execution on distributed-memory machines. Technical report OSU-CISRC-4/94-TR19, Department of Computer and Information Science, Ohio State University, Columbus, OH, March 1994.
• 9: R. v. Hanxleden. Handling irregular problems with fortran d - a preliminary report. Technical Report CRPC-TR93339-S, Center for Research on Parallel Computation, Rice University, October 1993.
• 10: P. Havlak , K. Kennedy, An Implementation of Interprocedural Bounded Regular Section Analysis, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.350-360, July 1991 [doi>10.1109/71.86110]
• 11: High Performance Fortran Forum. High Performance Fortran language specification. Scientific Programming, 2(1- 2):1-170, 1993.
• 12: S. Hiranandani, K. Kennedy, J. Mellor-Crummey, and A. Sethi. Advanced compilation techniques for fortran d. Technical Report CRPC-TR93338, Center {'or Research on Parallel Computation, Rice University, October 1993.
• 13: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiler optimizations for Fortran D on MIMD distributed-memory machines, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.86-100, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125886]
• 14: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Computer support for machine-independent parallel programming in Fortran D, Languages, compilers and run-time environments for distributed memory machines, Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 1992
• 15: 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]
• 16: Ken Kennedy , Kathryn S. McKinley , Chau-Wen Tseng, Analysis and transformation in the ParaScope editor, Proceedings of the 5th international conference on Supercomputing, p.433-447, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109126]
• 17: Charles Koelbel, Compile-time generation of regular communications patterns, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.101-110, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125890]
• 18: 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
• 19: C. Koelbel and P. Mehrotra. Compiling global name-space programs for distributed execution. ICASE Report 90-70, Institute for Computer Application in Science and Engineering, Hampton, VA, October 1990.
• 20: 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
• 21: Joel Saltz , Kathleen Crowley , Ravi Mirchandaney , Harry Berryman, Run-time scheduling and execution of loops on message passing machines, Journal of Parallel and Distributed Computing, v.8 n.4, p.303-312, Apr. 1990 [doi>10.1016/0743-7315(90)90129-D]
• 22: J. Stichnoth, D. O'Hallaron, and T. Gross. Generating communication for array statements: Design, implementation, and evaluation, in Proceedings of the Szxth Workshop on Languages and Compilers }or Parallel Computing, Portland, OR, August 1993.
• 23: 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:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Languages, Measurement, Performance, Theory