Advanced software pipelining and the program dependence graph

Architectures such as horizontal microengines, multiple reduced instruction set computer (RISC) architectures, very long instruction word (VLIW), and long instruction word (LIW) machines benefit from the utilization of low-level parallelism. The authors propose a novel technique, advanced software pipelining, which solves known problems of other pipelining techniques. Implementation on the program dependence graph (PDG) benefits from the data dependence information and the control structure of the program in a single representation. Software pipelines are constructed on the PDG without imposing a fixed schedule; instead the proposed method groups concurrent operations in anticipation of the needs of the final schedule