UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Comparison of Queueing Data-Structures for Kinetic Monte Carlo Simulations of Heterogeneous Catalysts

Savva, GD; Stamatakis, M; (2020) Comparison of Queueing Data-Structures for Kinetic Monte Carlo Simulations of Heterogeneous Catalysts. The Journal of Physical Chemistry A 10.1021/acs.jpca.0c06871. (In press).

[img] Text
Stamatakis_acs.jpca.0c06871.pdf - Accepted version
Access restricted to UCL open access staff until 2 September 2021.

Download (1MB)

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
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.
UCL classification: UCL
UCL > Provost and Vice Provost Offices
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
URI: https://discovery.ucl.ac.uk/id/eprint/10109069
Downloads since deposit
1Download
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item