Title :
Rate-optimal static scheduling for DSP data-flow programs
Author :
Chao, Liang-Fang ; Sha, Edwin Hsing-Mean
Author_Institution :
Dept. of Comput. Sci., Princeton Univ., NJ, USA
Abstract :
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
Keywords :
VLSI; circuit CAD; digital signal processing chips; logic CAD; parallel programming; pipeline processing; program compilers; scheduling; DSP data-flow programs; VLSI design; minimum unfolding factor; nonpipelined hardware design; parallel compilers; pipelined hardware design; rate-optimal static schedule; retiming; Computer architecture; Delay; Digital signal processing; Hardware; Parallel machines; Parallel processing; Process design; Processor scheduling; Scheduling algorithm; Very large scale integration;
Conference_Titel :
VLSI, 1993. 'Design Automation of High Performance VLSI Systems', Proceedings., Third Great Lakes Symposium on
Conference_Location :
Kalamazoo, MI
Print_ISBN :
0-8186-3430-8
DOI :
10.1109/GLSV.1993.224475