Parallel Pairwise Correlation Computation On Intel Xeon Phi Clusters

Yongchao Liu, Tony Pan, Srinivas Aluru

Abstract

Co-expression network construction is a critical technique for identifying inter-gene interactions, typically relying on all-pairs Pearson's correlation coefficient (PCC) computation. However, this process is computationally demanding for large datasets. We present LightPCC, the first parallel and distributed all-pairs PCC computation framework optimized for Intel Xeon Phi clusters. LightPCC achieves high performance by exploring SIMD-instruction-level, thread-level, and accelerator-level parallelism. To ensure balanced workload distribution for symmetric computations, we introduced a novel framework using bijective functions between job identifiers and coordinate space. Evaluation shows LightPCC runs up to 218.2× faster than sequential ALGLIB and 71.4× faster than single-threaded MKL, demonstrating excellent parallel scalability across clusters.

Introduction

In bioinformatics, researchers use gene co-expression networks to identify how genes interact. Building these networks requires calculating the Pearson Correlation Coefficient (PCC) for every possible pair of genes across hundreds or thousands of samples. For a dataset with $n$ genes and $l$ samples, the computational complexity is $O(n^2 \cdot l)$. As genomic datasets grow into the tens of thousands of genes, this "all-pairs" computation becomes a massive bottleneck.

While GPUs have been used for acceleration, the Intel Xeon Phi—a many-core coprocessor—presents unique challenges in memory management and workload balancing. Specifically, because PCC is symmetric (the correlation of gene A to B is the same as B to A), we only need to compute half of the matrix. Distributing this "triangular" workload evenly across a cluster of many-core processors without massive memory overhead is a non-trivial task.

Methods

LightPCC employs several optimization strategies to maximize the efficiency of the Xeon Phi architecture:

  1. Mathematical Reformulation: The input variables are transformed so that the PCC calculation becomes a simple dot product of two vectors. This eliminates redundant calculations of means and variances during the all-pairs phase.
  2. Direct Bijective Mapping: This is the core innovation of LightPCC. To balance the workload of the triangular job matrix, the authors derived a mathematical function that maps a linear job ID to specific $(x, y)$ coordinates in the matrix. This allows any processor to calculate exactly which "tile" of the matrix it should work on in $O(1)$ time and space, avoiding the need for memory-consuming lookup tables.
Triangular matrix tiling and indexing for workload distribution.
  1. Tiled Computation: The matrix is divided into $t \times t$ tiles. This improves cache locality and allows the algorithm to handle datasets that are too large to fit into the Xeon Phi’s limited 8GB onboard memory.
  2. Multi-level Parallelism: The system utilizes 512-bit SIMD instructions for vector-level parallelism, OpenMP for thread-level management within a single Phi, and MPI (Message Passing Interface) to distribute tiles across a cluster of multiple Phi coprocessors.
  3. Asynchronous Execution: A double-buffering scheme is used to hide the latency of transferring data between the host CPU and the Phi accelerator.

Key Results

LightPCC was evaluated using artificial datasets ($16K, 32K, 64K$ genes) and a real-world human genome expression dataset (17,555 genes). It was compared against ALGLIB (a standard sequential C++ library) and Intel MKL (a highly optimized parallel math library).

Performance comparison against MKL and parallel scalability across Xeon Phi clusters.
  • Speedup vs. ALGLIB: On a single Phi, LightPCC was up to 20.6× faster. On a cluster of 16 Phis, it reached a 218.2× speedup.
  • Speedup vs. Intel MKL: LightPCC outperformed single-threaded MKL by up to 71.4× on 16 Phis. Even compared to 16-threaded MKL, LightPCC was 5.3× faster on the largest artificial dataset.
  • Scalability: The algorithm demonstrated excellent parallel scalability; doubling the number of Phis nearly doubled the performance, indicating very low communication overhead.
  • Real-world Performance: For the human genome dataset, LightPCC finished in just 2.7 seconds on 16 Phis, compared to 162.8 seconds for ALGLIB.

Conclusion

LightPCC provides a high-performance solution for large-scale genomic network construction. By solving the load-balancing problem for symmetric computations through bijective mapping, it achieves significant speedups over standard libraries. Future work aims to develop a hybrid CPU-Phi model to utilize host processing power and integrate LightPCC into larger pipelines for constructing genome-wide networks from emerging data types like RNA-seq.

Source Code: LightPCC is open-source and available at http://lightpcc.sourceforge.net.

Summary updated

Abstract

Co-expression network is a critical technique for the identification of inter-gene interactions, which usually relies on all-pairs correlation (or similar measure) computation between gene expression profiles across multiple samples. Pearson's correlation coefficient (PCC) is one widely used technique for gene co-expression network construction. However, all-pairs PCC computation is computationally demanding for large numbers of gene expression profiles, thus motivating our acceleration of its execution using high-performance computing. In this paper, we present LightPCC, the first parallel and distributed all-pairs PCC computation on Intel Xeon Phi (Phi) clusters. It achieves high speed by exploring the SIMD-instruction-level and thread-level parallelism within Phis as well as accelerator-level parallelism among multiple Phis. To facilitate balanced workload distribution, we have proposed a general framework for symmetric all-pairs computation by building bijective functions between job identifier and coordinate space for the first time. We have evaluated LightPCC and compared it to two CPU-based counterparts: a sequential C++ implementation in ALGLIB and an implementation based on a parallel general matrix-matrix multiplication routine in Intel Math Kernel Library (MKL) (all use double precision), using a set of gene expression datasets. Performance evaluation revealed that with one 5110P Phi and 16 Phis, LightPCC runs up to $20.6\times$ and $218.2\times$ faster than ALGLIB, and up to $6.8\times$ and $71.4\times$ faster than single-threaded MKL, respectively. In addition, LightPCC demonstrated good parallel scalability in terms of number of Phis. Source code of LightPCC is publicly available at http://lightpcc.sourceforge.net.
BibTeX
@inproceedings{liu2016parallel,
  author = {Yongchao Liu and Tony Pan and Srinivas Aluru},
  title = {{Parallel Pairwise Correlation Computation On Intel Xeon Phi Clusters}},
  booktitle = {Sbac-pad},
  year = {2016},
  doi = {10.1109/sbac-pad.2016.26},
}
Figure