Three Contributions to the Theory and Practice of Optimizing Compilers

The theory and practice of optimizing compilers gather techniques that, from input computer programs, aim at generating code making the best use of modern computer hardware. On the theory side, this thesis contributes new results and algorithms in polyhedral geometry. On the practical side, this thesis contributes techniques for the tuning of parameters of programs targeting GPUs. We detailed these two fronts of our work below. Consider a convex polyhedral set P given by a system of linear inequalities A*x \u3c= b, where A is an integer matrix and b is an integer vector. We are interested in the integer hull PI of P which is the smallest convex polyhedral set that contains all the integer points in P. In Chapter 3 we discuss our findings on the pseudo-periodicity of the vertices of PI when the input vector b is parametric, that is, the coordinates b1, . . . , bm of b are treated as parameters while the coefficients of A have fixed values. We observe that the number of vertices of PI has a pseudo-period Ti w.r.t each bi. This result and its proof lead us to propose a new algorithm for computing the integer hull of a rational convex polyhedral set, see Chapter 4. We have implemented in the C programming language our algorithm for the case of polyhedral sets in dimensions 2 and 3. We have also realized a Maple implementation of our algorithm for polyhedral sets of arbitrary dimensions. Our experimental results show that our algorithm computes integer hulls efficiently and can deal with polyhedral sets with large numbers of integer points. On another front, we present KLARAPTOR (Kernel LAunch parameters RAtional Program estimaTOR), a freely available tool built on top of the LLVM Pass Framework and NVIDIA CUPTI API to dynamically determine the optimal values of launch parameters of a CUDA kernel. We describe a technique that, for a CUDA kernel, builds at compile-time, a so-called rational program. This rational program, based on some performance prediction model, and knowing particular data and hardware parameters at runtime, can be executed to automatically and dynamically determine the values of launch parameters, for the CUDA kernel, which will yield nearly optimal performance