Kompressions-Bibliothek mit Nvidias CUDA [geschlossen]

Question

Kennt jemand ein Projekt, das Standard-Kompressionsverfahren implementiert (wie Zip, gzip, bzip2, LZMA, ...) mit NVIDIAs CUDA-Bibliothek ?

Ich frage mich, ob Algorithmen, die Verwendung von vielen parallelen Aufgaben (wie Kompression) machen kann, würde nicht viel schneller auf einer Grafikkarte als mit einem Dual- oder Quad-Core-CPU ausgeführt werden.

Was denken Sie über die Vor- und Nachteile eines solchen Ansatzes?

Answer 1

Nicht bewusst, dass irgendjemand getan, und machte es öffentlich. Nur IMHO, ist es nicht sehr vielversprechend klingen.

Als Martinus weist darauf hin, sind einige Komprimierungsalgorithmen sehr serial. Block Kompressionsalgorithmen wie LZW kann durch Codieren jedes Blocks unabhängig parallelisiert werden. ein großer Baum von Dateien Ziping kann auf Dateiebene parallelisiert werden.

Doch keiner von ihnen ist wirklich SIMD-Stil Parallelität (Single Instruction Multiple Data), und sie sind nicht massiv parallel.

GPUs sind im Grunde Vektorprozessoren, wo Sie Hunderte oder Tausende von ADD Anweisungen alle im Gleichschritt zu tun, und Ausführen von Programmen werden können, wo es nur sehr wenige datenabhängige Verzweigungen.

Kompressionsalgorithmen im Allgemeinen Ton eher wie ein SPMD (Single Programm Multiple Data) oder MIMD (Multiple Instruction Multiple Data) Programmiermodell, das auf Multi-Core-CPUs besser geeignet ist.

Video-Kompressionsalgorithmen können in dem Umfang nur durch GPGPU Verarbeitung wie CUDA beschleunigte werden, dass es eine sehr große Anzahl von Pixelblöcken, die Cosinus-transformiert werden oder gefaltet (für die Bewegungserkennung) parallel und die IDCT oder Faltungs Subroutinen kann mit branchless Code ausgedrückt werden.

GPUs sehen auch Algorithmen, die eine hohe numerische Intensität haben (das Verhältnis der mathematische Operationen an den Speicher zugreift.) Algorithmen mit geringer numerischer Intensität (wie das Hinzufügen von zwei Vektoren) können massiv parallelen und SIMD sein, aber immer noch langsamer laufen auf der GPU als die cpu, weil sie Speicher gebunden ist.

Answer 2

Wir haben fertig erste Phase der Forschungsleistung von lossless Datenkomprimierungsalgorithmen zu erhöhen. Bzip2 wurde für den Prototyp gewählt, unser Team nur eine Operation optimiert - Burrows-Wheeler-Transformation, und wir haben einige Ergebnisse: 2x-4x auf gut komprimierbaren Dateien beschleunigen. Der Code funktioniert schneller auf allen unseren Tests.

Wir werden bzip2 vervollständigen, Unterstützung deflate und LZMA für einige wirkliche Leben Aufgaben wie:. HTTP-Datenverkehr und Backups Komprimierung

Blog Link: http: // www .wave-access.com / public_en / blog / 2011 / April / 22 / Durchbruch-in-CUDA-data-compression.aspx

Answer 3

Normalerweise Algorithmen Kompression nicht Verwendung von parallelen Aufgaben machen kann, ist es nicht einfach, die Algorithmen sehr parallelizeable zu machen. In Ihren Beispielen ist TAR kein Komprimierungsalgorithmus, und der einzige Algorithmus, der sehr parallelizeable sein könnte, ist BZIP, weil es ein Blockkompressionsalgorithmus ist. Jeder Block kann separat komprimiert werden, aber dies würde viel, viel Speicher benötigen. LZMA funktioniert nicht entweder parallel, wenn man unter Verwendung mehrerer Threads 7zip sehen ist dies, weil 7zip den Datenstrom in zwei verschiedene Ströme aufteilt, die jeweils in einem separaten Thread mit LZMA komprimiert werden, so dass der Komprimierungsalgorithmus selbst paralllel nicht. Diese Aufteilung funktioniert nur, wenn die Daten dies zulässt.

Answer 4

Verschlüsselungsalgorithmen haben in diesem Bereich sehr erfolgreich, so dass Sie in die aussehen möchten. Hier ist ein Papier im Zusammenhang mit CUDA und AES-Verschlüsselung: http://www.manavski.com/downloads/PID505889.pdf

Answer 5

Wir machen einen Versuch, bei bzip2 zu CUDA portieren. :) So weit (und mit nur groben Tests durchgeführt), unser Burrows-Wheeler-Transformation ist 30% schneller als der serielle Algorithmus. http://bzip2.github.com

Answer 6

30% ist schön, aber für Anwendungen wie Backups ist es nicht genug, um durch eine lange erschossen.

Meine Erfahrung ist, dass die durchschnittliche Datenstrom in solchen Fällen bekommt 1,2-1,7: 1-Komprimierung mit gzip und endet beschränkt sich auf einer Ausgaberate von 30-60Mb / s (das in einem breiten Spektrum von modern (ca. 2010- 2012) mittel High-End-CPUs.

Die Einschränkung hier ist in der Regel die Geschwindigkeit, mit den Daten in die CPU selbst zugeführt werden.

Leider, um ein LTO-5-Bandlaufwerk bei Laune zu halten, braucht es eine raw (komprimierbare) Datenrate von rund 160 MB / s. Wenn komprimierbaren Daten füttert es erfordert eine noch schnellere Datenraten.

LTO Kompression ist eindeutig viel schneller, aber etwas ineffizient (entspricht -1 bis gzip - es ist gut genug für die meisten Zwecke). LTO4 Laufwerke und aufwärts haben in der Regel integrierte AES-256-Verschlüsselung Motoren, die auch diese Art von Geschwindigkeiten beibehalten können.

Was bedeutet das für mein Fall ist, dass ich eine 400% oder besser impreovement, um es lohnt sich schon daran gedacht hatte.

ähnliche Überlegungen gelten für LANs. Bei 30Mb / s, Komprimierung ist ein Hinderniss auf Gb-Klasse-Netzwerken und die Frage, ob mehr auf Vernetzung verbringen oder auf Kompression ...:)