Кто-нибудь знает проект, который реализует стандартные методы сжатия (например, Zip, GZip, BZip2, LZMA,...) с использованием NVIDIA CUDA library
Мне было интересно, не будут ли алгоритмы, которые могут использовать множество параллельных задач (например, сжатие), не будут работать намного быстрее на графической карте, чем с двойным или четырехъядерным процессором.
Что вы думаете о плюсах и минусах такого подхода?
Не знаю, кто-то сделал это и сделал его общедоступным. Просто ИМХО, это звучит не очень многообещающе.
Как указывает Мартинус, некоторые алгоритмы сжатия очень последовательны. Алгоритмы сжатия блоков, такие как LZW, могут быть распараллелены путем кодирования каждого блока независимо. Ziping большое дерево файлов можно распараллелить на уровне файла.
Однако ни один из них не является действительно SIMD-style parallelism (Single Instruction Multiple Data), и они не являются массово параллельными.
Графические процессоры - это в основном векторные процессоры, где вы можете выполнять сотни или тысячи инструкций ADD на этапе блокировки и выполнять программы, в которых очень мало зависящих от данных ветвей.
Алгоритмы сжатия в общем звуке больше похожи на модель программирования SPMD (Single Program Multiple Data) или MIMD (несколько инструкций с несколькими данными), которая лучше подходит для многоядерного процессора.
Алгоритмы сжатия видео могут быть объединены обработкой GPGPU, например CUDA, только в той степени, в которой существует очень большое количество блоков пикселей, которые косинусно-трансформированы или свернуты (для обнаружения движения) параллельно, а подпрограммы IDCT или convolution может быть выражена с помощью нераспределенного кода.
Графические процессоры также похожи на алгоритмы с высокой числовой интенсивностью (отношение математических операций к обращению к памяти). Алгоритмы с низкой числовой интенсивностью (например, с добавлением двух векторов) могут быть массивно параллельными и SIMD, но все еще медленнее на gpu, чем cpu, потому что они связаны с памятью.
Мы закончили первую фазу исследований, чтобы повысить производительность алгоритмов сжатия без потерь. Bzip2 был выбран для прототипа, наша команда оптимизировала только одну операцию - преобразование Burrows-Wheeler, и мы получили некоторые результаты: 2x-4x ускоряется на хороших сжимаемых файлах. Код работает быстрее во всех наших тестах.
Мы собираемся завершить bzip2, поддержку deflate и LZMA для некоторых реальных задач, таких как: HTTP-трафик и сжатие резервных копий.
ссылка на блог: http://www.wave-access.com/public_en/blog/2011/april/22/breakthrough-in-cuda-data-compression.aspx
Обычно алгоритмы сжатия не могут использовать параллельные задачи, нелегко сделать алгоритмы очень параллельными. В ваших примерах TAR не является алгоритмом сжатия, и единственным алгоритмом, который может быть высокопараллелизуемым, является BZIP, потому что это алгоритм сжатия блоков. Каждый блок может быть сжат отдельно, но для этого потребуется много и много памяти. LZMA также не работает параллельно, когда вы видите 7zip, используя несколько потоков, это связано с тем, что 7zip разбивает поток данных на 2 разных потока, каждый из которых сжат с помощью LZMA в отдельном потоке, поэтому сам алгоритм сжатия не является параллельным. Это расщепление работает только тогда, когда данные позволяют это.
Алгоритмы шифрования были довольно успешными в этой области, поэтому вам может понадобиться изучить это. Вот статья, связанная с шифрованием CUDA и AES: http://www.manavski.com/downloads/PID505889.pdf
Мы пытаемся портировать bzip2 на CUDA.:) До сих пор (и только с грубыми испытаниями) наше преобразование Берроуза-Уилера на 30% быстрее, чем последовательный алгоритм. http://bzip2.github.com
30% хорош, но для таких приложений, как резервные копии, это недостаточно.
Мой опыт заключается в том, что средний поток данных в таких случаях получает сжатие 1,2-1,7: 1 с использованием gzip и заканчивается ограниченным объемом вывода 30-60 Мбит/с (это происходит в широком диапазоне современных (около 2010- 2012) среднего класса.
Ограничение здесь обычно - это скорость, с которой данные могут передаваться в самом ЦП.
К сожалению, для того, чтобы поддерживать ленточный накопитель LTO5, ему нужна сырая (несжимаемая) скорость передачи данных около 160 Мбит/с. При подаче сжимаемых данных требуется еще более высокая скорость передачи данных.
Сжатие LTO явно намного быстрее, но несколько неэффективно (эквивалентно gzip -1 - это достаточно хорошо для большинства целей). Приводы LTO4 и выше, как правило, встроены в механизмы шифрования AES-256, которые также могут поддерживать такие скорости.
Что это значит для моего случая, так это то, что мне понадобится 400% или лучше импрессивность, чтобы считать это стоящим.
Аналогичные соображения применимы к сетям. При скорости 30 Мбит/с сжатие является препятствием для сетей Gb-класса, и возникает вопрос, следует ли тратить больше средств на сетевое взаимодействие или на сжатие...:)