Data-Flow Transformations for Critical Path Time Reduction in High-Level DSP Synthesis

Iterative, deterministic, digital signal processing algorithms can be represented by synchronous data-flow graphs. Data-flow graphs are used for scheduling and resource allocation during high-level VLSI synthesis. Every data-flow graph has an associated critical path time which limits the achievable iteration period in critical-path-based scheduling techniques. Unfolding, retiming, and pipelining transformations unravel hidden concurrency within data-flow graphs to reduce their critical path times. The objective of this paper is to determine the minimum unfolding factor necessary to reduce the critical path time of the data-Row graph to less than or equal to the requirediteration period of the associated algorithm. Minimizingthe unfolding factor is important because the time complexity for scheduling and allocation increases linearly with the unfolding factor. We present a new iterative unfolding algorithm which calculates the minimum unfolding factor necessaryto achieve a given sample rate. We can further reduce the unfolding factor necessary to achieve a given sample rate. We can further reduce the unfolding factor in many cases with the use of retiming. Our algorithm can be utilized to preprocess a data-flow graph prior to resource scheduling and allocation.