Speaker: Tyrel Russell
Instruction scheduling is an important step for improving the performance of object code produced by a compiler. A fundamental problem in instruction scheduling is to find a minimum length schedule for a basic block---a straight-line sequence of code with a single entry point and a single exit point---subject to precedence, latency, and resource constraints. Solving the problem exactly is known to be difficult, and most compilers use a greedy list scheduling algorithm coupled with a heuristic. The heuristic is usually hand-crafted, a potentially time-consuming process. In contrast, we present a study on automatically learning good heuristics using techniques from machine learning. In our study, a recently proposed optimal basic block scheduler was used to generate the machine learning training data. A decision tree learning algorithm was then used to induce a simple heuristic from the training data. The automatically constructed decision tree heuristic was compared against a popular critical-path heuristic on the SPEC 2000 benchmarks. On this benchmark suite, the decision tree heuristic reduced the number of basic blocks that were not optimally scheduled by up to 55\% compared to the critical-path heuristic, and gave improved performance guarantees in terms of the worst-case factor from optimality.
To be presented at CASCON, Toronto, Ontario, October, 2005. Joint work with: Abid M. Malik, Michael Chase, and Peter van Beek
Food: Peter Van Beek