Reservation table scheduling: branch-and-bound based optimization vs. integer linear programming techniques

¹ Amar Telidji University, BP. 37G, 03000 Laghouat, Algeria; hadda_cherroun@mail.lagh-univ.dz
² LIP, ENS-Lyon (INRIA, CNRS, UCBL), 46 Allée d'Italie, 69007 Lyon, France; alain.darte@ens-lyon.fr

Received: 7 November 2006
Accepted: 15 May 2007

Abstract

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.