In the peer-reviewed paper, titled “Asynchronous and Load-Balanced Union-Find for Distributed and Parallel Scientific Data Visualization and Analysis,” the researchers present a parallel distributed union-find algorithm – a fundamental technique that determines which subset a particular element is in.
“Union-find is widely used in scientific visualization algorithms,” said Jiayi Xu, a Ph.D. candidate at the Ohio State University and lead author of the award-winning paper. “But the parallelization of these algorithms has presented two bottlenecks: high synchronization costs and imbalanced workloads.”
The solution developed by the research team is to overlap communications with local computations using asynchronous parallelism, a technique that eliminates global synchronizations and reduces synchronization costs. Then, by redistributing disjoint set elements evenly across processors, the researchers are able to balance process workloads for scalable scientific visualization and analysis.
Benchmark tests on 3D spatial synthetic data and 2D time-varying application data output from high-speed imaging and fusion plasma simulations indicate that the novel algorithm achieves shorter execution time and better scalability than other distributed union-find methods.
“We next want to evaluate our algorithm’s performance in four dimensions – 3D in space and 1D in time,” said Hanqi Guo, an assistant computer scientist in Argonne’s Mathematics and Computer Science Division who mentors Xu at Ohio State and co-developed the asynchronous union-find algorithm. Guo explained that this next step is possible because union-find algorithms accept elements and edges between elements as input independent of the dimensionality of elements. The team also plans to explore the algorithm’s use in other visualization and analysis applications, such as in situ visualization.
The paper has been published by IEEE Transactions on Visualization and Computer Graphics for a special issue on PacificVis 2021. Click here to see the full paper.