Bibliothèque de Compression à l'aide de Nvidia CUDA

Question

Quelqu'un sait-il d'un projet qui met en œuvre la norme méthodes de compression (Zip, GZip, BZip2, LZMA,...) à l'aide de NVIDIA CUDA de la bibliothèque?

Je me demandais si les algorithmes qui peut rendre l'utilisation de beaucoup de tâches en parallèle (comme la compression) ne serait pas beaucoup plus rapide sur une carte graphique qu'avec un double ou un CPU quadcore.

Que pensez-vous sur les avantages et les inconvénients d'une telle approche?

---

Edit: Suppression du "GOUDRON" (Copier-Coller l'erreur), comme mentionné par martinus.

Answer 1

Nous avons terminé la première phase de la recherche pour améliorer les performances des algorithmes de compression de données sans perte. Bzip2 a été choisi pour le prototype, notre équipe optimisé en une seule opération - transformée de Burrows–Wheeler transformation, et nous avons obtenu quelques résultats: 2x-4x vitesse sur les bons fichiers compressibles. Le code fonctionne plus rapidement sur l'ensemble de nos tests.

Nous allons compléter bzip2, soutien dégonfler et LZMA pour certains la vie réelle des tâches comme: le trafic HTTP et les sauvegardes à la compression.

lien de blog: http://waveaccessllc.blogspot.com/2011/04/breakthrough-in-cuda-data-compression.html

Answer 2

Pas au courant de toute personne ayant fait cela, et rendu public. Juste à mon humble avis, il n'a pas l'air très prometteur.

Comme Martinus points, certains algorithmes de compression sont très série. Bloquer les algorithmes de compression comme LZW peut être parallélisée par le codage de chaque bloc indépendamment. Ziping un grand arbre de fichiers peut être parallélisée au niveau du fichier.

Cependant, aucun d'eux n'est vraiment SIMD-style parallélisme (Single Instruction Multiple Data), et ils ne sont pas massivement parallèle.

Les gpu sont essentiellement vecteur processeurs, où vous pouvez faire des centaines ou des milliers d'AJOUTER des instructions à tous dans l'étape de verrouillage, et l'exécution de programmes où il y a très peu de données dépendant de branches.

Les algorithmes de Compression en général ressemble plus à un SPMD (Single Program Multiple Data) ou MIMD (Multiple Instruction Multiple Data) modèle de programmation, qui est mieux adaptée aux processeurs multicœurs.

Les algorithmes de compression vidéo peut être accellerated par GPGPU traitement comme CUDA seulement dans la mesure où il existe un très grand nombre de pixels des blocs qui sont en cours de cosinus de transformer ou de convolé (pour la détection de mouvement) en parallèle, et l'IDCT ou de convolution des sous-programmes peuvent être exprimées avec sans branches code.

Gpu aussi comme des algorithmes qui ont une forte numérique de l'intensité (le ratio des opérations mathématiques à l'accès à la mémoire.) Des algorithmes avec une faible numérique de l'intensité (comme l'ajout de deux vecteurs) peut être massivement parallèle et SIMD, mais encore de s'exécuter plus lentement sur le gpu que le cpu parce qu'ils sont lié à la mémoire.

Answer 3

Généralement, les algorithmes de compression ne peut pas faire usage de tâches en parallèle, il n'est pas facile de faire les algorithmes hautement parallelizeable. Dans votre exemple, le GOUDRON n'est pas un algorithme de compression, et le seul algorithme qui peut être très parallelizeable est BZIP parce que c'est un bloc de l'algorithme de compression. Chaque bloc peut être compressé séparément, mais cela demande beaucoup de mémoire. LZMA ne fonctionne pas en parallèle soit, quand vous voyez 7zip l'utilisation de plusieurs threads c'est parce que 7zip divise le flux de données dans 2 différents cours d'eau que chaque compressés avec LZMA dans un thread séparé, de sorte que l'algorithme de compression elle-même n'est pas paralllel. Ce fractionnement ne fonctionne que lorsque les données le permettent.

Answer 4

Les algorithmes de chiffrement ont été très réussie dans ce domaine, de sorte que vous voudrez peut-être regarder dans que. Voici un document lié à CUDA et le chiffrement AES:http://www.manavski.com/downloads/PID505889.pdf

Answer 5

Nous faisons une tentative de portage bzip2 à CUDA. :) Jusqu'à présent (et avec seulement approximative, les tests effectués), nos transformée de Burrows-Wheeler Transformation est 30% plus rapide que le numéro de série de l'algorithme. http://bzip2.github.com