Parallel Pairwise Correlation Computation on Intel Xeon Phi Clusters

Yongchao Liu, Yongchao Liu 0004, Tony Pan, Srinivas Aluru

TL;DR

LightPCC is a high-performance parallel algorithm designed to accelerate all-pairs Pearson Correlation Coefficient (PCC) calculations on Intel Xeon Phi clusters. By leveraging a novel bijective mapping for workload balancing and multi-level parallelism, it achieves up to a 218x speedup over standard sequential libraries, making large-scale genomic network construction significantly more efficient.

What Problem Does This Paper Address?

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

The authors introduce LightPCC, which employs several optimization strategies:

  1. Mathematical Reformulation: They transform the input variables 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 paper's core innovation. To balance the workload of the triangular job matrix, they 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 large, memory-consuming lookup tables.
  3. Tiled Computation: The matrix is divided into $t \times t$ tiles. This improves cache locality (keeping data close to the processor) and allows the algorithm to handle datasets that are too large to fit into the Xeon Phi’s limited onboard memory (8GB).
  4. Multi-level Parallelism:
    • Vector-level: Utilizing 512-bit SIMD instructions for data-level parallelism.
  5. Thread-level: Using OpenMP to manage the many cores within a single Phi.
  6. Accelerator-level: Using MPI (Message Passing Interface) to distribute tiles across a cluster of multiple Phi coprocessors.
  7. Asynchronous Execution: They use a double-buffering scheme to hide the latency of transferring data between the host CPU and the Phi accelerator.

Datasets

The researchers evaluated LightPCC using two types of data:

  • Artificial Datasets: Three sets of randomly generated gene expression values with $n = \{16K, 32K, 64K\}$ genes and $l = 5,000$ samples.
  • Real-world Dataset: A human genome expression dataset from the SEEK engine, consisting of 17,555 genes across 5,072 samples.

Key Insights and Ideas

  • Symmetry as a Challenge: While computing only the upper triangle of a matrix saves 50% of the work, it usually leads to "load imbalance" because rows at the top of the triangle are much longer than those at the bottom. The bijective mapping elegantly solves this by treating the entire triangular workload as a 1D array of jobs that can be sliced perfectly among processors.
  • Compiler Maturity: Interestingly, the authors found that modern Intel C++ compilers are now so efficient at "auto-vectorization" that manual SIMD intrinsics (hand-coding the vector instructions) provided only a negligible performance boost. They opted for auto-vectorization to keep the code more portable.
  • Memory Constraints: The Xeon Phi's memory is small compared to system RAM. The "multi-pass" execution model—where the Phi computes a subset of tiles and sends them back to the host—is critical for scaling to genome-wide studies.

Key Results

LightPCC was compared against ALGLIB (a standard sequential C++ library) and Intel MKL (a highly optimized parallel math library).

  • Speedup vs. ALGLIB: On a single Phi, LightPCC was up to 20.6x faster. On a cluster of 16 Phis, it reached a staggering 218.2x speedup.
  • Speedup vs. Intel MKL: LightPCC outperformed single-threaded MKL by up to 71.4x on 16 Phis. Even compared to 16-threaded MKL, LightPCC was 5.3x faster on the largest artificial dataset.
  • Scalability: The algorithm showed 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.

Limitations and Future Work

  • Offload Model: The current implementation uses an "offload" model where the host CPU acts primarily as a manager. The authors note that the host CPUs' own significant computing power is currently underutilized.
  • Hybrid Computing: Future work aims to develop a hybrid CPU-Phi model where both the host processors and the accelerators work on the matrix simultaneously.
  • Integration: The authors plan to integrate LightPCC into larger pipelines for constructing genome-wide networks from emerging data types like RNA-seq and integrating them with other genomic data.

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× and 218.2× faster than ALGLIB, and up to 6.8× and 71.4× 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 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},
}

Loading related content...

Figure