Unfolding and retiming data-flow DSP programs for RISC multiprocessor scheduling
Liang-Fang Chao, Edwin H.‐M. Sha · 1992
Retiming and unfolding are two useful techniques which have been effectively applied in many fields. These two techniques are combined to solve the problem of rate-optimal scheduling for unit-time data flow graphs (DFGs). A rate-optimal retimeable graph is a DFG such that after a legal retiming a rate-optimal schedule can be obtained. For the case of unit-time DFG, which is applicable to RISC multiprocessors, the best known upper-bound for an unfolding factor which produces a rate-optimal retimeable DFG is improved, and it is shown that the result is the minimum possible unfolding factor for rate-optimal schedules. Moreover, for any unfolding factor, the corresponding minimum rate is given by a simple criterion. Since it is proved that the order of retiming and unfolding is irrelevant, efficient polynomial-time retiming algorithms are obtained.>