Exact scheduling strategies based on bipartite graph matching
Adwin H. Timmer, J.A.G. Jess · 1995
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. 1. Introduction In high--level synthesis (HLS), the data path of a clocked VLSI circuit consisting of arithmetic modules (functional units), registers and interconnection units is synthesized from an algorithmic description represented by a data flow graph (DFG) [McFa90]. One of the central tasks in HLS is sch...