High-Level DSP Synthesis Using Concurrent Transformations, Scheduling, and Allocation

Ching Yi Wang, Keshab K. Parhi

Research output: Contribution to journalArticlepeer-review

61 Scopus citations


This paper addresses high-level synthesis methodologies for dedicated digital signal processing (DSP) architectures used in the iterative loop-based Minnesota Architecture Synthesis (MARS) design system. We present a novel concurrent scheduling and resource allocation algorithm which exploits inter-iteration and intra-iteration precedence constraints. The novel algorithm implicitly performs algorithmic transformations, such as pipelining and retiming, on the data-flow graphs during the scheduling process to produce solutions which are as good as those previously published and which executes in less time. MARS is capable of producing optimal and near-optimal schedules in fractions of seconds. Previous synthesis systems have focused on DSP algorithms which have single or lumped delays in the recursive loops. In contrast, MARS is capable of generating valid architectures for algorithms which have randomly distributed delays. MARS exploits these delays to produce more efficient architectures and allows our system to be more general. We are able to synthesize architectures which meet the iteration bound of any algorithm by unfolding, retiming, and pipelining the original data-flow graph.

Original languageEnglish (US)
Pages (from-to)274-295
Number of pages22
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number3
StatePublished - Mar 1995

Bibliographical note

Funding Information:
Manuscript received July 28, 1992; revised July 27, 1993 and October 18, 1994. This work was supported in part by the Advanced Research Projects Agency and the Solid State Electronics Directorate, Wright-Patterson AFB, Contract AFF33615-93-C-1309; and the Office of Naval Research, Contract N00014-91-J-1008. This paper was recommended by Associate Editor R. Camposano. The authors are with the Department of Electrical Engineering, University of Minnesota, Minneapolis, MN 55455 USA. IEEE Log Number 940861 1.


Dive into the research topics of 'High-Level DSP Synthesis Using Concurrent Transformations, Scheduling, and Allocation'. Together they form a unique fingerprint.

Cite this