Parallelized Kendall's Tau Coefficient Computation via SIMD Vectorized Sorting On Many-Integrated-Core Processors

Yongchao Liu, Yongchao Liu 0004, Tony Pan, Oded Green, Srinivas AluruarXiv 2017 · arXiv

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:

Table of notations used in the Kendall's Tau computation algorithms.

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:

  1. Naïve Kernel: An $O(n^2)$ approach that enumerates all pairs.
  2. Generic Sorting-Enabled (GSE) Kernel: An $O(n \log n)$ approach using standard library sorting.
  3. 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

Abstract

Pairwise association measure is an important operation in data analytics. Kendall's tau coefficient is one widely used correlation coefficient identifying non-linear relationships between ordinal variables. In this paper, we investigated a parallel algorithm accelerating all-pairs Kendall's tau coefficient computation via single instruction multiple data (SIMD) vectorized sorting on Intel Xeon Phis by taking advantage of many processing cores and 512-bit SIMD vector instructions. To facilitate workload balancing and overcome on-chip memory limitation, we proposed a generic framework for symmetric all-pairs computation by building provable bijective functions between job identifier and coordinate space. Performance evaluation demonstrated that our algorithm on one 5110P Phi achieves two orders-of-magnitude speedups over 16-threaded MATLAB and three orders-of-magnitude speedups over sequential R, both running on high-end CPUs. Besides, our algorithm exhibited rather good distributed computing scalability with respect to number of Phis. Source code and datasets are publicly available at http://lightpcc.sourceforge.net.
BibTeX
@misc{liu2017parallelized,
  author = {Yongchao Liu and Yongchao Liu and Tony Pan and Oded Green and Srinivas Aluru},
  title = {{Parallelized Kendall's Tau Coefficient Computation via SIMD Vectorized Sorting On Many-Integrated-Core Processors}},
  year = {2017},
  eprint = {1704.03767},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1704.03767},
}
Figure