Execution Interval Analysis under Resource Constraints

Execution intervals are commonly used in high--level synthesis systems to identify the relation between operations and the cycle steps in which they possibly can be scheduled. These intervals are normally based on the ASAP (as soon as possible) and ALAP (as late as possible) values of operations under the assumption of unlimited resources. In this paper a novel and much more accurate execution interval analysis is presented for designs on which resource constraints are imposed. The analysis prunes the search space of schedulers without limiting the solution space and therefore enhances the quality of schedulers. Themethod is based on a bipartite graph matching formulation and runs in polynomial time. Well--known benchmarks show the positive effects of the approach on scheduling results and run times. 1. Introduction In high--level synthesis a data path consisting of modules, registers, and interconnection units is synthesized from a description represented by a data flow graph (DFG) ..