Вибір редакції

Новый алгоритм скоростной компрессии данных

15 ноября, 2018. 08:11
Первоначально, сжатие информации использовалась для экономии информационного пространства на долговременных носителях информации. Постепенно эта задача утрачивает актуальность, сейчас проблем с емкостью носителей для хранения данных уже практически нет. В настоящее время сжатие информации актуально для «уплотнения» каналов передачи данных, чтобы прокачать за единицу времени как можно больше информации.

Имеющиеся алгоритмы компрессии, реализованные программно, работают на скоростях до 70-100МегаБайт/сек. и могут удовлетворить потребности относительно низкоскоростных каналов связи.

Более скоростные каналы передачи данных, включая связь дисковых подсистем и оперативной памяти (скорость до 3ГигаБайт/сек) обслуживаться существующими программными компрессорами не могут.

Новый алгоритм компрессии

Чтобы операция сжатия информации перестала быть «бутылочным горлышком» в прохождении данных между системами хранения на современных HDDи SSDдисков и Оперативной памятью требуется создать алгоритм компрессии с темпом реальной работы не менее 3 ГигаБайт/сек. и не загружающего при этом процессор.

Для решения этой задачи был создан новый алгоритм компрессии максимально быстро реализуемый в аппаратуре и системе команд современных процессоров х86/64.

Алгоритм имеет следующие особенности:

- Используется символьное представление данных с грануляцией кратной 8бит

- Используется один проход по сжимаемым данным

- Цикл создания сжатого образа совмещен с циклом поиска совпадений

- Индексация совпадений выполнена на базе относительных смещений

- Индексируются частично совпадающие блоки

- Если размер индекса больше индексируемой экономии то он отбрасывается

- Выявление совпадающих блоков производится методом сдвигов кратных символу

- Применяются только последовательные операции чтения/записи данных

- Все операции сжатия/распаковки выполняются на регистрах процессора

- Промежуточные данные хранятся на регистрах процессора

- Буфер исходного и сжатого текста совмещены (в цикле упаковки)

- Служебный буфер имеет размер ¼ исходного буфера (в цикле упаковки)

- В цикле распаковки служебные буфера не используются.

Новый алгоритм использует для поиска совпадений символьных строк Кеш первого уровня процессорного ядра (окно поиска совпадений 16 кБайт).

Алгоритм использует индивидуальный Кеш первого уровня процессорного ядра, поэтому процедура компрессии может масштабироваться на все физические ядра без потери быстродействия.

Поиск совпадений выполняется на регистрах YMMдлиной в 32байта, в окне просмотра 16кБайт, из-за этих ограничений новый алгоритм уступает по степени сжатия известным методам, но существенно превосходит их в скорости выполнения операций компрессии и декомпрессии.

На стенде получена скорость упаковки/распаковки 10ГигаБайт/сек. для одного процессорного ядра работающего на частоте 4ГигаГерца.

ЧИТАТЬ МАТЕРИАЛ
Комментарии: