Instructions Scheduling for Highly Super-scalar Processors

Super-scalar processors can execute multiple instructions out-of-order per cycle and speculatively execute instructions through branches. Such processors invalidate many of the assumptions of traditional instruction scheduling. This article analyzes the impact of super-scalar processor architecture upon instruction scheduling. The compile-time schedule is shown to significantly impact performance, despite out-of-order execution. The problem of determining an optimal schedule at compile-time is shown to be NP-complete. A variety of heuristics for instructions scheduling are applied to benchmarks, and it is shown that traditional depth-first instruction scheduling performs badly compared to a variety of breadth-first instruction scheduling heuristics