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_18: 
  @cite_22: 
  @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_1: Searching databases of protein sequences for those proteins that match patterns represented as profile HMMs is a widely performed bioinformatics task. The standard tool for the task is HMMER version 3 from Sean Eddy. HMMER3 achieved significant improvements in performance over version 2 through the introduction of a heuristic filter called the Multiple Segment Viterbi algorithm (MSV) and the use of native SIMD instruction set on modern CPUs. Our objective was to further improve performance by using a general-purpose graphical processing unit (GPU) and the CUDA software environment from Nvidia.
  @cite_32: This paper describes an implementation of HMMER with FPGA. HMMER is one of the most used software tools for sensitive profile HMM (Hidden Markov Model) searches of biological sequence databases. HMMER is a very cpuintensive program. In HMMER, the Viterbi algorithm, which is a quadratic dynamic programming algorithm, is used to align a profile HMM and a protein sequence. In the profile HMM, a feedback path from the end of the model to the beginning is allowed, and this loop makes it difficult to process the Viterbi algorithm in parallel. In our approach, the alignment is calculated speculatively in parallel, and when the feedback path is selected in the alignment, the alignment is recalculated from the beginning using the fedback score. According to our experiments, the ratio that the feedback path is selected is very low, and the performance loss by the recalculation is less than a few percent. Another problem for accelerating HMMER using FPGA is the large size of the score tables required for profile HMMs. By crossing the search direction in the quadratic search space and the moving direction of each processing unit in the search space, we can minimize the size of the memory banks for storing the score tables. This optimization technique makes it possible to process all profile HMMs in a database efficiently.
  @cite_27: 
  @cite_23: Due to the exponentially growing bioinformatics databases and rapidly popular of GPU for general purpose computing, it is promising to employ GPU techniques to accelerate the sequence search process. Hmmsearch from HMMER bioinformatics software package is a wildly used software tool for sensitive profile HMM (Hidden Markov Model) searches of biological sequence databases. In this paper, we implement a speculative hmmsearch implementation on NVIDIA Fermi GPU and apply various optimizations to it. We test the enhancements in our GPU implementation in order to demonstrate the effectiveness of optimization strategies. Result shows that our speculative hmmsearch implementation achieves up to 6.5x speedup over previous fast single-threaded SSE implementation.
  @cite_10: Background HMMER is a commonly used bioinformatics tool based on Hidden Markov Models (HMMs) to analyze and process biological sequences. One of its main homology engines is based on the Viterbi decoding algorithm, which was already highly parallelized and optimized using Farrar’s striped processing pattern with Intel SSE2 instruction set extension.
summary: However, with the heuristic pipeline, HMMER3 achieves about @math x to @math x speedups over its predecessor @cite_27 , which hence renders any acceleration effort of HMMER2 obsolete. There are only few existing work that aim to accelerate SSV, MSV and P7Viterbi stages of pipeline in HMMER3. Abbas @cite_32 re-writes mathematical formulas of MSV and Viterbi algorithms to expose reduction and prefix scan computation patterns which are fitted into the FPGA architecture. @cite_23 , a speculative method is proposed to reduce the number of global memory access on the GPU, which aims to accelerate the MSV stage. Lin @cite_18 @cite_1 also focus on MSV stage but incorporate SIMD video instructions provied by the CUDA-enabled GPU into their method. Like the strategy of @cite_7 , they assign each thread to handle a whole sequence. A CPU-based implementation of P7Viterb stage is done by Ferreira @cite_10 who propose a cache-oblivious parallel SIMD Viterbi algorithm that offsets cache miss penalties of original HMMER3 work. Neto @cite_22 accelerate the SSV stage via a set of optimizations on the GPU, such as model tiling, outer loop unrolling, coalesced and vectorized memory access.