Savva, GD;
Stamatakis, M;
(2020)
Comparison of Queueing Data-Structures for Kinetic Monte Carlo Simulations of Heterogeneous Catalysts.
The Journal of Physical Chemistry A
, 124
(38)
pp. 7843-7856.
10.1021/acs.jpca.0c06871.
Preview |
Text
Stamatakis_acs.jpca.0c06871.pdf - Accepted Version Download (1MB) | Preview |
Abstract
On-lattice Kinetic Monte Carlo (KMC) is a computational method used to simulate (among others) physico-chemical processes on catalytic surfaces. The KMC algorithm propagates the system through discrete configurations by selecting (with the use of random numbers) the next elementary process to be simulated, e.g. adsorption, desorption, diffusion or reaction. An implementation of such a selection procedure is the first-reaction method in which all realizable elementary processes are identified and assigned a random occurrence time based on their rate constant. The next event to be executed will then be the one with the minimum inter-arrival time. Thus, a fast and efficient algorithm for selecting the most imminent process and performing all the necessary updates on the list of realizable processes post-execution, is of great importance. In the current work, we implement five data-structures to handle the elementary process queue during a KMC run: an unsorted list, a binary heap, a pairing heap, a 1-way skip list, and finally, a novel 2-way skip list with a mapping array specialized for KMC simulations. We also investigate the effect of compiler optimizations on the performance of these data-structures on three benchmark models, capturing CO-oxidation, a simplified water-gas shift mechanism, and a temperature programmed desorption run. Excluding the least efficient and impractical for large problems unsorted list, we observe a 3× speedup of the binary or pairing heaps (most efficient) compared to the 1-way skip list (least efficient). Compiler optimizations deliver a speedup of up to 1.8×. These benchmarks provide valuable insight on the importance of, often-overlooked, implementation-related aspects of KMC simulations, such as the queueing data-structures. Our results could be particularly useful in guiding the choice of data-structures and algorithms that would minimize the computational cost of large-scale simulations.
| Type: | Article |
|---|---|
| Title: | Comparison of Queueing Data-Structures for Kinetic Monte Carlo Simulations of Heterogeneous Catalysts |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1021/acs.jpca.0c06871 |
| Publisher version: | https://doi.org/10.1021/acs.jpca.0c06871 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Elements, Algorithms, Optimization, Inorganic carbon compounds, Lattices |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Chemical Engineering UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Physics and Astronomy |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10109069 |
Archive Staff Only
 |
View Item |
