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:
- 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.
- 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.
- 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).
- Multi-level Parallelism:
- Vector-level: Utilizing 512-bit SIMD instructions for data-level parallelism.
- Thread-level: Using OpenMP to manage the many cores within a single Phi.
- Accelerator-level: Using MPI (Message Passing Interface) to distribute tiles across a cluster of multiple Phi coprocessors.
- 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