Software Performance Optimization with Genetic Algorithms

Abstract

Traditionally, compilers perform a sequence of optimizations that does not account for the distinct characteristics of different software/hardware combinations, often leading to suboptimal performance. We propose in this work a novel approach to automatize the process of optimizing the performance of a particular SW program on a specific HW. For that, we define a novel combinatorial optimization problem, that we call SCOP (for Software Code Optimization Problem), consisting in finding a sequence of code transformations that minimizes the runtime of the resulting SW on the considered HW architecture. Utilizing LLVM for transformations, our approach significantly diverges from conventional methods by automating the optimization process to adapt dynamically to various SW/HW pairs, surpassing standard optimization flags in efficacy. We propose the use of a Cellular Genetic Algorithm (cGA) to find a sequence of LLVM passes that minimizes the SW runtime. To deal with the uncertainty on the SW runtime, we study five different fitness functions: one execution, median, worst case, interval, and worst-case interval from 15 executions, the latter two being novel proposals.We evaluated our approach using the Polybench benchmark on various HW architectures, including ARM and Intel-based systems. The results demonstrate that the sequences identified by the cGA consistently outperform the runtime of SW optimized using traditional methods, such as the -O3 optimization flag provided by Clang. This paper describes a novel combinatorial optimization problem for automatically optimizing SW programs performance considering uncertainty in measurements. The work was originally published in [1]. Among the five different fitness functions considered, those based on the worst case are the most resilient to system uncertainty, with our proposed new approach being the most accurate. The execution time of the original program is reduced by up to 63.2%, outperforming the -O3 flag by up to 26.3%.