Rate-optimal static scheduling for DSP data-flow programs

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 ρ 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(|V||E|log|V|), a retiming to achieve the rate-optimal schedule in time O(|V||E|) 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