Workshop: IA^3 2026 — 16th Workshop on Irregular Applications: Architectures and Algorithms
Authors: Nicholas Brunsink (North Carolina State University, Sandia National Labs); Amy Powell (Sandia National Laboratories); Gavin Conant (North Carolina State University); James Elliott (Sandia National Laboratories); and Michela Becchi (North Carolina State University)
Abstract: De novo genome and metagenome assembly often relies on De Bruijn graph traversals to reconstruct microbial genomes. Effective GPU implementation of this phase of the assembly is complicated by the presence of highly variable and unpredictable walk lengths, leading to severe warp divergence and memory requirements that are not known a priori.
We present a GPU-accelerated de Bruijn graph traversal adapted from MetaHipMer2 that uses a three-pass walk design to address these challenges. First, bounded walks enable more uniform work distribution and reduce warp divergence while bounding memory requirements in the first traversal phase. Second, symbolic walks determine the memory required to store generated sequences without requiring dynamic memory allocation. Finally, connection walks link subsequences generated in the first stage. Compared to the parallel CPU implementation in MetaHipMer2, our GPU implementation achieves a 45.84× speedup on a 440-million-k-mer dataset, substantially reducing single-node assembly time without affecting assembly quality.
Back to IA^3 2026 — 16th Workshop on Irregular Applications: Architectures and Algorithms Archive Listing
Back to Full Workshop Archive Listing