Parallelizing the Smith-Waterman Algorithm Using OpenSHMEM and MPI-3 One-Sided Interfaces

The Smith-Waterman algorithm is used for determining the similarity between two very long data streams. A popular application of the Smith-Waterman algorithm is for sequence alignment in DNA sequences. Like many computational algorithms, the Smith-Waterman algorithm is constrained by the memory resources and the computational capacity of the system. As such, it can be accelerated and run at larger scales by parallelizing the implementation, allowing the work to be distributed to exploit HPC systems. A central part of the algorithm is computing the similarity matrix which is the mechanism that evaluates the quality of the matching sequences. This access pattern to the matrix to compute the similarity is non-uniform; as such, it better suits the Partioned Global Address Space PGAS programming model. In this paper, we explore parallelizing the Smith-Waterman algorithm using the OpenSHMEM model and interfaces in OpenSHMEM 1.2 as well as the one-sided communication interfaces in MPI-3. Further, we also explore the advantages of using non-blocking communication interfaces, which are proposed as extensions for a future OpenSHMEM specification. We evaluate the parallel implementation on Titan, a Cray XK7 system at the Oak Ridge Leadership Computing Facility OLCF. Our results demonstrate good weak and strong scaling characteristics for both of the OpenSHMEM and MPI-3 implementations.