SWAPHI-LS: Smith-Waterman Algorithm on Xeon Phi coprocessors for Long DNA Sequences

As an optimal method for sequence alignment, the Smith-Waterman (SW) algorithm is widely used. Unfortunately, this algorithm is computationally demanding, especially for long sequences. This has motivated the investigation of its acceleration on a variety of high-performance computing platforms. However, most work in the literature is only suitable for short sequences. In this paper, we present SWAPHI-LS, the first parallel SW algorithm exploiting emerging Xeon Phi coprocessors to accelerate the alignment of long DNA sequences. In SWAPHI-LS, we have investigated three parallelization approaches (naïve, tiled, and distributed) in order to deeply explore the inherent parallelism within Xeon Phis. To achieve high speed, we have explored two levels of parallelism within a single Xeon Phi and one more level of parallelism between Xeon Phis. Within a single Xeon Phi we exploit instruction-level parallelism within 512-bit single instruction multiple data (SIMD) instructions (vectorization) as well as thread-level parallelism over the many cores (multi-threading). Between Xeon Phis we employ device-level parallelism in order to harness the compute power of Xeon Phi clusters (distributed computing based on the MPI offload model). The performance of our algorithm has been evaluated using a variety of genome sequences of lengths ranging from 4.4 million to 50 million nucleotides. Our performance evaluation reveals that our implementation achieves a stable performance of up to 30.1 billion cell updates per second (GCUPS) on a single Xeon Phi and up to 111.4 GCUPS on four Xeon Phis sharing the same host. SWAPHI-LS is written in C++ (with a set of SIMD intrinsics), OpenMP and MPI. The source code is publicly available at http://swaphi-ls.sourceforge.net.