Multithreaded event-chain Monte Carlo with local times
arXiv:2004.11040 · doi:10.1016/j.cpc.2020.107702
Abstract
We present a multithreaded event-chain Monte Carlo algorithm (ECMC) for hard spheres. Threads synchronize at infrequent breakpoints and otherwise scan for local horizon violations. Using a mapping onto absorbing Markov chains, we rigorously prove the correctness of a sequential-consistency implementation for small test suites. On x86 and ARM processors, a C++ (OpenMP) implementation that uses compare-and-swap primitives for data access achieves considerable speed-up with respect to single-threaded code. The generalized birthday problem suggests that for the number of threads scaling as the square root of the number of spheres, the horizon-violation probability remains small for a fixed simulation time. We provide C++ and Python open-source code that reproduces all our results.
arXiv comment24 pages, 7 figures
References in corpus (11)
- Two-step melting in two dimensions: First-order liquid-hexatic transition
- 2D Melting: From Liquid-Hexatic Coexistence to Continuous Transitions
- Hard-disk equation of state: First-order liquid-hexatic transition in two dimensions with three simulation methods
- Event-chain Monte Carlo algorithms for hard-sphere systems
- Generalized event-chain Monte Carlo: Constructing rejection-free global-balance algorithms from infinitesimal steps
- Event-Driven Molecular Dynamics in Parallel
- Irreversible local Markov chains with rapid convergence towards equilibrium
- Event-chain Monte Carlo algorithms for three- and many-particle interactions
- All-atom computations with irreversible Markov chains
- Sampling from a polytope and hard-disk Monte Carlo
- Testing the event-chain algorithm in asymptotically free models
Cited by in corpus (9)
- Event-chain Monte Carlo: foundations, applications, and prospects
- Newtonian Event-Chain Monte Carlo and Collision Prediction with Polyhedral Particles
- Molecular simulation from modern statistics: Continuous-time, continuous-space, exact
- Circulation Statistics and the Mutually Excluding Behavior of Turbulent Vortex Structures
- Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains
- Sparse hard-disk packings and local Markov chains
- Control of probability flow in Markov chain Monte Carlo -- Nonreversibility and lifting
- Computational Methods toward Ultrastable Glasses
- Necessary and sufficient symmetries in Event-Chain Monte Carlo with generalized flows and Application to hard dimers