On optimal loop parallelization

ABSTRACT

The problem of automatic loop parallelization has received a lot of attention in the area of parallelizing compilers. Automatic loop parallelization can be achieved by several algorithms. In this paper we address the problem of time optimal parallelization of loops with conditional jumps. We prove that even for machines with unlimited resources there are simple loops for which no semantically and algorithmically equivalent time optimal program exists.

REFERENCES

• 1: Thomas L. Adam , K. M. Chandy , J. R. Dickson, A comparison of list schedules for parallel processing systems, Communications of the ACM, v.17 n.12, p.685-690, Dec 1974 [doi>10.1145/361604.361619]
• 2: A. Aiken , A. Nicolau, A Development Environment for Horizontal Microcode, IEEE Transactions on Software Engineering, v.14 n.5, p.584-594, May 1988 [doi>10.1109/32.6136]
• 3: A. Aiken , A. Nicolau, Optimal loop parallelization, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.308-317, June 20-24, 1988, Atlanta, Georgia, United States
• 4: Alexander Aiken , Alexandru Nicolau, Perfect Pipelining: A New Loop Parallelization Technique, Proceedings of the 2nd European Symposium on Programming, p.221-235, March 21-24, 1988
• 5: 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]
• 6: Coffman E.G. Computer and Job-shop Scheduling Theory. John Wiley and Sons, 1976.
• 7: Cytron R. Doacross: beyond vectorization for multiprocessors. In International Conference on Parallel Processing, pages 836-844, IEEE, August 1986.
• 8: Ebcioglu K. Some design ideas for a VLIW architecture for sequential-natured software. In Proceedings of the IFIP WG 10.3 Working Conference on Parallel Processing, pages 1-21, North- Holland, April 1988.
• 9: 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]
• 10: Fisher J.A. Trace scheduling: a technique for global microcode compaction. IEEE Transactions on Computers, C-30(7):478-490, July 1981.
• 11: Fisher J.A. The VLIW machine: a multiprocessor for compiling scientific code. IEEE Computer, 17(7):45-53, July 1984.
• 12: Foster C.C. and Riseman E.M. Percolation of code to enhance parallel dispatching and execution. IEEE Transactions on Computers, C- 21(12):1411-1415, December 1972.
• 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: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 15: Padua D.A., Kuck D.J. and Lawrie D.H. Highspeed multiprocessors and compilation techniques. IEEE Transactions on Computers, C- 29(9):763-776, September 1980.
• 16: 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]
• 17: Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Norwell, MA, 1988
• 18: Riseman E.M. and Foster C.C. The inhibition of potential parallelism by conditional jumps. IEEE Transactions on Computers, C-21(12):1405-1411, December 1972.
• 19: A. Uht, Requirements for optimal execution of oops with tests, Proceedings of the 2nd international conference on Supercomputing, p.230-237, June 1988, St. Malo, France [doi>10.1145/55364.55387]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design