HP Labs Technical Reports



Click here for full text: PDF

Profile-Driven Instruction Level Parallel Scheduling

Chekuri, Chandra; Motwani, Rajeev; Johnson, Richard; Rau, B. Ramakrishna; Natarajan, Balas K.

HPL-96-16

Keyword(s): VLIW scheduling, profile driven scheduling, superblocks, hyperblocks


Abstract: Code scheduling to exploit instruction level parallelism (ILP) 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. In this paper, we analyze the general problem of scheduling with profile information and present some experimental results on heuristics that are suggested by are analysis. Specifically, we carry out a theoretical analysis on a simplified abstraction of the problem to obtain insight into its structure, and to develop provably good algorithms. Based on the theoretical analysis of the simplified abstraction, we develop a generic scheme for converting any list scheduling heuristic for basic blocks into a heuristic for the superblocks/hyperblocks with associated profile information. Our techniques are applicable to the general case of scheduling on pipelined heterogeneous units with unequal latencies. Experiments show that our scheme offers substantial performance improvement over critical path scheduling on a range of benchmark inputs and machine models.

Back to Index

[Research] [News] [Tech Reports] [Palo Alto] [Bristol] [Japan] [Israel] [Site Map] [Home] [Hewlett-Packard]