Login | Register

Implementing and Accelerating HMMER3 Protein Sequence Search on CUDA-Enabled GPU


Implementing and Accelerating HMMER3 Protein Sequence Search on CUDA-Enabled GPU

Cheng, Lin (2014) Implementing and Accelerating HMMER3 Protein Sequence Search on CUDA-Enabled GPU. Masters thesis, Concordia University.

Text (Final version of Lin Cheng's Master thesis) (application/pdf)
thesis_LinCheng.pdf - Accepted Version
Available under License Spectrum Terms of Access.


The recent emergence of multi-core CPU and many-core GPU architectures has made parallel computing more accessible. Hundreds of industrial and research applications have been mapped onto GPUs to further utilize the extra computing resource. In bioinformatics, HMMER is a set of widely used applications for sequence analysis based on Hidden Markov Model. One of the tools in HMMER, hmmsearch, and the Smith-Waterman algorithm are two important tools for protein sequence analysis that use dynamic programming. Both tools are particularly well-suited for many-core GPU architecture due to the parallel nature of sequence database searches.

After studying the existing research on CUDA acceleration in bioinformatics, this thesis investigated the acceleration of the key Multiple Segment Viterbi algorithm in HMMER version 3. A fully-featured CUDA-enabled protein database search tool cudaHmmsearch was designed, implemented and optimized. We demonstrated a variety of optimization strategies that are useful for general purpose GPU-based applications. Based on our optimization experience in parallel computing, six
steps were summarized for optimizing performance using CUDA programming.

We made comprehensive tests and analysis for multiple enhancements in our GPU kernels in order to demonstrate the effectiveness of selected approaches. The performance analysis showed that GPUs are able to deal with intensive computations, but are very sensitive to random accesses to the global memory. The results show that our implementation achieved 2.5x speedup over the single-threaded HMMER3 CPU SSE2 implementation on average.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Cheng, Lin
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:27 July 2014
Thesis Supervisor(s):Butler, Gregory
Keywords:CUDA HMMER hmmsearch MSV GPU acceleration
ID Code:978785
Deposited By: LIN CHENG
Deposited On:10 Nov 2014 15:47
Last Modified:18 Jan 2018 17:47
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top