JIAYIN (KAY) LU 卢嘉茵
Applied Mathematician & Computational Artist & Freelance Photographer
Multi-threaded Parallel Computation of the Voronoi Diagrams and its Applications
Fall 2019-Fall 2023
Advisor: Prof. Christopher Rycroft
Collaborators: Emanuel Lazar, Deborah Schwarcz
Status: The project led to a paper published in Computer Physics Communications:
Working with my advisor Prof. Christopher Rycroft, I am currently developing software libraries in the computational geometry field. The software libraries can serve as useful tools for other researchers in the analysis of large-scale particle systems and in large-scale numerical simulations using the finite element method.
We recently developed a multi-threaded extension of Voro++. Voro++ [1] is a software written in C++ to generate Voronoi diagrams. It was released by my advisor in 2009 and has since gained popularity in the research community. Using OpenMP [2], I developed a shared-memory parallel computation extension for Voro++, and I implemented a custom-written random access iterator class for the particles so that the software has a simple user interface for parallelization. I tested the parallel performance with 100,000,000 particles for different particle distributions in both 2D and 3D, as shown in the figure below.
Figure: Three different particle distribution cases in both 2D and 3D.
(a) Homogeneous and random particle distribution.
(b) Localized and random particle distribution.
(c) Extreme clustering particle distribution.
With the right choices of parallel load-balancing strategies, all cases reached near perfect parallel efficiency, as shown in the parallel efficiency plots below.
Figure: Parallel efficiency against number of threads of five OpenMP built-in load-balancing strategies, for the three particle distribution cases in both 2D and 3D.
The multi-threaded Voro++ is very useful for research in physical sciences that requires computing large-scale Voronoi diagrams with thousands of millions of particles. For example, material scientists may analyze large-scale atomistic systems to study material properties. Indeed, multi-threaded Voro++ enabled the parallelization of a software that analyzes crystalline structures, VoroTop [3]. VoroTop was developed by our collaborator, Prof. Emanuel Lazar. It uses the Voronoi diagrams of atomistic structures to analyze defects in crystalline materials. With parallel computation, it can now analyze large-scale systems efficiently in a reasonable amount of time.
Reference
[1] C. H. Rycroft. Voro++: A three-dimensional Voronoi cell library in C++. Chaos: An Interdisciplinary Journal of Nonlinear Science, 19:041111, 2009. http://math.lbl.gov/voro++/.
[2] L. Dagum and R. Menon. OpenMP: an industry standard API for shared-memory programming. IEEE Computational Science and Engineering, 5(1):46–55, 1998. https://www.openmp.org.
[3] Emanuel A Lazar. VoroTop: Voronoi cell topology visualization and analysis toolkit. Modelling and Simulation in Materials Science and Engineering, 26(1):015011, dec 2017. https://www.vorotop.org.