(PDF) Tyrel Russell, Abid M. Malik, Michael Chase, and Peter van Beek. Learning heuristics for the superblock instruction scheduling problem. IEEE Transactions on Knowledge and Data Engineering, 21(10):1489-1502, 2009.


Modern processors have multiple pipelined functional units and can issue more than one instruction per clock cycle. This places a burden on the compiler to schedule the instructions to take maximum advantage of the underlying hardware. Superblocks---a straight-line sequence of code with a single entry point and multiple possible exit points---are a commonly used scheduling region within compilers. Superblock scheduling is NP-complete, and is done sub-optimally in production compilers using a greedy algorithm coupled with a heuristic. The heuristic is usually hand-crafted, a potentially time-consuming process. In this paper, we show that supervised machine learning techniques can be used to semi-automate the construction of heuristics for superblock scheduling. In our approach, labeled training data was produced using an optimal superblock scheduler. A decision tree learning algorithm was then used to induce a heuristic from the training data. The automatically constructed decision tree heuristic was compared against the best previously proposed, hand-crafted heuristics for superblock scheduling on the SPEC 2000 and MediaBench benchmark suites. On these benchmark suites, the decision tree heuristic reduced the number of superblocks that were not optimally scheduled by up to 38\%, and led to improved performance on some architectural models and competitive performance on others.

Return to Publications