Realistic scheduling: compaction for pipelined architectures

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. The authors build 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 the 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