Introduction
In large-scale data analytics, identifying non-linear relationships is a critical task. While Pearson’s correlation coefficient is widely used, it is limited to linear associations. Kendall’s tau coefficient offers a more robust, rank-based alternative for capturing non-linear dependencies. However, its computational complexity—scaling quadratically with the number of variables—poses a significant challenge for high-dimensional datasets, such as those found in bioinformatics. This paper presents a highly optimized parallel framework designed to compute "all-pairs" Kendall’s tau coefficients by leveraging the massive parallelism of Intel Xeon Phi processors.
Problem Statement and Notation
The "all-pairs" problem involves calculating the correlation for every possible pair in a dataset. For a dataset with $m$ vectors of $n$ elements each, this requires $m(m-1)/2$ pairwise calculations. Standard statistical software like R and MATLAB often struggle with these scales. To address this, the authors formalize the computation using the following notations:
The primary goal is to efficiently compute $\tau_B$, which accounts for ties in the data, using many-core architectures. The notation table above defines the specific components of the Kendall's Tau calculation, including the handling of concordant ($n_c$) and discordant ($n_d$) pairs.
Methodology
The researchers developed three algorithmic variants to optimize the computation:
- Naïve Kernel: An $O(n^2)$ approach that enumerates all pairs.
- Generic Sorting-Enabled (GSE) Kernel: An $O(n \log n)$ approach using standard library sorting.
- Vectorized Sorting-Enabled (VSE) Kernel: The core contribution, utilizing 512-bit SIMD instructions.
Key Innovations
- SIMD Vectorization: The VSE kernel packs variable pairs into 32-bit integers. It utilizes the Xeon Phi’s 512-bit registers to implement a 16-way bitonic merge network. Bitonic sorting is preferred here because its fixed execution path avoids branch divergence, which is critical for performance on many-core architectures.
- Direct Bijective Mapping: To ensure perfect load balancing across hundreds of threads, the authors derived a mathematical bijective function mapping a linear "job ID" to a 2D coordinate in the symmetric correlation matrix. This eliminates the overhead of dynamic task scheduling.
- Tiled Computing: The algorithm partitions the job matrix into tiles to maximize L1/L2 cache hits, minimizing slow off-chip memory access.
Experimental Results
The framework was evaluated using four real-world human genome gene expression datasets (DS21050, DS19784, DS13070, and DS3526) from the SEEK database.
The VSE algorithm demonstrated exceptional performance on a single Intel Xeon Phi 5110P:
- Massive Speedups: Achieved up to an 812x speedup over 16-threaded MATLAB and a 1,166x speedup over sequential R.
- Vectorization Efficiency: The VSE kernel provided a stable ~1.87x speedup over its non-vectorized counterpart for larger vector sizes.
- Scalability: Testing on a cluster of 16 Phis showed nearly linear scalability, validating the effectiveness of the bijective mapping framework.
Conclusion and Future Work
The proposed parallel framework significantly reduces the time required for large-scale correlation analysis. While the current 32-bit integer packing limits vector lengths to 32,767, future work aims to implement 64-bit support for ultra-high-dimensional data. The authors also plan to release an R package to make these high-performance kernels accessible to the broader scientific community.
Reference: Liu, Y., Pan, T., Green, O., & Aluru, S. (2017). Parallelized Kendall’s Tau Coefficient Computation via SIMD Vectorized Sorting On Many-Integrated-Core Processors. Preprint submitted to Journal of Parallel and Distributed Computing.
Summary updated