Extracting task-level parallelism

ABSTRACT

Automatic detection of task-level parallelism (also referred to as functional, DAG, unstructured, or thread parallelism) at various levels of program granularity is becoming increasingly important for parallelizing and back-end compilers. Parallelizing compilers detect iteration-level or coarser granularity parallelism which is suitable for parallel computers; detection of parallelism at the statement-or operation-level is essential for most modern microprocessors, including superscalar and VLIW architectures. In this article we study the problem of detecting, expressing, and optimizing task-level parallelism, where “task” refers to a program statement of arbitrary granularity. Optimizing the amount of functional parallelism (by allowing synchronization between arbitrary nodes) in sequential programs requires the notion of precedence in terms of paths in graphs which incorporate control and data dependences. Precedences have been defined before in a different context; however, the definition was dependent on the ideas of parallel execution and time. We show that the problem of determining precedences statically is NP-complete. Determining precedence relationships is useful in finding the essential data dependences. We show that there exists a unique minimum set of essential data dependences; finding this minimum set is NP-hard and NP-easy. We also propose a heuristic algorithm for finding the set of essential data dependences. Static analysis of a program in the Perfect Benchmarks was done, and we present some experimental results.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 1983
• 3: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 4: David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler Transformations for High-Performance Computing, University of California at Berkeley, Berkeley, CA, 1993
• 5: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 6: BERRY. hi., CHEN. D, KOSS. P., KucK. D., POINTER. L.. Lo. S. PANG. Y, ROLOFF R, SAhIEH. A.. CLEMENTI. E., CHIN. S.. SCHNEIDER. D., FOX. G., hIESSINA. P. \VALKER. D. HSIUNG. C, SCH\VARZhlEIER. J, LUE K, ORSZAG. S, SEIDL . F, JOHNSON. O, S\VAN- SON. G., GOODRUI~I R, AND hlARTIN. J. 1989 The Perfect Club Benchmarks: Effective performance evaluation of supercomputers Int. J. Supercomput. Appl. 3, 3 (Fall), 5-40.
• 7: David Callahan , Jaspal Sublok, Static analysis of low-level synchronization, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.100-111, May 05-06, 1988, Madison, Wisconsin, United States
• 8: COFFhtAN E. JR, Ed 1976. Computer and Job-shop Scheduling Theory. John Wiley, New York
• 9: CRAY 1985. l~Iultitasking user guide Tech Rep SN-0222, Cray Research. Inc., Eagan Minn.
• 10: 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
• 11: R. Cytron , M. Hind , W. Hsieh, Automatic generation of DAG parallelism, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.54-68, June 19-23, 1989, Portland, Oregon, United States
• 12: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 13: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 14: Milind Baburao Girkar, Functional parallelism: theoretical foundations and implementation, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 15: M. Girkar , C. D. Polychronopoulos, Automatic Extraction of Functional Parallelism from Ordinary Programs, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.166-178, March 1992 [doi>10.1109/71.127258]
• 16: 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]
• 17: 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]
• 18: Steven Novack , Alexandru Nicolau, A hierarchical approach to instruction-level parallelization, International Journal of Parallel Programming, v.23 n.1, p.35-62, Feb. 1995 [doi>10.1007/BF02577783]
• 19: POLYCHRONOPOI~LO~ C. D 1990 Aulm-scheduhng Control flow and data flow corne together. Tech Rep 1058. Center for Supercomputing Research and Development. Univ. of Ilhnols at Urbana-Champaign, Urbana Ill
• 20: Constantine D. Polychronopoulos, The hierarchical task graph and its use in auto-scheduling, Proceedings of the 5th international conference on Supercomputing, p.252-263, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109089]
• 21: POLYCHRONOPOULOS. C D. G~RKaa hi, HAGHIGHAT. ~{ LEE C ,LEIrNG B ,AND S~.'HOIrTEN D 1991 Parafiase-2Programmer'si~Ianual CSRD Int Doc ('enter for Supercomputlng Research and Development, Unlv of Illinois at Urbana-Champa~gn Urbana, Ill
• 22: Constantine D. Polychronopoulos , Milind B. Girkar , Mohammad Reza Haghighat , Chia Ling Lee , Bruce Leung , Dale Schouten, Parafrase-2: an environment for parallelizing, partitioning, synchronizing, and scheduling programs on multiprocessors, International Journal of High Speed Computing, v.1 n.1, p.45-72, May 1989 [doi>10.1142/S0129053389000044]
• 23: SCHWARTZ ,J T AND SHARIR i~i 1979 A design for opt~m~zat~ons of the b~tvectotmg class Tech Rep NSO-17. Courant Inst of Mathematmal Sciences, New "~brk UnP~- , New York Sept.
• 24: Mark Weiser, Programmers use slices when debugging, Communications of the ACM, v.25 n.7, p.446-452, July 1982 [doi>10.1145/358557.358577]
• 25: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982
• 26: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990

INDEX TERMS

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

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

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

General Terms:
Algorithms, Experimentation, Languages, Theory

Keywords:
code generation, control and data dependence, parallelizing compilers, synchronization