Electronic Thesis and Dissertation Repository

Thesis Format

Integrated Article

Degree

Doctor of Philosophy

Program

Computer Science

Supervisor

Moreno Maza, Marc

Abstract

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 <= 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.

Summary for Lay Audience

The theory and practice of optimizing compilers gather techniques that, when given input in the form of computer programs, aim at generating code that makes the best use of modern computer hardware to run those computer programs. 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 Graphic Processing Units (GPUs). We give a high-level introduction to these two fronts of our work below.

The many constraints of real-world problems, such as finding the number of construction workers required to complete a given task within a budget and before a deadline, can be translated into systems of multiple linear expressions. A solution to the system of expressions represents a solution to a real-world problem that satisfies all the constraints. Solving a linear system on real numbers can be simple but impractical, such as assigning 9 3/4 construction workers to the project, while practical solutions are often integers and require a long time to compute. Linear systems can often be represented as convex polyhedral sets, such as a triangle in 2-dimensional space or a cube in 3-dimensional space. If the integer points within a polyhedral set can be computed, these points can be used to solve the integer linear system. Therefore, we present the theory and an algorithm to find the integer points in a polyhedral set, and we show that our method is significantly faster than existing ones. Software can often be launched with different parameters. Sometimes, parameters are requirements of the users (data parameters) and affect the correctness of the results. In other cases, the parameters are fixed with regard to the hardware (hardware parameters). We focus on parameters that have no impact on the results but instead are related to the efficiency of the software (program parameters). Optimizing the program parameters can save resources such as time and memory but can be difficult without being an expert on the specific program. We present KLARAPTOR (Kernel LAunch parameters RAtional Program estimaTOR), a tool that dynamically computes program parameters that result in a good performance of the program. KLARAPTOR works on CUDA; the fine control of the hardware resources afforded by GPUs are preferable to CPUs and CUDA is the most popular programming language for GPUs. The underlying technique of KLARAPTOR can be applied to parallel programs in general, given a performance prediction model which accounts for data, program, and hardware parameters.

Download

Share

COinS