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

Area of Science:

• Bioinformatics
• Computational Biology
• High-Performance Computing

Background:

• Multiple pair-wise sequence alignment is crucial for understanding protein evolution and function.
• Existing algorithms face computational challenges with large biological datasets.
• Accelerating these alignments is essential for advancing genomic and proteomic research.

Purpose of the Study:

• To develop a novel hybrid model for efficient multiple pair-wise sequence alignment.
• To leverage Message Passing Interface (MPI) and CUDA for parallel processing on GPU clusters.
• To optimize the Smith-Waterman algorithm for enhanced performance.

Main Methods:

• A hybrid model combining MPI for distribution and CUDA for parallel computation on GPUs.
• Implementation of a Master Node Dispatcher (MND) and Worker GPU Nodes (WGN) architecture.
• A modified, row-wise computation approach for the Smith-Waterman algorithm.

Main Results:

• Significant reduction in running time with an increasing number of GPU nodes.
• Achieved a performance of approximately 12 Giga cell updates per second.
• Demonstrated scalability and efficiency on the SWISS-PROT protein knowledge base using four nodes.

Conclusions:

• The proposed hybrid MPI-CUDA model offers a substantial speedup for multiple pair-wise sequence alignment.
• The row-wise Smith-Waterman implementation contributes to computational efficiency.
• This approach is effective for large-scale biological sequence analysis on homogeneous GPU clusters.