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:
- 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.
- 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.
- 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.
- 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.
- 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).
- 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