Philip is a PhD student at the University of Copenhagen working on the parallel functional programming language Futhark, currently exploring ways to optimize memory usage in a programming language that has no notion of memory. His interests lie at the intersection between compilers, programming languages and parallelism.
AUTHORS: Philip Munksgaard, Svend Breddam, Troels Henriksen, Fabian Gieseke and Cosmin Oancea
We present a simple, reliable and efficient technique for autotuning programs whose computational kernels are compiled to multiple semantically-equivalent but differently-optimized code versions. These code versions are discriminated by predicates that each compare one statically given threshold value with a dynamic program value modelling the local program property that represent the subject of optimization, e.g., degree of exploited parallelism. Our framework assumes that the measure used to model the program property is monotonic, i.e., if a code version is found optimal for a certain value, then it will remain optimal for any higher values.
We require that each predicate must introduce exactly one unknown. This restriction allows datasets to be analyzed independently and the partial results to be merged together in a simple way. The framework guarantees that if there exist a set of threshold values that perfectly discriminate between datasets, then it will be found. The downside is that, in principle, such set might not exist. Fortunately, we have not observed this to be problematic in practice.
We demonstrate the feasibility of the approach on a number of public benchmarks by comparing it with a black-boxed solution using the popular OpenTuner library.Slides