Preallocation instruction scheduling with register pressure minimization using a combinatorial optimization approach
Preallocation instruction scheduling with register pressure minimization using a combinatorial optimization approach
复制标题
使用组合优化方法实现寄存器压力最小化的预分配指令调度
DOI：
10.1145/2512432
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Najm Eldeen Abu Rmaileh
中科院分区：
文献类型：
--
作者：
Ghassan Shobaki;Maxim Shawabkeh;Najm Eldeen Abu Rmaileh
在预分配指令调度中，如何平衡指令级并行性和寄存器压力是代码生成和优化中的一个重要问题。这个问题是NP完全问题。已经提出了许多启发式技术来解决这个问题。然而，由于最大化ILP和最小化寄存器压力的内在冲突的要求，启发式技术可能会产生不良的调度在许多情况下。如果这种情况发生在热代码中，可能会导致严重的性能下降。也提出了一些组合优化方法，但没有一个被证明可以在合理的时间内解决大型现实世界的实例。本文介绍了第一个组合算法，它足够有效，可以在每个实例几秒钟内最佳地解决这个问题的大型实例（具有数百条指令的基本块）。该算法使用分支定界枚举与一些强大的修剪技术，有效地搜索解决方案空间。搜索是基于成本函数，包括时间表长度和寄存器压力。所提出的调度算法的实现已被集成到LLVM调度器，并使用SPEC CPU 2006进行评估。在x86-64上，每条指令的时间限制为10 ms，它最佳地调度了FP 2006中79%的热基本块。另外19%的块不是最佳调度的，但相对于LLVM的启发式算法，成本有所改善。这将一些基准测试的执行时间提高了21%，整个基准测试套件的几何平均提高了2.4%。通过使用精确的延迟信息，几何平均改善增加到2.8%。
Balancing Instruction-Level Parallelism (ILP) and register pressure during preallocation instruction scheduling is a fundamentally important problem in code generation and optimization. The problem is known to be NP-complete. Many heuristic techniques have been proposed to solve this problem. However, due to the inherently conflicting requirements of maximizing ILP and minimizing register pressure, heuristic techniques may produce poor schedules in many cases. If such cases occur in hot code, significant performance degradation may result. A few combinatorial optimization approaches have also been proposed, but none of them has been shown to solve large real-world instances within reasonable time. This article presents the first combinatorial algorithm that is efficient enough to optimally solve large instances of this problem (basic blocks with hundreds of instructions) within a few seconds per instance. The proposed algorithm uses branch-and-bound enumeration with a number of powerful pruning techniques to efficiently search the solution space. The search is based on a cost function that incorporates schedule length and register pressure. An implementation of the proposed scheduling algorithm has been integrated into the LLVM Compiler and evaluated using SPEC CPU 2006. On x86-64, with a time limit of 10ms per instruction, it optimally schedules 79% of the hot basic blocks in FP2006. Another 19% of the blocks are not optimally scheduled but are improved in cost relative to LLVM's heuristic. This improves the execution time of some benchmarks by up to 21%, with a geometric-mean improvement of 2.4% across the entire benchmark suite. With the use of precise latency information, the geometric-mean improvement is increased to 2.8%.