HP Labs Technical Reports

Efficient Backtracking Instruction Schedulers

Abraham, Santosh

HPL-2000-56

Keyword(s): instruction scheduling; global scheduling; compiler optimization; EPIC; VLIW; instruction-level parallel processors

Abstract: Current schedulers for acyclic regions schedule operations in dependence order and never revisit or undo a scheduling decision on any operation. In contrast, backtracking schedulers may unschedule already scheduled operations, in order to make space for the operation currently being scheduled. Backtracking schedulers have the potential for generating better schedules, e.g. more effectively filling branch delay slots, but are more compile-time intensive and therefore, not considered practical for production use. In this report, we first describe conventional cycle and list schedulers followed by two novel backtracking schedulers. The full-backtracking OperBT scheduler enables backtracking for all operations and un-schedules already scheduled operations to make space for the current operation, if, among other situations, there is no available slot that satisfies dependence constraints. This scheduler is effective in generating high quality schedules that for instance, successfully fill branch delay slots but likely backtracks too often. The selective backtracking ListBT scheduler enables backtracking only when scheduling certain types of operations, for which backtracking is likely to be advantageous, e.g. branches. When not scheduling these operations (or operations that were displaced through backtracking), the scheduler reverts to efficient scheduling in dependence order. The ListBT scheduler backtracks less often than the OperBT scheduler. Both schedulers successfully fill a large fraction of the branch delay slots and improve performance of the scheduled code significantly.

33 Pages

Back to Index