Varsi, Alessandro 
ORCID: 0000-0003-2218-4720
(2021)
Streaming Multi-core Sample-based Bayesian Analysis.
PhD thesis, University of Liverpool.
|
Text
201231282_Jun2021.pdf - Unspecified Download (2MB) | Preview |
Abstract
Sequential Monte Carlo (SMC) methods are a well-established family of Bayesian inference algorithms for performing state estimation for Non-Linear Non-Gaussian models. As the models become more accurate, the run-time of SMC applications becomes increasingly slow. Parallel computing can be used to compensate for this side-effect. However, an efficient parallelisation of SMC is hard to achieve, due to the challenges involved in parallelising the bottleneck, resampling, and its constituent redistribute step. While redistribution can be performed in O((N/T) x logN) on a Shared Memory Architecture (SMA) using T parallel threads (e.g. a GPU or mainstream CPUs), a state-of-the-art redistribute takes O((logN)^2) computations on Distributed Memory Architectures (DMAs) which most supercomputers are made of. In this thesis, the focus is on three major goals. First, the thesis proposes a novel parallel redistribute for DMAs which achieves O(logN) time complexity. It is shown that on Message Passing Interface (MPI) the novel redistribute is up to eight times faster than the O((logN)^2) one. On a cluster of 256 cores, an SMC method employing the O((logN)^2) redistribute becomes up to six times faster when switching to the novel redistribution, which is also proved to no longer be the bottleneck. For the same number of cores, the maximum reported speed-up vs a single-core SMC method is 160. A patent application on this invention is currently filed. Second, the thesis describes a novel parallel redistribute for SMAs which takes O((N/T) + logN) steps and fully exploits the computational power of SMAs. The proposed approach is up to six times faster than the O((N/T) x logN) one. This shared memory implementation is then combined with the MPI O(logN) redistribution to obtain a hybrid distributed-shared memory parallel redistribute that fully exploits the large parallelism that modern supercomputers offer. In the end, to make these advances widely available this thesis presents Streaming-Stan and SMC-Stan, two extension packages for Stan, a popular statistical programming language. Streaming-Stan and SMC-Stan offer the possibility to describe models by using the same intuitive syntax used by regular Stan, but they are also equipped with the aforementioned High Performance Computing (HPC) SMC method, in the form of Fixed-Lag SMC and SMC sampler respectively. The same SMC methods also provide a vast choice of proposal distributions, including (on Streaming-Stan) two novel ones, presented in this thesis, which combine the main features of Fixed-Lag SMC methods with Hamiltonian Monte Carlo (HMC) and No-U-Turn Sampler (NUTS).
| Item Type: | Thesis (PhD) |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 09 Sep 2021 14:49 |
| Last Modified: | 18 Jan 2023 22:33 |
| DOI: | 10.17638/03127409 |
| Supervisors: |
|
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3127409 |
Dimensions
Dimensions
