Learning heuristics for basic block instruction scheduling |
| |
Authors: | Abid M Malik Tyrel Russell Michael Chase Peter van Beek |
| |
Institution: | (1) School of Computer Science,, University of Waterloo, Waterloo, Canada |
| |
Abstract: | Instruction scheduling is an important step for improving the performance of object code produced by a compiler. A fundamental
problem that arises 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. |
| |
Keywords: | Instruction scheduling Machine learning List scheduling heuristics |
本文献已被 SpringerLink 等数据库收录! |
|