A global resource-constrained parallelization technique

ABSTRACT

This paper presents a new approach to resource-constrained compiler extraction of fine-grain parallelism, targeted towards VLIW supercomputers, and in particular, the IBM VLIW (Very Large Instruction Word) processor. The algorithms described integrate resource limitations into Percolation Scheduling—a global parallelization technique—to deal with resource constraints, without sacrificing the generality and completeness of Percolation Scheduling in the process. This is in sharp contrast with previous approaches which either applied only to conditional-free code, or drastically limited the parallelization process by imposing relatively local heuristic resource constraints early in the scheduling process.

REFERENCES

• 1: Alexander Scott Aiken, Compaction-based parallelization, 1988
• 2: 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
• 3: John R. Allen , Ken Kennedy, Automatic loop interchange, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.233-246, June 17-22, 1984, Montreal, Canada
• 4: Ronald Gary Cytron, Compile-time scheduling and optimization for asynchronous machines (multiprocessor, compiler, parallel processing), 1984
• 5: Kemal Ebcioğlu, A compilation technique for software pipelining of loops with conditional jumps, Proceedings of the 20th annual workshop on Microprogramming, p.69-79, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255317]
• 6: K.Ebcioglu. Some Design Ideas for a VLII4r Architecture for Sequential Natured Software in Parallel Processing (Proc. IFIP WG 10.3 Working Conference on Parallel Processing), M. Cosnard et al. (editors), North Holland, 1988.
• 7: K. Ebcioğlu, A wide instruction word architecture for fine-grain parallelism, Proceedings of the conference on CONPAR 88, p.424-437, October 1989, UMIST, Manchester, United Kingdom
• 8: K.Ebcioglu and A.Nicolau. Resource Constrained Percolation Scheduling. IBM T.J.Watson Research Center, and U.of Cal. Irvine Dept of ICS Tech.Rep., May 1989.
• 9: J.A.Fisher Trace scheduling: A technique}or global microcode compaction. IEEE Transactions on Computers, Number 7, 1981.
• 10: Nicolau. A. Uniform Parallelism Exploitation in Ordinary Programs. Proc. International Conf. on Parallel Processing, August 1985.
• 11: 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]
• 12: 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]
• 13: M.Tokoro, E.Tamura, T.Takizuka. Optimization of Microprograms. IEEE Transactions on Computers, Number 7, 1981.
• 14: M.Wolfe. Loop Skewing: the Wavefront Method Revisited. Tech. Rep., CSRD, U.of Ill. Urbana Champaign, April 1987.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

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

  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION

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

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Management, Performance, Theory