СТРУКТУРНАЯ МОДИФИКАЦИЯ МЕТОДА ХАФФМАНА ДЛЯ СЖАТИЯ ПЛОТНЫХ ПОТОКОВ ДАННЫХ БЕЗ ПОТЕРЬ НА РВС
Аннотация
Современные запросы общества требуют решения целого ряда вычислительно трудоемких
задач в режиме реального времени. Для подобных решений необходимы огромные вычислительные
мощности, широкополосные высокоскоростные каналы передачи данных и внушительные объемы
памяти. Обеспечить подобные запросы можно за счет разработки и внедрения новых технологий,
наращивания технической инфраструктуры, что потребует значительных финансовых и временных
затрат. Облегчить подобный переход, используя существующую техническую базу, можно за счет
использования алгоритмов сжатия данных в реальном времени. Средства сжатия данных в темпе
поступления могут повысить скорость вычислений, передачи данных, снизить занимаемый объем
при хранении, используя имеющуюся инфраструктуру. Современные технические платформы на
базе CPU не способны обеспечить потоковую обработку данных в темпе их поступления, реальная
производительность подобных систем не превышает 10 % от пиковой. Новой платформой для сис-
тем сжатия данных без потерь в темпе поступления могут стать реконфигурируемые вычисли-
тельные системы (РВС) на базе программируемых логических интегральных схем (ПЛИС). Однако
для эффективной работы подобных систем требуется разработка новых методов с применением
структурных вычислений, позволяющих полностью раскрыть потенциал ресурса ПЛИС. В данной
работе представляется реализация на РВС модификации динамического алгоритма кодирования
Хаффмана, которая позволяет создавать префиксные коды оптимальной длины и обрабатывать
плотные потоки данных в темпе поступления с пропускной способностью не менее 128 Гбит\с. Про-
изводительность разработанной модификации в 5 раз превосходит наилучшую известную компле-
ментарную реализацию на базе FPGA на один вычислительный конвейер.
Литература
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.
