Title: Design and implementation of a hybrid MPI-CUDA model for the Smith-Waterman algorithm

Authors: Heba Khaled; Hossam El Deen Mostafa Faheem; Rania El Gohary

Addresses: Computer Systems Department, Faculty of Computer & Information Science, Ain Shams University, Cairo 11566, Egypt ' Computer Systems Department, Faculty of Computer & Information Science, Ain Shams University, Cairo 11566, Egypt ' Information Science Department, Faculty of Computer & Information Science, Ain Shams University, Cairo 11566, Egypt

Abstract: This paper provides a novel hybrid model for solving the multiple pair-wise sequence alignment problem combining message passing interface and CUDA, the parallel computing platform and programming model invented by NVIDIA. The proposed model targets homogeneous cluster nodes equipped with similar Graphical Processing Unit (GPU) cards. The model consists of the Master Node Dispatcher (MND) and the Worker GPU Nodes (WGN). The MND distributes the workload among the cluster working nodes and then aggregates the results. The WGN performs the multiple pair-wise sequence alignments using the Smith-Waterman algorithm. We also propose a modified implementation to the Smith-Waterman algorithm based on computing the alignment matrices row-wise. The experimental results demonstrate a considerable reduction in the running time by increasing the number of the working GPU nodes. The proposed model achieved a performance of about 12 Giga cell updates per second when we tested against the SWISS-PROT protein knowledge base running on four nodes.

Keywords: molecular biology; sequence alignment; Smith-Waterman algorithm; dynamic programming; MPI; message passing interface; clustering; GPGPU; GPU nodes; graphical processing unit; CUDA; compute unified device architecture; parallel processing; bioinformatics; cluster nodes.

DOI: 10.1504/IJDMB.2015.069710

International Journal of Data Mining and Bioinformatics, 2015 Vol.12 No.3, pp.313 - 327

Received: 20 Jul 2014
Accepted: 22 Dec 2014
Published online: 29 May 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article