The Character of the Instruction Scheduling Problem

Here I present some measurements that serve to characterize the nature of the problem of basic block instruction scheduling, as it is encountered in practice. Finding optimal schedules is known to be NP-hard [Hennessy and Gross, 1983]; but it is worth knowing how hard the task is in an average sense, where the average is with respect to an input space of problems (basic blocks) found in the everyday practice of compiling. The space I consider is the set of all basic blocks in all of SPEC95 benchmarks, produced by compiling on the Digital Alpha architecture [Bhandarkar, 1996]. It is also worth knowing how close a heuristic scheduler comes to the optimum, especially when one wants to design a new heuristic scheduler; I present one such evaluation for a scheduler made available by Digital and show that it is almost optimal (with respect to its own cost measure).

4

Report, Department of Computer Science, University of Massachusetts