FPC: A High-Speed Compressor for Double-Precision Floating-Point Data

Abstract

📜 Abstract

Many scientific programs exchange large quantities of double-precision data between processing nodes and with mass storage devices. Data compression can reduce the number of bytes that need to be transferred and stored. However, data compression is only likely to be employed in high-end computing environments if it does not impede the throughput. This paper describes and evaluates FPC, a fast lossless compression algorithm for linear streams of 64-bit floating-point data. FPC works well on hard-to-compress scientific data sets and meets the throughput demands of high-performance systems. A comparison with five lossless compression schemes, BZIP2, DFCM, FSD, GZIP, and PLMI, on 4 architectures and 13 data sets shows that FPC compresses and decompresses one to two orders of magnitude faster than the other algorithms at the same geometric-mean compression ratio. Moreover, FPC provides a guaranteed throughput as long as the prediction tables fit into the L1 data cache. For example, on a 1.6-GHz Itanium 2 server, the throughput is 670 Mbytes/s regardless of what data are being compressed.

Description

✨ Summary

The paper introduces FPC, a lossless, single-pass, linear-time compressor for streams of IEEE 754 double-precision values. FPC combines two complementary context-based predictors—an fcm predictor for recurring value contexts and a dfcm predictor for recurring differences—then selects the prediction producing the longer common prefix with the actual value. The prediction residual is generated with XOR and encoded using a compact leading-zero-byte representation. The implementation operates on 64-bit integers rather than floating-point arithmetic and organizes output into blocks containing predictor codes and residual bytes.

The evaluation covers 13 scientific data sets and four processor architectures, comparing FPC with BZIP2, DFCM, FSD, GZIP, and PLMI. FPC achieves the best geometric-mean compression ratio among the evaluated methods when sufficiently large predictor tables are used, while also providing substantially higher compression and decompression throughput at comparable ratios. Its principal technical distinction is predictable execution: when predictor tables fit in the L1 data cache, the critical loops follow a data-independent instruction path, giving approximately constant processing time per value. Larger tables improve compression on many data sets but increase memory use and eventually reduce throughput because of cache and memory-latency effects.

The results also show that compression effectiveness is highly data-dependent. FPC performs particularly well on some scientific and message data sets, but no method dominates every data set, and nearly random streams remain difficult to compress. The paper therefore positions FPC as a throughput-oriented compressor for unstructured streams rather than as a universally optimal codec. The authors identify structured multidimensional data, single-precision values, independent block processing, parallelization, and an optional second coding stage as directions for further development.

The work directly led to pFPC, a parallel implementation that extends FPC to multithreaded compression and decompression, and to gFPC, a self-tuning successor developed by the same authors. (userweb.cs.txstate.edu) FPC has also been incorporated into independent software implementations, including a Go implementation that preserves the paper’s predictor-based format and reports gigabyte-per-second class performance on contemporary systems. (github.com) Later floating-point compression studies have used FPC as a lossless comparison method or baseline, including evaluations involving ZFP and newer adaptive floating-point compressors. (vis.cs.ucdavis.edu)