Domanda Libreria di compressione con CUDA di Nvidia [chiusa]


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?


45
2018-01-19 07:54


origine


risposte:


Non sapendo che qualcuno lo ha fatto e reso pubblico. Solo IMHO, non sembra molto promettente.

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

Tuttavia, nessuno di questi è in realtà un parallelismo in stile SIMD (Single Instruction Multiple Data), e non sono massicciamente paralleli.

Le GPU sono fondamentalmente processori vettoriali, in cui è possibile eseguire centinaia o migliaia di istruzioni ADD in blocco e eseguire programmi in cui sono presenti 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 per cpus multicore.

Gli algoritmi di compressione video possono essere accelerati dall'elaborazione GPGPU come CUDA solo nella misura in cui esiste un numero molto elevato di blocchi di pixel che vengono trasformati o convoluti dal coseno (per il rilevamento del movimento) in parallelo e le subroutine IDCT o convoluzione possono essere espresse con codice senza ramo.

Alle GPU piacciono anche gli algoritmi che hanno un'intensità numerica elevata (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 funzionano più lentamente sulla CPU rispetto alla CPU perché sei legato alla memoria.


35
2018-01-20 22:41



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

Stiamo per completare bzip2, supportare deflate e LZMA per alcune attività reali come: compressione del traffico e dei backup HTTP.

collegamento al blog: http://www.wave-access.com/public_en/blog/2011/april/22/breakthrough-in-cuda-data-compression.aspx


43
2018-04-22 16:46



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 può essere altamente parallelizzabile è BZIP perché è un algoritmo di compressione a blocchi. Ogni blocco può essere compresso separatamente, ma ciò richiederebbe molta e molta memoria. Anche LZMA non funziona in parallelo, quando vedi 7zip usando thread multipli questo perché 7zip divide il flusso di dati in 2 flussi diversi che sono tutti compressi con LZMA in un thread separato, quindi l'algoritmo di compressione non è parallelo. Questa suddivisione funziona solo quando i dati lo consentono.


7
2018-01-19 08:04



Gli algoritmi di crittografia hanno avuto un certo successo in quest'area, quindi potresti volerlo esaminare. Ecco un documento relativo alla crittografia CUDA e AES:http://www.manavski.com/downloads/PID505889.pdf 


2
2018-01-19 08:32



Stiamo tentando di trasferire bzip2 in CUDA. :) Finora (e con solo test approssimativi effettuati), la nostra Transform Burrows-Wheeler è il 30% più veloce dell'algoritmo seriale. http://bzip2.github.com


2
2017-12-23 11:39



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

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

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

Sfortunatamente, per mantenere una unità nastro LTO5 felice, ha bisogno di a crudo (non comprimibile) velocità di trasmissione di circa 160 Mb / s. Se alimentati dati compressibili, richiede velocità di trasmissione ancora più veloci.

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

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

Considerazioni simili si applicano alle LAN. A 30 Mb / s, la compressione è un ostacolo sulle reti di classe Gb e la domanda è se spendere di più sul networking o sulla compressione ... :)


1
2018-03-05 15:58