corrfunc – a suite of blazing fast correlation functions on the CPU

Manodeep Sinha, Lehman H. GarrisonMonthly Notices of the Royal Astronomical Society 2019 · DOI

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 popcnt instruction 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

Abstract

ABSTRACT The two-point correlation function (2PCF) is the most widely used tool for quantifying the spatial distribution of galaxies. Since the distribution of galaxies is determined by galaxy formation physics as well as the underlying cosmology, fitting an observed correlation function yields valuable insights into both. The calculation for a 2PCF involves computing pair-wise separations and consequently, the computing time-scales quadratically with the number of galaxies. The next-generation galaxy surveys are slated to observe many millions of galaxies, and computing the 2PCF for such surveys would be prohibitively time-consuming. Additionally, modern modelling techniques require the 2PCF to be calculated thousands of times on simulated galaxy catalogues of at least equal size to the data and would be completely unfeasible for the next-generation surveys. Thus, calculating the 2PCF forms a substantial bottleneck in improving our understanding of the fundamental physics of the Universe, and we need high-performance software to compute the correlation function. In this paper, we present corrfunc – a suite of highly optimized, openmp parallel clustering codes. The improved performance of corrfunc arises from both efficient algorithms as well as software design that suits the underlying hardware of modern CPUs. corrfunc can compute a wide range of 2D and 3D correlation functions in either simulation (Cartesian) space or on-sky coordinates. corrfunc runs efficiently in both single- and multithreaded modes and can compute a typical two-point projected correlation function [wp(rp)] for ∼1 million galaxies within a few seconds on a single thread. corrfunc is designed to be both user-friendly and fast and is publicly available at https://github.com/manodeep/Corrfunc.
BibTeX
@inproceedings{sinha2019corrfunc,
  author = {Manodeep Sinha and Lehman H. Garrison},
  title = {{corrfunc – a suite of blazing fast correlation functions on the CPU}},
  booktitle = {Monthly Notices of the Royal Astronomical Society},
  year = {2019},
  doi = {10.1093/mnras/stz3157},
}
Figure