Scheduling Data-Flow Graphs via Retiming and Unfolding

Abstract:

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.