Scheduling Data-Flow Graphs via Retiming and Unfolding
Report ID: TR-396-92Author: Chao, Liang-Fang / Sha, Edwin Hsing-Mean
Date: 1992-10-00
Pages: 30
Download Formats: |Postscript|
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.