Exact scheduling strategies based on bipartite graph matching
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Scheduling is one of the central tasks in high-level synthesis. In recent publications a bipartite graph matching formulation has been introduced to prune the search space of schedulers. In this paper, we improve that formulation and introduce two novel aspects related to the way the search space is traversed, namely problem formulation and bottleneck identification. The approach results in a very run time efficient branch-and-bound scheduler searching for a correct ordering of operations from which a schedule can be derived in linear time. The results show that the use of these bipartite graph matching strategies leads to the most run time efficient exact scheduler to date.<>Keywords
This publication has 10 references indexed in Scilit:
- Estimating lower-bound performance of schedules using a relaxation techniquePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Module selection and scheduling using unrestricted librariesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- NEAT: an object oriented high-level synthesis interfacePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Efficient code generation for in-house DSP-coresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Predicting system-level area and delay for pipelined and nonpipelined designsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992
- Optimal VLSI Architectural SynthesisPublished by Springer Nature ,1992
- A formal approach to the scheduling problem in high level synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- The high-level synthesis of digital systemsProceedings of the IEEE, 1990
- Force-directed scheduling in automatic data path synthesisPublished by Association for Computing Machinery (ACM) ,1987
- Two Algorithms for Bipartite GraphsJournal of the Society for Industrial and Applied Mathematics, 1963