During the latter part of my Ph.D. research, my advisor Yoram Bresler and I worked on parallel algorithms for lossless data compression. This page describes what lossless compression algorithms are good for, why one might want to parallelize them, and what the design goals for a parallal compression algorithm are. We then describe our research in this context.

In lossless data compression, we want to represent an input x, which we assume to be N bits long, with a code C(x), which is also comprised of bits. We also require that

• The input x can be reconstructed without error (hence the term lossless) from C(x).
• The length of C(x) is small.

Many modern data compression methods are lossy, i.e., the input cannot be reconstructed perfectly from the code. For some types of data, such as images and video, some distortion between the input and its reconstruction may be acceptable. Lossy compression methods have the additional benefit that they often compress very well.

In contrast, in some applications it is crucial to be able to decode the input perfectly:

• Text files.
• Executables.
• Medical images.

As processors, storage systems, and communications devices become faster, data compression systems must also support much higher data rates. At a fixed data rate, there is a tradeoff between the amount of resources, e.g., memory, that we allow the compression algorithm to use, and how well it compresses.

If we want to increase the speed by a small factor, it may suffice to choose a (faster) algorithm, possibly resulting in a slight degradation in compression quality. Alternatively, we could run the original algorithm on faster hardware, but that may be costly. If we need substantially higher data rates, then parallel algorithms are our only feasible option.

There are two trivial approaches to speed up compression by a factor of B:

• Partition the length-N input x into B blocks. Run the original compression algorithm in parallel on each of the blocks. However, it is well known that compression algorithms achieve poor compression ratios for short inputs. Therefore, if N/B is small, then this approach severely degrades the compression quality.
• Run the original algorithm in parallel on B length-N inputs. Although the compression ratio with this method will be identical (on average) to that of the original algorithm, this method consumes B times more hardware.

The goal of our recent research was to develop parallel lossless compression algorithms that avoid both problems described above. We want to have B computational units processing a single length-N input, such that the compression ratio is almost as good as that obtained with a regular (serial) compression algorithm.

Building on these insights, we developed techniques that compress using B parallel computational units, where each unit has only O(N/B) memory. The units learn the statistics of the input in a collabortive manner; the compression itself is then performed in parallel. Our approach results in a speedup that is linear in the number of parallel processing units B while the compression quality experiences only a minor degradation.