Skip to main content
Popular Press
Inducing Heuristics To Decide Whether To Schedule
Proceedings of the 2004 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2004) (2004)
  • Eliot B. Moss
Abstract

Instruction scheduling is a compiler optimization that can improve program speed, sometimes by 10% or more—but it can also be expensive. Furthermore, time spent optimizing is more important in a Java just-in-time (JIT) compiler than in a traditional one because a JIT compiles code at run time, adding to the running time of the program. We found that, on any given block of code, instruction scheduling often does not produce significant benefit and sometimes degrades speed. Thus, we hoped that we could focus scheduling effort on those blocks that benefit from it. Using supervised learning we induced heuristics to predict which blocks benefit from scheduling. The induced function chooses, for each block, between list scheduling and not scheduling the block at all. Using the induced function we obtained over 90% of the improvement of scheduling every block but with less than 25% of the scheduling effort. When used in combination with profile-based adaptive optimization, the induced function remains effective but gives a smaller reduction in scheduling effort. Deciding when to optimize, and which optimization(s) to apply, is an important open problem area in compiler research. We show that supervised learning solves one of these problems well.

Keywords
  • Compiler optimization,
  • Machine learning,
  • Supervised learning,
  • Instruction scheduling,
  • Java,
  • Jikes RVM
Disciplines
Publication Date
June, 2004
Citation Information
Eliot B. Moss. "Inducing Heuristics To Decide Whether To Schedule" Proceedings of the 2004 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2004) (2004)
Available at: http://works.bepress.com/eliot_moss/29/