Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/27233
Title: | Relaxing Scalability Limits with Speculative Parallelism in Sequential Monte Carlo | Authors: | NEMETH, Balazs HABER, Tom LIESENBORGS, Jori LAMOTTE, Wim |
Issue Date: | 2018 | Publisher: | IEEE | Source: | IEEE Computer Society, IEEE,p. 494-503 | Series/Report: | IEEE International Conference on Cluster Computing (CLUSTER) | 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. | Keywords: | speculative parallelism; sequential Monte Carlo; high performance computing; load imbalance | Document URI: | http://hdl.handle.net/1942/27233 | ISBN: | 9781538683194 | DOI: | 10.1109/CLUSTER.2018.00065 | ISI #: | 000454692400055 | Rights: | (C) 2018 IEEE | Category: | C1 | Type: | Proceedings Paper | Validations: | ecoom 2020 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
6wpENwJOSZImp8OL5KkAfI.pdf Restricted Access | Published version | 195.99 kB | Adobe PDF | View/Open Request a copy |
main.pdf Restricted Access | Peer-reviewed author version | 250.54 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
3
checked on Sep 3, 2020
WEB OF SCIENCETM
Citations
2
checked on Oct 12, 2024
Page view(s)
122
checked on Sep 7, 2022
Download(s)
78
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.