Relaxing Scalability Limits with Speculative Parallelism in Sequential Monte Carlo

Abstract

Sequential Monte Carlo methods are a useful tool to tackle non-linear problems in a Bayesian setting. A target posterior distribution is approximated by moving a set of weighted particles through a sequence of distributions. To counteract degeneracy caused by sequentially changing the underlying distribution, particles occasionally need to be resampled. Deciding if this is necessary requires a reduction operation on the weights after each update. Hence, scalability on a cluster is not only determined by the number of particles used, but also by how well load is balanced. This paper shows how speculative execution in Sequential Monte Carlo with Markov Chain Monte Carlo steps can improve parallel scalability. The key insight is that decisions taken based on the reduction result in each step can be accurately predicted. Consequently, synchronization inherent in the reduction can, in most cases, be avoided, relaxing the limit imposed by load imbalance. Particles are renumbered during resampling to further improve accuracy. Multiple test scenarios, each with different load balance characteristics, are studied empirically on a compute cluster. Tests show that when decisions are predicted correctly, execution time is reduced drastically for use cases with high load imbalance. Furthermore, the maximum theoretical gain, derived from execution characteristics, is compared with the measured improvement to verify that most speculative evaluations are actually useful. If predictions are incorrect, or load is balanced, speculation has no measurable negative impact. Performance is also evaluated in a weak scaling setting on cluster with 36 cores in each system.