Basic-block Instruction Scheduling Using Reinforcement Learning and Rollouts

The execution order of a block of computer instructions on a pipelined machine can make a difference in its running time by a factor of two or more. In order to achieve the best possible speed, compilers use heuristic schedulers appropriate to each specific architecture implementation. However, these heuristic schedulers are time-consuming and expensive to build. We present empirical results using both rollouts and reinforcement learning to construct heuristics for scheduling basic blocks. In simulation, both the rollout scheduler and the reinforcement learning scheduler outperformed a commercial scheduler on several applications. 1 Motivation Although high-level code is generally written as if it were going to be executed sequentially, most modern computers exhibit parallelism in instruction execution using techniques such as the simultaneous issue of multiple instructions. In order to take the best advantage of multiple pipelines, when a compiler turns the high-level code into mac..