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

Author： Cherroun Hadda Darte Alain Feautrier Paul

E-ISSN： 1290-3868|41|4|427-454

ISSN： 0399-0559

Source： RAIRO - Operations Research, Vol.41, Iss.4, 2007-10, pp. : 427-454

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

The recourse to operation research solutions has strongly increasedthe performances of scheduling task in the High-Level Synthesis(called hardware compilation). Scheduling a whole program is notpossible as too many constraints and objectives interact. We decomposehigh-level scheduling in three steps. Step 1: Coarse-grain schedulingtries to exploit parallelism and locality of the whole program (inparticular in loops, possibly imperfectly nested) with a rough view ofthe target architecture. This produces a sequence of logical steps,each of which contains a pool of macro-tasks. Step 2: Micro-schedulingmaps and schedules each macro-task independently taking into accountall peculiarities of the target architecture. This produces areservation table for each macro-task. Step 3: Fine-grain schedulingrefines each logical step by scheduling all its macro-tasks. Thispaper focuses on the third step.As tasks are modeled as reservation tables, we can express resourceconstraints using dis-equations (i.e., negations of equations). Asmost scheduling problems, scheduling tasks with reservation tables tominimize the total duration is NP-complete. Our goal here is todesign different strategies and to evaluate them, on practicalexamples, to see if it is possible to find optimal solution inreasonable time. The first algorithm is based on integer linearprogramming techniques for scheduling, which we adapt to our specificproblem. Our main algorithmic contribution is an exactbranch-and-bound algorithm, where each evaluation is accelerated byvariant of Dijkstra's algorithm. A simple greedy heuristic is alsoproposed for comparisons. The evaluation and comparison are done onpieces of scientific applications from the PerfectClub and theHLSynth95 benchmarks. The results demonstrate the suitability of thesesolutions for high-level synthesis scheduling.