Rate-optimal static scheduling for DSP data-flow programs
Liang-Fang Chao, Edwin H.‐M. Sha · 2002
It is shown how to find a rate-optimal static schedule with the minimum unfolding factor under two design approaches: pipelined hardware design and nonpipelined hardware design. For pipelined hardware design, the technique also can be applied to so-called software pipelining in parallel compilers. It is shown that the minimum unfolding factor to achieve a rate-optimal schedule is the denominator rho of the irreducible form of B(G). After the minimum rate-optimal unfolding factor is derived from the iteration bound B(G) in time O( mod V//E mod log mod V mod ), a retiming to achieve the rate-optimal schedule in time O( mod V//E mod ) can be obtained. The rate-optimal schedule is then computed from the retiming. The minimum rate-optimal unfolding factor for nonpipelined design is also found.>