Software pipelining: a comparison and improvement

ABSTRACT

Software pipelining can significantly increase the execution rate of loops. Each of the four major software pipelining algorithms takes a different approach to software pipelining. This paper discusses each method and explores some of the similarities and differences among the methods. On loops consisting of a single basic block, the Perfect Pipelining Algorithm [1] is the only software pipelining algorithm that currently achieves time optimality, in the absence of resource constraints. A technique for unrolling the loop before pipelining is presented as an improvement to software pipelining, as it can allow Lam's algorithm [2] to achieve time optimality for these restricted loops. Unrolling has an advantage over Perfect Pipelining because it can reduce the code space required for the software pipeline.

REFERENCES

• 1: 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
• 2: 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
• 3: B. Su , S. Ding , J. Xia, URPR—An extension of URCR for software pipelining, Proceedings of the 19th annual workshop on Microprogramming, p.94-103, October 15-17, 1986, New York, New York, United States
• 4: K.S. Lin. Software Pipelining - A Loop Optimization Method. Technical Report CS-89-02, Department of Computer Science, Utah State Uni-.ersity, Logan, UT, Oct 1989.
• 5: Monica Sin-Ling Lam, A systolic array optimizing compiler, 1987
• 6: R.E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal of Computing, 1(2):146-160, June 1972.
• 7: Alexander Scott Aiken, Compaction-based parallelization, 1988
• 8: 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]
• 9: 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
• 10: 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]
• 11: T. Nakatani , K. Ebcioğlu, “Combining” as a compilation technique for VLIW architectures, Proceedings of the 22nd annual workshop on Microprogramming and microarchitecture, p.43-55, August 14-16, 1989, Dublin, Ireland
• 12: R.B. Jones. Constrained Software Pipelining. Master's thesis, Utah State University, Logan, Utah, December 1990. expected.
• 13: B. Su and J. Wang. Loop-carried Dependence and the Improved URPR Software Pipelining Approach. 1990. Submitted to HICSS-24.
• 14: Bogong Su , Shiyuan Ding , Jian Wang , Jinshi Xia, GURPR—a method for global software pipelining, Proceedings of the 20th annual workshop on Microprogramming, p.88-96, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255322]
• 15: 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
• 16: Alexander Aiken , Alexandru Nicolau, Loop Quantization: an Analysis and Algorithm, Cornell University, Ithaca, NY, 1987
• 17: V. H. Allen , R. A. Mueller, Compaction with General Synchronous Timing, IEEE Transactions on Software Engineering, v.14 n.5, p.595-599, May 1988 [doi>10.1109/32.6137]
• 18: Bogong Su , Shiyuan Ding , Jian Wang , Jinshi Xia, Microcode compaction with timing constraints, Proceedings of the 20th annual workshop on Microprogramming, p.59-68, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255314]

INDEX TERMS

Keywords:
operation scheduling, recognition of parallelism, software pipelining