N-Point Correlation

Two-point Correlation Function (TPCF) is widely used in astronomy to characterize the distribution of matter/energy in the Universe, and help derive the physics that can trace back to the creation of the universe. However, it is prohibitively slow for current sized datasets, and would continue to be a critical bottleneck with the trend of increasing dataset sizes to billions of particles and more, which make TPCF is a compelling benchmark application for future exa-scale architectures.

State-of-the-art TPCF implementations do not map well to the underlying SIMD hardware, and also suffer from load-imbalance for large core counts. In this paper, we present a novel SIMD- friendly histogram update algorithm that exploits the spatial locality of histogram updates to achieve near-linear SIMD scaling. We also present a load-balancing scheme that combines domain- specific initial static division of work and dynamic task migration across nodes to effectively balance computation across nodes.

Using Zin supercomputer at Lawrence Livermore National Laboratory (25,600 cores of Intel Xeon E5-2670, each with 256- bit SIMD), we achieve 90% parallel efficiency and 96% SIMD efficiency, and perform TPCF computation on a 1.7 billion particle dataset in 5.3 hours (a minimum of 35x faster than previous approaches). In terms of cost per performance (measured in flops/$), we achieve at least an order-of-magnitude (11.1x) higher flops/$ as compared to the best known results [1]. Consequently, we now have line-of-sight to achieving the processing power for correlation computation to process billion+ particles telescopic data.

DOWNLOAD CODE »

PUBLICATIONS

1. Billion-Particle SIMD-Friendly Two-Point Correlation on Large-Scale HPC Cluster Systems Jatin Chhugani, Changkyu Kim, Hemant Shukla, Jongsoo Park, Pradeep Dubey, John Shalf and Horst D. Simon. ACM 2012 Gordon Bell Finalist.