Many-Core Compiler Fuzzing

Dr Alastair Donaldson

Parallel programming models for many-core systems, such as the OpenCL programming model, claim to allow the construction of portable many-core software.  Though performance portability may be an elusive goal, functional portability should not be.  Functional portability depends on reliable compilers for many-core programming languages.  This presents a real challenge for industry because many-core devices, such as GPUs, are evolving rapidly, as are the associated many-core languages (e.g., a revision of the OpenCL specification appears approximately once every 18 months). Compiler-writers are thus continually playing catch-up.

I will present recent ideas on how to apply random testing (fuzzing) to many-core compilers, in the context of OpenCL.  The aim of this work is to help vendors to improve the quality of their compilers by discovering bugs quickly.  Following up on successful prior works on sequential compiler testing, we have designed two techniques for generating random OpenCL kernels for purposes of compiler testing. The first approach builds on the Csmith project from the University of Utah (PLDI'11).  
Here, we generate random OpenCL kernels that are guaranteed to be free from undefined behaviour and to behave deterministically.  For such a kernel, differing results between two OpenCL implementations indicates that one of the implementations has compiled the kernel erroneously.  
The second approach builds on the "equivalence modulo inputs" idea from researchers at UC Davis (PLDI'14).  Here we start with an OpenCL kernel and generate mutations from the kernel such that, for a given input, each mutant is guaranteed by construction to compute the same result as the original kernel.  In this case, observable differences between mutants for the given input indicate compiler bugs.

I will report on a large testing campaign with respect to 19 OpenCL (device, compiler) configurations.  We found bugs in every configuration that we tested, including in compilers from AMD, Nvidia, Intel and Altera.  Many of the bugs we reported have now been fixed by the associated vendors.  In the talk I will show some examples of the bugs the technique has uncovered.

This is joint work with Christopher Lidbury, Andrei Lascu and Nathan Chong, and is due to appear at PLDI'15.

Bio: Alastair Donaldson is a Senior Lecturer in the Department of Computing, Imperial College London, where he leads the Multicore Programming Group and is Coordinator of the FP7 project CARP: Correct and Efficient Accelerator Programming.  He has published more than 50 peer-reviewed papers in formal verification and multicore programming, and leads the GPUVerify project on automatic verification of GPU kernels, which is a collaboration with Microsoft Research.  Before joining Imperial, Alastair was a Visiting Researcher at Microsoft Research Redmond, a Research Fellow at the University of Oxford and a Research Engineer at Codeplay Software Ltd.  He holds a PhD from the University of Glasgow.