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

Lori E. Lucke, Keshab K Parhi

Research output: Contribution to journalArticle

21 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1063-1068
Number of pages6
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume12
Issue number7
DOIs
StatePublished - Jul 1993

Fingerprint Dive into the research topics of 'Data-Flow Transformations for Critical Path Time Reduction in High-Level DSP Synthesis'. Together they form a unique fingerprint.

  • Cite this