A Study on the Influence of Runtime Uncertainty in the Optimization of Software Programs

Abstract

Compilers apply different optimizations to the software during the compilation process. These code transformations are generic, not taking into account the properties of the software to be compiled and the hardware where it will be executed. In addition, measuring the execution time of a program is not a simple task, causing the effect of uncertainty differences between independent measurements of the same experiment. In the literature, it is usual to perform several executions of the software program, taking a statistic from the sample, without taking into account that the choice of a non-representative statistic can cause an erroneous evolution of the algorithm. In this work, we propose the use of a cellular genetic algorithm to reduce the execution time of a software program executed on a given hardware architecture by treating the uncertainty of the fitness function with four different methods. The results evidence the presence of the uncertainty, obtaining high precision estimates with the method based on the interval of values of the five worst executions.