Computing lower bounds on functional units before scheduling
- 1 June 1996
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Very Large Scale Integration (VLSI) Systems
- Vol. 4 (2), 273-279
- https://doi.org/10.1109/92.502199
Abstract
The authors present a new polynomial-time algorithm for computing lower bounds on the number of functional units (FUs) of each type required to schedule a data flow graph in a specified number of control steps. A formal approach is presented that is guaranteed to find the tightest possible bounds that can be found by relaxing either the precedence constraints or integrality constraints on the scheduling problem. This tight, yet fairly efficient, bounding method can be used to estimate FU area, to generate resource constraints for reducing the search space, or in conjunction with exact techniques for efficient optimal design space exploration.Keywords
This publication has 13 references indexed in Scilit:
- An exact methodology for scheduling in a 3D design spacePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Estimating implementation bounds for real time DSP application specific circuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1994
- Estimating architectural resources and performance for high-level synthesis applicationsIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1993
- SALSA: a new approach to scheduling with timing constraintsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1993
- Predicting system-level area and delay for pipelined and nonpipelined designsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992
- A formal approach to the scheduling problem in high level synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- Algorithmic and Register-Transfer Level Synthesis: The System Architect’s WorkbenchPublished by Springer Science and Business Media LLC ,1990
- Integer and Combinatorial OptimizationPublished by Wiley ,1988
- NP-complete scheduling problemsJournal of Computer and System Sciences, 1975
- Bounds on the Number of Processors and Time for Multiprocessor Optimal SchedulesIEEE Transactions on Computers, 1973