Array privatization for shared and distributed memory machines (extended abstract)

ABSTRACT

Memory related anti- and output-dependences can limit the potential parallelism in ordinary programs. In a distributed memory system, improper partition and distribution of data involved in memory related dependences may incur unnecessary communications and load imbalance. In this extended abstract, we present an overview of our work on using array privatization to enhance inherent parallelism and reduce communications.

REFERENCES

• 1: Vasanth Balasundaram, Translating Control Parallelism to Data Parallelism, Proceedings of the Fifth SIAM Conference on Parallel Processing for Scientific Computing, p.555-563, March 25-27, 1991
• 2: [BCFH89] M. Burke, R. Cytron, J. Ferrante, and W. Hsieh. Automatic generation of nested, fork-join parallelism. Journal of Supercomputing , pages 71-88, 1989.
• 3: [Che89] Ding-Kai Chen. MAXPAR: An execution driven simulator for studying parallel systems. MS thesis, Univ. of Illinois at Urbana-Champaign, Center for Supercomp. R&D, October 1989. CSRD Report 917.
• 4: [CK88] D. Callahan and K. Kennedy. Compiling programs for distributed-memory multiprocessors. Journal of Supercomputing, 2:151- 169, October 1988.
• 5: George Cybenko , Lyle Kipp , Lynn Pointer , David Kuck, Supercomputer performance evaluation and the Perfect Benchmarks, Proceedings of the 4th international conference on Supercomputing, p.254-266, June 11-15, 1990, Amsterdam, The Netherlands
• 6: Rudolf Eigenmann , Jay Hoeflinger , Z. Li , David A. Padua, Experience in the Automatic Parallelization of Four Perfect-Benchmark Programs, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.65-83, August 07-09, 1991
• 7: P. Feautrier, Array expansion, Proceedings of the 2nd international conference on Supercomputing, p.429-441, June 1988, St. Malo, France [doi>10.1145/55364.55406]
• 8: [GB90] M. Gupta and P. Banerjee. Automatic data partitioning on distributed memory multiprocessors. Technical Report CRHC-90-14, Center for Reliable and High-Performance Computing, Univeristy of Illinois, October 1990.
• 9: [HKT91] S. Hiranandani, K. Kennedy, and Ch.-W. Tseng. Compiler support for machine-independent parallel programming in Fortran D. Technical Report Rice COMP TR91-149, Department of Computer Science, Rice University, January 1991.
• 10: M. Kumar, Measuring Parallelism in Computation-Intensive Scientific/Engineering Applications, IEEE Transactions on Computers, v.37 n.9, p.1088-1098, September 1988 [doi>10.1109/12.2259]
• 11: [Pad89] David A. Padua. The Delta Program Manipulation system -- Preliminary design. CSRD Report 808, University of Illinois at Urbana-Champaign, Center for Supercomp. R&D, June 1989.
• 12: [PP92] Paul Petersen and David Padua. Machine-Independent Evaluation of Parallelizing Compilers. In Advanced Compilation Techniques for Novel Architectures, January 1992.
• 13: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 14: 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
• 15: [ZBG88] 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:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

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