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).
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.
@cite_5 @cite_25 @cite_7 @cite_11
841199482 1964629970 1598336441 2133642410
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. 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. 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. 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.