(538d) Linked-List Based Queuing System for Kinetic Monte Carlo Simulations of Heterogeneous Catalysts

Stochastic modelling, and in particular the kinetic Monte Carlo (KMC) approach, has proven to be a useful tool for simulating molecular phenomena on catalytic surfaces characterised by structural complexity and extensive reaction networks. The backbone of the lattice KMC method consists of identifying and randomly selecting a realizable elementary event among adsorption, desorption, diffusion on the surface and reaction. Then, the chosen process is executed, the lattice state and list of realizable events are updated and the procedure is repeated. In representative KMC simulations, the required number of executed steps ranges in the order of billions in order to propagate the system in time and accumulate sufficient statistics for reliable results.

Zacros [1, 2], a Graph-Theoretical Kinetic Monte Carlo software implements the first-reaction method for listing and randomly choosing the next process. This method is based on the idea that the next event to occur has to be the most imminent one, namely, the one with the smallest waiting time. The main task is, therefore, reduced to creating a “catalogue” containing the waiting time of all realizable events, finding their minimum and updating the time values of the affected processes at every simulation step (in addition to adding new events or removing obsolete events). These operations are managed by a queuing system that handles bookkeeping, insertions and removals of all realizable processes on the lattice. These operations have to be highly efficient as they can be performed billions of times within a typical KMC run. Queuing systems previously implemented in Zacros are the “unsorted list” and the “binary heap”. In the former, waiting times are stored in a one-dimensional unsorted array and the minimum element is found by transversing it element by element. The Binary Heap is a partially sorted data-structure that enables constant time minimum element retrieval.

In the current work, the “Skip List” [3], a linked-list based, probabilistic and fully sorted data structure is adapted and further extended to a suitable KMC queuing system. An almost constant time removal operation was achieved, improving the data-structure’s performance by a factor of two as compared to its initial design by W. Pugh.

Appropriate benchmarks enabled us to compare the runtime scaling of the above methods as a function of the total lattice sites using simple yet representative chemical reaction models. It was found that the “unsorted list” algorithm exhibits the poorest performance since finding the smallest time value is a considerably slow process. The “Binary Heap” performs notably better and seems to share the same performance, in terms of orders of magnitude, as the “Skip List”. Lastly, the “Skip List” outperforms the “Binary Heap” in a special class of problems. The “bottlenecks”, namely the time consuming operations that incur negative effects on performance were clearly identified in each algorithm. Finally, improvements are proposed to further improve their runtime.

[1] http://zacros.org

[2] Nielsen et al, J. Chem. Phys, 139(22): 224706, 2013

[3] William Pugh, Commun ACM, 33(6):668–676, 1990