842 (алгоритм сжатия)

842 , 8-4-2 или EFT — это алгоритм сжатия данных . Это вариант сжатия Лемпеля-Зива с ограниченной длиной словаря. Для типичных данных 842 обеспечивает от 80 до 90 процентов сжатия LZ77 с гораздо более высокой пропускной способностью и меньшим использованием памяти. ^[1] Аппаратные реализации также обеспечивают минимальное потребление энергии и минимальную площадь чипа.

Сжатие 842 можно использовать для сжатия виртуальной памяти , для баз данных — особенно для хранилищ, ориентированных на столбцы , и при потоковой передаче ввода-вывода — например, для создания резервных копий или записи в файлы журналов .

Алгоритм [ править ]

Алгоритм работает с блоками по 8 байт с подфразами по 8, 4 и 2 байта. Хэш каждой фразы используется для поиска хеш-таблицы со смещениями в буфере скользящего окна прошлых закодированных данных. Совпадения можно заменить смещением, поэтому результатом для каждого блока может быть некоторая смесь совпадающих данных и новых литеральных данных. ^[2]^[1]^[3]

Реализации [ править ]

IBM добавила аппаратные ускорители и инструкции для сжатия 842 в свои Power процессоры , начиная с POWER7+ . ^[4] Кроме того, в POWER9 и Power10 добавлено аппаратное ускорение для RFC 1951 алгоритма Deflate , который используется zlib и gzip . ^[5]

для Драйвер устройства аппаратного сжатия 842 на процессоре POWER был добавлен в ядро Linux в 2011 году. ^[6] В последнее время Linux может вернуться к программной реализации, что, конечно, намного медленнее. ^[7] zram , модуль ядра Linux для дисков со сжатым RAM , можно настроить на использование 842.

Исследователи реализовали 842 с использованием графических процессоров и обнаружили, что распаковка примерно в 30 раз быстрее с использованием выделенных графических процессоров. ^[8] Библиотека с открытым исходным кодом предоставляет 842 для CUDA и OpenCL . ^[9] Реализация 842 на FPGA продемонстрировала в 13 раз большую пропускную способность, чем программная реализация. ^[10]

Ссылки [ править ]

^ Перейти обратно: ^а ^б Плаут, Макс; Польце, Андреас. «На пути к повышению эффективности передачи данных для ускорителей с использованием аппаратного сжатия» .
^ Франашек, Питер А; Ластрас-Монтаньо, Луис А; Пэн, Сун; Робинсон, Джон Т. (14 сентября 2016 г.). «Сжатие данных с ограниченным анализом» . Исследования IBM . ИБМ . Проверено 13 июля 2021 г.
^ Бланер, Б.; Абали, Б.; Басс, Б.М.; Чари, С.; Калла, Р.; Кункель, С.; Лауриселла, К.; Ливенс, Р.; Рейли, Джей-Джей; Сэндон, Пенсильвания (ноябрь 2013 г.). «Встроенные ускорители процессора IBM POWER7+ для криптографии и расширения активной памяти» . Журнал исследований и разработок IBM . 57 (6): 3:1–3:16. дои : 10.1147/JRD.2013.2280090 . Проверено 13 июля 2021 г.
^ «Сжатие POWER NX842 для Db2» (PDF) . ИБМ . Проверено 13 июля 2021 г.
^ Вил, Брайан Ф (14 марта 2022 г.). «Ускорение GZip с помощью AIX в энергосистемах» . Сообщество IBM Power . ИБМ . Проверено 22 октября 2022 г.
^ «Торвальдс/Линукс» . Гитхаб . 12 февраля 2022 г.
^ «Торвальдс/Линукс» . Гитхаб . 12 февраля 2022 г.
^ Плаут, Макс; Польце, Андреас (2019). «Декомпрессия на основе графического процессора для алгоритма 842» . 2019 Седьмой международный симпозиум по вычислительной технике и сетям (CANDARW) . стр. 97–102. дои : 10.1109/CANDARW.2019.00025 . ISBN 978-1-7281-5268-4 . S2CID 210694935 .
^ «Либ842» . Гитхаб . 3 ноября 2020 г.
^ Сухвани, Бхарат; Абали, Бюлент; Бреццо, Бернар; Асаад, Самех (2011). «Высокопроизводительное сжатие данных без потерь на FPGA». 2011 19-й ежегодный международный симпозиум IEEE по программируемым пользовательским вычислительным машинам . IEEE. стр. 113–116. дои : 10.1109/FCCM.2011.56 . ISBN 978-1-61284-277-6 . S2CID 7828316 . Проверено 22 октября 2022 г. {{cite book}}: |website= игнорируется ( помогите )

[plauth_polze-1] Перейти обратно: ^а ^б Плаут, Макс; Польце, Андреас. «На пути к повышению эффективности передачи данных для ускорителей с использованием аппаратного сжатия» .

[842paper-2] Франашек, Питер А; Ластрас-Монтаньо, Луис А; Пэн, Сун; Робинсон, Джон Т. (14 сентября 2016 г.). «Сжатие данных с ограниченным анализом» . Исследования IBM . ИБМ . Проверено 13 июля 2021 г.

[3] Бланер, Б.; Абали, Б.; Басс, Б.М.; Чари, С.; Калла, Р.; Кункель, С.; Лауриселла, К.; Ливенс, Р.; Рейли, Джей-Джей; Сэндон, Пенсильвания (ноябрь 2013 г.). «Встроенные ускорители процессора IBM POWER7+ для криптографии и расширения активной памяти» . Журнал исследований и разработок IBM . 57 (6): 3:1–3:16. дои : 10.1147/JRD.2013.2280090 . Проверено 13 июля 2021 г.

[4] «Сжатие POWER NX842 для Db2» (PDF) . ИБМ . Проверено 13 июля 2021 г.

[5] Вил, Брайан Ф (14 марта 2022 г.). «Ускорение GZip с помощью AIX в энергосистемах» . Сообщество IBM Power . ИБМ . Проверено 22 октября 2022 г.

[6] «Торвальдс/Линукс» . Гитхаб . 12 февраля 2022 г.

[7] «Торвальдс/Линукс» . Гитхаб . 12 февраля 2022 г.

[8] Плаут, Макс; Польце, Андреас (2019). «Декомпрессия на основе графического процессора для алгоритма 842» . 2019 Седьмой международный симпозиум по вычислительной технике и сетям (CANDARW) . стр. 97–102. дои : 10.1109/CANDARW.2019.00025 . ISBN 978-1-7281-5268-4 . S2CID 210694935 .

[9] «Либ842» . Гитхаб . 3 ноября 2020 г.

[10] Сухвани, Бхарат; Абали, Бюлент; Бреццо, Бернар; Асаад, Самех (2011). «Высокопроизводительное сжатие данных без потерь на FPGA». 2011 19-й ежегодный международный симпозиум IEEE по программируемым пользовательским вычислительным машинам . IEEE. стр. 113–116. дои : 10.1109/FCCM.2011.56 . ISBN 978-1-61284-277-6 . S2CID 7828316 . Проверено 22 октября 2022 г. {{cite book}}: |website= игнорируется ( помогите )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]