The privatizing DOALL test: a run-time technique for DOALL loop identification and array privatization

ABSTRACT

Current parallelizing compilers cannot identify a significant fraction of fully parallel loops because they have complex or statically insufficiently defined access patterns. For this reason, we have developed the Privatizing DOALL test—a technique for identifying fully parallel loops at run-time, and dynamically privatizing scalars and arrays. The test itself is fully parallel, and can be applied to any loop, regardless of the structure of its data and/or control flow. The technique can be utilized in two modes: (i) the test is performed before executing the loop and indicates whether the loop can be executed as a DOALL; (ii) speculatively—the loop and the test are executed simultaneously, and it is determined later if the loop was in fact parallel. The test can also be used for debugging parallel programs. We discuss how the test can be inserted automatically by the compiler and outline a cost/performance analysis that can be performed to decide when to use the test. Our conclusion is that the test should almost always be applied—because, as we show, the expected speedup for fully parallel loops is significant, and the cost of a failed test (a not fully parallel loop), is minimal. We present some experimental results on loops from the PERFECT Benchmarks which confirm our conclusion that this test can lead to significant speedups.

REFERENCES

• 1: Alliant Computer Systems Corporation. 42 Nagog Park, Acton, Massachusetts 01720. FX/Series Architecture Manual, 1986. Part Number: 300-00001-B.
• 2: Alliant Computers Systems Corporation. AlIiant FX/2800 Series System Description, 1991.
• 3: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 4: M. Berry, D. Chen, P. Koss, D. Kuck, S. Lo, Y. Pang, R. Roloff, A. Sameh, E. Clementi, S. Chin, D. Schneider, G. Fox, P. Messina, D. Walker, C. Hsiung, J. Schwarzmeier, K. Lue, S. Orzag, F. Seidl, O. Johnson, G. Swanson, R. Goodrum, and J. Martin. The PERFECT club benchmarks: Effective performance evaluation of supercomputers. Technical Report CSRD-827, Center for Supercomputing Research and Development, University of Illinois, Urbana, IL, May 1989.
• 5: H. Berryman and J. Saltz. A manual for PARTI runtime primitives. Interim Report 90-13, ICASE, 1990.
• 6: 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]
• 7: M. Burke, R. Cytron, J. Ferrante, and W. Hsieh. Automatic generation of nested, fork-join parallelism. Journal of Supercomputing, pages 71-88, 1989.
• 8: R. Eigenmann and W. Blume. An effectiveness study of parallelizing compiler techniques. In Proc. of the i991 Int'l. Conf. on Parallel Processing, pages 17-25, August 1991.
• 9: Perry A. Emrath , Sanjoy Ghosh , David A. Padua, Detecting Nondeterminacy in Parallel Programs, IEEE Software, v.9 n.1, p.69-77, January 1992 [doi>10.1109/52.108783]
• 10: M. D. Guzzi , D. A. Padua , J. Hoeflinger , D. H. Lawrie, Cedar Fortran and other vector and parallel Fortran dialects, The Journal of Supercomputing, v.4 n.1, p.37-62, Mar. 1990 [doi>10.1007/BF00162342]
• 11: 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]
• 12: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 13: 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
• 14: 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]
• 15: 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
• 16: 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]
• 17: 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]
• 18: C. D. Polychronopoulos, Compiler Optimizations for Enhancing Parallelism and Their Impact on Architecture Design, IEEE Transactions on Computers, v.37 n.8, p.991-1004, August 1988 [doi>10.1109/12.2249]
• 19: J. Saltz and R. Mirchandaney. The preprocessed doacross loop. In Dr. H.D. Schwetman, editor, Proc. of the 1991 Int'l. Conf. on Parallel Processing, St. Charles, Illinois, August 12- 16, pages 174-178. CRC Press, Inc., 1991. Vol. II - Software.
• 20: 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]
• 21: 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]
• 22: 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
• 23: J. E. Thornton, Design of a Computer—The Control Data 6600, Scott Foresman & Co, 1970
• 24: R.M. Tomasulo. An efficient algorithm for exploitingmultipIe arithmetic units. IBM Journal of Research and Development, 11:25-33, January 1967.
• 25: P. Tu and D. Padua. Array privatization for shared and distributed memory machines. In Proc. 2nd Workshop on Languages, Compilers, and Run-Tzme Environments.for Distributed Memory Machines, September 1992.
• 26: 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
• 27: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
• 28: Wu, J. Saltz, S. Hiranandani, and H. Berryman. Runtime compilation methods for multicomputers. In Dr. H.D. Schwetman, editor, Proc. of the 1991 Int'l. Conf. on Parallel Processing, St. Charles, Illinois, August 1~-16, pages 26-30. CRC Press, Inc., 1991. Vol. II- Software.
• 29: 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]
• 30: Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM Press, New York, NY, 1990

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization

General Terms:
Measurement, Performance, Theory