Constructing the Burrows-Wheeler Transform in Distributed Memory

The BURROWS-WHEELER TRANSFORM (BWT) [10] is an important fundamental algorithm in the world of string algorithms. It serves as the foundation of several algorithms [40, 6, 13], for example, text indices, enabling efficient string pattern matching [16]. The BWT is a permutation of the given string obtained by sorting all cyclic rotations of the string. The amount of genome data parsed using the BWT increases daily because of efforts like the GenomeTrakr network [22], which is collecting hundreds of thousands of genome sequences. Therefore, constructing the BWT for large datasets is of interest. There are multiple algorithms to construct the BWT [10, 51, 9, 14], some of which already focus on processing large amounts of data [9, 39, 11]. So far, there have not been efforts to develop BWT construction algorithms that use distributed high-performance computing systems. We present two distributed BWT construction algorithms. One adapts the traditional approach of constructing the BWT by computing the suffix array [43] in distributed memory. The other distributed algorithm is based on BIG-BWT [9], a BWT construction algorithm that uses PREFIX-FREE PARSING [9] as a preprocessing step. ... mehrWe modified the BIG-BWT algorithm to efficiently and scalably work in distributed memory. We show that both of our distributed BWT construction algorithms can scale up to 6144 cores. This makes them, to the best of our knowledge, the first distributed BWT construction algorithms to do so. This enables us to use more computation resources to construct the BWT. Our distributed PFP-based algorithm requires only 96 cores to match or surpass the runtime of the stateof-the-art shared-memory parallel BWT construction based on Lyndon words [51] running on a single 48-core compute node. Using 64x more cores, our distributed PFP-based construction algorithm achieves a speedup of up to 20.9x over the Lyndon-based construction running on a single compute node.