Gpu method reduces memory use for text indexing transform
Engineering Lightweight Burrows-Wheeler Transform Construction on the GPU via Prefix-Free Parsing
Data Structures and Algorithms
Summary
When computers search or align sequences of text, they use a technique called the Burrows-Wheeler transform that usually needs a lot of memory, especially on graphics cards. The authors found a way to build this transform using less memory on a GPU by changing the way data is organized and processed, avoiding complex structures unsuitable for GPUs. Their approach works well on repetitive texts, allowing larger files to be processed than previous methods, but it is slower on less repetitive ones. This approach offers a trade-off between using less GPU memory and running speed.
What this means in practice
- •For bioinformatics engineers: Build read alignment tools that handle larger genomic datasets on GPUs by reducing memory needed during Burrows-Wheeler transform construction.
- •For software developers for search systems: Implement compressed text indexing on GPUs for large text collections by efficiently constructing the Burrows-Wheeler transform with lower memory demand.
Authors
Florian Kurpicz, Maximilian Paris
Abstract
The Burrows-Wheeler transform (BWT) is the core of many compressed full-text indexes and most read aligners. The fastest BWT constructions on GPUs need about $20$ bytes of device memory per character, which severely limits the texts that can be processed there. For example, on our GPU with 24 GB device memory, this is only about 1200 MiB. Prefix-free parsing (PFP) can be used to reduce the memory requirements of BWT construction algorithms in main memory. But, it uses hash tables and inverted lists which are not suited for GPUs. We show that PFP-based BWT construction can work with only sorting, scanning, and simple data-parallel procedures. This results in our GPU construction gpupfpbwt that on an NVIDIA RTX 3090, reduces the peak memory on an English text 11.9 bytes per character. There, it can processes 2108 MiB input files, which is 1.8 times larger than what the current state of the art libcubwt can handle. It is faster than or on par with libcubwt on eight of nine repetitive texts but 2.0 to 3.2 times slower on five of six non-repetitive ones, i.e., it provides a trade-off between required device memory and throughput.