search-icon
Paper
:
Optimizing High Performance Distributed Memory Parallel Hash Tables for DNA k-mer Counting
Event Type
Paper
Registration Categories
TP
Tags
Algorithms
Applications
Computational Biology
Scientific Computing
TimeTuesday, November 13th2pm - 2:30pm
LocationC140/142
DescriptionHigh-throughput DNA sequencing is the mainstay of modern genomics research. A common operation used in bioinformatic analysis for many applications of high-throughput sequencing is the counting and indexing of fixed length substrings of DNA sequences called k-mers. Counting k-mers is often accomplished via hashing, and distributed memory k-mer counting algorithms for large data sets are memory access and network communication bound. In this work, we present two optimized distributed parallel hash table techniques that utilize cache friendly algorithms for local hashing, overlapped communication and computation to hide communication costs, and vectorized hash functions that are specialized for k-mer and other short key indices. On 4096 cores of the NERSC Cori supercomputer, our implementation completed index construction and query on an approximately 1 TB human genome dataset in just 11.8 seconds and 5.8 seconds, demonstrating speedups of 2.06x and 3.7x, respectively, over the previous state-of-the-art distributed memory k-mer counter.
Back To Top Button