Title :
Data-flow transformations for critical path time reduction in high-level DSP synthesis
Author :
Lucke, Lori E. ; Parhi, Keshab K.
Author_Institution :
Dept. of Electr. Eng., Minnesota Univ., Minneapolis, MN, USA
fDate :
7/1/1993 12:00:00 AM
Abstract :
The minimum unfolding factor necessary to reduce the critical path time of the data-flow graph to less than or equal to the required iteration period of the associated algorithm is determined. Minimizing the unfolding factor is important because the time complexity for scheduling and allocation increases linearly with the unfolding factor. An iterative unfolding algorithm that calculates the minimum unfolding factor necessary to achieve a given sample rate is introduced. The unfolding factor can be further reduced to achieve a given sample rate, in many cases with the use of retiming. The algorithm can be utilized to preprocess a data-flow graph prior to resource scheduling and allocation
Keywords :
computational complexity; digital signal processing chips; iterative methods; parallel algorithms; parallel architectures; allocation; critical path time reduction; data-flow graph; high-level DSP synthesis; iteration period; iterative unfolding algorithm; minimum unfolding factor; sample rate; scheduling; time complexity; Central Processing Unit; Design automation; Digital signal processing; Integrated circuit modeling; Integrated circuit synthesis; Routing; Signal processing algorithms; Sun; Wiring; Workstations;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on