Qi Ning
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].
- 1.A. V. Aho, R. Sethi, and J. D. Ullman. Compilers-- Principles, Techniques, and Tools. Addison-Wesley Publishing Co., 1986.]] Google Scholar
Digital Library
- 2.A. Aiken. Compaction-based parallelization. (PhD thesis), Technical Report 88-922, Cornell University, 1988.]] Google ScholarDigital Library
- 3.A. Aiken and A. Nicolau. Optimal loop parallelization. In Proceedings of the 1988 A CM SIGPLAN Conference on Programming Languages Design and Implementation, June 1988.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 5.D. G. Bradlee, S. J. Eggers, and R. R. Henry. Integrating register allocation and instruction scheduling for RISCs. International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS IV), pages 122-131, April 1991.]] Google ScholarDigital Library
- 6.David Callahan, Steve Carr, and Ken Kennedy. Improving register allocation for subscripted variables. Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation, June 1990. White Plains, NY.]] Google ScholarDigital Library
- 7.G. J. Chaitin. Register allocation & spilling via graph coloring. A CM SIGPLAN Syrup. on Compiler Construction, pages 98-105, 1982.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 9.V. Chvatal. Linear Porgramming. W.H. Freeman and Company., 1983.]]Google Scholar
- 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.]]Google Scholar
- 11.K. Ebcioglu and T. Nakatani. A new compilation technique for parallelization loops with unpredictable branches on a VLIW architecture. Technical report, IBM, 1990.]]Google Scholar
- 12.K. Ebcioglu. A compilation technique for software pipelining of loops with conditional jumps. In Proceedings o} the 20th Annual Workshop on Microprogramruing, December 1987.]] Google ScholarDigital Library
- 13.K. Ebcio~lu and A. Nicolau. A global resourceconstrained paraUelization technique. In Proceedings of the A CM SIGARCH International Conference on Supercomputing, June 1989.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 15.P. B. Gibbons and S. S. Muchnick. Efficient instruction scheduling for a pipelined architecture. In Proceedings of the A CM Symposium on Compiler Construction, pages 11-16, Palo Alto, CA, June 1986.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 17.J. Hennessy and T. Gross. Postpass code optimization of pipelined constraints. A CM Transactions on Programming Languages and Systems, 5(3):422-448, July 1983.]] Google ScholarDigital Library
- 18.N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4:373-395, 1984.]] Google ScholarDigital Library
- 19.L. G. Khachian. A polynomial algorithm in linear programming. Soviet Math. Doklady, 20:191-194, 1979.]]Google Scholar
- 20.Monica Lain. Software pipelining: An effective scheduling technique for VLIW machines. In Proceedings of the 1988 A CM SIGPLAN Conference on Programming Languages Design and Implementation, pages 318-328, Atlanta, GA, June 1988.]] Google ScholarDigital Library
- 21.Eugene L. Lawler. Combinatorial Optimization: Net. works and Matroids. Saunders College Publishing, Ft Worth, TX, 1976.]]Google Scholar
- 22.T. Nakatani and K. Ebcioglu. Using a lookahaed window in a compaction-based parallelizing compiler. In Proceedings of the 23rd Annual Workshop on Microprogramming and Microarchitectures, pages 57-68, 1990.]] Google ScholarDigital Library
- 23.A. Nicolau, R. Potasman, and H. Wang. Register allocation, renaming and their impact on fine-grained parallelism. In U. Banerjee et al., editor, Languages and Compilers for Parallel Computing, Lecture Notes in Computer Science 589, pages 359-373, Santa Clara, California, 1992. Springer-Verlag.]] Google Scholar
- 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.]]Google Scholar
- 25.Qi Ning. Optimal Register Allocation to Support Time- Optimal Scheduling }or Loops. PhD thesis, in preparation, School of Computer Science, McGill University, 1992.]]Google Scholar
- 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.]]Google Scholar
- 27.B. R. Rau and C. D. Glaeser. Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing. In Proceedings o/ the 14th Annual Workshop on Microprogramruing, pages 183-198, 1981.]] Google ScholarDigital Library
- 28.B.R. Rau, M. Lee, P.P. Tirurnalai, and M.S. Schlansker. Register allocation for modulo scheduled loops: Strategies, algorithms and heuristics. In Proceedings of SIG- PLAN '92 Conf. on Programming Language Design and Implementation, San Francisco, CA, 1992.]] Google ScholarDigital Library
- 29.R. Reiter. Scheduling parallel computations. Journal of A CM, 15:590-599, October 1968.]] Google ScholarDigital Library
- 30.A. Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, 1986.]] Google ScholarDigital Library
- 31.R. F. Touzeau. A FORTRAN compiler for the FPS- 164 scientific computer. In Proceedings of the A CM SIGPLAN '8~ Symposium on Compiler Construction, pages 48-57, June 1984.]] Google ScholarDigital Library
- 32.H.S. Warren. Instruction scheduling for the IBM RISC System/6000 processor. IBM J. Res. Develop., 34(1), January 1990.]] Google ScholarDigital Library
Index Terms
- A novel framework of register allocation for software pipelining
Recommendations
Register allocation for software pipelined multidimensional loops
This article investigates register allocation for software pipelined multidimensional loops where the execution of successive iterations from an n-dimensional loop is overlapped. For single loop software pipelining, the lifetimes of a loop variable in ...
Heuristics for register-constrained software pipelining
MICRO 29: Proceedings of the 29th annual ACM/IEEE international symposium on MicroarchitectureSoftware Pipelining is a loop scheduling technique that extracts parallelism from loops by overlapping the execution of several consecutive iterations. There has been a significant effort to produce throughput-optimal schedules under resource ...
Software pipelining: an effective scheduling technique for VLIW machines
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A SelectionThe basic idea behind software pipelining was first developed by Patel and Davidson for scheduling hardware pipe-lines. As instruction-level parallelism made its way into general-purpose computing, it became necessary to automate scheduling. How and ...
Comments