The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization

ABSTRACT

Current parallelizing compilers cannot identify a significant fraction of parallelizable loops because they have complex or statically insufficiently defined access patterns. As parallelizable loops arise frequently in practice, we advocate a novel framework for their identification: speculatively execute the loop as a doall, and apply a fully parallel data dependence test to determine if it had any cross-iteration dependences; if the test fails, then the loop is re-executed serially. Since, from our experience, a significant amount of the available parallelism in Fortran programs can be exploited by loops transformed through privatization and reduction parallelization, our methods can speculatively apply these transformations and then check their validity at run-time. Another important contribution of this paper is a novel method for reduction recognition which goes beyond syntactic pattern matching; it detects at run-time if the values stored in an array participate in a reduction operation, even if they are transferred through private variables and/or are affected by statically unpredictable control flow. We present experimental results on loops from the PERFECT Benchmarks which substantiate our claim that these techniques can yield significant speedups which are often superior to those obtainable by inspector/executor methods.

REFERENCES

• 1: S. Abraham. Private communication, 1994.
• 2: J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567085]
• 3: Allxant Computer 5gystems Corporation. ~"w~/Serles Architecture Manual, 1986.
• 4: Alhant Computers Systems Corporation. Alliant FX/2800 Series System Descrtption, 1991.
• 5: Karl J. Ottenstein , Robert A. Ballance , Arthur B. MacCabe, The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.257-271, June 1990, White Plains, New York, United States
• 6: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 7: M. Berry, D. Chen, P. Koss, D. Kuck, S. Lo, Y. Pang, R. Roloff, A. Sameh, E. Clemenu, S. Chin, D. Schneider, G. Fox, P. Messina, D. WaLker, C. Hsiung, J. Schwarzmemr, K. Lue, S. Orzag, E Seidl, O. Johnson, G. Swanson, R. Goodmm, and J. Martin. The PER- FECT club benchmarks: Effective performance evaluation of supercomputers. Technical Report CSRD-827, Center for Supercomputmg Research and Development, University of Illinois, Urbana, IL, May 1989.
• 8: H. Berryman and J. Saltz. A manual for PARTI runtime primluves. Interim Report 90-13, ICASE, 1990.
• 9: W. Blume , R. Eigenmann, Performance Analysis of Parallelizing Compilers on the Perfect Benchmarks Programs, IEEE Transactions on Parallel and Distributed Systems, v.3 n.6, p.643-656, November 1992 [doi>10.1109/71.180621]
• 10: M. Burke, R. Cytron, J. Ferrante, and W. Hsieh. Automatic generation of nested, fork-join parallehsm. Journal of Supercomputing, pages 71-88, 1989.
• 11: W. J. Camp , S. J. Plimpton , B. A. Hendrickson , R. W. Leland, Massively parallel methods for engineering and science problems, Communications of the ACM, v.37 n.4, p.30-41, April 1994 [doi>10.1145/175276.175279]
• 12: Ding-Kai Chen , Josep Torrellas , Pen-Chung Yew, An efficient algorithm for the run-time parallelization of DOACROSS loops, Proceedings of the 1994 conference on Supercomputing, p.518-527, December 1994, Washington, D.C., United States
• 13: A. Dinning , E. Schonberg, An empirical comparison of monitoring algorithms for access anomaly detection, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.1-10, March 14-16, 1990, Seattle, Washington, United States
• 14: 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
• 15: V. P. Krothapalli , P. Sadayappan, An approach to synchronization for parallel computing, Proceedings of the 2nd international conference on Supercomputing, p.573-581, June 1988, St. Malo, France [doi>10.1145/55364.55420]
• 16: C. Kruskal. Efficient parallel algorithms for graph problems. In Proceedings of the 1985 Internattonal Conference on Parallel Processing, August 1985.
• 17: C. Kruskal. Efficient parallel algorithms for graph problems. In Proceedings of the 1986 International Conference on Parallel Processing, pages 869-876, August 1986.
• 18: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• 19: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 20: Shun-Tak Leung , John Zahorjan, Improving the performance of runtime parallelization, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.83-91, May 19-22, 1993, San Diego, California, United States
• 21: Zhiyuan Li, Array privatization for parallel execution of loops, Proceedings of the 6th international conference on Supercomputing, p.313-322, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143426]
• 22: Dror E. Maydan , S. Amarsinghe , Monica S. Lam, Data Dependence and Data-Flow Analysis of Arrays, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.434-448, August 03-05, 1992
• 23: S. P. Midkiff , D. A. Padua, Compiler algorithms for synchronization, IEEE Transactions on Computers, v.36 n.12, p.1485-1495, Dec. 1987 [doi>10.1109/TC.1987.5009499]
• 24: I. Nudler and L. Rudolph. Tools for the efficient developementof efficient parallel programs. In Proc. 1st Israeli Conference on Computer System Engineering, 1988.
• 25: 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]
• 26: Lawrence Rauchwerger , David Padua, The privatizing DOALL test: a run-time technique for DOALL loop identification and array privatization, Proceedings of the 8th international conference on Supercomputing, p.33-43, July 11-15, 1994, Manchester, England [doi>10.1145/181181.181254]
• 27: Lawrence Rauchwerger , David A. Padua, Parallelizing while loops for multiprocessor systems, Proceedings of the 9th International Symposium on Parallel Processing, p.347-356, April 25-28, 1995
• 28: J. Sakz and R. Mirchandaney. The preprocessed doacross loop. In Dr. H.D. Schwetman, editor, Proceedings of the 1991 International Conference on Parallel Processmg, pages 174-178. CRC Press, Inc., 1991. Vol. II - Software.
• 29: Joel H. Saltz , Ravi Mirchandaney , Kathleen Crowley, The doconsider loop, Proceedings of the 3rd international conference on Supercomputing, p.29-40, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318794]
• 30: Joel H. Salz , Ravi Mirchandaney , Kay Crowley, Run-Time Parallelization and Scheduling of Loops, IEEE Transactions on Computers, v.40 n.5, p.603-612, May 1991 [doi>10.1109/12.88484]
• 31: D. Schonberg, On-the-fly detection of access anomalies, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.285-297, June 19-23, 1989, Portland, Oregon, United States
• 32: P. Tu and D. Padua. Array privatizafion for shared and distributed memory machines. In Proceedings 2nd Workshop on Languages, Compilers, and Run-Time Envtronments for Distributed Memory Machines, September 1992.
• 33: Peng Tu , David A. Padua, Automatic Array Privatization, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.500-521, August 12-14, 1993
• 34: Penn Tu and David Padua. GSA based demand-driven symbolic analysis. Technical Report t339, University of Illinois at Urbana- Champaign, Cntr for Supercomputing Res & Dev, February 1994.
• 35: Andrei Vladimirescu, Lsi circuit simulation on vector computers (spice2, classie), 1982
• 36: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
• 37: J. Wu, J. Saltz, S. Hlranandam, and H. Berryman. Runtime compilauon methods for multicomputers. In Dr. H.D. Schwetman, editor, Proceedings of the 1991 International Conference on Parallel Processing, pages 26-30. CRC Press, Inc., 1991. Vol. II - Software.
• 38: Chuan-Qi Zhu , Pen-Chung Yew, A scheme to enforce data dependence on large multiprocessor systems, IEEE Transactions on Software Engineering, v.13 n.6, p.726-739, June 1987 [doi>10.1109/TSE.1987.233477]
• 39: Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM Press, New York, NY, 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers; Code generation

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Experimentation, Languages, Performance