PaperlayerView exact revision on arXiv

Source-linked AI summary

Engineering Lightweight Burrows-Wheeler Transform Construction on the GPU via Prefix-Free Parsing

Florian Kurpicz, Maximilian Paris

arXiv:2610.33889v1cs.DS

TL;DR

GPU BWT construction is limited by high device-memory requirements, while prefix-free parsing offers a lower-memory basis but uses structures poorly suited to GPUs. The paper reformulates PFP-based construction around sorting, scanning, and simple data-parallel procedures. Its construction processes larger inputs and performs well on repetitive texts, with slower throughput on non-repetitive texts.

  • Problem

    GPU BWT construction requires about 20 bytes of device memory per character in libcubwt, limiting the text sizes that fit on a GPU.

    Source: §1 · p. 1

  • Method

    The construction retains phrase occurrences and reformulates PFP-based BWT construction using sorting, scanning, and simple data-parallel procedures.

    Source: §1 · p. 2

  • Results

    The construction is faster than or on par with libcubwt on eight of nine repetitive inputs but slower on non-repetitive inputs, while processing 2,108 MiB on English versus libcubwt's 1,164 MiB prefix.

    Source: §7 · pp. 14, 16, §8 · p. 19

  • Takeaways & Limitations

    The construction is preferable for repetitive and larger texts, while libcubwt remains the better choice for non-repetitive texts that fit its memory.

    Source: §7 · p. 16

    On non-repetitive inputs, the construction is significantly slower because suffix sorting is the bottleneck.

    Source: §8 · p. 19

Abstract

from arXiv · show

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.

1 Introduction

The BWT underlies compressed full-text indexes and read aligners, but GPU construction is constrained by high device-memory use. This work adapts prefix-free parsing to GPU-friendly operations and develops memory-saving configurations and sorting cores.

1 Introduction

  • The BWT supports compressed pattern matching and is central to compressed full-text indexes used by read aligners and pangenome indexes.Examples include the FM-index, r-index, and move data structure.Source: §1 · p. 1
  • 20 bytes per character limits libcubwt to about 1,200 MiB on a 24 GB GPU, below the size of some string collections and pangenomes targeted by BWT indexes.Prefix-free-parsing-based BWT construction reduces working memory in main memory.Source: §1 · p. 1
  • The GPU algorithm keeps phrase occurrences rather than only distinct phrases, so sorting, scanning, and simple data-parallel kernels replace hash tables and inverted lists.The paper also presents a sorts-and-scans formulation, lower-memory levels, two sorting cores, a space-saving configuration, and an experimental evaluation.Source: §1 · p. 2

2 Preliminaries

The preliminaries establish the suffix-array and BWT notation, introduce Karp–Rabin fingerprints, and describe the GPU execution and memory model used by the algorithms.

2 Preliminaries

  • The suffix array lists suffix starting positions in lexicographic order, and BWT[i] is the character cyclically preceding the suffix at SA[i].The construction returns the primary index q for which SA[q] = 0 rather than appending a sentinel.Source: §2 · p. 2
  • Karp–Rabin fingerprints are computed modulo p, and fingerprints of fixed-length windows can be updated in one left-to-right scan with a rolling hash.The fingerprint uses a base z and a modulus p.Source: §2 · p. 2
  • GPU thread blocks contain up to 1,024 threads, and device-memory bandwidth is reached only when neighboring threads access consecutive locations.The implementation combines CUB and Thrust primitives such as scans, discarding, reductions, and radix sorts.Source: §2 · p. 2

3 Related Work

Related work covers GPU BWT construction and GPU suffix sorting, while identifying Rapid-PFP as a close approach that computes a GPU parse but not the BWT.

3 Related Work

  • The discussion situates GPU BWT construction within broader BWT-related building blocks, including compressed-index structures such as wavelet trees and minimal perfect hash functions.A survey is cited for further building blocks of full-text indexes that use the BWT.Source: §3 · pp. 2–3
  • Rapid-PFP computes prefix-free parsing on the GPU but does not construct the BWT; libcubwt is identified as the current state of the art for GPU BWT construction.Earlier work includes blockwise GPU suffix sorting and CPU–GPU or multi-GPU construction.Source: §3 · p. 2
  • GPU suffix-array construction spans prefix doubling, skew, hybrid, CPU–GPU, lexicographic-naming, genome-specific, and multi-GPU techniques, all of which sort all n suffixes.The authors note that they are not aware of a GPU suffix-array construction using induced sorting.Source: §3 · p. 3

4 Prefix-Free Parsing and the Original PFP-BWT

Prefix-free parsing divides the text into overlapping phrases and uses their distinct dictionary and parse to recover BWT order. The original construction exploits phrase-suffix ordering and phrase occurrences, with Big-BWT implementing the process in three programs.

4 Prefix-Free Parsing and the Original PFP-BWT

  • The original PFP-BWT replaces sorting all text suffixes with sorting distinct phrase suffixes, which are few for repetitive texts.The GPU construction builds on this approach.Source: §4 · p. 3

4.1 The Parse

  • A phrase runs from one trigger-string occurrence to the next, neighboring phrases overlap by w characters, and the dictionary stores distinct phrases while the parse records their lexicographic ranks.The parse is parameterized by window length w and trigger strings E, with sentinel symbols prepended and appended.Source: §4.1 · p. 3

4.2 The Structure of the Phrase Suffixes

  • Phrase suffixes are prefix-free, and every text suffix longer than w has exactly one phrase-suffix prefix, allowing suffix order to be inferred from phrase-suffix order.The mapping f from each longer suffix to its unique phrase-suffix prefix preserves the relevant lexicographic order.Source: §4.2 · pp. 3–4

4.3 From the Dictionary and the Parse to the BWT

  • The BWT is assembled in phrase-suffix blocks: equal preceding characters form easy runs, while hard blocks order characters by the parse suffixes following their occurrences.The dictionary D and parse P provide the information needed to compute the BWT.Source: §4.3 · p. 4

4.4 The Implementation Big-BWT

  • Big-BWT uses three sequential programs: parse and build the dictionary, order parse suffixes and occurrences, then enumerate phrase suffixes and emit BWT runs or ordered characters.For hard blocks, the final program merges inverted occurrence lists; for easy blocks, it writes a run using the summed phrase frequencies.Source: §4.4 · p. 5

5 Our PFP-BWT Variant for the GPU

The GPU PFP-BWT variant replaces hash tables and inverted lists with sorts and scans, deriving the construction from a single phrase-occurrence array. Its stages sort phrases and phrase suffixes to order and emit the BWT.

5 Our PFP-BWT Variant for the GPU

  • The GPU variant replaces hash tables, inverted lists, W, and the heap with sorts and scans, deriving its objects from one occurrence array C sorted in three orders.The three orders are text order, lexicographic phrase order, and lexicographic reversed-phrase order.Source: §5 · p. 5

5.1 Parsing

  • Parsing uses T[0..w−1] as the trigger string without prepending #, yielding the BWT directly in libcubwt’s convention.Each occurrence records a phrase’s end, length, and text-order index in C.Source: §5.1 · p. 6

5.2 Dictionary, Parse, and Parse Ranks

  • Grouping occurrences after a left-to-right phrase sort assigns dictionary ranks that form the parse; prefix doubling then orders parse suffixes by payload rank.The last occurrence receives sentinel rank ⊥, smaller than all other ranks.Source: §5.2 · p. 6

5.3 Phrase Suffixes and Their Occurrence Sets

  • A right-to-left phrase sort makes shared phrase suffixes contiguous, so LCP lengths identify each suffix once and NSV queries find its occurrence interval.Each suffix is represented by its leftmost occurrence, length, and interval length.Source: §5.3 · p. 7

5.4 Generating the BWT

  • A scan assigns output offsets, then easy suffix intervals emit a repeated preceding character while hard intervals emit preceding characters in parse-rank order.An interval is easy when its endpoint occurrences have the same preceding character.Source: §5.4 · pp. 7–8
  • The primary index q is the output offset of α0 plus the number of its interval occurrences with parse rank below phrase 0’s rank.Here α0 is the phrase-suffix element that prefixes the suffix starting at text position 0.Source: §5.4 · p. 8

6 Engineering PFP-based BWT Construction on the GPU

The engineering changes reduce the suffix-sort memory footprint through bucketed sorting, in-place output, and compact sorting cores. The section also describes a prefix-doubling alternative for suffixes with long common prefixes.

6.1 Improving the Memory Footprint

  • Small groups finish in shared memory before receiving blocks, bounding the auxiliary buffers at 12s bytes; sorting state is allocated only for the largest first-character bucket.The implementation also drops cached upcoming characters and recomputes them from the text and suffix end.Source: §6.1 · p. 10
  • On english (θ ≈0.17), the memory bound falls from at least 44s bytes to 28θs bytes, allowing the peak to be more than halved.At the beginning, the bound is 56s + 12 maxt max(Hbt, st) + 12d + 2n bytes.Source: §6.1 · p. 11

6.2 Performance improvements

  • After memory reductions significantly reduced performance, the section introduces changes intended to improve throughput while slightly reducing memory requirements.Source: §6.2 · p. 11

6.2.1 In-Place Bucketed Output

  • In-place bucketed output uses stable passes, per-chunk permutations, and byte-per-suffix classification storage; presorting by two characters bounds bucket size by the most frequent bigram.With the MSD sort, sorting memory is 14s + 12d + 2n + 44 max(bmax, s/K) bytes.Source: §6.2.1 · pp. 11–12

6.3 MSD Radix Sort

  • The MSD radix sort handles eight characters per round, while LCP skipping advances each rank group over shared words to avoid redundant rounds.A chunk needs ⌈λ/8⌉ rounds, where λ is the longest common prefix of two suffixes in that chunk.Source: §6.3 · pp. 12–13

6.4 Saving More Space

  • Delaying interval-length computation lowers bucketing memory to 12s + 12d + 2n bytes and uses 10s + 16d + 2n bytes after sorting.The dictionary sorts instead bucket entries by their first or last two characters and sort consecutive buckets in 16 chunks.Source: §6.4 · p. 13

6.5 Prefix-Doubling

  • Prefix-doubling sorts a dictionary text whose suffixes encode the phrase suffixes, replacing MSD rounds that each pay a fixed cost for long common prefixes.The dictionary text concatenates phrases generating elements of S in RL order, followed by a separator.Source: §6.5 · pp. 13–14

7 Experimental Evaluation

The evaluation compares GPU BWT configurations with libcubwt on an RTX 3090, measuring throughput and memory across Pizza&Chili texts. The results show a memory-capacity advantage for larger and repetitive texts, alongside slower performance on non-repetitive inputs.

Setup

  • Experiments ran on an NVIDIA GeForce RTX 3090 under CUDA 12.6, with whole-construction host-to-host times reported as medians of three runs.Inputs came from the Pizza&Chili corpus, and maximum handled sizes were tested on progressively larger prefixes.Source: §7 · p. 14

Largest inputs

  • Our best configurations process all 15 inputs, including the full 2,108 MiB english text, while libcubwt handles only a 1,164 MiB prefix of english.At the largest size each handles, libcubwt needs 20.4 bytes per character, cub6 uses 6.1 to 17.0, and space uses 5.9 to 14.6.Source: §7 · p. 14

Comparison with libcubwt

  • On repetitive inputs, cub6 is faster than libcubwt on five of nine texts, on par on three, and slower on one; on non-repetitive inputs it is 2.0 to 3.2 times slower.fast improves on cub6 but remains 1.8 to 3.1 times slower on non-repetitive inputs; libcubwt remains the better choice for non-repetitive texts that fit its memory, while this construction is preferable for repetitive and larger texts.Source: Figure 11 · p. 15, §7 · p. 16

Where the time goes

  • On repetitive inputs, dictionary phases take 53 to 81% of runtime, while the parse-rank phase alone takes 38 to 45% on five texts because all phrase occurrences are retained.On non-repetitive inputs, suffix sorting takes 39 to 88% of cub6 runtime; fast and dbl are respectively 2.4 and 3.1 times faster than cub6 on pitches, while dbl is 1.2 times slower on english.Source: §7 · p. 16

8 Conclusion

The conclusion presents a GPU-compatible PFP-based BWT construction and reports a substantial memory and input-size advantage. Its speed advantage is concentrated on repetitive texts; non-repetitive suffix sorting remains a bottleneck.

8 Conclusion

  • The GPU-oriented PFP-BWT variant uses sorting, scans, and simple data-parallel procedures rather than hash tables and inverted lists.On repetitive texts, dictionary phases dominate because they process all phrase occurrences; the authors identify using distinct phrases with a compact occurrence structure as a possible improvement.Source: §8 · p. 19
  • On english, peak memory falls by a factor of four, allowing a 24 GB GPU to process a prefix 1.8 times larger than libcubwt.The construction is faster than or on par with libcubwt on eight of nine repetitive inputs, but significantly slower on non-repetitive inputs.Source: §8 · p. 19

A More Related Work

Related work surveys BWT construction and suffix sorting across computational models, then places GPU methods within that broader landscape. It notes that existing PFP-based constructions known to the authors run on CPUs and use hash tables and inverted lists.

BWT construction in other models

  • Sequential BWT methods include compact-space, blockwise, induced-sorting, linear-time, and in-place constructions, while repetitive-text methods include run-length BWT and PFP-based approaches [46, 47] [48] [90] [6, 83] [21] [84] [16].External-memory, shared-memory, PRAM, and distributed-memory constructions are also surveyed.Source: A More Related Work · p. 25

GPU context

  • The cited discussion states that all PFP-based constructions the authors are aware of run on CPUs and rely on hash tables and inverted lists.Source: A More Related Work · p. 25

Suffix sorting in other models

  • Suffix-array construction work spans classical prefix doubling, recursive linear-time algorithms, induced sorting, and practical implementations such as divsufsort and libsais [75, 66] [51, 57, 59] [88, 86] [82, 33] [41].The survey also covers external, shared-memory, distributed-memory, PRAM, and BSP suffix-array algorithms.Source: A More Related Work · p. 25

B Additional Experimets

The additional experiments examine the memory–time trade-offs across configurations and input types. The space-saving configuration lies on the Pareto front for most inputs, while memory levels and sorting cores affect peak memory and runtime differently.

B Additional Experimets

  • Figure 14 reports phase times, including setup and output transfers, at the largest input size handled by all configurations.Source: B Additional Experimets · p. 25
  • space lies on the Pareto front for 13 of 15 inputs, while levels below 5 are dominated on 14 of 15.On repetitive inputs where dictionary sorting determines the peak, space reduces it by 24–27% on eight of nine texts.Source: B Additional Experimets · p. 26
  • On whole english, space reduced LR dictionary-sort peak from 6.7 to 4.6 bytes per character and suffix-generation peak from 7.8 to 5.8, but overall peak only fell from 10.0 to 9.9.Source: B Additional Experimets · p. 26
  • At pitches, level 4 took 19.1 s versus 3.2 s at level 0, and levels 5–6 recovered only part of the loss, taking 9.1 s.On english at 381.5 MiB, peak memory fell from 47.7 bytes per character at level 0 to 11.9 at level 6.Source: B Additional Experimets · p. 26
  • On english, cub6 matched opt6 at 11.9 bytes per character while reducing runtime from 2.6 to 1.6 s; on pitches, it used 17.0 bytes per character versus 14.2 for 9.1 versus 1.2 s.Source: B Additional Experimets · p. 26
  • On six of nine repetitive inputs, peak memory stayed unchanged across levels because s was at most 0.10n and dictionary phases determined the peak.cub6 used more memory than opt6 there because its unchunked dictionary sorts required scratch space.Source: B Additional Experimets · p. 26

C Comparison with Big-BWT

This section compares the original PFP-BWT steps with the GPU algorithm and presents phase timings for configurations on repetitive and non-repetitive texts.

C Comparison with Big-BWT

Loading 2610.33889v1…