CUDASW++4.0: ultra-fast GPU-based Smith–Waterman protein sequence database search Authors: Bertil Schmidt, Felix Kallenborn, Alejandro Chacon, Christian Hundt Published: 2024 ABSTRACT AbstractBackgroundThe maximal sensitivity for local pairwise alignment makes the Smith-Waterman algorithm a popular choice for protein sequence database search. However, its quadratic time complexity makes it compute-intensive. Unfortunately, current state-of-the-art software tools are not able to leverage the massively parallel processing capabilities of modern GPUs with close-to-peak performance. This motivates the need for more efficient implementations.ResultsCUDASW++4.0 is a fast software tool for scanning protein sequence databases with the Smith-Waterman algorithm on CUDA-enabled GPUs. Our approach achieves high efficiency for dynamic programming-based alignment computation by minimizing memory accesses and instructions. We provide both efficient matrix tiling, and sequence database partitioning schemes, and exploit next generation floating point arithmetic and novel DPX instructions. This leads to close-to-peak performance on modern GPU generations (Ampere, Ada, Hopper) with throughput rates of up to 1.94 TCUPS, 5.01 TCUPS, 5.71 TCUPS on an A100, L40S, and H100, respectively. Evaluation on the Swiss-Prot, UniRef50, and TrEMBL databases shows that CUDASW++4.0 gains over an order-of-magnitude performance improvements over previous GPU-based approaches (CUDASW++3.0, ADEPT, SW#DB). In addition, our algorithm demonstrates significant speedups over top-performing CPU-based tools (BLASTP, SWIPE, SWIMM2.0), can exploit multi-GPU nodes with linear scaling, and features an impressive energy efficiency of up to 15.7 GCUPS/Watt.ConclusionCUDASW++4.0 changes the standing of GPUs in protein sequence database search with Smith-Waterman alignment by providing close-to-peak performance on modern GPUs. It is freely available at https://github.com/asbschmidt/CUDASW4.Supplementary InformationThe online version contains supplementary material available at 10.1186/s12859-024-05965-6.Keywords: Smith–Waterman, CUDA, GPU, Protein sequence database search, Dynamic programming, DPX Background Computing optimal local pairwise alignments of biological sequences with the dynamic programming (DP)-based Smith–Waterman (SW) algorithm [1] is a core algorithm in bioinformatics. A prominent example is protein sequence database search where similarities between a query sequence and a database sequence can be identified by computing their optimal local alignment score. However, the associated time complexity to compute an alignment score between a pair of sequences is proportional to the product of their lengths which renders Smith–Waterman a comparably expensive yet highly accurate algorithm. The computational demand is further increased when considering the ever-growing number of sequences stored in large-scale datasets propelled by the continuous advances in high-throughput technologies. Consequently, a number of parallelized implementations have been developed for computing pairwise sequence alignments on a variety of architectures including CPUs [2–7], GPUs [8–19], and FPGAs [20–23]. They typically target two types of application scenarios: computing a single pairwise alignment of two very long DNA sequences (typically whole genomes or chromosomes), and computing a single pairwise alignment of two very long DNA sequences (typically whole genomes or chromosomes), and computing batches of different pairwise alignments of DNA/RNA or protein sequences of shorter length. computing batches of different pairwise alignments of DNA/RNA or protein sequences of shorter length. Widely adopted parallelization schemes are inter-sequence (computes a number of independent alignment tasks in parallel), intra-sequence (computes the DP matrix of a single alignment in parallel), and their hybrid combination. Another approach to accelerate time-consuming sequence database search is the usage of fast heuristics to replace expensive alignments. Prominent examples include FASTA [24] and BLAST [25–27]. These heuristics can often produce reasonably good results, but could fail to detect some distantly related sequences due to the loss of sensitivity [28–30]. In addition, their efficient fine-grained parallelization is made challenging by irregular computation and memory access patterns for vector and streaming processing architectures. ADEPT [13] and NVBIO [14] provide GPU accelerated APIs that can align protein sequences in addition to DNA sequences mostly targeting the use case of pairwise alignments. They typically compute an independent alignment per CUDA thread block whereby threads compute cells along a minor diagonal of the DP matrix in parallel. Data between neighboring diagonals is typically communicated via shared memory. Existing GPU implementations specifically optimized for protein sequence database search include CUDASW++3.0 [9], SWhybrid [15], and SW#DB [31]. More specifically, CUDASW++3.0 computes one alignment per thread using CUDA PTX SIMD video instructions, whereby intermediate buffers are stored in per-thread local memory and substitution scores are fetched from texture memory. While this approach proved to be efficient for the Kepler generation, it is bottlenecked by memory transfers on newer GPUs. In summary, previous approaches in this area are limited by inefficient memory access schemes and thus cannot fully exploit the performance of modern GPUs leading to slow runtimes. In this paper, we present CUDASW++4.0, which yields significantly faster and highly energy-efficient SW-based protein database searches compared to previous GPU implementations. To achieve high performance on modern GPUs, we take advantage of the following concepts: Different from previous hybrid fine-grained parallelization strategies and previous CUDASW++ versions we use warp intrinsics for inter-thread communication (instead of shared memory or local memory), which can minimize the overall executed instructions. It has recently also been successfully applied to accelerate dynamic time warping (DTW, [32]), Different from previous hybrid fine-grained parallelization strategies and previous CUDASW++ versions we use warp intrinsics for inter-thread communication (instead of shared memory or local memory), which can minimize the overall executed instructions. It has recently also been successfully applied to accelerate dynamic time warping (DTW, [32]), Tiling scheme for DP matrices in order to support batches with highly varying sequence lengths occurring in typical real-world database, Tiling scheme for DP matrices in order to support batches with highly varying sequence lengths occurring in typical real-world database, Sequence database partitioning to achieve fully-functional and high-performance support on GPUs with limited memory size, Sequence database partitioning to achieve fully-functional and high-performance support on GPUs with limited memory size, Advanced sequence length binning strategies combined with warp specialized kernels, Advanced sequence length binning strategies combined with warp specialized kernels, Efficient support of new architectural features of modern GPUs, such as half-precision using half2 arithmetic or s16x2 arithmetic by using novel DPX instructions. Efficient support of new architectural features of modern GPUs, such as half-precision using half2 arithmetic or s16x2 arithmetic by using novel DPX instructions. We initially evaluate the theoretical peak performance of CUDASW++4.0 using simulated databases comprised of equal-length protein sequences for different datatypes (float, half2, int32, s16x2) on three different recent GPU architectures (Ampere, Ada, Hopper). This also includes an evaluation of the performance of the recently introduced DPX instructions [33]. Subsequently, we evaluate the performance of CUDASW++4.0 using the real-world Swiss-Prot, UniRef50, and TrEMBL databases. Our performance comparison shows that CUDASW++4.0 consistently outperforms other GPU-based implementations (CUDASW++3.0, ADEPT) and CPU-based tools (SWIPE, SWIMM2.0, BLASTP) for queries of various lengths. CUDASW++4.0 achieves peak throughput rates of up to 1.94 TCUPS (Trillions of Cell Updates Per Second), 5.01 TCUPS, and 5.71 TCUPS on an A100, L40S, and H100 GPU, respectively. In addition, even higher speeds can be achieved by using multiple GPUs connected to the same host with close-to-linear linear scaling; e.g. 96.5% parallel efficiency can be achieved for a server with 8 H100 GPUs. Furthermore, our conducted power consumption analysis shows that GPUs can offer an order-of-magnitude higher energy efficiency than the most recent FPGA implementation at a similar power budget. Smith–Waterman algorithm Consider two sequences Q=(q0q1…qm-1) and S=(s0s1…sn-1) over the alphabet Σ of length m and n, respectively. For each pair (qi,sj) of characters the recurrence relation in Eq. 1 of the DP algorithm for local alignment decides if these characters should be aligned, if a gap should be inserted, or a new alignment is started. A corresponding score is recorded in DP matrix H. where 1≤i≤m,1≤j≤n and E and F are defined in Eqs. 2 and 3 and determine the gap penalty scheme, E and F are defined in Eqs. 2 and 3 and determine the gap penalty scheme, σ is a substitution function over Σ×Σ that determines the score of aligning two characters (for protein sequences this is typically a BLOSUM or PAM matrix). σ is a substitution function over Σ×Σ that determines the score of aligning two characters (for protein sequences this is typically a BLOSUM or PAM matrix). We consider an affine gap penalty scheme, where a gap of length k is penalized by α+(k-1)·β where α is the cost of the first gap (opening) and β the cost of each subsequent gap (extension): The matrices are initialized by H(0,0)=H(i,0)=H(0,j)=0, E(0,0)=F(0,0)=F(i,0)=E(0,j)=-∞, E(i,0)=-α-(i-1)·β, and F(0,j)=-α-(j-1)·β. The dependency relation in H is illustrated in Fig. 1, where light gray cells are initialization cells and dark gray cells indicate the ancestral subproblems of the currently active cell in black. Layout and dependency relationships of the DP matrix H The optimal local alignment score is equal to the maximum value in H and can be computed in linear space O(min{m,n}) and quadratic time O(m·n). Note that for protein database search we are interested in score-only computation but not the traceback. Features of CUDA-enabled GPUs CUDA kernels are executed using a number of independent thread blocks. Each thread block is mapped onto exactly one streaming multiprocessor (SM) and consists of a number of warps. All 32 threads within a warp are executed in lock-step fashion (SIMT). CUDA-enabled GPUs contain several types of memory: large but high latency global memory and fast but small on-chip shared and constant memory. Nevertheless, the fastest way to access data is through usage of the thread-local register file. Modern GPUs provide instructions for warp-level collectives in order to efficiently support communication of data stored in registers between threads within a warp without the need for accessing global or shared memory. A crucial feature of our approach is the usage of warp shuffles for low latency communication and minimization of memory traffic. In particular, we take advantage of the warp-level collectives __shfl_down_sync() and __shfl_up_sync(); e.g. the intra-warp communication operation R1 = __shfl_up_sync(0xFFFFFFFF, R0, 1, 32); moves the contents of register R0 in thread i within each warp to register R1 in thread i+1 for 0≤i<31. Advanced architectural GPU features for DP The three latest GPU generations (Ampere, Ada, Hopper) have incrementally included key hardware features that can be used to improve the performance of DP algorithms. Each architecture includes the following hardware forward-compatible features (e.g. Hopper supports all points below): [Ampere] Half2: Support of half-precision floating point arithmetic instructions that allow for the simultaneous execution of one 32-bit operation on two half-precision values. This allows for computing two values of the DP recurrence relation within a single register, effectively doubling the throughput. Ampere enables the necessary half2 min/max comparison function present in SW. [Ampere] Half2: Support of half-precision floating point arithmetic instructions that allow for the simultaneous execution of one 32-bit operation on two half-precision values. This allows for computing two values of the DP recurrence relation within a single register, effectively doubling the throughput. Ampere enables the necessary half2 min/max comparison function present in SW. [Ada] FP dual-port and max3: Enables dual ports for min/max and add/sub floating point (FP) operations. This allows us to execute both instructions independently in the SM and increase the overall throughput. Additionally, Ada introduced a new half2 set of instructions to perform the min/max operation of three input values (vhmnmx). [Ada] FP dual-port and max3: Enables dual ports for min/max and add/sub floating point (FP) operations. This allows us to execute both instructions independently in the SM and increase the overall throughput. Additionally, Ada introduced a new half2 set of instructions to perform the min/max operation of three input values (vhmnmx). [Hopper] ALU dual-port and DPX: Inclusion of DPX instructions to support fast computation of typical DP recurrence relations with integer-based arithmetic. This includes a set of functions that enable finding a max value of three inputs (vimax3), as well as fused addition with max operations (viaddmax). The instructions support any combination of min/max, sub/add for 16-bit or 32-bit integer parameters, with optional ReLU (clamping to zero). Similarly to Ada, Hopper supports integer parallel execution of max/min and add/sub in independent SM internal resources. [Hopper] ALU dual-port and DPX: Inclusion of DPX instructions to support fast computation of typical DP recurrence relations with integer-based arithmetic. This includes a set of functions that enable finding a max value of three inputs (vimax3), as well as fused addition with max operations (viaddmax). The instructions support any combination of min/max, sub/add for 16-bit or 32-bit integer parameters, with optional ReLU (clamping to zero). Similarly to Ada, Hopper supports integer parallel execution of max/min and add/sub in independent SM internal resources. Following sections will describe the necessary algorithmic changes to achieve high performance using these features and analyse their impact on real workloads. Implementation Program information and workflow CUDASW++4.0 is written in C++17 and targets Linux workstations and servers. It gains high speed by benefiting from the use of GPU accelerators attached to a host CPU (typically via PCIe) and requires a system with one or more GPUs compatible with CUDA 12. Detailed instructions are included in the software repository. Our algorithm for scanning a protein sequence database (DB) with a (single) query protein sequence Q on a single GPU consists of the following stages: Read local DB and Q from file. Read local DB and Q from file. Transfer the first batch of DB sequences and Q from CPU to GPU. Transfer the first batch of DB sequences and Q from CPU to GPU. Partition current DB batch by sequence lengths on GPU. Partition current DB batch by sequence lengths on GPU. Execute GPU alignment kernels for each partition. Execute GPU alignment kernels for each partition. Transfer the next batch of DB sequence from CPU to GPU concurrently to alignment computation. Transfer the next batch of DB sequence from CPU to GPU concurrently to alignment computation. Re-compute all alignments with indicated overflow (for 16-bit arithmetic) using GPU alignment kernels with 32-bit arithmetic. Re-compute all alignments with indicated overflow (for 16-bit arithmetic) using GPU alignment kernels with 32-bit arithmetic. If all DB sequences have been aligned to Q continue with Stage 8, otherwise continue with Stage 3. If all DB sequences have been aligned to Q continue with Stage 8, otherwise continue with Stage 3. Sort all alignment scores on GPU and transfer results to CPU for output. Sort all alignment scores on GPU and transfer results to CPU for output. Since GPU memory can be a scarce resource, we process batches of DB sequences in order to support large-scale protein sequence sets. Furthermore, this approach allows for concurrent PCIe data transfer and kernel execution. Although libraries for parsing of FASTA files exist [34], this task can still take significant time for reading databases like UniRef or TrEMBL. Thus, CUDASW++4.0 includes a preprocessor called makeDB (Stage 0) that creates a local database from protein FASTA files. We also support reading input files in gzip-compressed format (fasta.gz). The local database can then be used by CUDASW++4.0 for scanning with greatly accelerated file parsing time1. This approach is effective since databases are frequently scanned but only need to be preprocessed once. Sequences in the database are stored in a custom format and are sorted by length to allow for partitioning by sequence length during the main algorithm. Note that our program also accepts a set of query sequences {Q0,…QP-1} in a single FASTA file as input. In the case of multiple query sequences the workflow is repeated (except for reading the input files) for each query. If all database sequences can be stored in GPU device memory (which is typically the case for relatively small or medium-sized databases like Swiss-Prot or UniRef50) they only need to be transferred once for all P scan tasks. Figure 2 illustrates the workflow of CUDASW++4.0. Workflow of CUDASW++4.0 for scanning a database DB with a set of queries {Q0,…QP-1}. Steps executed on the GPU (CPU) are colored in green (grey) In addition to the features shown in the standard workflow we offer an interactive mode and a multi-GPU mode. In interactive mode the user can supply query sequences from the command line to scan a (pre-loaded) database. The multi-GPU mode takes advantage of several GPUs attached to the same host CPU by partitioning the input database into equal-sized parts per GPU. GPU-based alignment computation We base our parallelization scheme on computing an independent alignment per (sub)warp – a group of synchronized threads executed in lockstep that can efficiently communicate by means of warp shuffles. Threads in a (sub)warp compute DP matrix cell values in cooperative fashion. Note that according to Eqs. 1, 2 and 3 each DP cell depends on its left, upper, and upper-left neighbour (see Fig. 1), which means that (parallel) computation of DP cells has to follow this topological order. The fine-grained parallel design proposed in this work combined with optimizations described in the following sections leads to important advantages [35, 36] such as (a) avoiding thread divergence, (b) dynamic partitioning of large memory footprints on local memories, and (c) reduction of the overall executed instructions (e.g. removing LD/ST instructions) thus allowing the implementation of highly efficient tiling methods. In order to unlock the full potential of modern GPUs, we apply the following techniques: Full in-register computation of recurrence relations. Full in-register computation of recurrence relations. Low-latency communication of neighboring DP cells between threads through warp shuffles. Low-latency communication of neighboring DP cells between threads through warp shuffles. Reduction of frequent sequence character loading from memory by employing an intra-warp communication scheme based on warp shuffles. Reduction of frequent sequence character loading from memory by employing an intra-warp communication scheme based on warp shuffles. Efficient scheme for substitution table lookups σ(qi,sj) for BLOSUM matrices. Efficient scheme for substitution table lookups σ(qi,sj) for BLOSUM matrices. DP matrix tiling scheme for long sequences. DP matrix tiling scheme for long sequences. Optimized kernel variants for various sequence lengths and datatypes using half2 and float arithmetic and evaluation of DPX instructions for integer arithmetic (int32 and s16x2). Optimized kernel variants for various sequence lengths and datatypes using half2 and float arithmetic and evaluation of DPX instructions for integer arithmetic (int32 and s16x2). Mapping DP matrix cells to threads Each (sub)warp (a group of p threads T0,…,Tp-1 with p∈{2,4,8,16,32} executed in lock step), computes the optimal local alignment score between a (query) protein sequence Q and a database sequence S(i). Assume Q=(q0q1…qm-1) of length m and S(i)=(s0(i)s1(i)…sn-1(i)) of length n=k·p. We assign k columns of the DP matrix to be calculated by each thread. Computation proceeds along a wavefront in m+p iterations. In iteration i, thread Tt computes k adjacent cells of the DP matrix row i-t. In practice, the maximum possible value of k depends on the number of available registers and used datatype. Each DP matrix cell depends on its left, upper, and upper-left neighbor. All cells of the current and previous iteration are stored in thread-local registers. The required access of thread Tt to the rightmost value of thread Tt-1 computed in the previous iteration is accomplished by using the low-latency warp shuffle instruction __shfl_up_sync(). Our mapping strategy is illustrated in Fig. 3. Example of mapping DP matrix computation for comparing Q=(q0q1…qm-1) length m and S(i)=(s0(i)s1(i)…sn-1(i)) of length n=k·p to a group of p threads using k=4. Each thread computes k matrix cells (red) in each iteration i using the values of the antecedent row (blue) and an additional value from the second antecedent row (gray). Threads communicate values in the rightmost of their k columns as well as characters of q (green) by warp shuffle operations (dashed arrows) At the beginning each thread Tt,0≤t