TL;DR
This paper introduces Corrfunc, a highly optimized C-based software suite designed to dramatically accelerate the computation of correlation functions, a crucial tool in cosmology. By leveraging efficient algorithms and modern CPU architectures, Corrfunc can calculate these functions for millions of galaxies in seconds, overcoming a major bottleneck for current and future astronomical surveys.
What Problem Does This Paper Address?
The two-point correlation function (2PCF) is a fundamental statistic used to understand the distribution of galaxies in the Universe. This distribution holds vital clues about both the underlying cosmology and the processes of galaxy formation. However, calculating the 2PCF involves comparing every pair of galaxies, leading to a computational complexity that scales quadratically with the number of galaxies ($O(N^2)$). As next-generation galaxy surveys aim to observe tens of millions to billions of galaxies, and as modern cosmological modeling requires thousands of 2PCF calculations for parameter estimation, the brute-force approach becomes prohibitively time-consuming. This computational bottleneck hinders our ability to extract maximum scientific insight from these vast datasets.
Methods
Corrfunc tackles this challenge through a multi-pronged approach focusing on both algorithmic improvements and hardware-aware software design:
- Algorithmic Optimizations:
- Spatial Partitioning (Gridding): The search volume for potential galaxy pairs is drastically reduced by dividing the simulation domain into 3D grid cells. Only particles within neighboring cells need to be considered, pruning the vast majority of unnecessary pair calculations.
- Cell Refinement: Further optimization is achieved by subdividing these cells, reducing the search volume even more.
- Symmetry Considerations: For auto-correlations, redundant pair calculations are avoided by only considering unique cell pairs and unique particle pairs within a cell.
- Late Entry/Early Exit Conditions: By sorting particles along the z-axis, the code can quickly determine when a particle pair is too far apart to be within the maximum search radius, allowing for early termination of inner loops.
- Software Optimizations:
- Cache Locality: Particle data is duplicated and stored contiguously within each grid cell. This ensures that when the CPU accesses particle positions, it's performing sequential memory reads, maximizing the benefit of CPU caches.
- SIMD (Vectorization): Explicit SIMD (Single Instruction, Multiple Data) vector intrinsics are used to perform calculations on multiple data elements simultaneously, leveraging modern CPU instruction sets like AVX and SSE. This is crucial because compilers struggle to automatically vectorize the histogram update step.
- OpenMP Parallelism: The code is parallelized using OpenMP for shared-memory multi-core processors, allowing for efficient utilization of multiple CPU cores.
- Optimized Histogram Updates: The histogram update, a serial bottleneck, is optimized using bit-masking and the
popcntinstruction for efficient counting.
Datasets
The paper does not describe datasets used for training. For evaluation and benchmarking, the authors used:
- Fiducial Catalogue: A clustered dark matter halo catalogue of 4.7 million objects in a 1100 h⁻¹Mpc box, derived from the ABACUS project. Smaller datasets were generated by randomly down-sampling this catalogue.
- Comparison Benchmarks: The authors compare Corrfunc's performance against several other publicly available correlation function codes, including SciPy cKDTree, scikit-learn KDTree, kdcount, halotools, TreeCorr, CUTE_box, mlpack RangeSearch, and swot.
Key Insights and Ideas
- The $O(N^2)$ bottleneck is real and severe: The paper vividly illustrates how the quadratic scaling of pair-counting makes even moderately large datasets computationally intractable for brute-force methods.
- Hardware-aware design is paramount: Simply having a good algorithm isn't enough. Corrfunc's significant speedup comes from meticulously tailoring its implementation to how modern CPUs work, particularly their cache hierarchies and SIMD capabilities.
- Compilers are not magic bullets for correlation functions: The authors found that compilers struggle to automatically vectorize the histogram update step, necessitating explicit SIMD programming.
- The "late entry/early exit" strategy is a powerful optimization: By sorting particles and using triangle inequalities, the code can prune large numbers of potential pairs without full distance calculations.
- OpenMP scaling is excellent, but cross-correlations lag auto-correlations: While multi-core parallelism is highly effective, auto-correlations show better scaling due to improved cache reuse.
Key Results
- Blazing Fast Performance: Corrfunc can compute a typical projected correlation function ($w_p(r_p)$) for ~1 million galaxies in a few seconds on a single thread.
- Significant Speedups:
- Compared to generic "Fallback" kernels, AVX kernels achieve a 3x speedup, and SSE kernels achieve a 2x speedup.
- In multi-threaded benchmarks, Corrfunc is generally a factor of a few faster than other codes. For instance, it achieves 93% efficiency with 24 threads for auto-correlations.
- Scalability: The code exhibits $O(N^2)$ scaling with the number of particles for large N, and its runtime scales with $R_{max}$ and $\theta_{max}$ as theoretically expected.
- User-Friendly and Publicly Available: The software is designed to be easy to use and is available on GitHub.
Limitations and Future Work
- Limitations:
- The authors acknowledge that at very low particle numbers, the overhead of grid construction can be significant, and their performance might not be optimal.
- The current implementation of the histogram update, while optimized, is still a serial bottleneck.
- There is a significant amount of duplicated source code across different pair-counters, which increases maintenance overhead.
- Future Work:
- Further Cell Refinement: Exploring more advanced cell subdivision strategies and incorporating minimum separation criteria.
- Loop Blocking: Implementing loop blocking in the vector kernels to improve data reuse and potentially achieve higher arithmetic operation to memory access ratios.
- GPU Acceleration: Investigating offloading computations to GPUs using libraries like cuBLAS.
- Auto-generated Codebase: Developing a system to auto-generate code from a higher-level description to reduce code duplication and improve maintainability.
- Refined Histogram Updates: Exploring techniques to process more particle pairs before histogram updates, potentially by using 64-bit integers per bin.
Summary updated