An FPGA-based bwt accelerator for bzip2 data compression

Weikang Qiao, Zhenman Fang, Mau Chung Frank Chang, Jason Cong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

The Burrows-Wheeler Transform (BWT) has played an important role in lossless data compression algorithms. To achieve a good compression ratio, the BWT block size needs to be several hundreds of kilobytes, which requires a large amount of on-chip memory resources and limits effective hardware implementations. In this paper, we analyze the bottleneck of the BWT acceleration and present a novel design to map the anti-sequential suffix sorting algorithm to FPGAs. Our design can perform BWT with a block size of up to 500KB (i.e., bzip2 level 5 compression) on the Xilinx Virtex UltraScale+ VCU1525 board, while the state-of-Art FPGA implementation can only support 4KB block size. Experiments show our FPGA design can achieve ~2x speedup compared to the best CPU implementation using standard large Corpus benchmarks.

Original languageEnglish
Title of host publicationProceedings - 27th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages96-99
Number of pages4
ISBN (Electronic)9781728111315
DOIs
StatePublished - Apr 2019
Event27th Annual IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2019 - San Diego, United States
Duration: 28 Apr 20191 May 2019

Publication series

NameProceedings - 27th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2019

Conference

Conference27th Annual IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2019
CountryUnited States
CitySan Diego
Period28/04/191/05/19

Keywords

  • BWT
  • Compression
  • FPGA

Fingerprint Dive into the research topics of 'An FPGA-based bwt accelerator for bzip2 data compression'. Together they form a unique fingerprint.

  • Cite this

    Qiao, W., Fang, Z., Chang, M. C. F., & Cong, J. (2019). An FPGA-based bwt accelerator for bzip2 data compression. In Proceedings - 27th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2019 (pp. 96-99). [8735540] (Proceedings - 27th IEEE International Symposium on Field-Programmable Custom Computing Machines, FCCM 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/FCCM.2019.00023