betaFeedback

WorksComputer Science

In-depth data movement characterization of DNA read mapping algorithms

Abstract

Read mapping algorithms represent a critical bottleneck in genomic analysis pipelines due to the resources required; a problem that is becoming more pronounced as sequencing technologies advance and datasets expand. We present an extensive workload characterization of leading read mapping algorithms across diverse sequencing technologies to identify hardware acceleration and optimization opportunities. We analyzed the following implementations: MashMap, wfmash, and Minimap2 for whole-genome alignment (WGA); NGMLR, Minimap2, and LRA for long reads; and Bowtie2, BWA-MEM, StrobeAlign, and minibwa for short reads. We used the Intel VTune Profiler for detailed memory analysis to identify memory- bound functions, cache usage patterns, and data transfer bottlenecks. We further analyzed a selected subset of alignment tools using the DAMOV-SIM simulator to obtain a more granular view of data movement characteristics for two different cache structures. Based on our results, Minimap2 emerges as the fastest alignment tool for long read scenarios, but falls behind in whole-genome alignment due to poor multithreading. Across all three categories, some programs (e.g., LRA, BWA-MEM) are highly memory-bound. More in-depth analysis via DAMOV-SIM revealed that some memory-bound tools, in particular, do not fully utilize the multi-level cache hierarchy in modern multi-core CPU architectures. Our results show that while some tools require algorithmic redesign for performance gains, some others can benefit from running on PIM architectures.

Introduction

High-throughput sequencing (HTS) technologies revolutionized genomics by offering large-scale, affordable, and accurate sequencing of entire genomes. Read mapping is the process of aligning sequencing data to a reference genome. However, the massive amount of data produced by modern sequencers poses a significant computational challenge for read mapping. Even after decades of progress, read mapping remains a bottleneck in many genomic pipelines due to its resource intensiveness and growing algorithmic complexity. A key reason read mapping remains a resource-intensive workload is the cost of moving data between memory and processor cores, which creates a data movement bottleneck. This problem is heightened by large search spaces and irregular memory access patterns inherent to genome alignment. Processing-in-memory (PIM) architectures emerged as a promising solution to the data movement bottleneck [1]. PIM architectures can drastically reduce the latency costs associated with transferring data between memory and the CPU by integrating the two, placing computational logic directly within memory units [2]. While prior work such as [3] demonstrated the potential of PIM for accelerating data-intensive workloads, or even more specifically, read mappers [4], and Appuswamy et al. [5] analyzed sequence aligners from a microarchitectural perspective; their analysis was limited to single-core performance. There still remains a lack of detailed workload characterization of read mappers that takes multi-core performance and data movement patterns into account. Such an analysis would highlight how current algorithms could be adapted

Supplementary Materials

to leverage this paradigm and aid the development of future algorithms that account for data movement.

In this study, we aim to bridge this gap by conducting a comprehensive workload characterization of widely used alignment tools. Our goal is to understand which components of current algorithms are most constrained by memory access and data movement and to assess them as candidates for future PIM acceleration. To this end, we profile alignment tools across three categories: whole genome aligners, long read aligners, and short read aligners.

Whole genome aligners are represented by minimap2 [6], mashmap [7], and wfmash [8, 9, 10]; long read aligners by NGMLR [11], minimap2 [6], and LRA [12]; and short read aligners by BWA-MEM [13], bowtie2 [14], StrobeAlign [15] and minibwa [16].

We follow a two-phase approach: we first perform performance profiling with Intel VTune, and if the tool indicates a moderate to high percentage of memory-bound components, we follow up with DAMOV-SIM [17] for further analysis.

Methods

Analyzed tools

We analyze the following DNA read mapping tools:

  • Whole genome alignment (WGA): minimap2 [6], mashmap [7], wfmash [8, 9, 10]

  • Long read alignment: NGMLR [11], minimap2 [6], LRA [12]

  • Short read alignment: BWA-MEM [13], bowtie2 [14], StrobeAlign [15], minibwa [16]

See the Supplementary Material for the program versions and commands used to invoke the tools.

Top-down analysis

We use Intel VTune’s memory access mode to characterize a given program’s data movement patterns. VTune is a profiler utilizing performance counters on Intel CPUs to report a hardware-based performance characterization, using a technique called top-down performance analysis, first proposed by Yasin [18].

This analysis method classifies the time spent on each pipeline slot of a superscalar x86 CPU as follows [18]:

  1. Frontend bound: This category denotes any pipeline stalls while instructions are being fetched, parsed, or decoded into micro-operations (μ\muOps).

  2. Bad speculation: This category denotes μ\muOps that are flushed out of the pipeline due to branch misprediction.

  3. Backend bound: This category denotes μ\muOps that are not accepted to the “back end” of the pipeline due to resource constraints. The two constraints most relevant to our analysis are the following: a. Memory bound: The CPU does not process the μ\muOp on the current clock cycle since the operands have not arrived from the memory yet. b. Core bound: The CPU cannot process the μ\muOp since all the ALUs are currently busy processing other μ\muOps.

  4. Retiring: This category denotes μ\muOps that the CPU finished processing and are being “retired”. A high percentage of retired operations indicates that the workload utilizes the CPU efficiently and achieves throughput close to the theoretical maximum for the given processor.

Given our characterization’s focus on data movement, we are most concerned with the memory-boundness percentage for the entire workload and for each function. We use these metrics to select memory-bound functions in the target tools for further analysis using DAMOV-SIM. We use the same threshold as the DAMOV [17] benchmark suite: we consider functions that take at least 3% of total CPU time and are at least 30% memory-bound.

Function-level in-depth analysis

To understand the data-movement characteristics of specific, critical functions, we use the DAMOV-SIM simulator in the DAMOV benchmark suite. DAMOV-SIM combines the Zsim x86 simulator with Ramulator, a memory simulator capable of simulating a diverse array of memory and cache configurations. We chose to use DAMOV-SIM for the function-level analysis because simulating all memory accesses provides a cleaner view of the data movement patterns of a given function, without the influence of other processes running on the test system or of parts of the workload we are not interested in. Furthermore, DAMOV-SIM allows us to experiment with different cache hierarchy configurations to see whether they alleviate data movement bottlenecks, as well as to simulate configurations with more CPU cores than the host system, thanks to Zsim.

To simulate how different cache hierarchy configurations affect the performance of a given function, we test two different cache hierarchy configurations as shown in Figure 1: a “host” configuration where each core has private L1 and L2 caches, but shares an L3 cache across all cores, and a “PIM” configuration where each core only has a private L1 cache. This allows us to observe cases where the given workload does not efficiently utilize higher levels of cache memory. However, the “PIM” configuration does not account for possible limitations of real PIM systems, such as a limited instruction set, lower clock speed, and limited communication between DRAM processing units (DPUs) in some processing-near-memory implementations.

Figure 1. The memory hierarchy configurations simulated by DAMOV-SIM.

The impact of these limitations should be investigated separately for a specific accelerator design.

Results

Whole genome alignment

We analyzed minimap2, mashmap, and wfmash’s performance while mapping CHM13 and HG002 reads to the hg38 reference. We observe the end-to-end performance of each tool using 8, 16, 32, and 64 threads. Detailed hardware and software specifications of the test system are listed in the Supplementary Material.

As shown in Table 1, the three whole-genome aligners exhibit varying degrees of parallelism at the same thread counts, leading to discrepancies in wall-clock times. The overall microarchitecture utilization of each tool is available in Table 2. We give more details on each program’s performance in its respective subsection.

Program nameRetiringCore BoundMemory BoundFront-end BoundBad Speculation
minimap248.9%16.9%19.1%5.4%10.7%
mashmap23.3%5.8%16.1%24.5%30.2%
wfmash32.6%12%53.4%5.5%0%

Table 2. Microarchitecture utilization metrics obtained from each whole genome aligner, using the hg38 vs. CHM13 dataset with 64 threads.

Program namehg38 vs. CHM13hg38 vs. hg002
(a) 8 threads
minimap22.37×10132.37 \times10^{13} (5008.33s)1.86×10131.86 \times10^{13} (3828.65s)
mashmap9.11×10139.11 \times10^{13} (6637.91s)7.84×10137.84 \times10^{13} (6416.57s)
wfmash4.80×10134.80 \times10^{13} (2480.27s)6×10136 \times10^{13} (3116.45s)
(b) 64 threads
minimap22.56×10132.56 \times10^{13} (5069.33s)2.07×10132.07 \times10^{13} (3880.22s)
mashmap9.26×10139.26 \times10^{13} (3006.44s)8.49×10138.49 \times10^{13} (2990.88s)
wfmash8.9×10138.9 \times10^{13} (1004.52s)1.2×10141.2 \times10^{14} (1235.45s)

Table 1. Number of total elapsed clockticks and CPU wall clock time for each whole genome aligner program.

We observe that while minimap2 executes the fewest total instructions, it does not fully use all the hardware threads available to it, regardless of the number of cores in a given machine. This lack of parallelism causes minimap2 to run slower than other whole-genome aligners on systems with many cores.

minimap2

The most significant performance issue we observe with minimap2 in whole genome alignment scenarios is a lack of parallelism, which prevents the program from scaling with the available CPU count, as is apparent in the core usage histogram in Figure 2, where it spends 67% of the CPU time utilizing only a single logical core.

Figure 2. Logical core usage histogram for minimap2 on hg38 vs. CHM13 when the program is instructed to use 96 threads.

Despite this lack of parallelism, minimap2 appears to be less bound by microarchitectural inefficiencies than the other two programs, with approximately 49% of pipeline slots used to successfully retire instructions. The function

ksw_extd2_sse41, which minimap2 uses for banded Smith-Waterman alignment, takes 26.4% of total CPU time and uses 82.1% of pipeline slots for retiring instructions. As the name suggests, this function also uses the SSE4.1 SIMD extension for instruction-level parallelism. Since the scope of this work is to analyze how these tools perform in a server environment, we did not run tests with fewer than 8 threads. Therefore, it is possible that minimap2 is more suited for whole genome alignment on environments with few threads available.

mashmap

We observe that mashmap can meaningfully use up to 24 hardware threads on our server, which explains why it takes less wall-clock time than minimap2 as the thread count increases. We observe an abnormally high percentage of CPU pipeline stalls due to bad speculation and frontend-bound latency, suggesting unpredictable branching patterns in the mashmap codebase. As seen in Table 3, this issue affects all functions that consume significant CPU time, thereby negatively affecting the cycles-per-instruction (CPI) metric. We do not perform any function-level data movement analysis on mashmap because none of the functions that take more than 3% of CPU time are noticeably memory-bound, possibly due to the branch misprediction issue.

Function nameCPU%CPIRetiringFEBSMEMCORE
std::map<uint32_t, SlideMapper>::operator[]30.9%1.5713.4%33.1%36%14.8%2.7%
SlideMapper::insert ref26.8%1.3516.2%30.2%40.8%10.6%2.2%
Map::computeL2MappedRegions14.2%1.4415%24.7%35.1%21.8%3.4%
std::_Rb_tree::erase6.6%1.5812.7%31.1%41%11.8%3.4%
Map::mergeMappings3.3%1.0213.5%4.9%10.7%17.1%53.8%

Table 3. Microarchitecture utilization metrics of the top five functions in mashmap (hg38 vs. CHM13 dataset, 64 threads). CPU%: Percentage of total time spent executing the given function, CPI: Clock cycles per executed instruction, FE: Front-end bound, BS: Bad speculation, MEM: Memory-bound, CORE: Core bound.

wfmash

During our testing, we found wfmash to be consistently the fastest whole genome alignment program among the three we tested. However, it is also very memory-bound, with 53.4% of pipeline slots wasted. Examining the memory-bound functions, we observe that an I/O function (progress_meter::increment) is extremely memory-bound (97.9%) and has an average CPI of 82.9. We would like to note that at the time of writing, there is no method (documented or otherwise) to disable the progress meter or otherwise alter the verbosity of the program’s output without modifying the source code. The second function of interest is wavefront_compute_affine2p_idm, which is a wavefront alignment computation function from WFA2-lib [9, 10].

Long read alignment

As with whole-genome alignment, we observe that the input size does not meaningfully affect the program’s overall performance. We provide results for the VTune analyses using the full SRR1304331 dataset, and for the DAMOV-SIM analyses, we use a randomly sampled subset of 10,000 reads. We shrink the dataset for DAMOV-SIM because the simulation-based approach is orders of magnitude slower than the VTune event counter approach.

As seen in Table 4, unlike in the whole genome alignment scenario, all three programs we tested can benefit from increasing the thread count (except LRA, which could not parallelize beyond 24 threads, as reported by VTune). NGMLR was an order of magnitude slower compared to the other tools when all tools were constrained to 8 threads. However, the gap shrank to NGMLR being approximately 4× slower than the competition at a thread count of 64.

Program name8 threads16 threads32 threads64 threads
ngmlr4.36×10134.36 \times10^{13} (2250.10s)4.25×10134.25 \times10^{13} (1222.22s)4.19×10134.19 \times10^{13} (721.673s)4.74×10134.74 \times10^{13} (483.64s)
minimap24.33×10124.33 \times10^{12} (283.72s)4.32×10124.32 \times10^{12} (188.77s)4.73×10124.73 \times10^{12} (151.54s)5.27×10125.27 \times10^{12} (135.93s)
lra6.53×10126.53 \times10^{12} (368.10s)6.82×10126.82 \times10^{12} (226.57s)7.08×10127.08 \times10^{12} (180.33s)7.28×10127.28 \times10^{12} (186.13s)

Table 4. Number of total elapsed clockticks and CPU wall clock time for each long read aligner program.

NGMLR

NGMLR was measured to be the slowest of the three long read aligners we have tested. We hypothesize that this is due to the algorithm NGMLR uses being more sensitive compared to the other aligners. The program executed 1.24×10141.24 \times10^{14} instructions for the same dataset and thread count (SRR1304331, 64 threads) compared to minimap2’s 8×10128 \times10^{12} instructions.

We did not observe an overall inefficiency in microarchitecture utilization, since both the entire program and the functions that took the most time had a high percentage of retiring pipeline slots (> 70%, see Table 5).

Function nameCPU%CPIRetiringFEBSMEMCORE
AlignmentBuffer::cLIS49.7%0.3186.4%4.6%6.0%0.6%2.4%
Convex::fwdFillMatrixSSESimple16.9%0.471.9%4.8%12%2.7%8.6%
Convex::getDirection4.5%0.3577.2%6.1%9.4%1.9%5.4%
CS::AddLocationStd4.3%0.9735.8%3.2%10.7%40.1%10.2%
RefEntry::getRealLocation2.6%9.623.3%0.5%0.2%93.8%2.2%

Table 5. Microarchitecture utilization metrics of the top five functions in ngmlr (SRR1304331, 64 threads).

Further inspecting the function-by-function breakdown of execution time on Table 5, we spot CS::AddLocationStd and RefEntry::getRealLocation as highly memory-bound functions. The second function, in particular, has an abnormally high CPI and is 93.8% memory-bound.

Searching the NGMLR source code for the function RefEntry::getRealLocation reveals that it is a one-liner that adds an offset to a field in a Location struct. Based on this information, we suggest that NGMLR use prefetching, either by reorganizing the data layout to be more cache-friendly on the CPU or by using hardware-software co-design to implement a prefetcher for the Location data CPU%: Percentage of total time spent executing the given function, CPI: Clock cycles per instruction, FE: Front-end bound, BS: Bad speculation, MEM: Memory-bound, CORE: Core bound.

structure to avoid memory latency. Another hardware-based method for latency reduction would be to use a processing-in-memory framework, such as Ambit [19] or ComputeDRAM [20] (which runs on off-the-shelf DRAM), to perform this simple calculation on the DRAM chip itself rather than moving the data between the CPU and system memory.

minimap2

minimap2 was the fastest out of the three long read aligners we tested. Unlike whole-genome alignment tests, the program did not suffer as much from poor parallelization, and its retiring pipeline slot rate was similar to that in the whole-genome alignment scenario (49.3%).

CPU%: Percentage of total time spent executing the given function, CPI: Clock cycles per instruction, FE: Front-end bound, BS: Bad speculation, MEM: Memory-bound, CORE: Core bound.

Inspecting Table 6, we see that ksw_extd2_sse41 still takes most of the execution time and does not exhibit any apparent microarchitectural inefficiencies. The functions mm_idx_get and collect_seed_hits both suffer from high CPI due to memory-bound latency, warranting further analysis using DAMOV-SIM.

Function nameCPU%CPIRetiringFEBSMEMCORE
ksw_extd2_sse4170.9%0.5258.7%2.4%1.5%13.7%23.7%
rs_sort_128x5.5%0.6443.2%4.6%13.7%22.3%16.2%
mm_sketch3.8%0.548.3%6.4%31.7%2.9%10.7%
mm_idx_get3.7%17.61.8%0.5%1.3%91.3%5.1%
collect_seed_hits2.6%2.3911.1%6.5%9%55.6%17.1%

Table 6. Microarchitecture utilization metrics of the top five functions in minimap2 (SRR1304331, 64 threads).

Upon further analysis using DAMOV-SIM, we observe that both functions exhibit increasing LFMR (last-to-first cache miss ratio) as thread size increases under the “host” configuration (see Table 7a). This alludes to the last level of the cache hierarchy becoming less useful as the core count increases, where checking and repopulating L3 cache entries becomes an architectural burden on the simulated system. Specifically for mm_idx_get, these cache misses cause the instructions per cycle (IPC) metric to stall at around 30 for thread counts ≥64\ge64. (DAMOV-SIM’s IPC calculation method is different from VTune’s CPI calculation, which means that the ideal IPC for DAMOV-SIM is equal to the core count.) We rerun the DAMOV-SIM experiments using the simpler “PIM” cache configuration and observe a slight improvement in the IPC metric, as seen in Table 7b. This shows that a multi-level, general-purpose cache configuration causes latency issues as thread counts increase, rather than closing the speed gap between the CPU and RAM.

(a) Host configuration
ThreadsIPCL1 Miss RatesLFMR
L2L3
11.3924.1%61.9%14.2%0.09
45.1624.1%62.2%25.5%0.174
1616.624.1%62.5%56.4%0.386
6430.524.4%72.5%96.1%0.741
12831.224.7%84.6%96.0%0.838
25628.226.3%91.9%95.0%0.887
(b) PIM configuration
ThreadsIPCL1 Miss Rate
11.2124.1%
44.5424.1%
1615.124.1%
6429.524.1%
12833.824.2%
25634.125.4%

Table 7. Cache statistics obtained via DAMOV-SIM for the mm_idx_get function of minimap2

LRA

While running LRA for long read alignment, the function CompareLists<GenomeTuple, uint64_t> took the most time to execute, taking 27.1% of the execution time. This function had an abnormally high CPI of 11.2 and was 81% memory-bound. LRA also suffers the most from microarchitectural inefficiencies across the entire program, with the lowest retiring-pipeline-slot rate among the long read aligners at 27%.

We further analyzed CompareLists using DAMOV-SIM, revealing a less pronounced variant of the pattern observed in minimap2’s memory-bottlenecked functions as seen on Table 8. The L1 cache miss rate stabilizes at approximately 18% for multi-core experiments on the “host” configuration, while the L3 cache miss rate (shared across cores) continues to climb as the core count increases. Meanwhile, the L2 miss rate decreases slightly, suggesting an issue with the shared nature of the last-level cache. These problems cause the IPC value to stall between 1.98 and 2.32 in the multi-core experiments, consistent with the limited parallelism we observed in the VTune results.

ThreadsIPCMiss RatesLFMR
L1L2L3
10.56722.7%49.4%51.5%0.373
41.9918.5%46.1%63.3%0.420
162.3218.4%45.2%65.2%0.430
642.2418.2%46.5%73.2%0.491
1282.2318.7%43.9%73.4%0.478

Table 8. Cache statistics obtained via DAMOV-SIM for the CompareLists function of lra.

Short read alignment

We test four short-read alignment programs: StrobeAlign, bowtie2, BWA-MEM, and minibwa. We used several reads from the CHM1 dataset (Eichler-CHM1htert.1 500 library25) with SRA IDs SRR1514950-1514952 to analyze all three aligners. The read sets are pair-ended, each averaging 43G bases and providing a fold coverage of 41×. We let all three programs construct indexes of the reference prior to the performance measurements.

As seen in Table 9, StrobeAlign is the fastest among the short read mappers we have tested, followed by minibwa, except for the runs using 32 threads, where minibwa is faster than StrobeAlign. We further observe that, based on the microarchitecture utilization metrics shown in Table 10, StrobeAlign has the highest percentage of retiring pipeline slots, closely followed by minibwa. Bowtie2 and BWA-MEM have similar retirement rates; however, BWA-MEM is overall more memory-bound, with a 45.6% memory-boundness rate.

Program nameRetiringCore BoundMemory BoundFront-end BoundBad Speculation
strobealign42%10.6%23.3%10.2%13.9%
bowtie234.8%16.4%31.8%10.2%6.8%
bwa-mem35.1%8.5%45.6%3.9%6.8%
minibwa41.9%19.0%22.8%7.0%9.3%

Table 10. Microarchitecture utilization metrics obtained from each short-read aligner (SRR1514950, 64 threads).

Program name8 threads16 threads32 threads64 threads
strobealign7.83×10137.83 \times10^{13} (3.97 ×10−3\times10^{-3}s)7.99×10127.99 \times10^{12} (2.10 ×10−3\times10^{-3}s)8.41×10138.41 \times10^{13} (2.04 ×10−3\times10^{-3}s)4.43×10134.43 \times10^{13} (1.44 ×10−3\times10^{-3}s)
bowtie23.41×10143.41 \times10^{14} (1.91 ×104\times10^{4}s)3.64×10143.64 \times10^{14} (1.01 ×104\times10^{4}s)3.70×10143.70 \times10^{14} (5.16 ×103\times10^{3}s)4.57×10144.57 \times10^{14} (3.02 ×103\times10^{3}s)
bwa-mem3.81×10143.81 \times10^{14} (2.24 ×104\times10^{4}s)3.98×10143.98 \times10^{14} (1.17 ×104\times10^{4}s)4.32×10144.32 \times10^{14} (6.12 ×103\times10^{3}s)4.43×10144.43 \times10^{14} (4.59 ×103\times10^{3}s)
minibwa8.28×10138.28 \times10^{13} (4.18 ×103\times10^{3}s)8.14×10138.14 \times10^{13} (2.42 ×103\times10^{3}s)1×10141 \times10^{14} (1.58 ×103\times10^{3}s)7.98×10137.98 \times10^{13} (2.23 ×103\times10^{3}s)

Table 9. Number of total elapsed clockticks and CPU wall clock time for each short-read aligner program (average of SRR1514{[}950,951,952{]}).

StrobeAlign

We observe diminishing returns in StrobeAlign’s performance at thread counts above 16. On our test machine with four 14-core processors with hyperthreading, using more than 28 threads requires spreading them across multiple processors. This might incur additional memory-bound delays during execution due to non-uniform memory access (NUMA), where requested data may reside on a different core and require additional data movement.

CPU%: Percentage of total time spent executing the given function, CPI: Clock cycles per instruction, FE: Front-end bound, BS: Bad speculation, MEM: Memory-bound, CORE: Core bound.

Investigating the profiler data for StrobeAlign reveals that the experiments using more than 8 CPU threads report a high overall percentage of remote memory accesses, which contributes to the high memory boundness percentage of the StrobermerIndex::get_masked_from function, as seen in Table 11. At low thread counts, pinning StrobeAlign’s CPU and memory usage to a single NUMA node reduces overall memory boundness but does not yield a significant decrease in execution time.

Function nameCPU%CPIRetiringFEBSMEMCORE
sw_sse2_byte26.1%0.3471.7%8.9%11.1%1.0%7.2%
StrobermerIndex::get_masked_from15.9%5.30343.4%2.0%9.9%78.7%5.0%
ssw_align6.1%0.39469.3%7.6%12.6%1.6%8.9%
mem::searcher5.8%1.08224.1%9.3%45.5%12.0%9.1%
get_nam::by_chaining5.5%0.57744.1%11.3%18.9%12.6%13.1%

Table 11. Microarchitecture utilization metrics of the top five functions in StrobeAlign (SRR1514950, 64 threads).

Bowtie2

We observe that the functions SideLocus::initFromRow and AlignmentCache::addOnTheFlyImpl are memory-bound in Bowtie2, as seen in Table 13. Hotspot analysis

Function nameCPU%CPIRetiringFEBSMEMCORE
SwAligner::alignNucleotidesEnd2EndSseU811.3%0.46663.4%8.6%7.8%8.5%11.6%
SideLocus::initFromRow9.9%4.676.6%4.3%11.0%54.4%23.8%
AlignmentCache::addOnTheFlyImpl5.9%1.07817.4%0.5%2.7%42.7%36.6%
__mm_max_epu84.4%0.37674.3%8.0%4.3%5.6%7.8%
__mm_subs_epu84.1%0.37973.2%8.2%0.5%7.7%10.4%

Table 13. Microarchitecture utilization metrics of the top five functions in Bowtie2 (SRR1514950, 64 threads). CPU%: Percentage of total time spent executing the given function, CPI: Clock cycles per instruction, FE: Front-end bound, BS: Bad speculation, MEM: Memory-bound, CORE: Core bound.

Thread countPinned?RemoteMEMTime (s)
8No54.3%18.1%3938
8Yes1.8%14.1%3876
14No70.9%21.6%2623
14Yes3.6%14.5%2504

Table 12. Effect of pinning StrobeAlign to a single NUMA node in low thread counts (SRR1514950). Remote: Remote memory access percentage, MEM: Overall memory boundness, Time: Wall clock time

on SideLocus::initFromRow reveals that the memory boundness of this function is caused by calls to __builtin_prefetch. Disabling prefetching inside this function reduces the function’s memory boundness but does not meaningfully affect overall memory boundness or execution time.

BWA-MEM
Function nameCPU%CPIRetiringFEBSMEMCORE
bwt_sa23.6%4.367.2%1.4%3.4%83.6%4.4%
bwt_occ415.9%1.6317.4%0.6%3.4%71.9%6.7%
ksw_extend215.5%0.4476.4%2.7%10.3%2.3%8.3%
ksw_u810.8%0.3475.8%4.9%4.9%1.6%12.7%
bwt_2occ48.7%1.75114.4%1.0%6.9%73.6%4.0%

Table 14. Microarchitecture utilization metrics of the top five functions in BWA-MEM (SRR1514950, 64 threads). CPU%: Percentage of total time spent executing the given function, CPI: Clock cycles per instruction, FE: Front-end bound, BS: Bad speculation, MEM: Memory-bound, CORE: Core bound.

We identify two target functions in BWA-MEM for in-depth analysis: bwt_sa, used for suffix array lookup; and ksw_extend2, which is used for the banded Smith-Waterman alignment algorithm. We switch to using reads simulated from C. elegans for the function-level performance characterization, since the simulator-based workflow is orders of magnitude slower than VTune. We simulate reads using art_illumina [21], generating pair-end reads that are 150 bp on average with 2×2 \times coverage. We use GCF_000002985.6_WBcel235 as our reference. As seen on Table 15a, bwt_sa also suffers from last-level-cache induced latency and its IPC starts to plateau as we increase the thread count. Upon switching to the simpler “PIM” cache layout (see Table 15b and Figure 3), we see a remarkable increase in IPC for high thread counts, which also points to L3 cache contention causing latency problems for BWA-MEM. These findings are consistent with previous literature. Daib et al. [4] observed that a system with lower thread count but a bigger L3 cache was more performant compared to a similar system with more CPU cores but a smaller L3 cache.

ThreadsIPCL1L2L3LFMR
(a) Host configuration
11.6310.1%54.3%70.2%0.388
44.6810.2%55.4%68.5%0.392
1624.710.7%54.3%70.0%0.393
6443.910.3%56.5%72.9%0.428
12855.110.5%60.4%75.1%0.474
(b) PIM configuration
11.6610.4%
46.4010.5%
1624.810.9%
6480.010.6%
12812510.7%

Table 15. Cache statistics obtained via DAMOV-SIM for the bwt_sa function of BWA-MEM, using the “host” cache layout

Figure 3. IPC comparison for bwt_sa, under the “host” and “PIM” configurations of DAMOV-SIM

minibwa

minibwa [16] is a short read mapper that improves upon BWA-MEM by combining the seeding step from BWA-MEM2 with the seed extension and alignment steps from minimap2. We observe that these design changes translate into improved performance compared to both the original BWA-MEM and Bowtie2. In particular, the batched suffix array lookup function mb_bwt_sa_batch is approximately 0.6×0.6 \times as memory-bound as its counterpart in BWA-MEM

Function nameCPU%CPIRetiringFEBSMEMCORE
ksw_extd2_sse32.6%0.5055.3%7.9%9.9%8.0%18.8%
mb_bwt.sa_batch10.5%1.47817.7%3.0%8.9%48.4%22.0%
ksw_ll_u8_core7.4%0.36353.7%3.2%6.4%4.6%32.0%
mb_bwt.rank1a7.3%0.65341.3%2.4%2.5%32.9%20.9%
mb_bwt.smem_batch5.6%0.94428.9%5.2%27.4%13.7%24.8%

Table 16. Microarchitecture utilization metrics of the top five functions in minibwa (SRR1514950, 64 threads).

CPU%: Percentage of total time spent executing the given function, CPI: Clock cycles per instruction, FE: Front-end bound, BS: Bad speculation, MEM: Memory-bound, CORE: Core bound.

(bwt_sa). This contributes to a reduced overall memory boundness percentage and to less time spent on suffix array lookups.

Conclusions and future work

The aim of this study is to analyze the performance and data movement characteristics of DNA read mapping tools as the programs scale to higher thread counts. To achieve this, we profiled nine tools across three read mapping categories and collected their microarchitecture utilization metrics. We further analyzed specific memory-bound functions using a simulation-based workflow to observe their cache utilization patterns in detail.

We observe that microarchitectural inefficiencies, including memory-bound functions, and poor parallelism are the main culprits of poor performance across whole genome, long read, and short read alignment tools. We combine results from both real server-grade hardware and in-depth memory and CPU simulations to reveal that DNA read mapping tools are likely to suffer from memory-related bottlenecks due to L3 cache contention, with LRA and BWA-MEM being the most prominent examples. We hypothesize that such bottlenecks can be alleviated by offloading memory-intensive parts of these programs onto accelerator circuitry closer to system memory, thereby avoiding data movement bottlenecks.

The scope of our experiments was limited to highly-parallelized, server-grade systems. As we noted in Section 3.1.1, tools like minimap2 could prove to be more efficient for systems with very limited core counts, since the program is highly vectorized and does not utilize many CPU cores during whole genome alignment. We also came across obstacles while performing function-level analysis on mashmap and NGMLR due to some bugs in Zsim. Since improving the DAMOV-SIM simulator was out of the scope of this article, we did not fully investigate the Zsim or Ramulator codebases. Future work could improve upon the DAMOV-SIM workflow by augmenting or replacing the DRAM and CPU simulators with their more up-to-date counterparts.

Conflicts of Interest

C. Alkan is a co-founder of Lidya Genomics.

Acknowledgments

This work was supported by the European Union’s Horizon Programme for Research and Innovation under grant agreement No. 101047160 (Project BioPIM).

Supplementary Materials

Test environment

Program versions

  • minimap2: 2.26-r1175

  • mashmap: v2.0

  • wfmash: v0.24.1

  • NGMLR: 0.2.7

  • LRA: 1.3.5

  • BWA-MEM: 0.7.17

  • bowtie2: 2.5.1

  • StrobeAlign: v0.17.1

  • minibwa: 0.3 (r391)

  • Analysis tools:

    • VTune: 2025.0

    • DAMOV-SIM: Latest release modified for compatibility with later Ubuntu versions. Available at https://github.com/biopim/DAMOV

Server specifications

  • 4×Intel(R) Xeon(R) CPU E7-4850 v3 @ 2.20GHz

    • Number of cores: 14

    • Number of hyperthreads: 28

    • Supported SIMD extensions: mmx, sse, sse2, sse3, ssse3, sse4.1, sse4.2, avx, avx2

  • 1 TB system memory

  • Operating system: Ubuntu 22.04

    • Kernel version: 5.15.0-131-generic

Program invocations

Whole genome alignment

minimap2
sudo /opt/intel/oneapi/vtune/latest/bin64/vtune -collect memory-access -data-limit=20000 \
/mnt/compgen/inhouse/bin/minimap2 -ax asm5 -t ${SLURM_CPUS_PER_TASK} ${GRCh38} ${QUERY_FILE} \
> ${OUTPUT_DIR}/${TOOL_NAME}_grch38_${QUERY_FILENAME}_t${SLURM_CPUS_PER_TASK}.sam
mashmap
sudo /opt/intel/oneapi/vtune/latest/bin64/vtune -collect memory-access -data-limit=20000 \
/mnt/compgen/inhouse/bin/mashmap -t ${SLURM_CPUS_PER_TASK} -r ${GRCh38} -q ${QUERY_FILE} \
-o ${OUTPUT_DIR}/mashmap_grch38_${QUERY_FILENAME}_t${SLURM_CPUS_PER_TASK}.mashmapout \
> ${OUTPUT_DIR}/mashmap_grch38_${QUERY_FILENAME}_t${SLURM_CPUS_PER_TASK}.stdout
wfmash
sudo ${VTUNE_CMD} -collect memory-access -result-dir \
${VTUNE_OUT} -data-limit=100000 \
wfmash ${GRCh38} ${QUERY_FILE} \
-p 99 --threads ${SLURM_CPUS_PER_TASK} \
> ${OUTPUT_DIR}/${EXPERIMENT_NAME}.paf

Long read alignment

NGMLR
zcat /mnt/storage1/projects/human-cell-lines/chm1/pacbio/fastq/SRR1304331.fastq.gz | \
sudo /opt/intel/oneapi/vtune/latest/bin64/vtune -collect \
memory-access -data-limit=20000 ./ngmlr-0.2.7/ngmlr -t 8 -r \
/mnt/compgen/inhouse/share/rg_annot/b38/human_v38.fasta -q \
/dev/stdin -o ./vtune_sam_outputs/ngmlr_fulldataset_t8.sam > \
./biopim/vtune-reports/memory-access/vtune-ngmlr-t8-human-SRR31-memory-access.txt
minimap2
zcat /mnt/storage1/projects/human-cell-lines/chm1/pacbio/fastq/SRR1304331.fastq.gz | \
sudo /opt/intel/oneapi/vtune/latest/bin64/vtune -collect memory-access \
./minimap2/minimap2 -ax map-pb -t 8 \
/mnt/compgen/inhouse/share/rg_annot/b38/human_v38.fasta /dev/stdin > \
./vtune_sam_outputs/minimap2_fulldataset_t8.sam
LRA
zcat /mnt/storage1/projects/human-cell-lines/chm1/pacbio/fastq/SRR1304331.fastq.gz | \
sudo /opt/intel/oneapi/vtune/latest/bin64/vtune -collect memory-access \
/mnt/compgen/inhouse/bin/lra align -CLR \
/mnt/compgen/inhouse/share/rg_annot/b38/human_v38.fasta \
/dev/stdin -t 8 -p s > ./vtune_sam_outputs/lra_fulldataset_t8.sam

Short read alignment

BWA-MEM
PIM_ROOT/bwa-0.7.17/bwa mem -t THREADS \
PIM_ROOT/../data/celegans/GCF_000002985.6_WBcel235_genomic.fna.gz \
PIM_ROOT/../data/celegans/paired_dat1.fq.gz \
PIM_ROOT/../data/celegans/paired_dat2.fq.gz -o \
PIM_ROOT/../data/celegans/paired_THREADS.sam
Bowtie2
/home/bsahin/DAMOV/workloads/bowtie2-2.5.4/bowtie2 "-x" \ "./data/chm1_reads/CHM1_1.1" "-1" \
"./data/chm1_reads/SRR1514950_CHM1_Illumina_WGS_UW__1.fastq.gz" \
"-2" "./data/chm1_reads/SRR1514950_CHM1_Illumina_WGS_UW__2.fastq.gz" \
"-p" "64" "-t" "--met-file" "workloads/bowtie2-2.5.4/chm1_metrics.log" "-S" "/dev/null"
StrobeAlign
sudo /opt/intel/oneapi/vtune/latest/bin64/vtune -collect memory-access -data-limit=20000 \
${STROBEALIGN}$ --use-index -t ${SLURM_CPUS_PER_TASK} ${CHM1} ${QUERY1} ${QUERY2} > \
${OUTPUT_DIR}/${TOOL_NAME}_chm1_${QUERY_FILENAME}_t${SLURM_CPUS_PER_TASK}.sam
minibwa
sudo /opt/intel/oneapi/vtune/latest/bin64/vtune -collect memory-access -data-limit=20000 \
${MINIBWA} mem -t ${SLURM_CPUS_PER_TASK} ${CHM1} ${QUERY1} ${QUERY2} -p -o \
${OUTPUT_DIR}/${TOOL_NAME}_chm1_${QUERY_FILENAME}_t${SLURM_CPUS_PER_TASK}.sam

References

  1. [1]Onur Mutlu, Saugata Ghose, Juan Gómez-Luna, and Rachata Ausavarungnirun. A Modern Primer on Processing in Memory. In Mohamed M. Sabry Aly and Anupam Chattopadhyay, editors, Emerging Computing: From Devices to Systems, pages 171–243. Springer Nature Singapore, Singapore, 2023. Series Title: Computer Architecture and Design Methodologies.arxiv.org/abs/2012.03112
  2. [2]William Andrew Simon, Leonid Yavits, Konstantina Kolioergi, Yann Falevoz, Yoshihiro Shibuya, Dominique Lavenier, Irem Boybat, Klea Zambaku, Berkan Şahin, Mohammad Sadrosadati, Onur Mutlu, Abu Sebastian, Rayan Chikhi, The BioPIM Consortium, and Can Alkan. Processing-in-memory for genomics workloads. IEEE Micro, 46(2):70–80, 2026.DOI
  3. [3]Amirali Boroumand, Saugata Ghose, Youngsok Kim, Rachata Ausavarungnirun, Eric Shiu, Rahul Thakur, Daehyun Kim, Aki Kuuusela, Allan Knies, Parthasarathy Ranganathan, and Onur Mutlu. Google Workloads for Consumer Devices: Mitigating Data Movement Bottlenecks. In Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’18, pages 316–331, New York, NY, USA, March 2018. Association for Computing Machinery.
  4. [4]Safaa Diab, Amir Nassereldine, Mohammed Alser, Juan Gómez Luna, Onur Mutlu, and Izzat El Hajj. A framework for high-throughput sequence alignment using real processing-in-memory systems. Bioinformatics, 39(5):btad155, 03 2023.
  5. [5]Raja Appuswamy, Jacques Fellay, and Nimisha Chaturvedi. Sequence Alignment Through the Looking Glass. In 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pages 257–266, May 2018.DOI
  6. [6]Heng Li. Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics, 34(18):3094–3100, 05 2018.DOI
  7. [7]Chirag Jain, Alexander Dilthey, Sergey Koren, Srinivas Aluru, and Adam M. Phillippy. A fast approximate algorithm for mapping long reads to large reference databases. In S. Cenk Sahinalp, editor, Research in Computational Molecular Biology, pages 66–81, Cham, 2017. Springer International Publishing.
  8. [8]Andrea Guarracino, Njagi Mwaniki, Santiago Marco-Sola, and Erik Garrison. Wfmash: a pangenome-scale aligner. Zenodo, 2021.DOI
  9. [9]Santiago Marco-Sola, Juan Carlos Moure, Miquel Moreto, and Antonio Espinosa. Fast gap-affine pairwise alignment using the wavefront algorithm. Bioinformatics, 37(4):456–463, 2021.
  10. [10]Santiago Marco-Sola, Jordan M. Eizenga, Andrea Guarracino, Benedict Paten, Erik Garrison, and Miquel Moreto. Optimal gap-affine alignment in o(s) space. Bioinformatics, 39(2):btad074, 02 2023.DOI
  11. [11]Fritz J. Sedlazeck, Philipp Rescheneder, Moritz Smolka, Han Fang, Maria Nattestad, Arndt von Haeseler, and Michael C. Schatz. Accurate detection of complex structural variations using single-molecule sequencing. Nature Methods, 15(6):461–468, 2018.DOI
  12. [12]Jingwen Ren and Mark J. P. Chaisson. lra: A long read aligner for sequences and contigs. PLOS Computational Biology, 17(6):1–23, 06 2021.DOI
  13. [13]Heng Li. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM, 2013.arxiv.org/abs/1303.3997
  14. [14]Ben Langmead and Steven L Salzberg. Fast gapped-read alignment with Bowtie 2. Nature Methods, 9(4):357–359, 2012.DOI
  15. [15]Ivan Tolstoganov, Marcel Martin, Nicolas Buchin, and Kristoffer Sahlin. Multi-context seeds enable fast and high-accuracy read mapping. Genome Biology, 27(1):118, February 2026.DOI
  16. [16]Heng Li and Nils Homer. Fast genomic read alignment with minibwa, 2026.arxiv.org/abs/2606.15357
  17. [17]Geraldo F. Oliveira, Juan Gómez-Luna, Lois Orosa, Saugata Ghose, Nandita Vijaykumar, Ivan Fernandez, Mohammad Sadrosadati, and Onur Mutlu. DAMOV: A New Methodology and Benchmark Suite for Evaluating Data Movement Bottlenecks. IEEE Access, 9:134457–134502, 2021. Conference Name: IEEE Access.
  18. [18]Ahmad Yasin. A Top-Down method for performance analysis and counters architecture. In 2014 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 35–44, March 2014.DOI
  19. [19]Vivek Seshadri, Donghyuk Lee, Thomas Mullins, Hasan Hassan, Amirali Bournmand, Jermie Kim, Michael A. Kozuch, Onur Mutlu, Phillip B. Gibbons, and Todd C. Mowry. Ambit: in-memory accelerator for bulk bitwise operations using commodity DRAM technology. In Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-50 ’17, page 273–287, New York, NY, USA, 2017. Association for Computing Machinery.
  20. [20]Fei Gao, Georgios Tziantzioulis, and David Wentzlaff. ComputeDRAM: In-memory compute using off-the-shelf DRAMs. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-52, page 100–113, New York, NY, USA, 2019. Association for Computing Machinery.
  21. [21]Weichun Huang, Leping Li, Jason R. Myers, and Gabor T. Marth. Art: a next-generation sequencing read simulator. Bioinformatics, 28(4):593–594, 12 2011.DOI

Paper details

vlnc:W_sw3wq7qw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents