Abstract
In this Master’s project, we develop an enhanced Ant Colony Optimization (ACO) algorithm for register-pressure-aware instruction scheduling in a compiler. The challenge in this scheduling problem lies in balancing the exploitation of Instruction-Level Parallelism (ILP) and the minimization of Register Pressure (RP). Most production compilers use greedy heuristics to perform instruction scheduling. However, previous work has shown that such algorithms may produce sub-optimal solutions that significantly degrade performance. The algorithmic enhancements explored in this project are intended to either generate more efficient code (by reducing spilling to main memory) or reduce overall compile time relative to baseline ACO. There are three code-efficiency enhancements. The first is using a local search to find better schedules. The second enhancement updates the pheromone table to reflect the current best solution at any given point. The third enhancement initializes the pheromone table using a greedy heuristic. The compile-time reduction enhancement is a change in the baseline ACO algorithm’s termination condition from zero change in the cost function to a small change within a certain minimum delta. The enhanced ACO algorithm is implemented in the open-source LLVM compiler. Previous work has shown that reducing the Sum of Live Interval Lengths (SLIL) in the schedule produces better results than reducing the Peak Excess Register Pressure (PERP). Therefore, the experimentation in this project uses the SLIL as a scheduling cost function. SPEC CPU2006 benchmarks are used for the experimental evaluation of the enhanced ACO algorithm. The experimental results show that when the parameters are finely tuned, a local search optimization does reduce spills, but the reduction is less than 1%. The minimum-delta enhancement results in reducing compile time by 35% at the reasonable price of increasing both the schedule cost and the number of spills by approximately 1%. The initial heuristic enhancement results show an improvement of 2.9% in the schedule cost; however, the spill count reduction was limited to 0.28%. The enhancement which changes the pheromone table to always represent the best solution produced a schedule cost improvement of 1.77%, but there was no significant spill count reduction. The Two-Way Exchange did not produce any significant reductions.