Workshops Archive

Efficient cosmological friends-of-friends computation with fine-grained optimizations


Workshop: IA^3 2026 — 16th Workshop on Irregular Applications: Architectures and Algorithms

Authors: Ritvik Rao (University of Illinois Urbana-Champaign) and Laxmikant Kale (University of Illinois at Urbana-Champaign)

Abstract: One computationally intensive part of cosmological simulations is identifying clusters. One method to do this is via the friends-of-friends (FoF) algorithm, which is functionally equivalent to finding incremental connected components. Optimizing FoF for large, imbalanced datasets is challenging due to load and communication imbalance. In this paper, we present a parallel approach that integrates a tree traversal library with a union-find library. While this combination provided a foundational framework, we discovered that it fell short of meeting the rigorous performance demands of complex cosmological data. To overcome this, we designed and implemented a series of fine-grained optimizations tailored to the unique memory and processing patterns of the algorithm. We demonstrate that our approach achieves significant performance gains for highly imbalanced outputs without compromising cluster accuracy or quality. Finally, we analyze these results and identify remaining opportunities for further improvement in scalable cluster finding.


Back to IA^3 2026 — 16th Workshop on Irregular Applications: Architectures and Algorithms Archive Listing

Back to Full Workshop Archive Listing