Allocation and Scheduling using Linear Programming in the SPIRAL Compiler 1. Project Description Optimizing Compilers: Project Proposal

Today’s compilers are usually doing register allocation and scheduling in two different passes, with the first pass imposing unnecessary constraints to the second pass. Different studies [1] have proposed simultaneous register allocation and scheduling using integer linear programming (ILP) to get an optimal solution to those problems. However, since ILP is an NP-complete problem, compilation time increases exponentially with code size, and thus, only small code segments can be scheduled this way. Nonetheless, under some conditions [2], the integer linear programming constraints can be relaxed to linear programming (LP) whose response time is polynomial instead of exponential. Our project involves implementing an LP scheduler/allocator within the SPIRAL compiler. SPIRAL is a Carnegie Mellon University project that generates competitive code entirely autonomously for digital signal processing algorithms and other numerical kernels. When asking for a specific transform, SPI-RAL will create a platform specific search space (e.g. taking into account different algorithms, simdization or parallelization) and look for the best possible implementation. In this project, we will focus our efforts on the back-end of the SPIRAL compiler, which accepts a simple language as input (loops, additions, multiplications, no pointers) and will be configured to produce fully unrolled SSE code (intrinsics or assembly). Preliminary work by Yevgen Voronenko on Integer Linear Programming has shown potential for significan