Acceleration and Parallelization of ZENO/Walk-on-Spheres

Published

June 1, 2016

Author(s)

Derek Juba, Walid Keyrouz, Michael V. Mascagni, Mary C. Brady, Michael Mascagni

Abstract

This paper describes our on-going work to accelerate ZENO, a software tool based on Monte Carlo methods (MCMs), used for computing material properties at the nanoscale. ZENO employs three main algorithms: (1)Walk on Spheres (WoS), (2)interior sampling, and (3)surface sampling. We have accelerated the first two algorithms. For the sake of brevity, the paper will discuss our work on the first one only as it is the most commonly used and the acceleration techniques were similar in both cases. WoS is a Brownian Motion (BM) MCM for solving a class of partial differential equations (PDEs). It provides a stochastic solution to a PDE by estimating the probability that a random walk started at infinity will hit the surface of the material under consideration. WoS is highly effective when the problem's geometry is additive, as this greatly reduces the number of walk steps needed to achieve accurate results. The walks start on the surface of an enclosing sphere and can make much larger jumps than in a direct simulation of BM. Our current implementation represents the molecular structure of nanomaterials as a union of possibly overlapping spheres. The core processing bottleneck in WoS is a computational geometric one, as the algorithm repeatedly determines the distance from query point to the material surface in each step of the random walk. In this paper, we present results from benchmarking spatial data structures, including several open-source implementations of $k$-D trees, for accelerating WoS algorithmically. The paper also presents results from our multicore and cluster parallel implementation to show that it exhibits linear strong scaling with the number of cores and compute nodes; this implementation delivers up to 4 orders of magnitude speedup compared to the original FORTRAN code when run on 5 nodes (each with dual 6-core Intel Xeon CPUs) with 24 threads per node.

Proceedings Title

Proceedings of the 2016 International Conference on Computational Science

Volume

80

Conference Dates

June 6-8, 2016

Conference Location

San Diego, CA, US

Conference Title

International Conference on Computational Science

Pub Type

Conferences

Download Paper

DOI Link

Keywords

Monte Carlo Methods, nanomaterial properties, Walk on Spheres, parallelization, $k$-D tree

Citation

Juba, D. , Keyrouz, W. , Mascagni, M. , Brady, M. and Mascagni, M. (2016), Acceleration and Parallelization of ZENO/Walk-on-Spheres, Proceedings of the 2016 International Conference on Computational Science, San Diego, CA, US, [online], https://doi.org/10.1016/j.procs.2016.05.319 (Accessed October 9, 2025)