Realistic scheduling: compaction for pipelined architectures

ABSTRACT

This paper presents an approach for the development of microcode for parallel and pipelined machines. The approach is geared towards mapping programs with real-time constraints and/or massive time requirements onto synchronous parallel computers (VLIW's, superscalars and microengines). In order to exploit the maximal parallelism from such machines, both spatial (multiple functional units) and temporal (pipelined) capabilities of the architecture need to be exploited. Until now, parallelizing compilers for parallel machines have not fully taken advantage of pipelining capabilities: they have either assumed that all operations take one cycle or have added pipelining as an after thought. These approaches restrict the speed-up. We built a system which is based on a set of low-level transformations called Pipelined Percolation Scheduling (PPS). The transformations integrate the exploitation of temporal and spatial parallelism. Although these low-level transformations are integrated into our system they are self-contained and may be used separately by applying 'higher level' transformations (on top of PPS) to optimize performance for a target architecture.

REFERENCES

• Ai88: Alexander Scott Aiken, Compaction-based parallelization, 1988
• AiNi88a: 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]
• AiNi88: Alexander Aiken , Alexandru Nicolau, Perfect Pipelining: A New Loop Parallelization Technique, Proceedings of the 2nd European Symposium on Programming, p.221-235, March 21-24, 1988
• Co88: Robert P. Colwell , Robert P. Nix , John J. O'Donnell , David B. Papworth , Paul K. Rodman, A VLIW architecture for a trace Scheduling Compiler, IEEE Transactions on Computers, v.37 n.8, p.967-979, August 1988 [doi>10.1109/12.2247]
• Eb87: 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]
• Eb88: K.Ebcioglu. Some Design Ideas for a VLIW Architecture for Sequential-Natured Software. Proceedings IFIP, 1988.
• EbNa89: 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
• EbNi89: 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]
• El86: John R. Ellis, Bulldog: a compiler for VLSI architectures, MIT Press, Cambridge, MA, 1986
• Fi81: J. A. Fisher. Trace Scheduling: A technique for global microcode compaction. IEEE Transactions on Computers, No. 7,pp. 478-490, 1981.
• GrLa86: 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
• Ni84: Alexandru Nicolau, Percolation Scheduling: A Parallel Compilation Technique, Cornell University, Ithaca, NY, 1985
• RaGl82: B. Ramakrishna Rau , Christopher D. Glaeser , Raymond L. Picard, Efficient code generation for horizontal architectures: Compiler techniques and architectural support, Proceedings of the 9th annual symposium on Computer Architecture, p.131-139, April 26-29, 1982, Austin, Texas, United States