  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.
