Profile-Driven Instruction Level Parallel Scheduling
Chandra Chekuri, Rajeev Motwani, Richard Johnson, B. Ramakrishna Rau, BALAS K. NATARAJAN · 1996
VLIW scheduling, profile driven scheduling, superblocks, hyperblocks Code scheduling to exploit instruction level parallelism (lLP) is a central problem in compiler optimization research, in light of the increased use of long-instruction-word computers. Unfortunately, optimum scheduling is computationally intractable, and one must resort to carefully crafted heuristics in practice. If the scope of application of a scheduling heuristic is limited to basic blocks, considerable performance loss may be incurred at block boundaries. To overcome this obstacle, basic blocks are coalesced across branches to form either superblocks or hyperblocks, with the branches labeled with branch probabilities obtained via profiling. Then, the goal of the scheduling heuristic is to minimize the expected completion time of the superblock or the hyperblock.