Abstract
Burrows-Wheeler Transform (BWT) is a widely-used algorithm applied in data compression techniques like bzip2 and bioinformatics. The BWT-based compression strategy has better compression rate, but longer compression time. In mathematically point of view, BWT can be derived from the constructed suffix array. For decades, researchers developed many of suffix array construction algorithms (SACAs) that benefit the BWT algorithm. On the other hand, graphics processing units (GPU) has emerged as the most cost-efficient solution in the field of parallel computation recently, and former linear-time SACAs begin utilizing the computational power of GPUs. In this work, we analyze the current parallel implementations of SACAs and introduce the first heterogeneous implementation of SA-DS algorithm. The implementation leverages both of the CPU and GPU, and we focus on the typical block sizes, 100K to 2M characters, for BWT-based compression. In order to achieve better performance, we also optimizes the up-to-date radix sort on GPU for our platform. Finally, the implementation is evaluated on the heterogeneous platform equipped with a NVIDIA GPU using the CUDA programming model. As the result, the optimized radix sorting on GPU shows up to 23% decreased time compared with latest Thrust library for sorting millions of keys. Our heterogeneous SA-DS demonstrates up to 4x over sequential C++ version of SA-DS and has a performance gain up to 2x than parallel BWT provided by the CUDPP library.