text: Genomic sequence alignment is an important research topic in bioinformatics and continues to attract significant efforts. As genomic data grow exponentially, however, most of alignment methods face challenges due to their huge computational costs. HMMER, a suite of bioinformatics tools, is widely used for the analysis of homologous protein and nucleotide sequences with high sensitivity, based on profile hidden Markov models (HMMs). Its latest version, HMMER3, introdues a heuristic pipeline to accelerate the alignment process, which is carried out on central processing units (CPUs) with the support of streaming SIMD extensions (SSE) instructions. Few acceleration results have since been reported based on HMMER3. In this paper, we propose a five-tiered parallel framework, CUDAMPF++, to accelerate the most computationally intensive stages of HMMER3's pipeline, multiple single segment Viterbi (MSV SSV), on a single graphics processing unit (GPU). As an architecture-aware design, the proposed framework aims to fully utilize hardware resources via exploiting finer-grained parallelism (multi-sequence alignment) compared with its predecessor (CUDAMPF). In addition, we propose a novel method that proactively sacrifices L1 Cache Hit Ratio (CHR) to get improved performance and scalability in return. A comprehensive evaluation shows that the proposed framework outperfroms all existig work and exhibits good consistency in performance regardless of the variation of query models or protein sequence datasets. For MSV (SSV) kernels, the peak performance of the CUDAMPF++ is 283.9 (471.7) GCUPS on a single K40 GPU, and impressive speedups ranging from 1.x (1.7x) to 168.3x (160.7x) are achieved over the CPU-based implementation (16 cores, 32 threads).
  @cite_5: Many biologically motivated problems are expressed as dynamic programming recurrences and are difficult to parallelize due to the intrinsic data dependencies in their algorithms. Therefore their solutions have been sped up using task level parallelism only. Emerging platforms such as GPUs are appealing parallel architectures for high-performance; at the same time they are a motivation to rethink the algorithms associated with these problems, to extract finer-grained parallelism such as data parallelism. In this paper, we consider the hmmersearch program as a representative of these problems and we re-design its computational algorithm to extract data parallelism for a more efficient execution on emerging platforms, despite the fact that hmmersearch has data dependencies. Our approach outperforms other existing methods when searching a very large database of unsorted sequences on GPUs.
  @cite_25: GPUs have recently been used to accelerate data-parallel applications for they provide easier programmability and increased generality while maintaining the tremendous memory bandwidth and computational power. Most of those applications use CPU as a controller who decides when GPUs run the computing-intensive tasks. This CPU-control-GPU-compute pattern wastes much of CPU's computational power. In this paper, we present a new CPU-GPU cooperative pattern for bioinformatics applications which can use both of CPU and GPU to compute. This pattern includes two parts: 1) the load-balanced data structure which manages data to keep the computational efficiency of GPU high enough when the length distribution of sequences in a sequence database is very uneven; 2) multi-threaded code partition which schedules computing on CPU and GPU in a cooperative way. Using this pattern, we develop CuHMMer based on HMMER which is one of the most important algorithms in bioinformatics. The experimental result demonstrates that CuHMMer get 13x to 45x speed up over available CPU implementations and could also outperform the traditional CUDA implementations which use CPU-control-GPU-compute pattern.
  @cite_7: In this paper we present the results of parallelizing two life sciences applications, Markov random fields-based (MRF) liver segmentation and HMMER's Viterbi algorithm, using GPUs. We relate our experiences in porting both applications to the GPU as well as the techniques and optimizations that are most beneficial. The unique characteristics of both algorithms are demonstrated by implementations on an NVIDIA 8800 GTX Ultra using the CUDA programming environment. We test multiple enhancements in our GPU kernels in order to demonstrate the effectiveness of each strategy. Our optimized MRF kernel achieves over 130× speedup, and our hmmsearch implementation achieves up to 38× speedup. We show that the differences in speedup between MRF and hmmsearch is due primarily to the frequency at which the hmmsearch must read from the GPU's DRAM.
  @cite_11: The proliferation of biological sequence data has motivated the need for an extremely fast probabilistic sequence search. One method for performing this search involves evaluating the Viterbi probability of a hidden Markov model (HMM) of a desired sequence family for each sequence in a protein database. However, one of the difficulties with current implementations is the time required to search large databases. Many current and upcoming architectures offering large amounts of compute power are designed with data-parallel execution and streaming in mind. We present a streaming algorithm for evaluating an HMMs Viterbi probability and refine it for the specific HMM used in biological sequence search. We implement our streaming algorithm in the Brook language, allowing us to execute the algorithm on graphics processors. We demonstrate that this streaming algorithm on graphics processors can outperform available CPU implementations. We also demonstrate this implementation running on a 16 node graphics cluster.
summary: As one of the most popular tool for the analysis of homologous protein and nucleotide sequences, HMMER attracts many acceleration attempts. The previous version, HMMER2, is based on Viterbi algorithm that has proved to be the computational bottleneck. The initial effort of GPU-based implementation for HMMER2 is ClawHMMER @cite_11 which introduces a streaming version of Viterbi algorithm for GPUs. They also demonstrate the implementation running on a 16-node GPU cluster, each equipped with a Radeon 9800 Pro GPU. Another early GPU-based implementation is proposed by Walters @cite_7 who properly fit the Viterbi algorithm into the CUDA-enabled GPU with several optimizations, like memory coalescing, proper kernel occupancy and shared constant memory usage, which outperforms the ClawHMMER substantially. Yao @cite_25 present a CPU-GPU cooperative pattern to accelerate HMMER2. Ganesan @cite_5 re-design the aligment process of a single sequence across multiple threads to partially break the sequential dependency in computation of Viterbi scores. This helps building a hybrid task and data-level parallelism that eliminates the overhead due to unbalanced sequence lengths.