An optimal software-pipelining method for instruction-level parallel processors based on scaled retiming

Software pipelining is an instruction-level loop scheduling method for achieving high performance fine-grain parallelism on VLIW (very long instruction word) processors. This paper presents a novel software pipelining method for non-pipelining parallel processors based on integer scaling and retiming transformations. This approach generalises and simplifies the analogous extended retiming model of T.W. O'Neil et al. (see Proc. ISCA 12th Int. Conf. Parallel & Distributed Computing Syst., p.292-7, 1999; Proc. of ICASSP'99 Conf., vol.4 p.2001-4, 1999). Matrix techniques are used in order to simplify the corresponding graph transformations. Some general properties taken from algebraic graph theory are applied in order to obtain general scheduling techniques: node and cycle methods. The two-phase scheduling method considered is first defined by means of two standard linear programming problems. We transform the corresponding problems into some variants of the maximum cost-to-time ratio problem and shortest path problem, in order to obtain efficient polynomial time algorithms. An example of software pipelining optimization of a digital correlator is also given.