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

University Enterprises, Incorporated, Sacramento CA

Investigators

Abstract

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.