Register-Pressure-Aware Instruction Scheduling Using Ant Colony Optimization
Register-Pressure-Aware Instruction Scheduling Using Ant Colony Optimization
复制标题
DOI：
10.1145/3505558
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Ghassan Shobaki;V. S. Gordon;P. Mchugh;Theodore Dubois;Austin Kerbow
中科院分区：
文献类型：
--
作者：
Ghassan Shobaki;V. S. Gordon;P. Mchugh;Theodore Dubois;Austin Kerbow
本文介绍了一种使用蚂蚁菌落优化（ACO）的新方法来进行寄存器压力感知指令计划。 ACO是一种受自然风格的优化技术，研究人员已成功地应用于NP-HARD测序问题，例如旅行推销员问题（TSP）及其导数。在这项工作中，我们描述了一种ACO算法，用于解决平衡指令级并行性（ILP）和寄存器压力（RP）的长期编译器优化问题（RP）。研究了三种不同的成本功能，以估算指令计划期间的RP。所提出的ACO算法在LLVM开源编译器中实现，并且其性能在具有三种不同的指令架构的三台不同机器上进行了实验评估：Intel X86，ARM和AMD GPU。将所提出的ACO算法与先前工作中提出的精确分支结合（B＆B）算法进行比较。在X86和ARM上，对两种算法进行了相对于LLVM的通用调度程序的评估，而在AMD GPU上，对AMD的生产调度程序进行了评估。实验结果表明，使用Specrate 2017浮点，该算法分别相对于LLVM调度程序，该算法分别在X86和ARM上分别在X86和ARM上的执行速度分别提高了1.13％和1.25％。在AMD GPU上使用plaidml，相对于AMD调度程序，它的执行速度的几何表现均值提高了7.14％。所提出的ACO算法给出的执行时间结果与B＆B算法大致相同，而每种算法在大量的硬计划区域上都优于另一个算法。在许多大型实例中，ACO比B＆B给出了更好的结果。 ACO和B＆B均优于CPU上的LLVM算法和GPU上的AMD算法。
This paper describes a new approach to register-pressure-aware instruction scheduling, using Ant Colony Optimization (ACO). ACO is a nature-inspired optimization technique that researchers have successfully applied to NP-hard sequencing problems like the Traveling Salesman Problem (TSP) and its derivatives. In this work, we describe an ACO algorithm for solving the long-standing compiler optimization problem of balancing Instruction-Level Parallelism (ILP) and Register Pressure (RP) in pre-allocation instruction scheduling. Three different cost functions are studied for estimating RP during instruction scheduling. The proposed ACO algorithm is implemented in the LLVM open-source compiler, and its performance is evaluated experimentally on three different machines with three different instruction-set architectures: Intel x86, ARM, and AMD GPU. The proposed ACO algorithm is compared to an exact Branch-and-Bound (B&B) algorithm proposed in previous work. On x86 and ARM, both algorithms are evaluated relative to LLVM's generic scheduler, while on the AMD GPU, the algorithms are evaluated relative to AMD's production scheduler. The experimental results show that using SPECrate 2017 Floating Point, the proposed algorithm gives geometric-mean improvements of 1.13% and 1.25% in execution speed on x86 and ARM, respectively, relative to the LLVM scheduler. Using PlaidML on an AMD GPU, it gives a geometric-mean improvement of 7.14% in execution speed relative to the AMD scheduler. The proposed ACO algorithm gives approximately the same execution-time results as the B&B algorithm, with each algorithm outperforming the other on a substantial number of hard scheduling regions. ACO gives better results than B&B on many large instances that B&B times out on. Both ACO and B&B outperform the LLVM algorithm on the CPU and the AMD algorithm on the GPU.