Compiler techniques for maximizing fine-grain and coarse-grain parallelism in loops with uniform dependences

ABSTRACT

In this paper, an approach to the problem of exploiting parallelism within nested loops is proposed. The proposed method first finds out all the initially independent computations, and then, based on them, identifies the valid partitioning bases to partition the entire iteration space of the loop nest. Because the shape of the iteration space is taken into account, pseudo-dependence relations are eliminated and hence more parallelism is exploited. Our approach provides a systematic method to maximize the degree of fine- or coarse-grain parallelism and is free from the open question of how to combine different loop transformations for the goal of maximizing parallelism. It is also shown that our approach can exploit more parallelism than other related work and have many advantages over them.

REFERENCES

• 1: Y.-S. Chen and S.-D. Wang, "A Parallelizing Compilation Approach to Maximizing Parallelism within Uniform Dependence Nested loops," in Proc. 1993 Inr Conf. Parallel and Distributed Systems, Taipei, Taiwan, Dec. 1993.
• 2: E. H. D'Hollander, Partitioning and Labeling of Loops by Unimodular Transformations, IEEE Transactions on Parallel and Distributed Systems, v.3 n.4, p.465-476, July 1992 [doi>10.1109/71.149964]
• 3: J.A.B. Fortes and F. Parisi-Presicce, "Optimal Linear Schedules for the Parallel execution of Algorithms," in Proc. Int. Conf. Parallel Processing, 1984, pp. 322-329.
• 4: F. Irigoin , R. Triolet, Supernode partitioning, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.319-329, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73588]
• 5: Richard M. Karp , Raymond E. Miller , Shmuel Winograd, The Organization of Computations for Uniform Recurrence Equations, Journal of the ACM (JACM), v.14 n.3, p.563-590, July 1967 [doi>10.1145/321406.321418]
• 6: D.J. Kuck, Y. Muraoka and S.-C. Chen, "On the number of operations Simultaneously Executable in FORTRAN-Like Programs and Their Resulting Speed-Up," IEEE Trans. Comput., Vol. C-21, No. 12, pp. 1293-1310, Dec. 1972.
• 7: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 8: Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
• 9: Alexandru Nicolau, Loop quantization: a generalized loop unwinding technique, Journal of Parallel and Distributed Computing, v.5 n.5, p.568-586, October 1988 [doi>10.1016/0743-7315(88)90013-5]
• 10: J.-K. Peir , R. Cytron, Minimum Distance: A Method for Partitioning Recurrences for Multiprocessors, IEEE Transactions on Computers, v.38 n.8, p.1203-1211, August 1989 [doi>10.1109/12.30873]
• 11: Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Norwell, MA, 1988
• 12: 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]
• 13: C. D. Polychronopoulos , D. J. Kuck, Guided self-scheduling: A practical scheduling scheme for parallel supercomputers, IEEE Transactions on Computers, v.36 n.12, p.1425-1439, Dec. 1987 [doi>10.1109/TC.1987.5009495]
• 14: 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]
• 15: Weijia Shang , Jose A. B. Fortes, Time Optimal Linear Schedules for Algorithms with Uniform Dependencies, IEEE Transactions on Computers, v.40 n.6, p.723-742, June 1991 [doi>10.1109/12.90251]
• 16: W. Shang , J. A. B. Fortes, On Time Mapping of Uniform Dependence Algorithms into Lower Dimensional Processor Arrays, IEEE Transactions on Parallel and Distributed Systems, v.3 n.3, p.350-363, May 1992 [doi>10.1109/71.139208]
• 17: Weijia Shang , Jose A. B. Fortes, Independent Partitioning of Algorithms with Uniform Dependencies, IEEE Transactions on Computers, v.41 n.2, p.190-206, February 1992 [doi>10.1109/12.123395]
• 18: C. M. Wang , S. D. Wang, Efficient Processor Assignment Algorithms and Loop Transformations for Executing Nested Parallel Loops on Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.3 n.1, p.71-82, January 1992 [doi>10.1109/71.113083]
• 19: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 20: M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991 [doi>10.1109/71.97902]
• 21: M. Wolfe, More iteration space tiling, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.655-664, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76337]
• 22: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
• 23: 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

General Terms:
Measurement, Performance, Theory, Verification