Libreria di compressione che utilizza CUDA di Nvidia [chiuso]

Question

Qualcuno conosce un progetto che implementa metodi di compressione standard (come Zip, GZip, BZip2, LZMA, ...) usando NVIDIA libreria CUDA ?

Mi chiedevo se gli algoritmi che possono fare uso di molte attività parallele (come la compressione) non funzionerebbero molto più velocemente su una scheda grafica che con una CPU dual o quadcore.

Cosa ne pensi dei pro e dei contro di un simile approccio?

Answer 1

Non sono a conoscenza di nessuno che l'abbia fatto e reso pubblico. Solo IMHO, non sembra molto promettente.

Come sottolinea Martinus, alcuni algoritmi di compressione sono altamente seriali. Gli algoritmi di compressione dei blocchi come LZW possono essere parallelizzati codificando ciascun blocco in modo indipendente. La compressione di un grande albero di file può essere parallelizzata a livello di file.

Tuttavia, nessuno di questi è in realtà un parallelismo in stile SIMD (dati multipli per istruzioni singole) e non sono massicciamente paralleli.

Le GPU sono fondamentalmente processori vettoriali, dove puoi fare centinaia o migliaia di istruzioni ADD tutte in fase di blocco ed eseguire programmi in cui ci sono pochissimi rami dipendenti dai dati.

Gli algoritmi di compressione in generale suonano più come un modello di programmazione SPMD (Single Program Multiple Data) o MIMD (Multiple Instruction Multiple Data), che è più adatto al cpus multicore.

Gli algoritmi di compressione video possono essere accelerati dall'elaborazione GPGPU come CUDA solo nella misura in cui esiste un numero molto grande di blocchi di pixel che vengono trasformati in coseno o contorti (per il rilevamento del movimento) in parallelo, e le subroutine IDCT o di convoluzione può essere espresso con un codice branchless.

Le GPU amano anche gli algoritmi che hanno un'alta intensità numerica (il rapporto tra operazioni matematiche e accessi alla memoria.) Gli algoritmi con bassa intensità numerica (come l'aggiunta di due vettori) possono essere massicciamente paralleli e SIMD, ma continuano a funzionare più lentamente sulla GPU rispetto alla GPU CPU perché sono associati alla memoria.

Answer 2

Abbiamo terminato la prima fase della ricerca per aumentare le prestazioni degli algoritmi di compressione dei dati senza perdita di dati. Bzip2 è stato scelto per il prototipo, il nostro team ha ottimizzato una sola operazione - Burrows & # 8211; Trasformazione Wheeler, e abbiamo ottenuto alcuni risultati: velocità 2x-4x su buoni file comprimibili. Il codice funziona più velocemente su tutti i nostri test.

Completeremo bzip2, supporteremo deflate e LZMA per alcune attività reali come: traffico HTTP e compressione dei backup.

link al blog: http: // www .wave-access.com / public_en / blog / 2011 / Aprile / 22 / innovazione-in-CUDA-dati-compression.aspx

Answer 3

In genere gli algoritmi di compressione non possono utilizzare attività parallele, non è facile rendere gli algoritmi altamente parallelizzabili. Nei tuoi esempi, TAR non è un algoritmo di compressione e l'unico algoritmo che potrebbe essere altamente parallelizzabile è BZIP perché è un algoritmo di compressione a blocchi. Ogni blocco può essere compresso separatamente, ma ciò richiederebbe molta e molta memoria. LZMA non funziona neanche in parallelo, quando vedi 7zip usando più thread questo è perché 7zip divide il flusso di dati in 2 flussi diversi che sono compressi con LZMA in un thread separato, quindi l'algoritmo di compressione stesso non è parallelo. Questa suddivisione funziona solo quando i dati lo consentono.

Answer 4

Gli algoritmi di crittografia hanno avuto abbastanza successo in questo settore, quindi potresti voler esaminare questo. Ecco un documento relativo alla crittografia CUDA e AES: http://www.manavski.com/downloads/PID505889.pdf

Answer 5

Stiamo tentando di eseguire il porting di bzip2 su CUDA. :) Fino ad ora (e solo con test approssimativi), la nostra trasformazione di Burrows-Wheeler è del 30% più veloce dell'algoritmo seriale. http://bzip2.github.com

Answer 6

Il 30% è bello, ma per applicazioni come i backup non è sufficiente da un colpo lungo.

La mia esperienza è che il flusso di dati medio in questi casi ottiene una compressione 1,2-1,7: 1 usando gzip e finisce limitato a una velocità di uscita di 30-60 Mb / s (questo è attraverso una vasta gamma di moderni (circa 2010- 2012) CPU di fascia medio-alta.

La limitazione qui è di solito la velocità con cui i dati possono essere inseriti nella CPU stessa.

Sfortunatamente, per rendere felice un'unità nastro LTO5, è necessaria una velocità dati grezza (non comprimibile) di circa 160 Mb / s. Se alimentato con dati comprimibili, richiede velocità di trasferimento dati ancora più elevate.

La compressione LTO è chiaramente molto più veloce, ma in qualche modo inefficiente (equivalente a gzip -1 - è abbastanza buono per la maggior parte degli scopi). Le unità LTO4 e verso l'alto di solito hanno motori di crittografia AES-256 integrati che possono anche mantenere questo tipo di velocità.

Ciò che questo significa per il mio caso è che avrei bisogno di un potenziamento del 400% o migliore per considerarlo utile.

Considerazioni simili si applicano a tutte le LAN. A 30 Mb / s, la compressione è un ostacolo per le reti di classe Gb e la domanda è se spendere di più in rete o in compressione ... :)