A Real-Time Fully-Parallel Alternative to MCMC (industrial CASE award)

The aim of this PhD is to develop techniques for implementing state-of-the-art Bayesian techniques in ways that fully exploit the computational power of modern and next generation many-core architectures and systems (such as multicore CPUs, GPUs, Xeon Phis and super-computing clusters). This will build on previous research related to high performance computing, Big Data and Bayesian statistics. The aim is to solve difficult problems related to defence and security applications (in which context combining runtime efficiency with accurate estimation is very important).
Markov-Chain Monte Carlo (MCMC) is a numerical Bayesian method that allows high-fidelity physical models to be combined with data to make inferences in the presence of pronounced uncertainty. Improvements to MCMC have historically focused on algorithmic advances, involving, for example, the use of local gradient information and of gradually migrating from an easy reference problem to the problem of interest. Particularly with these improvements, MCMC is an effective solution to the vast number of problems that can be posed as inferences involving data using statistical models. In the context of any one problem, bespoke optimisation can be used to exploit the available (parallel) computational resources. However, because MCMC fundamentally uses the evolution of a single Markov-Chain to convey uncertainty, such optimisation is necessarily problem-specific. There is therefore little scope to develop a generic MCMC implementation that fully exploits parallel processing architectures. As a result, the ability of MCMC to provide solutions to next-generation problems is limited.
Sequential Monte Carlo (SMC) samplers can solve the same problems as MCMC. In contrast to MCMC, SMC samplers use the diversity of a population of samples to convey uncertainty. For the majority of the operation of an SMC sampler, each sample is processed independently. This makes it trivial to parallelise the majority of the SMC sampler. However, at a specific point in the SMC sampler, it becomes necessary to perform a “resampling” step. A text-book implementation of this resampling step is impossible to parallelise in a scalable fashion. However, previous research has demonstrated that it is possible to describe the resampling operation using a divide-and-conquer strategy. In so doing, it becomes possible to parallelise the resampling step. More recent work has identified that, if using more cores if to result in faster operation, it is crucial that data locality and pipelining are explicitly considered in the implementation. There is a need for this research to be extended significantly with a view to providing a generic parallel implementation of an SMC sampler which can dramatically outperform MCMC.
The PhD will therefore comprise three main strands of research on: understanding the problem and solution space (ie applying off-the-shelf SMC samplers to problems relevant to the defence and security industry); developing implementations of SMC samplers that fully exploit some exemplar many-core architectures; using these implementations to develop real-time solutions to some exemplar industry-relevant problems.
The PhD includes components that pull on Computer Science, Statistics, and Engineering and is at the intersection of these three academic disciplines. The successful applicant will have experience in one of these domains and will gain experience in the others. It is also anticipated that the successful applicant will gain experience on a number of HPC technologies (MPI, CUDA, OpenMP, Vectorisation to name a few), Big Data technologies (eg Hadoop and Spark) and that the project will enable the student to enhance valuable programming skills (eg in MATLAB, Java and C++).
Prof Simon Maskell (see: www.simonmaskell.com