SHF:Small:RUI: Optimizing Compiler Instruction Scheduling Using GPU-Accelerated Intelligent Search

SHF:Small:RUI：使用 GPU 加速智能搜索优化编译器指令调度

• 批准号: 1911235
• 负责人: Ghassan Shobaki
• 金额: $ 29.33万
• 依托单位: University Enterprises, Incorporated
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1911235&HistoricalAwards=false
• 关键词: SHF; Small; RUI; Optimizing; Compiler

A compiler translates a program written in a programming language into machine code. In addition to performing the translation, the compiler also performs optimizations that improve the quality of the generated code by increasing its performance and reducing its energy consumption. In this research project, the investigators will use a combination of intelligent search techniques and parallel computing to develop enhanced compiler-optimization algorithms that will improve the performance of a wide range of programs running on the Central Processing Unit (CPU) and/or the Graphics Processing Unit (GPU). The GPU's parallel computing power is widely used to accelerate the implementations of certain Artificial Intelligence (AI) algorithms. The project's novelties are using intelligent search techniques to generate more efficient code for both CPUs and GPUs, and taking advantage of modern parallel computing to maximize the speed of these intelligent search techniques. The project's impacts are developing algorithms for parallelizing intelligent search techniques and using these algorithms to optimize the performance of a wide range of applications running on the CPU and/or the GPU. More specifically, this research project addresses pre-allocation instruction scheduling, which is a long-standing and fundamentally important problem in compiler optimizations. Current production compilers solve this problem using heuristic approaches. Experimental evaluation has shown that existing heuristics may produce poor-quality code in terms of both performance and energy consumption, especially in compiling for the GPU. This project uses today's powerful parallel computing to apply two specific intelligent search techniques, namely Branch-and-Bound (B&B) and Ant Colony Optimization (ACO), to this problem. Parallel computing on the GPU is used to make these compute-intensive search techniques feasible. The proposed intelligent algorithms are also used to generate more efficient code for the GPU itself, thus allowing future GPUs to deliver higher performance for future AI programs. The project also develops parallel GPU-based versions of these algorithms to both minimize compilation time and to explore the limits of the performance gain that can be achieved using intelligent search.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

编译器将用编程语言编写的程序翻译成机器代码。除了执行翻译之外，编译器还执行优化，通过提高性能和降低能耗来提高生成代码的质量。在这个研究项目中，研究人员将结合使用智能搜索技术和并行计算来开发增强的编译器优化算法，该算法将提高在中央处理单元（CPU）和/或图形处理器上运行的各种程序的性能处理单元 (GPU)。 GPU 的并行计算能力被广泛用于加速某些人工智能 (AI) 算法的实现。该项目的新颖之处在于使用智能搜索技术为 CPU 和 GPU 生成更高效的代码，并利用现代并行计算最大限度地提高这些智能搜索技术的速度。该项目的影响是开发并行智能搜索技术的算法，并使用这些算法来优化在 CPU 和/或 GPU 上运行的各种应用程序的性能。 更具体地说，该研究项目解决了预分配指令调度问题，这是编译器优化中长期存在且极其重要的问题。当前的生产编译器使用启发式方法解决这个问题。实验评估表明，现有的启发式方法可能会在性能和能耗方面产生质量较差的代码，特别是在针对 GPU 进行编译时。该项目利用当今强大的并行计算，将两种特定的智能搜索技术，即分支定界（B&B）和蚁群优化（ACO）应用于该问题。 GPU 上的并行计算用于使这些计算密集型搜索技术变得可行。所提出的智能算法还用于为 GPU 本身生成更高效的代码，从而使未来的 GPU 能够为未来的 AI 程序提供更高的性能。该项目还开发了这些算法的基于 GPU 的并行版本，以最大限度地减少编译时间，并探索使用智能搜索可以实现的性能增益的极限。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准。

项目成果

A parallel branch-and-bound algorithm with history-based domination

一种基于历史支配的并行分支定界算法

• DOI: 10.1145/3503221.3508415
• 发表时间: 2022-03
• 期刊: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
• 作者: Gonggiatgul, Taspon;Shobaki, Ghassan;Muyan
• 通讯作者: Muyan

Optimizing occupancy and ILP on the GPU using a combinatorial approach

使用组合方法优化 GPU 上的占用率和 ILP

• DOI: 10.1145/3368826.3377918
• 发表时间: 2020-02
• 期刊: Proceedings of the International Symposium on Code Generation and Optimization
• 作者: Shobaki, Ghassan;Kerbow, Austin;Mekhanoshin, Stanislav
• 通讯作者: Mekhanoshin, Stanislav

Graph transformations for register-pressure-aware instruction scheduling

用于寄存器压力感知指令调度的图形转换

• DOI: 10.1145/3497776.3517771
• 发表时间: 2022-03
• 期刊: International Conference on Compiler Construction
• 作者: Shobaki, Ghassan;Bassett, Justin;Heffernan, Mark;Kerbow, Austin
• 通讯作者: Kerbow, Austin

Register-Pressure-Aware Instruction Scheduling Using Ant Colony Optimization

使用蚁群优化的寄存器压力感知指令调度

• DOI: 10.1145/3505558
• 发表时间: 2022-01-31
• 期刊: ACM Transactions on Architecture and Code Optimization (TACO)
• 作者: Ghassan Shobaki;V. S. Gordon;P. Mchugh;Theodore Dubois;Austin Kerbow
• 通讯作者: Austin Kerbow

Combining a Parallel Branch-and-Bound Algorithm with a Strong Heuristic to Solve the Sequential Ordering Problem

将并行分支定界算法与强启发式相结合来解决顺序排序问题

• DOI: 10.1145/3605731.3608929
• 发表时间: 2023-08
• 期刊: ICPP Workshops '23: Proceedings of the 52nd International Conference on Parallel Processing Workshops
• 作者: Shobaki, Ghassan;Gonggiatgul, Taspon;Normington, Jacob;Muyan
• 通讯作者: Muyan