An Introduction to Simplex Scheduling
Benoît Dupont de Dinechin · 1994
Simplex scheduling refers to an approach where the central scheduling problems originating from instruction scheduling and modulo scheduling are solved on a simplex tableau (a matrix) instead of a scheduling graph. By definition, a central scheduling problem is a subproblem of the original scheduling problem, where all the resource constraints have been removed, and where some extra precedence constraints have been included to materialize the fact that some of the tasks have already been scheduled. By using a parametric version of the simplex algorithm, we optimally solve central scheduling problems involving symbolic valuations of the scheduling graph edges, such as linear expressions of a yet unknown software pipeline initiation interval. In addition, by using a lexicographic cost function and by introducing extra equations in the simplex tableau, we also compute optimum solutions to the central scheduling problems in polynomial time, while simultaneously minimizing the cumulative register lifetimes.