“Combining” as a compilation technique for VLIW architectures

ABSTRACT

Combining is a local compiler optimization technique that can enhance the performance of global compaction techniques for VLIW machines. Given two adjacent operations of a certain class that are flow (read-after-write) dependent and that cannot be placed in the same micro-instruction, the combining technique can transform the operations so that the modified operations have no dependence. The transformed operations can be executed in the same micro-instruction, thus allowing the total execution time of the program to be reduced. In this paper, combining a pair of flow-dependent operations into a wide instruction word is suggested as an important compilation technique for VLIW architectures. Combining is particularly effective with software pipelining and loop unrolling since combinable operations can come together with a higher probability when these compilation techniques are used. We implemented combining in our parallelizing compiler for the wide instruction word architecture, which is now being built at the IBM T. J. Watson Research Center. It is shown that ten percent speedup is obtained on the Stanford integer benchmarks and other sequential-matured C programs, in comparison to compaction techniques that do not use combining. For a class of inner loops, combining can remove the inter-iteration dependencies completely and can improve performance in the same ratio as the loop is unrolled.

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: 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]
• 3: Ebcioglu, K. {1988}. Some Design Ideas for a VLIW Architecture for Sequential Natured Software, Parallel Processing (Proceedings of IFIP WC 10.3 Working Conference on Parallel Processing), M. Cosnard et al. (eds.), pp. 1-21, North Holland.
• 4: K. Ebcioğlu , Toshio Nakatani, A new compilation technique for parallelizing loops with unpredictable branches on a VLIW architecture, Selected papers of the second workshop on Languages and compilers for parallel computing, p.213-229, May 1990, Urbana, Illinois, United States
• 5: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 6: Alexandru Nicolau, Percolation Scheduling: A Parallel Compilation Technique, Cornell University, Ithaca, NY, 1985
• 7: Warren, S.H., Auslandcr, M.A., Chaitin, G.J., Chibib, A.C., Hopkins, M.E., and MacKay, A.L. {1986}. Final Code G eneration in the PL.8 Compiler, Report No. RC 11974, IBM T.J. Watson Research Center.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization
      B.1.5 Microcode Applications
          Subjects: Instruction set interpretation

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

General Terms:
Design, Languages