The recourse to operation research solutions has strongly increased
the performances of scheduling task in the High-Level Synthesis
(called hardware compilation). 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. Step 2: Micro-scheduling
maps and schedules each macro-task independently taking into account
all peculiarities of the target architecture. This produces a
reservation table for each macro-task. Step 3: Fine-grain scheduling
refines each logical step by scheduling all its macro-tasks. This
paper focuses on the third step.
As tasks are modeled as reservation tables, we can express resource
constraints using dis-equations (i.e., negations of equations). As
most scheduling problems, scheduling tasks with reservation tables to
minimize the total duration is NP-complete. Our goal here is to
design different strategies and to evaluate them, on practical
examples, to see if it is possible to find optimal solution in
reasonable time. The first algorithm is based on integer linear
programming techniques for scheduling, which we adapt to our specific
problem. Our main algorithmic contribution is an exact
branch-and-bound algorithm, where each evaluation is accelerated by
variant of Dijkstra's algorithm. A simple greedy heuristic is also
proposed for comparisons. The evaluation and comparison are done on
pieces of scientific applications from the PerfectClub and the
HLSynth95 benchmarks. The results demonstrate the suitability of these
solutions for high-level synthesis scheduling.