Библиотека сжатия с использованием Nvidia CUDA
Кто-нибудь знает проект, который реализует стандартные методы сжатия (например, Zip, GZip, BZip2, LZMA, ...) с использованием NVIDIA Библиотека CUDA?
Мне было интересно, не будут ли алгоритмы, которые могут использовать множество параллельных задач (например, сжатие), работать на видеокарте намного быстрее, чем с двух- или четырехъядерным процессором.
Что вы думаете о плюсах и минусах такого подхода?
В этой презентации основное внимание уделяется Gzip и ускорению порядка 10 on-demand.gputechconf.com/gtc/2014/presentations/….
Ответы 6
Обычно алгоритмы сжатия не могут использовать параллельные задачи, нелегко сделать алгоритмы распараллеливаемыми. В ваших примерах TAR не является алгоритмом сжатия, и единственный алгоритм, который может быть сильно распараллелен, - это BZIP, потому что это алгоритм сжатия блоков. Каждый блок можно сжать отдельно, но для этого потребуется много-много памяти. LZMA также не работает параллельно, когда вы видите, что 7zip использует несколько потоков, это связано с тем, что 7zip разделяет поток данных на 2 разных потока, каждый из которых сжимается с помощью LZMA в отдельном потоке, поэтому сам алгоритм сжатия не параллелен. Это разделение работает только тогда, когда данные позволяют это.
Encryption algorithms have been quite successful in this area, so you might want to look into that. Here is a paper related to CUDA and AES encryption:http://www.manavski.com/downloads/PID505889.pdf
На первый взгляд кажется, что это ускоряет шифрование каждого блока. Не помогает то, что блочные шифры нужно связывать в цепочку, чтобы избежать определенных типов атак. en.wikipedia.org/wiki/Block_cipher_modes_of_operation
Это правда, что эта статья не касается этого, но есть статья в драгоценных камнях графического процессора, написанная коллегой о расшифровке AES с помощью шейферного кода, а не Cuda, которая охватывает цепочки. К сожалению, статьи нет в сети. В любом случае цепочка может обрабатываться графическим процессором
Неизвестно, что кто-то это сделал и обнародовал. Просто ИМХО, это звучит не очень многообещающе.
Как указывает Мартинус, некоторые алгоритмы сжатия очень последовательны. Алгоритмы сжатия блоков, такие как LZW, могут быть распараллелены путем независимого кодирования каждого блока. Архивирование большого дерева файлов можно распараллелить на уровне файлов.
Однако ни один из них не является параллелизмом в стиле SIMD (одна инструкция и несколько данных), и они не являются массово параллельными.
Графические процессоры - это в основном векторные процессоры, в которых вы можете выполнять сотни или тысячи инструкций ADD на этапе блокировки и выполнять программы, в которых очень мало ветвей, зависящих от данных.
Алгоритмы сжатия в целом больше похожи на модель программирования SPMD (Single Program Multiple Data) или MIMD (Multiple Instruction Multiple Data), которая лучше подходит для многоядерных процессоров.
Алгоритмы сжатия видео могут быть ускорены обработкой GPGPU, такой как CUDA, только в той степени, в которой существует очень большое количество блоков пикселей, которые параллельно подвергаются косинусному преобразованию или свертке (для обнаружения движения), а подпрограммы IDCT или свертки могут быть выражены с внеблоковым кодом.
Графическим процессорам также нравятся алгоритмы с высокой числовой интенсивностью (отношение математических операций к доступу к памяти). Алгоритмы с низкой числовой интенсивностью (например, сложение двух векторов) могут быть массово параллельными и SIMD, но все же работать на графическом процессоре медленнее, чем на центральном процессоре, потому что они привязаны к памяти.
Моя первая мысль о параллелизации была связана с «большим деревом файлов», но другие причины, о которых вы упомянули, убедили меня, спасибо.
Можете ли вы ссылаться на измерения, которые показывают, что алгоритмы с привязкой к памяти (например, добавление двух векторов) работают медленнее на GPU, чем на CPU?
@bene Я неправильно это сформулировал. Алгоритмы с привязкой к памяти могут работать на графическом процессоре так же быстро или быстрее - большинство графических процессоров имеют очень высокую пропускную способность памяти. Какой бы процессор ни имел самую высокую эффективную пропускную способность памяти, он будет выполнять эти алгоритмы быстрее.Однако, если вы берете данные на процессор, передаете их на графический процессор (обычно через шину PCIE), затем выполняете добавление, а затем передаете данные обратно в cpu, который всегда будет намного медленнее, и для этого очень легко построить тест.
Мы пытаемся перенести bzip2 на CUDA. :) Пока (и только после грубых тестов) наше преобразование Барроуза-Уиллера на 30% быстрее последовательного алгоритма. http://bzip2.github.com
Насколько я могу судить, bzip2 использует несколько ядер ЦП, но не CUDA. Ссылка не работает. Текущая ссылка кажется bzip.org
Мы завершили первый этап исследований по повышению производительности алгоритмов сжатия данных без потерь. В качестве прототипа был выбран Bzip2, наша команда оптимизировала только одну операцию - преобразование Барроуза – Уиллера, и мы получили некоторые результаты: ускорение в 2-4 раза на хорошо сжимаемых файлах. Код работает быстрее во всех наших тестах.
Мы собираемся завершить bzip2, поддерживать deflate и LZMA для некоторых реальных задач, таких как: HTTP-трафик и сжатие резервных копий.
ссылка на блог: http://www.wave-access.com/public_en/blog/2011/april/22/breakthrough-in-cuda-data-compression.aspx
Плюс один за ответ на этот вопрос через год после его публикации. Плюс ваша работа выглядит интересной, спасибо
Прошло 4 года ... Я (все мы) хотел бы больше узнать о вашем проекте. Какие результаты? Где найти источники, если таковые имеются? Ждем ваших отзывов
Александр, есть новости? Код есть где-нибудь?
Я нашел этот libbsc.com только для справки, я не изучал его, но он мертв уже ~ 7 лет (это 2019 год!)
30% - это хорошо, но для таких приложений, как резервное копирование, этого явно недостаточно.
Мой опыт показывает, что средний поток данных в таких случаях получает сжатие 1,2-1,7: 1 с использованием gzip и в конечном итоге ограничивается скоростью вывода 30-60 Мбит / с (это относится к широкому спектру современных (примерно 2010-2012) носителей. -high-end процессоры.
Ограничением здесь обычно является скорость, с которой данные могут быть загружены в сам ЦП.
К сожалению, для того, чтобы ленточный накопитель LTO5 оставался довольным, ему нужна скорость передачи данных сырой (без сжатия) около 160 Мбит / с. При подаче сжимаемых данных требуется еще более высокая скорость передачи данных.
Сжатие LTO явно намного быстрее, но несколько неэффективно (эквивалентно gzip -1 - этого достаточно для большинства целей). Диски LTO4 и выше обычно имеют встроенные механизмы шифрования AES-256, которые также могут поддерживать такие скорости.
В моем случае это означает, что мне потребуется очистка на 400% или выше, чтобы я сочла это целесообразным.
Аналогичные соображения применимы к локальным сетям. На скорости 30 Мбит / с сжатие является помехой в сетях класса Gb, и вопрос в том, тратить ли больше на сеть или на сжатие ... :)
Что такое ограничения памяти CUDAS? Т.е. составляет от 4K до 32K блоков слишком много для параллельной обработки данных, gzip можно сжимать параллельно, не сохраняя словарь между блоками, это увеличивает размер файла примерно на 5%. Видеть. Dictzip для примера.