Array privatization for parallel execution of loops

ABSTRACT

In recent experiments, array privatization played a critical role in successful parallelization of several real programs. This paper presents compiler algorithms for the program analysis for this transformation. The paper also addresses issues in the implementation.

REFERENCES

• ABC+88: F. Allen , M. Burke , R. Cytron , J. Ferrante , W. Hsieh, A framework for determining useful parallelism, Proceedings of the 2nd international conference on Supercomputing, p.207-215, June 1988, St. Malo, France [doi>10.1145/55364.55385]
• All70: Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
• ASU86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Ban88: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• BT82: T. Belytschko and C. S. Tsay. Whamse: A program for three-dimensional nonlinear nonlinear structural dynamics. Tech. Rept. No. NP- 2250, Dept. of Civil Engin., Northwestern Univ, Evanston, IL, Feb. 1982.
• CF87: R. Cytron and J. Ferrante. What's in a name? or the value of renaming for parallelism detection and storage allocation. In Proc. of the 1987 Int'l Conf. on Parallel Processing, pages 19-27, August 1987.
• Coc70: John Cocke, Global common subexpression elimination, ACM SIGPLAN Notices, v.5 n.7, p.20-24, July 1970
• EB91: R. Eigenmann and W. Blume. An effectiveness study of parallelizing compiler techniques. In Proc. of the Int'l Conf. on Parallel Processing, August 1991.
• EHJ+91: R. Eigenmann, J. Hoeflinger, G. Jaxon, Z. Li, and D. Padua. Restructuring fortran programs for cedar. In Proc. of the 1991 Int'l Conf. on Parallel Processing, August 1991.
• EHLP91: 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
• Fea88: 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]
• GS90: T. Gross , P. Steenkiste, Structured dataflow analysis for arrays and its use in an optimizing complier, Software—Practice & Experience, v.20 n.2, p.133-155, February 1990 [doi>10.1002/spe.4380200203]
• Li92: Z. Li. Array privatization: A loop transformation for parallel execution. Tech. Rept. No. 9226, Dept. of Computer Science, Univ. of Minnesota, April 1992.
• LT88: A. Lichnewsky , F. Thomasset, Introducing symbolic problem solving techniques in the dependence testing phases of a vectorizer, Proceedings of the 2nd international conference on Supercomputing, p.396-406, June 1988, St. Malo, France [doi>10.1145/55364.55403]
• PER89: M. berry et al. the PERFECT club benchmarks: Effective performance evaluation of supercomputers. International Journal of Supercomputing Applications, 3(3):5-40, 1989.
• Ros77: Barry K. Rosen, High-level data flow analysis, Communications of the ACM, v.20 n.10, p.712-724, Oct. 1977 [doi>10.1145/359842.359849]
• TIF86: Rémi Triolet , Francois Irigoin , Paul Feautrier, Direct parallelization of call statements, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.176-185, June 25-27, 1986, Palo Alto, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms