Decomposed Software Pipelining: A New Approach to Exploit Instruction Level Parallelism for Loop Programs

Abstract

This paper presents a new view on software pipelining, in which we consider software pipelining as an instruction level transformation from a vector of one-dimension to a matrix of two-dimensions. Thus, the software pipelining problem can be naturally decomposed into two subproblems, one is to determine the row-numbers of operations in the matrix and another is to determine the column-numbers. Using this view-point as a basis, we develop a new loop scheduling approach, called decomposed software pipelining. Keywords: Loop Scheduling; Instruction Level Parallelism; Software Pipelining; Loop-carried Dependence; Problem Decomposition 1 Introduction Since loop execution dominates total execution time of almost all practical programs, the exploitation of instruction level parallelism for loops is a major challenge in the design of optimizing compilers for high-performance computers such as VLIW, superscalar and pipelined processors [Alm89]. Software pipelining is an effective instruction ...