Title :
Data-Dependency Graph Transformations for Superblock Scheduling
Author :
Heffernan, Mark ; Wilken, Kent ; Shobaki, Ghassan
Author_Institution :
ECE Dept., California Univ., Davis, CA
Abstract :
The superblock is a scheduling region which exposes instruction level parallelism beyond the basic block through speculative execution of instructions. In general, scheduling superblocks is an NP-hard optimization and prior work includes both heuristic (polynomial-time) and optimal (enumerative) scheduling techniques. This paper presents a set of transformations to the data-dependency graph which significantly improves the results of heuristic and enumerative superblock scheduling. The graph transformations prune redundant and inferior schedules from the problem solution space. Heuristically scheduling the transformed data-dependency graphs yields significant reduction in expected execution time for hard superblocks. Also, enumeratively scheduling the transformed graphs is faster, and an optimal schedule is found for more problem instances within a bounded time. The transformations are applied to superblocks generated with the GNU compiler collection (GCC) using the SPEC CPU2000 benchmarks targeted to various processor models. The experimental results confirm that the transformations significantly improve the results for heuristic and enumerative superblock scheduling
Keywords :
computational complexity; optimising compilers; parallel programming; processor scheduling; GNU compiler collection; NP-hard optimization; data-dependency graph transformation; instruction level parallelism; speculative execution; superblock scheduling; Clocks; Microarchitecture; Optimal scheduling; Optimizing compilers; Pipelines; Polynomials; Processor scheduling; Program processors; Retirement; Tail;
Conference_Titel :
Microarchitecture, 2006. MICRO-39. 39th Annual IEEE/ACM International Symposium on
Conference_Location :
Orlando, FL
Print_ISBN :
0-7695-2732-9
DOI :
10.1109/MICRO.2006.16