Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Acceleration and Parallelization of ZENO/Walk-on-Spheres



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


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
Conference Dates
June 6-8, 2016
Conference Location
San Diego, CA, US
Conference Title
International Conference on Computational Science


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


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], (Accessed February 20, 2024)
Created May 31, 2016, Updated October 12, 2021