Multithreaded event-chain Monte Carlo with local times

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. Program summary Program title: ParaSpheres. CPC Library link to program files: https://doi.org/10.17632/c3rjk5k3z9.1 Developer's repository link: https://github.com/jellyfysh/ParaSpheres Licensing provisions: GNU GPLv3. Programming languages: Python 3, C++, Fortran90. Nature of problem: Multithreaded event-chain Monte Carlo for hard spheres. Solution method: Event-driven irreversible Markov-chain Monte Carlo algorithm using local times. Additional comments: The collection of programs is complete with shell scripts that allow one to reproduce all data, and all the figures of the paper. Change of density and system size is straightforward. The manuscript is accompanied by a frozen copy of the GitHub repository that is made publicly available on GitHub (repository tps://github.com/jellyfysh/ParaSpheres, commit hash e2aa5b9727fb080ebe65581586cof6133efa495d). (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

The study introduces a multithreaded event-chain Monte Carlo algorithm for hard spheres, achieving significant speed-up in computations. Rigorous proof on small test suites shows that the horizon-violation probability is small within a fixed simulation time. The research provides open-source codes in C++ and Python for reproducing all results.