loading...
Optimal versus Heuristic Global Code Scheduling
Chicago, Illinois, USA December 01-December 05
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/MICRO.2007.1040th Annual IEEE/ACM International Sy ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
We present a global instruction scheduler based on inte- ger linear programming (ILP) that was implemented exper- imentally in the Intel Itanium? product compiler. It features virtually the full scale of known EPIC scheduling optimiza- tions, more than its heuristic counterpart in the compiler, GCS, and in contrast to the latter it computes optimal so- lutions in the form of schedules with minimal length. Due to our highly efficient ILP model it can solve problem in- stances with 500-750 instructions, and in combination with region scheduling we are able to schedule routines of arbi- trary size. In experiments on five SPEC? CPU2006 integer bench- marks, ILP-scheduled code exhibits a 32% schedule length advantage and a 10% runtime speedup over GCS-scheduled code, at the highest compiler optimization levels typically used for SPEC submissions. We further study the impact of different code motion classes, region sizes, and target microarchitectures, gaining insights into the nature of the global instruction scheduling problem.
Citation:
Sebastian Winkel, "Optimal versus Heuristic Global Code Scheduling," micro, pp.43-55, 40th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO 2007), 2007
Usage of this product signifies your acceptance of the Terms of Use.