An Exact Resource Constrained-Scheduler using Graph Coloring technique

Scheduling is an important technique in high-level synthesis to match application computations and hardware resources. Scheduling a whole program is not possible as too many constraints and objectives interact. We decompose high-level scheduling in three steps. Step 1: Coarse-grain scheduling tries to exploit parallelism and locality of the whole program (in particular in loops, possibly imperfectly nested) with a rough view of the target architecture. This produces a sequence of logical steps, each of which contains a pool of macro-tasks (with no loops). Step 2: Fine-grain scheduling refines each logical step by scheduling all its macro-tasks. Between both steps a resource assignation is done by mapping each macro-task independently. We uniformly expressed the data dependences and resource constraints. As most scheduling problems, scheduling tasks under resources constraints to minimize the total duration is NP-complete. Our goal here is to design strategy for reaching optimal solutions in reasonable time. Our algorithmic contribution is an exact branch-and-bound algorithm, where each evaluation is accelerated by both maximal and greedy clique computation. The effectiveness and efficiency of the approach are good, which is illustrated by means of some practical benchmarks.