Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-396-92

Authors:

Date:

September 1992

Pages:

30

Download Formats:

Loop scheduling is an important problem in parallel processing.

Retiming technique reorganizes an iteration by introducing a prologue

section. Unfolding technique schedules several iterations together.

We invent a new technique by combining these two to obtain a static

schedule with a reduced average computation time per iteration. Many

fundamental properties of loop scheduling are derived through this

combination. We first prove that the order of retiming and unfolding

is irrelevant for scheduling a data-flow graph (DFG). >From this nice

property, we present a polynomial-time algorithm on the original DFG,

before unfolding, to find the minimum-rate static schedule for a given

unfolding factor. For the case of a unit-time DFG, the minimum

rate-optimal unfolding factor is derived, and efficient checking and

retiming algorithms are presented. The problem of software pipelining

is modeled as a unit-time DFG, and an efficient algorithm for finding

the rate-optimal schedule is presented.