Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

SCAN : a Heuristic for Near-Optimal Software Pipelining

SpeakerFlorent Blachot

Co-authorGuillaume Huard

Software pipelining is a well known compiler technique to improve loops performance. In embedded context, where applications are compiled once during the design of the system, it is interesting to spend more time performing deep optimizations as the gain is amplified by the mass production.

Usually software pipelining is computed using iterative heuristics such as modulo scheduling. While optimal solutions have been formulated as integer linear program, their resolution becomes intractable as the loops size grows. In this article, we investigate a new approach, the SCAN heuristic, which uses a simplified form of the optimal formulation to compute near-optimal software pipelines.

We conducted experiments on multimedia applications benchmarks for the ST200 VLIW processor which show that, for difficult cases, our approach is almost always able to compute an optimal solution while classical optimal formulations are already intractable. This results in up to 33.3% performance gain over modulo scheduling.