Learning Heuristics for the Superblock Instruction Scheduling Problem
Authors:
- 19 January 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 21 (10) , 1489-1502
Abstract
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 suboptimally in production compilers using a greedy algorithm coupled with a heuristic. The heuristic is usually handcrafted, a potentially time-consuming process. In this paper, we show that supervised machine learning techniques can be used to semiautomate the construction of heuristics for superblock scheduling. In our approach, labeled training data were 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, handcrafted 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 percent, and led to improved performance on some architectural models and competitive performance on others.Keywords
This publication has 20 references indexed in Scilit:
- Learning heuristics for basic block instruction schedulingJournal of Heuristics, 2007
- Discovering Dispatching Rules Using Data MiningJournal of Scheduling, 2005
- Effective Compiler Support For Predicated Execution Using The Hyperblock2005
- Profile-driven instruction level parallel scheduling with application to super blocks2002
- Building a Basic Block Instruction Scheduler with Reinforcement Learning and RolloutsMachine Learning, 2002
- 10.1162/153244303322753616Applied Physics Letters, 2000
- Instruction scheduling in the TOBEY compilerIBM Journal of Research and Development, 1994
- The superblock: An effective technique for VLIW and superscalar compilationThe Journal of Supercomputing, 1993
- Efficient DAG construction and heuristic calculation for instruction scheduling1991
- Postpass Code Optimization of Pipeline ConstraintsACM Transactions on Programming Languages and Systems, 1983