17-07-2012, 12:22 PM
Optimal Superblock Scheduling Using Enumeration
Optimal Superblock .ppt (Size: 198 KB / Downloads: 20)
Region Formation
Scheduler’s scope is a sub-graph of the program’s control flow graph (CFG)
Local scheduling: single basic block
Global scheduling: multiple basic blocks:
Trace
Superblock and hyperblock
Treegion
General acyclic: e.g. Wavefront (2000)
Schedule Construction
NP-Hard problem for realistic machines
Heuristic Solutions: Virtually all production compilers and most research
Optimal Approaches: Recent research
Local: Integer Programming and enumeration
Global: Integer Programming
The Superblock
Single-entry multiple-exit sequence of basic blocks
Data and control dependencies and allowed code motions are represented by a Directed Acyclic Graph (DAG)
Optimal Scheduling
Can make improvement over heuristics
Accurate heuristic methods are already complex
In some applications, longer compile times can be tolerated
Reference for evaluating accuracy of heuristics and studying ILP limits
Enumeration
List scheduling with backtracking
Explores one target length at a time
A subset of instructions can be fixed
Branch-and-Bound approach with four feasibility tests (pruning techniques)
Node superiority
LB tightening
History-based domination
Relaxed Scheduling