Publication: Parallel Lossless Data Compression Based on the Burrows-Wheeler Transform

All || By Area || By Year

Title Parallel Lossless Data Compression Based on the Burrows-Wheeler Transform
Authors/Editors* Jeff Gilchrist, Aysegul Cuhadar
Where published* Proceedings of the 21st International Conference on Advanced Information Networking and Applications (AINA 2007)
How published* Proceedings
Year* 2007
Volume -1
Number -1
Pages 877-884
Publisher IEEE
Keywords BWT, Burrows-Wheeler Transform, bzip2, data compression, parallel computing, MPI, multi-threaded
In this paper, we present parallel algorithms for lossless data compression based on the Burrows-Wheeler Transform (BWT) block-sorting technique. We investigate the performance of using data parallelism and task parallelism for both multi-threaded and message-passing programming. The output produced by the parallel algorithms is fully compatible with their sequential counterparts. To balance the workload among processors we develop a task scheduling strategy. An extensive set of experiments is performed with a shared memory NUMA system using up to 120 processors and on a distributed memory cluster using up to 100 processors. Our experimental results show that significant speedup can be achieved with both data parallel and task parallel methodologies. These algorithms will greatly reduce the amount of time it takes to compress large amounts of data while the compressed data remains in a form that users without access to multiple processor systems can still use.
Go to Biomedical Modeling and Simulation
Back to page 68 of list