Synthesis using path-based scheduling: Algorithms and exercises

Abstract

Path-based scheduling algorithms consider all possible sequences of operations (called paths) in a control-flow graph. Unlike most scheduling techniques used in high-level synthesis, they stress optimization across conditional branches. Several path-based algorithms are presented. An exact algorithm finds the minimum number of control steps required for each possible path being executed. Heuristic solutions are also implemented. Extensive application of these algorithms to the benchmarks of the High-Level Synthesis Workshop shows the practical feasibility of such methods.