Structured Parallel Programming

Chapter 12

Bzip2 Data Compression

Bzip2 is a popular file compression program. We show it as a practical application of the pipeline pattern. The pattern is more than a classic pipeline because for the sake of scalability some stages process multiple items simultaneously. The TBB implementation shows parallel_pipeline in action. The Cilk Plus implementation demonstrates how creative use of reducers can go far beyond implementing mathematically pure reductions. Another point of the example is that, when designing file formats, you should consider their impact on parallel processing.

12.1 The Bzip2 Algorithm

Bzip2 chops its input stream into blocks, compresses each block separately, and writes the blocks to an output stream. Two features of the output ...