АЛГОРИТМ ПОТОКОВОЙ КОМПРЕССИИ ДАННЫХ С ПЛАВАЮЩЕЙ ЗАПЯТОЙ В ИНФОРМАЦИОННЫХ СИСТЕМАХ ОБЕСПЕЧЕНИЯ НАУЧНЫХ ЭКСПЕРИМЕНТОВ
Аннотация
Представлен оригинальный алгоритм и метод реализации однопроходной компрессии
потока числовых данных с плавающей запятой. Целью работы является разработка и фор-
мализация алгоритмического метода однопроходной потоковой компрессии числовых значе-
ний с плавающей запятой, обеспечивающего высокую оперативность кодирования и декоди-
рования, поскольку практика применения для этого существующих реализаций показывает их
недостаточную оперативность, неприемлемую ресурсоемкость, низкую применимость для
потоковой обработки большого объема данных с плавающей запятой в реальном времени.
Для достижения этой цели были решены следующие задачи. Описана математическая мо-
дель и алгоритм компрессии потока скалярных числовых значений с плавающей запятой, а
также результаты проведенного экспериментального исследования созданного метода реа-
лизации компрессии структур одномерных и двумерных научных данных. Модель опирается
на распространенный метод реализации расширенного множества действительных чисел,
отображаемых на числа с плавающей запятой двойной точности, представление которых
регламентировано форматом binary_64 стандарта IEEE-754. Алгоритм может быть ис-
пользован в составе распределенных высокопроизводительных информационных систем
обеспечения научных экспериментов для реализации задач, критичных к производительностиопераций ввода-вывода и инфокоммуникационного обмена данными. Производительность и
применимость алгоритма в реализациях потоковой обработки данных обусловлены его одно-
проходным поведением, относительно низкими требованиями к априорно известному и фик-
сированному размеру истории, на основе которой построена работа предиктора алгоритма
компрессии. Действительно, полученные результаты показывают сравнимую с более ресур-
соемкими универсальными кодерами результативность компрессии при значительном росте
оперативности. При синхронизации параметров компрессии и декомпрессии векторных дан-
ных в предположении взаимной корреляции магнитуд скаляров одного измерения, возможно
применение параллелизма класса ОКМД (одна команда-множество данных) для дальнейшего
увеличения производительности предиктора (а следовательно, компрессии и декомпрессии),
если реализующее устройство обладает возможностью обращения к изменяемой памяти,
реализующей историю, на основе сдвиговых значений, формируемых параллельно или вектор-
но, например, с помощью инструкций класса VGATHER микропроцессоров Intel. Реализация
алгоритма внедрена авторами в параллельно-распределенную систему моделирования волно-
вых полей с целью снижения издержек, обусловленных операциями ввода-вывода при взаимо-
действии системы узлов через вычислительную сеть. Экспериментально показана более вы-
сокая оперативность компрессии при сравнимой результативности универсальных много-
проходных кодеров RAR, ZIP и 7Z.
Литература
from simulations, In Data Compression Conference, 2000, pp. 574-586.
2. Ratanaworabhan P., Ke J., Burtscher M. Fast lossless compression of scientific floating-point
data, In Proceedings of Data Compression Conference, 2006, pp. 133-142.
3. Lindstrom P. Isenburg M. Fast and efficient compression of floating-point data, IEEE Transactions
on Visual and Computer Graphics, 2006, Vol. 12, No. 5, pp. 1245-1250.
4. IEEE 754: Standard for binary floating-point arithmetic, 2008.
5. Gomez L.A., Cappello F. Improving floating point compression through binary masks, In Proc.
2013 IEEE Int. Conf. Big Data, 2013, pp. 326-331.
6. Imai S., Fukuma S., Mori S. A Floating Point Data Compression Using Inter-Extrapolative
Predictor, IEEE 61st International Midwest Symposium on Circuits and Systems (MWSCAS),
2018, pp. 546-549.
7. Burtscher M., Ratanaworabhan P. FPC: A High-Speed Compressor for Double-Precision
Floating-Point Data, IEEE transactions on computers, 2009, Vol. 58, No. 1, pp. 18-31.
8. Knorr F., Thoman P., Fahringer T. ndzip: A High-Throughput Parallel Lossless Compressor
for Scientific Data, 2021 Data Compression Conference (DCC), 2021, pp. 103-112.
9. Hildebrandt J., Habich D. and Lehner W. BOUNCE: Memory-Efficient SIMD Approach for
Lightweight Integer Compression, 2022 IEEE 38th International Conference on Data Engineering
Workshops (ICDEW), 2022, pp. 123-128. DOI: 10.1109/ICDEW55742.2022.00025.
10. Tomari H., Inaba M., Hiraki K. Compressing floating-point number stream for numerical applications,
2010 First International Conference on Networking and Computing, 2010, pp. 112-119.
11. Katahira K., Sano K., Yamamoto S. FPGA-based lossless compressors of floating-point data
streams to enhance memory bandwidth, In Proceedings of the International Conference on
Application-specific Systems, Architectures and Processors, 2010, pp. 246-253.
12. Mondigo A., Ueno T., Tanaka D., Sano K., Yamamoto S. Design and scalability analysis of
bandwidth-compressed stream computing with multiple fpgas, In Proceedings of 2017 12th International
Symposium on Reconfigurable Communication-centric Systems-on-Chip
(ReCoSoC), 2017, pp. 108-115.
13. Ueno T., Kono Y., Sano K., Yamamoto S. Parameterized Design and Evaluation of Bandwidth
Compressor for Floating-Point Data Streams in FPGA-Based Custom Computing. Berlin, Heidelberg:
Springer Berlin Heidelberg. 2013, pp. 90-102.
14. Ueno T., Sano K., Furusawa T. Performance Analysis of Hardware-Based Numerical Data Compression
on Various Data Formats, 2018 Data Compression Conference, 2018, pp. 345-354.
15. Ueno T., Sano K., Yamamoto S. Bandwidth Compression of Floating-Point Numerical Data
Streams for FPGA-Based High-Performance Computing, ACM Transactions on Reconfigurable
Technology and Systems, 2017, Vol. 10, No. 3, pp. 1-22.
16. Yang A., Mukka H., Hesaaraki F., Burtscher M. MPC: A Massively Parallel Compression
Algorithm for Scientific Data, IEEE International Conference on Cluster Computing, 2015.
17. Claggett S., Azimi S., Burtscher M. SPDP: An Automatically Synthesized Lossless Compression
Algorithm for Floating-Point Data, Data Compression Conference, 2018.
18. Burtscher M., Hesaaraki F., Mukka H., Yang A. Real-Time Synthesis of Com-pression Algorithms
for Scientific Data, ACM/IEEE International Conference for High-Performance Computing,
Networking, Storage and Analysis, 2016, pp. 264-275.
19. Kopaeva M.A., Chusov A.A. Algoritm i sistemnaya realizatsiya kompressii potokov chisel s
plavayushchey tochkoy pri realizatsii obrabotki eksperimental'nykh nauchnykh dannykh [An
algorithm and systematic approach to compression of floating-point data streams for processing
of scientific data], Radioelektronika. Problemy i perspektivy razvitiya: Sb. trudov
Sed'moy vserossiyskoy molodezhnoy nauchnoy konferentsii [Radioelectronics. Problems and
future developements: Seventh Russian Youth Scientific Conference]. Tambov: Izd. tsentr
FGBOU VO «TGTU», 2022.
20. Ainsworth M., Klasky S., Whitney B. Compression Using Lossless Decimation: Analysis and
Application, SIAM J. Sci. Comput., 2017, Vol. 39 (4), pp. B732-B757.
