Loop optimization for horizontal microcoded machines

ABSTRACT

Long Instruction Word (LIW) architectures exploit parallelism between various functional units. In order to produce efficient code for such an architecture, the microcode compiler will have to expose a relatively large degree of fine grain parallelism and it will have to take into account the fine level characteristics of the architecture. This paper aims at describing a microcode compiler developed at IRISA for such architectures. After a brief overview of the compilation process, we focus on loop scheduling techniques. The software pipelining algorithm is firstly described. Then a new unrolling-based optimization algorithm is introduced and compared to the classical software pipelining algorithm. This algorithm differs from the traditional loop unrolling algorithm because the unrolling of the loop is only used to find a cyclic scheduling of the loop, then this scheduling allows a software pipelining to be constructed.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: A. Aiken , A. Nicolau, A development environment for horizontal microcode programs, ACM SIGMICRO Newsletter, v.17 n.4, p.23-31, Dec. 1986
• 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: Franc¸ois Bodin , Franc¸ois Charot , Charles Wagner, Overview of a high-performance programmable pipeline structure, Proceedings of the 3rd international conference on Supercomputing, p.398-409, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318868]
• 5: S. Dasgupta and J. Tartar. The identification of maximal parallelism in straight-line microprograms. IEEE Transactions on Computers, 25(10):086-991, 1976.
• 6: David Landskov , Scott Davidson , Bruce Shriver , Patrick W. Mallett, Local Microcode Compaction Techniques, ACM Computing Surveys (CSUR), v.12 n.3, p.261-294, Sept. 1980 [doi>10.1145/356819.356822]
• 7: David Johns Dewitt, A machine independent approach to the production of optimized horizontal microcode., 1976
• 8: C. Eisenbeis. Optimisation automatique de programmes sur array-processors. Th~se d'universit~ de Pierre et Marie Curie Paris 6, J uin 1986.
• 9: C. Eisenbeis, Optimization of horizontal microcode generation for loop structures, Proceedings of the 2nd international conference on Supercomputing, p.453-465, June 1988, St. Malo, France [doi>10.1145/55364.55408]
• 10: C. Eisenbeis , W. Jalby , A. Lichnewsky, Squeezing more CPU performance out of a Cray-2 by Vector block scheduling, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.237-246, November 12-17, 1988, Orlando, Florida, United States
• 11: J.A. Fisher. Trace scheduling: A technique for global microcode compaction. IEEE Transactions on Computers, 30(7):478-490, 1981.
• 12: 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
• 13: Thomas Gross , Monica S. Lam, Compilation for a high-performance systolic array, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.27-38, June 25-27, 1986, Palo Alto, California, United States
• 14: R.W. Hockney and C.R. Jcsshope. Parallel Computers. Adam Hilger Ltd, Bristol, 1981.
• 15: M. Lain. A Systolic Array Optimizing Compiler. PhD thesis, Carnegie Mellon University, May 1987.
• 16: Alexandru Nicolau, A Fine-Grain Parallelizing Compiler, Cornell University, Ithaca, NY, 1986
• 17: 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]
• 18: Janak H. Patel , Edward S. Davidson, Improving the throughput of a pipeline by insertion of delays, Proceedings of the 3rd annual symposium on Computer architecture, p.159-164, January 19-21, 1976
• 19: B. R. Rau , C. D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, Proceedings of the 14th annual workshop on Microprogramming, p.183-198, December 01-01, 1981, Chatham, Massachusetts, United States
• 20: Roy F. Touzeau, A Fortran compiler for the FPS-164 scientific computer, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.48-57, June 17-22, 1984, Montreal, Canada

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

  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: System architectures

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

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