Global optimization approach for architectural synthesis
- 1 January 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 12 (9) , 1266-1278
- https://doi.org/10.1109/43.240074
Abstract
A relaxed linear programming model which simultaneously schedules and allocates functional units and registers is presented for synthesizing cost-constrained globally optimal architectures. This approach is important for industrial applications, because it provides exploration of optimal synthesized architectures and early architectural decisions have the greatest impact on the final design. An integer programming formulation of the architectural synthesis problem is transformed into the mode packing problem. Polyhedral theory is used to formulate constraints that decrease the size of the search space, thus improving solution efficiency. Execution times are an order of magnitude faster than for previous heuristic techniques. The present approach breaks new ground by (1) simultaneously scheduling and allocating in practical execution times, (2) guaranteeing globally optimal solutions for a specific objective function, and (3) providing a polynomial run-time algorithm for solving some instances of this NP-complete problemKeywords
This publication has 14 references indexed in Scilit:
- Optimal synthesis of high-performance architecturesIEEE Journal of Solid-State Circuits, 1992
- A formal approach to the scheduling problem in high level synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- Path-based scheduling for synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- Algorithms for hardware allocation in data path synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1989
- Force-directed scheduling for the behavioral synthesis of ASICsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1989
- Integer and Combinatorial OptimizationPublished by Wiley ,1988
- Automated datapath synthesis: a compilation approachMicroprocessing and Microprogramming, 1987
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984
- Solving Large-Scale Zero-One Linear Programming ProblemsOperations Research, 1983
- A Formal Method for the Specification, Analysis, and Design of Register-Transfer Level Digital LogicIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1983