High-level DSP synthesis using concurrent transformations, scheduling, and allocation
- 1 March 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 14 (3), 274-295
- https://doi.org/10.1109/43.365120
Abstract
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 graphKeywords
This publication has 44 references indexed in Scilit:
- Generalized ILP scheduling and allocation for high-level DSP synthesisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Synthesizing embedded speed-optimized architecturesIEEE Journal of Solid-State Circuits, 1993
- Global optimization approach for architectural synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- PLS: a scheduler for pipeline synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- Optimal automatic periodic multiprocessor scheduler for fully specified flow graphsIEEE Transactions on Signal Processing, 1993
- Range-chart-guided iterative data-flow graph schedulingIEEE Transactions on Circuits and Systems I: Regular Papers, 1992
- Optimal synthesis of high-performance architecturesIEEE Journal of Solid-State Circuits, 1992
- A systematic approach for design of digit-serial signal processing architecturesIEEE Transactions on Circuits and Systems, 1991
- Scheduling for functional pipelining and loop windingPublished by Association for Computing Machinery (ACM) ,1991
- Algorithm transformation techniques for concurrent processorsProceedings of the IEEE, 1989