842 (compression algorithm)
From Wikipedia, the free encyclopedia
842, 8-4-2, or EFT is a lossless data compression algorithm. It is a variation on Lempel–Ziv compression with a limited dictionary length. With typical data, 842 gives 80 to 90 percent of the compression of LZ77 with much faster throughput and less memory use.[1] Hardware implementations also provide minimal use of energy and minimal chip area.
842 compression can be used for virtual memory compression, for databases — especially column-oriented stores, and when streaming input-output — for example to do backups or to write to log files.
The algorithm operates on blocks of 8 bytes with sub-phrases of 8, 4 and 2 bytes. A hash of each phrase is used to look up a hash table with offsets to a sliding window buffer of past encoded data. Matches can be replaced by the offset, so the result for each block can be some mixture of matched data and new literal data.[2][1][3]
Implementations
IBM added hardware accelerators and instructions for 842 compression to their Power processors from POWER7+ onward.[4] In addition, POWER9 and Power10 added hardware acceleration for the RFC 1951 Deflate algorithm, which is used by zlib and gzip.[5]
A device driver for hardware-assisted 842 compression on a POWER processor was added to the Linux kernel in 2011.[6] More recently, Linux can fallback to a software implementation, which of course is much slower.[7] zram, a Linux kernel module for compressed RAM drives, can be configured to use 842.
Researchers have implemented 842 using graphics processing units and found about 30x faster decompression using dedicated GPUs.[8] An open source library provides 842 for CUDA and OpenCL.[9] An FPGA implementation of 842 demonstrated 13 times better throughput than a software implementation.[10]
References
- 1 2 Plauth, Max; Polze, Andreas. "Towards Improving Data Transfer Efficiency for Accelerators using Hardware Compression".
- ↑ Franaszek, Peter A; Lastras-Montaño, Luis A; Peng, Song; Robinson, John T (14 September 2016). "Data Compression with Restricted Parsings". IBM Research. IBM. Retrieved 2021-07-13.
- ↑ Blaner, B.; Abali, B.; Bass, B. M.; Chari, S.; Kalla, R.; Kunkel, S.; Lauricella, K.; Leavens, R.; Reilly, J. J.; Sandon, P. A. (November 2013). "IBM POWER7+ processor on-chip accelerators for cryptography and active memory expansion". IBM Journal of Research and Development. 57 (6): 3:1–3:16. doi:10.1147/JRD.2013.2280090. Retrieved 2021-07-13.
- ↑ "POWER NX842 Compression for Db2" (PDF). IBM. Retrieved 2021-07-13.
- ↑ Veale, Brian F (14 March 2022). "GZip Acceleration with AIX on Power Systems". IBM Power Community. IBM. Retrieved 2022-10-22.
- ↑ "Torvalds/Linux". GitHub. 12 February 2022.
- ↑ "Torvalds/Linux". GitHub. 12 February 2022.
- ↑ Plauth, Max; Polze, Andreas (2019). "GPU-Based Decompression for the 842 Algorithm". 2019 Seventh International Symposium on Computing and Networking Workshops (CANDARW). pp. 97–102. doi:10.1109/CANDARW.2019.00025. ISBN 978-1-7281-5268-4. S2CID 210694935.
- ↑ "Lib842". GitHub. 3 November 2020.
- ↑ Sukhwani, Bharat; Abali, Bulent; Brezzo, Bernard; Asaad, Sameh (2011). "High-Throughput, Lossless Data Compression on FPGAs". 2011 IEEE 19th Annual International Symposium on Field-Programmable Custom Computing Machines. IEEE Xplore. pp. 113–116. doi:10.1109/FCCM.2011.56. ISBN 978-1-61284-277-6. S2CID 7828316.