STRUCTURAL MODIFICATION OF THE HUFFMAN METHOD FOR COMPRESSION OF DENSE DATA STREAMS WITHOUT LOSS ON A RCS
Abstract
Modern society demands require solving a whole range of computationally intensive tasks in real
time. Such solutions require enormous computing power, broadband high-speed data transmission channels
and impressive memory capacities. Such demands can be met by developing and implementing new
technologies, expanding the technical infrastructure, which will require significant financial and time
costs. Such a transition can be facilitated using the existing technical base by using real-time data compression
algorithms. Data compression tools at the rate of receipt can increase the speed of calculations,
data transfer, and reduce the occupied space during storage, using the existing infrastructure. Modern
CPU-based technical platforms are not capable of providing streaming data processing at the rate of their
receipt; the actual performance of such systems does not exceed 10% of the peak. Reconfigurable computing
systems (RCS) based on programmable logic integrated circuits (FPGAs) can become a new platform
for lossless data compression systems at the rate of receipt. However, for the efficient operation of such
systems, it is necessary to develop new methods using structural calculations that allow the full potential
of the FPGA resource to be unleashed. This paper presents the implementation of a modification of the
dynamic Huffman coding algorithm on the RCS, which allows creating prefix codes of optimal length and
processing dense data flows at the rate of receipt with a throughput of at least 128 Gbit/s. The performance
of the developed modification is 5 times higher than the best known complementary implementation
based on FPGA per computing pipeline.
References
Cloud Computing, 2022, No. 11 (1).
2. Morgan S. The 2020 Data Attack Surface Report, White Paper. Available at:
https://cybersecurityventures.com/wp-content/uploads/2020/12/ArcserveDataReport2020.pdf.
3. 2020: Oracle’s Top 10 Cloud Predictions. Available at: https://www.oracle.com/a/ocom/docs/
cloud/oracle-cloud-predictions-2020.pdf 2020.
4. Popov A.V. Algoritmy entropiynogo kodirovaniya pri szhatii spektra televizionnogo signala [Entropy
coding algorithms for spectrum compression of television signals], T-Comm — Telekommunikatsii
i Transport [T-Comm — Telecommunications and Transport], 2013, No. 4, pp. 43-46.
5. Lukanov A.S. Sistemy real'nogo vremeni: ucheb. posobie [Real-time systems: a tutorial]. Samara: Izdvo
Samarskogo universiteta, 2020, 156 p.
6. Available at: https://aws.amazon.com/ru/blogs/aws/data-compression-improvements-in-amazon-redshift/.
7. Promberger L., Schwemmer R., Fröning H. Characterization of data compression across CPU platforms
and accelerators, Concurrency and Computation: Practice and Experience, 2021, Vol. 35,
No. 20 (e6465).
8. Knorr F., Thoman P., Fahringer T. ndzip-gpu: Efficient Lossless Compression of Scientific Floating-
Point Data on GPUs, SC '21: Proceedings of the International Conference for High Performance
Computing, Networking, Storage and Analysis Article, Nov. 2021, No. 93, pp. 1-14.
9. Deaton J.D., Purdy J., Bacon A. Smashing Big Data Costs with GZIP Hardware, AHA Products
Group, Technical White Paper.
10. Qiao W., Du J., Fang Z., Lo M. et. al. High-Throughput Lossless Compression on Tightly Coupled
CPU-FPGA Platforms, 2018 IEEE 26th Annual International Symposium on Field-Programmable
Custom Computing Machines, 2018, pp. 37-44.
11. Huffman D.A. A method for the construction of minimum-redundancy codes, Proceedings of the IRE,
Sept. 1952, Vol. 40, No. 9, pp. 1098-1101.
12. Shannon C.E. A mathematical theory of communication, Bell Sys. Tech. Jour., 1948, Vol. 27, pp. 398-403.
13. Witten I.H., Moffat A., Bell T.C. Managing Gigabytes: Compressing and Indexing Documents and
Images. 1st ed. Van Nostrand Reinhold, New York, USA, 1994, 429 p.
14. Moffat A., Turpin A. On the Implementation of Minimum Redundancy Prefix Codes, IEEE Transactions
on Communications, 1997, Vol. 45, No. 10, pp. 1200-1207.
15. Hashemian R. Memory Efficient and High-speed Search Huffman Coding, IEEE Transactions on
Communications, 1995, Vol. 43, No. 10, pp. 2576-2581.
16. Kraft L.G. A Device for Quantizing, Grouping, and Coding Amplitude-modulated Pulses. Massachusetts
Institute of Technology. Dept. of Electrical Engineering, 1949.
17. International Standard ISO/IEC 10918-1:1993(E). CCITT Rec. T.81 (1992 E). Information technology
— Digital compression and coding of continuous-tone still images — Requirements and Guidelines.
18. Kalyaev A.V., Levin I.I. Modul'no-narashchivaemye mnogoprotsessornye sistemy so strukturnoprotsedurnoy
organizatsiey vychisleniy [Modular-scalable multiprocessor systems with structural-
procedural organization of computations]. Moscow: Yanus-K, 2003, 380 p.
19. Kalyaev I.A., Levin I.I. Rekonfiguriruemye vychislitel'nye sistemy na osnove PLIS [Reconfigurable
computing systems based on FPGAs]. Rostov-on-Don: Izd-vo YuFU, 2021, 458 p.
20. Alekseev K.N., Sorokin D.A., Levin I.I. Structural-procedural implementation the huffman coding on
reconfigurable computer systems in real time, Vestnik Komp'iuternykh i Informatsionnykh Tekhnologii
(Herald of Computer and Information Technologies), 2018, No. 9, pp. 3-10.
