Source-linked AI summary
Efficient Architecture-Aware Acceleration of BWA-MEM for Multicore Systems
Vasimuddin Md, Sanchit Misra, Heng Li, Srinivas Aluru
TL;DR
High-throughput sequencing makes read mapping an increasingly important computational bottleneck, while BWA-MEM is widely used and must retain identical output. The paper applies architecture-aware multicore optimizations to BWA-MEM and reports substantial kernel and end-to-end speedups on Intel Skylake. Its scope is bounded by kernel irregularity and limited benefits from SIMD-heavy architectures.
Problem
Sequence mapping accounts for more than 30% of GATK workflow time, creating a need to accelerate widely used BWA-MEM as sequencing data volumes increase.
Method
The paper performs end-to-end, architecture-aware optimization of BWA-MEM’s three key kernels for multicore systems while preserving identical output.
Results
Up to 3.5× and 2.4× end-to-end speedups over original BWA-MEM were achieved on single thread and single socket, respectively, on Intel Xeon Skylake.
Takeaways & Limitations
The implementation is intended as a seamless, output-identical replacement for BWA-MEM and is open sourced for users to benefit from increased performance.
Takeaways & Limitations
Irregular algorithms limit vectorization benefits, so processors relying heavily on SIMD can achieve only limited BWA-MEM performance.
Abstract
from arXiv · showhide
Innovations in Next-Generation Sequencing are enabling generation of DNA sequence data at ever faster rates and at very low cost. Large sequencing centers typically employ hundreds of such systems. Such high-throughput and low-cost generation of data underscores the need for commensurate acceleration in downstream computational analysis of the sequencing data. A fundamental step in downstream analysis is mapping of the reads to a long reference DNA sequence, such as a reference human genome. Sequence mapping is a compute-intensive step that accounts for more than 30% of the overall time of the GATK workflow. BWA-MEM is one of the most widely used tools for sequence mapping and has tens of thousands of users. In this work, we focus on accelerating BWA-MEM through an efficient architecture aware implementation, while maintaining identical output. The volume of data requires distributed computing environment, usually deploying multicore processors. Since the application can be easily parallelized for distributed memory systems, we focus on performance improvements on a single socket multicore processor. BWA-MEM run time is dominated by three kernels, collectively responsible for more than 85% of the overall compute time. We improved the performance of these kernels by 1) improving cache reuse, 2) simplifying the algorithms, 3) replacing small fragmented memory allocations with a few large contiguous ones, 4) software prefetching, and 5) SIMD utilization wherever applicable - and massive reorganization of the source code enabling these improvements. As a result, we achieved nearly 2x, 183x, and 8x speedups on the three kernels, respectively, resulting in up to 3.5x and 2.4x speedups on end-to-end compute time over the original BWA-MEM on single thread and single socket of Intel Xeon Skylake processor. To the best of our knowledge, this is the highest reported speedup over BWA-MEM.
1 Introduction
Rapid, inexpensive sequencing has intensified the need to accelerate read mapping, a compute-intensive stage of genomic analysis dominated by BWA-MEM. This work presents architecture-aware, output-preserving optimization for multicore systems, focusing on single-socket performance.
- More than 30% of the GATK best-practices workflow is spent on sequence mapping, which maps reads to reference sequences or genomes.
- BWA-MEM is a widely used short-read mapper with tens of thousands of users, and faster sequencing creates demand for commensurate mapping speedups.
- The study targets single-socket multicore performance because reads can be distributed across multiple sockets without usually encountering load imbalance.
- Three BWA-MEM kernels account for over 85% of total compute time, making their optimization central to preserving identical output while reducing runtime.
- 2×, 183×, and 8× speedups were achieved on the SMEM, SAL, and BSW kernels, respectively, using architecture-aware optimizations.
- Up to 3.5× single-thread and 2.4× single-socket speedups were achieved over original BWA-MEM on an Intel Xeon Skylake processor while maintaining identical output.
2 A Brief Overview of BWA-MEM
BWA-MEM maps short reads to long reference sequences through seed-and-extend processing, with SMEM, SAL, and BSW dominating runtime and serving as acceleration targets.
- 2.1 Short Read Sequence Mapping Problem: Sequence mapping finds the best matches of a short read Q in a long reference sequence R.Typical read lengths are 50–250 bases, while human reference sequences contain about 3 billion base-pairs.
- 2.2 Seed-and-Extend Method: Seed-and-extend first locates short seed matches, then extends them on both sides to identify and report the best alignments.BWA-MEM uses an FM-index during seeding and dynamic programming during extension.
- 2.3 BWA-MEM Algorithm: BWA-MEM searches for SMEMs, performs suffix-array lookups, chains nearby collinear seeds, and extends seeds with banded Smith-Waterman alignment.The workflow concludes by formatting alignment output in SAM format.
- 2.4 Break up of computation time spent: 86.5% and 85.7% of runtime is spent in SMEM, SAL, and BSW on the D1 and D4 datasets, respectively.These three kernels were therefore selected as acceleration targets.
- 2.5 Kernel Characteristics: Nearly 17 billion instructions are executed by SMEM for 60,000 reads, while SAL requires nearly 5000 instructions per lookup because of compressed indexes.SMEM is memory-latency bound, whereas BSW is instruction-bound because its irregular branching and short loops require scalar execution.
3 Modifications Applied to Entire Code
The implementation reorganizes read processing into batches and replaces fragmented allocation patterns with reusable contiguous buffers to improve parallelism, SIMD use, prefetching, and cache reuse.
- Workflow Reorganization: Reads are divided into batches, with each processing step applied across a batch before advancing to the next step.OpenMP dynamically distributes batches across threads instead of distributing individual reads with pthreads.
- Workflow Reorganization: Batch-wise processing enables SIMD parallelism across different reads, which is used for BSW.The reorganization exposes parallel work at the same algorithmic step across multiple reads.
- Memory Allocation: All required memory is allocated once in large contiguous blocks and reused across batches.This reduces frequent small allocations while improving hardware prefetching and cache reuse.
4 Optimizations Applied to SMEM and SAL
SMEM and SAL are optimized by changing FM-index and suffix-array representations, adding software prefetching, and replacing compressed suffix-array lookup with direct uncompressed access where memory permits.
- FM-index Representation: The compressed FM-index stores O in buckets of size η, reducing its entries to |R|/η while retaining counts and BWT substrings.The implementation uses the FM-index of the reference concatenated with its reverse complement for SMEM search.
- FM-index Representation: FM-index compression improves locality because longer matches produce shorter suffix-array intervals, increasing the chance that k and k+s share a cache line.The trade-off is raising per-base processing from O(1) to O(h).
- Software Prefetching: Software prefetching uses newly computed matching intervals to prefetch likely future Oc locations during SMEM extension.This addresses irregular accesses for which hardware prefetching is ineffective.
- Software Prefetching: Processing multiple queries in round-robin fashion was rejected because extra instructions outweighed the benefit of more completely hiding memory latency.The approach introduced many instructions because of the algorithm’s branching complexity.
- FM-index Representation: η is set to 32 so one Oc entry fits within a cache line and power-of-two indexing avoids expensive division and modulo operations.The design balances cache-line size, memory bandwidth, and BWT substring storage.
- Suffix Array Lookup: SAL returns reference coordinate j from suffix-array position i using j = S[i].The optimized implementation uses an uncompressed suffix array, requiring about 48 GB for the entire human genome, instead of compressed lookup.
5 Optimizations Applied to BSW
BSW extends seed alignments using a banded, early-terminating dynamic-programming matrix, creating limited intra-task parallelism. The paper therefore selects inter-task SIMD vectorization to exploit parallelism across sequence pairs.
- BSW computes alignment scores within a band around the main diagonal and can abort rows when scores become zero or sufficiently decline.
- Each BSW cell depends on three neighbors, so the implementation maintains only one row of each E, F, and H.The compact arrays remain in cache for smaller sequence pairs, making BSW compute bound.
- Intra-task vectorization is constrained by short sequences, band-limited computation, and possible band reduction during BSW.
- Inter-task vectorization assigns different sequence pairs to vector lanes, but irregular matrix sizes and computed-cell locations complicate performance extraction.
- Dependency among seeds within a read restricts seed-level parallelism, so the paper uses inter-task vectorization across reads.
5.3 Inter-Task Vectorization
The inter-task BSW design processes multiple sequence pairs simultaneously, while grouping similar workloads and reorganizing data to reduce vector inefficiency and memory-access overhead.
- Inter-task vectorization: W sequence pairs are processed at once, with each SIMD lane computing corresponding cells across the matrices.If one pair requires a cell, that cell is computed for every pair, causing wasteful computations.
- Inter-task vectorization: Figure 3 distinguishes banded cells, computed cells, and the currently computed cell Hij across a batch of sequence pairs.
- Inter-task vectorization: Radix sorting groups tasks with equal or similar sequence lengths to reduce waste from differing matrix dimensions.
- Inter-task vectorization: Parallelism is available across reads because seed dependencies restrict parallelism within a read, but varying seed counts can imbalance vector-lane work.Large batches could help dynamic allocation balance this work, but memory constraints limit batch size.
- Inter-task vectorization: AoS-to-SoA conversion enables vector loads of corresponding bases from W sequence pairs instead of gather operations.
- Inter-task vectorization: BSW uses 8-bit or 16-bit matrix implementations according to sequence length, increasing available vector lanes when narrower integers suffice.
6.1 Experimental Setup
The evaluation measures architecture-aware BWA-MEM optimizations on two Intel multicore generations using single-socket experiments and real sequencing datasets, while checking output identity.
- Experimental platforms: Experiments used one socket, with memory allocations forced to that socket; multithreaded runs used two threads per core.File I/O time was excluded from the reported results.
- Datasets: The workloads used the first half of the Hg38 human genome and five read datasets spanning prominent short-read lengths.Datasets D1 and D2 were obtained directly from the Broad Institute.
- Correctness: Every experiment verified output exactly identical to original BWA-MEM.
- Scope caveats: Benchmark results may vary because the tested software and workloads may be optimized for Intel microprocessors and system-specific configurations.
- Evaluation data: The evaluation includes system configuration and SMEM performance-counter tables, with Table 4 using 60,000 reads from D2 on a single SKX thread.
6.2 Performance Evaluation of Key Kernels On a Single Thread
Kernel-level evaluation shows that architecture-aware changes substantially accelerate SMEM, SAL, and BSW, while exposing limits from irregular computation and vectorization overhead.
- SMEM search using FM-index: 2× fewer instructions and nearly 3× fewer LLC misses with software prefetching produce a 2× SMEM speedup.Using bucket size η=32 and vectorization reduces instructions; software prefetching lowers memory latency at a small instruction-count cost.
- Suffix Array Lookup (SAL): 183× SAL speedup follows from nearly 200× fewer instructions per suffix-array offset despite increased LLC misses and memory latency.Further prefetching could improve SAL, but its optimized runtime is negligible in the full application.
- Banded Smith-Waterman: 13.85× fewer executed instructions in 8-bit BSW reflects the benefit of vectorization over the original scalar implementation.The optimized code has lower IPC because most instructions are SIMD instructions, while the original uses scalar ALU ports.
- Banded Smith-Waterman: Only 43% of optimized 8-bit BSW time computes the dynamic-programming matrix, while AoS-to-SoA conversion and cell-range adjustment consume the remainder.Inter-task vectorization computes wasteful cells, leaving only 21.5% of runtime for useful DP-matrix cells.
6.3 End-to-end Performance Evaluation on Single Socket
Integrating the optimized kernels preserves their benchmark speedups in BWA-MEM and delivers substantial end-to-end gains on single-socket Skylake and Haswell systems.
- Scaling with respect to the number of cores: Greater than 25× kernel scaling is reduced at the application level because unoptimized Misc components are memory-bandwidth bound and scale below 15×.Overall optimized-application scaling reaches 22× on D1 and 20× on D5 from 1 to 28 cores.
- Time to solution: 2.6×–3.5× single-thread and 1.7×–2.4× single-socket speedups are achieved on Skylake across five real datasets.On Haswell, the corresponding ranges are 2.3×–3.0× and 1.9×–2.7×.
- Time to solution: 14% more sequence pairs aligned on average reduces BSW application-level benefit compared with its isolated-kernel speedup.For D2 on Skylake, 13.5% more seed pairs produced nearly 1.43× more BSW time and a 1.47× loss of BSW speedup.
7 Related Work
Prior acceleration efforts typically target one BWA-MEM kernel on FPGAs or GPGPUs, whereas holistic multicore optimization with identical output remains unreported in the cited work.
- Prior accelerator approaches: Most prior approaches accelerate one kernel on GPGPUs or FPGAs and report 1.45×–2× overall speedups, excluding the four-FPGA approach.BSW-focused studies use intra-task parallelism because seeds within a read have dependencies.
- Prior accelerator approaches: Four FPGAs accelerate SAL and BSW by 2.8× and 5.7×, respectively, while host-side SMEM optimization reaches 1.7× and 2.6× overall speedup.The cited approach may produce output differing from BWA-MEM because it bypasses some BSW heuristics.
- FM-index optimization: Exact-search FM-index optimization has received more attention than the more intricate BWA-MEM mapping kernels.Most cited FM-index work targets the simpler exact search for full-query matches.
- BSW acceleration: Only a few studies target exact BSW because BWA-MEM differs from standard Smith-Waterman.Both intra-task and inter-task vectorization are established approaches for standard Smith-Waterman acceleration.
8 Conclusion and Future Work
The optimized multicore BWA-MEM implementation maintains identical output and achieves large kernel and application speedups, while remaining constrained by unoptimized components and limited SIMD suitability.
- Conclusion: 2×, 183×, and 8× speedups on SMEM, SAL, and BSW yield 3.5× single-thread and 2.4× single-socket gains on Skylake.The implementation is open sourced for seamless adoption by existing BWA-MEM users.
- Conclusion: Irregular SMEM and BSW algorithms limit vectorization gains, making SIMD-heavy processors less advantageous for BWA-MEM.SMEM is also partly memory-latency bound, while better gather support could help.
- Future Work: Future work targets the unoptimized application components, lower SMEM memory latency, and fewer SMEM and BSW instructions.These changes are intended to improve multicore scaling and overall application performance further.