Skip to main content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.


The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

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 nist-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
Conference Title
International Conference on Computational Science


Monte Carlo Methods, nanomaterial properties, Walk on Spheres, parallelization, $k$-D tree
Created June 1, 2016, Updated November 10, 2018