A novel framework of register allocation for software pipelining

ABSTRACT

Although software pipelining has been proposed as one of the most important loop scheduling methods, simultaneous scheduling and register allocation is less understood and remains an open problem [28]. The objective of this paper is to develop a unified algorithmic framework for concurrent scheduling and register allocation to support time-optimal software pipelining. A key intuition leading to this surprisingly simple formulation and its efficient solution is the association of maximum computation rate of a program graph with its critical cycles due to Reiter's pioneering work on Karp-Miller computation graphs [29]. In particular, our method generalizes the work by Callahan, Carr and Kennedy on scalar expansion[6], the work by Lam on modular variable expansion for software pipelined loops [20], and the work by Rau et al. on register allocation for modulo scheduled loops[28].

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: Alexander Aiken, Compaction-Based Parallelization, Cornell University, Ithaca, NY, 1988
• 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: A. Aiken and A. Nicolau. A realistic resourceconstrained software pipelining algorithm. In Proceedings of the Third Workshop on Programming Languages and Compilers for Parallel Computing, Irvine, CA, August 1990.
• 5: David G. Bradlee , Susan J. Eggers , Robert R. Henry, Integrating register allocation and instruction scheduling for RISCs, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.122-131, April 08-11, 1991, Santa Clara, California, United States
• 6: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
• 7: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 8: G. J. Chaitin, M. Auslander, A. Chandra, J. Cocke, M. Hopkins, and P. Markstein. Register allocation via coloring. Computer Languages 6, pages 47-57, January 1981.
• 9: V. Chvatal. Linear Porgramming. W.H. Freeman and Company., 1983.
• 10: E. Duesterwald, R. Gupta, and M.L. Sofia. Register pipelining: An integrated approacn to register allocation for scalar and subscripted variables. Technical report, Department of Computer Science, University of Pittsburgh, 1991.
• 11: K. Ebcioglu and T. Nakatani. A new compilation technique for parallelization loops with unpredictable branches on a VLIW architecture. Technical report, IBM, 1990.
• 12: 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]
• 13: Kemal Ebcioglu , Alexandru Nicolau, A global resource-constrained parallelization technique, Proceedings of the 3rd international conference on Supercomputing, p.154-163, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318807]
• 14: Christine Eisenbeis, William Jalby, Daniel Windheiser, and Francois Bodin. A strategy for array management in local memory. In Third Workshop on Programming Languages and Compilers }or Parallel Computing. University of California, Irvine, 1990. To be published by Pitman/MIT Press.
• 15: Philip B. Gibbons , Steven S. Muchnick, Efficient instruction scheduling for a pipelined architecture, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.11-16, June 25-27, 1986, Palo Alto, California, United States
• 16: L. Hendren, G.R. Gao, E. Altman, and C. Mukerjl. A register allocation framework based on hierarchical cyclic interval graphs. Lecture Notes in Computer Science 641, pages 176-191, October 1992.
• 17: John L. Hennessy , Thomas Gross, Postpass Code Optimization of Pipeline Constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.422-448, July 1983 [doi>10.1145/2166.357217]
• 18: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 19: L. G. Khachian. A polynomial algorithm in linear programming. Soviet Math. Doklady, 20:191-194, 1979.
• 20: 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
• 21: Eugene L. Lawler. Combinatorial Optimization: Net. works and Matroids. Saunders College Publishing, Ft Worth, TX, 1976.
• 22: Toshio Nakatani , Kemal Ebcioğlu, Using a lookahead window in a compaction-based parallelizing compiler, Proceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture, p.57-68, November 27-29, 1990, Orlando, Florida, United States
• 23: Alexandru Nicolau , Roni Potasman , Haigeng Wang, Register Allocation, Renaming and Their Impact on Fine-Grain Parallelism, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.218-235, August 07-09, 1991
• 24: Q. Ning and G.R. Gao. A novel framework of register allocation for software pipelining. Technical Report ACAPS Technique Memo 42, School of Computer Science, McGill University, Montreal, Quebec, Canada, 1992.
• 25: Qi Ning. Optimal Register Allocation to Support Time- Optimal Scheduling }or Loops. PhD thesis, in preparation, School of Computer Science, McGill University, 1992.
• 26: C. V. Ramamoorthy and G. S. Ho. Performance evaluation of asynchronous concurrent systems using Petri Nets. IEEE Transactions on Computers, pages 440- 448, September 1980.
• 27: 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
• 28: B. R. Rau , M. Lee , P. P. Tirumalai , M. S. Schlansker, Register allocation for software pipelined loops, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.283-299, June 15-19, 1992, San Francisco, California, United States
• 29: Raymond Reiter, Scheduling Parallel Computations, Journal of the ACM (JACM), v.15 n.4, p.590-599, Oct. 1968 [doi>10.1145/321479.321485]
• 30: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 31: 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
• 32: H. S. Warren, Jr., Instruction scheduling for the IBM RISC System/6000 processor, IBM Journal of Research and Development, v.34 n.1, p.85-92, Jan. 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures
      D.3.4 Processors
          Subjects: Code generation

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

General Terms:
Algorithms, Performance, Theory