Parallelizing Instruction Scheduling for the GPU on the GPU

In this article, we describe how to use the GPU to parallelize a precise search-based algorithm for solving the instruction scheduling problem for a GPU target. Instruction scheduling for the GPU is a multi-objective optimization problem in which the challenge lies in balancing the conflicting objectives of minimizing register pressure (RP) and maximizing instruction-level parallelism (ILP). We solve this problem using a precise algorithm that is based on Ant Colony Optimization (ACO), which is a nature-inspired intelligent-search technique that has been used to compute precise solutions to NP-hard problems in operations research (OR). Such intelligent-search techniques were not used in the past to solve NP-hard compiler optimization problems, because they require substantially more computation than the heuristic techniques used in production compilers. In this article, we show that parallelizing such a technique on the GPU does not only make it reasonably practical for compilation, but it also makes it possible to simultaneously explore different ways of balancing RP and ILP. Different groups of GPU threads search for solutions that balance RP and ILP differently, and then the most balanced solution is selected based on a certain cost function. We also describe a number of techniques that we developed to efficiently parallelize an ACO algorithm for solving this multi-objective optimization problem on the GPU. The experimental evaluation shows that parallel ACO-based scheduling on the GPU runs up to 21 times faster than sequential ACO-based scheduling on the CPU, and this leads to reducing the total compile time of the rocPRIM benchmarks by 42%. ACO-based scheduling improves the execution speed of the compiled benchmarks by up to 72% relative to AMD’s production scheduler. To the best of our knowledge, our work is the first successful attempt to parallelize a compiler optimization algorithm on the GPU.