Parallelizzazione di un algoritmo per la marchiatura video

1 INTRODUZIONE
Negli ultimi anni abbiamo assistito a un completo abbandono dei formati 
audio/video analogici in favore di quelli digitali.
E' molto facile e poco dispendioso, in termini economici, effettuare copie 
illegali di un file multimediale. Questo ha portato a un grande incremento 
della pirateria, accentuato ancora di più dallo sviluppo di Internet; oggigiorno 
ad esempio è diventata una cosa comune scaricare film dalla rete. Tutto 
questo ha comportato la necessità di migliorare e sviluppare nuove tecniche 
per proteggere il diritto d'autore. Ad oggi il metodo che viene considerato 
migliore per proteggere il copyright è il watermarking, termine che si riferisce 
all'inclusione di un marchio all'interno di un file multimediale che può essere 
successivamente rilevato ed estratto per trarre informazioni sull'origine e 
1
provenienza di tale file; per mezzo del watermark il documento è ancora 
accessibile ma è contrassegnato in maniera permanente. La tecnica del 
watermarking digitale può essere utilizzata per diversi scopi: rendere 
manifesto a tutti gli utenti chi sia il legittimo proprietario del documento (nel 
caso in cui il marchio sia visibile), dimostrare l'originalità di un documento 
non contraffatto e di evitare la distribuzione di copie non autorizzate.
Negli ultimi anni i formati video hanno subito una grande evoluzione 
migliorando la qualità video e di conseguenza l'esperienza visiva dell'utente. 
Questo incremento di qualità ha comportato un grande aumento dello spazio 
richiesto per memorizzare i dati e di conseguenza le applicazioni per 
l'elaborazione video si sono trovate a lavorare con moli di dati sempre 
maggiori e le CPU con carichi computazionali sempre più alti. Le applicazioni 
destinate al watermarking devono evolversi per restare al passo con questa 
innovazione dei formati video in modo da permettere una marchiatura video 
sempre in tempi ragionevoli.
 Sinonimo di marchio
17
Lo scopo di questo progetto è ottimizzare l'applicazione per la marchiatura 
video sviluppata da Fabio Lanzi in modo da migliorarne il più possibile le 
prestazioni (velocità di inserimento e di estrazione del marchio). Il fine ultimo 
sarebbe ottenere una marchiatura video in real-time, obiettivo raggiunto nelle 
ultime fasi del progetto.
La strada scelta per migliorare l'applicazione sviluppata da Fabio Lanzi, pura 
implementazione in C dell'algoritmo di Koz-Alatan (con lievi modifiche 
rispetto a quest'ultimo), consiste nel parallelizzare l'inserimento e l'estrazione 
del marchio; tale processo si adatta molto bene alla parallelizzazione in 
quanto, nell'applicazione sviluppata da F. Lanzi, il marchio viene inserito 
all'interno di sedici frames e ripetuto ogni sedici frames. Al posto di inserire il 
watermak in maniera sequenziale ogni sedici frames si può fare in modo di 
marchiare più blocchi da sedici frames contemporaneamente e in maniera 
indipendente, velocizzando l'intera procedura.
Esistono due modi e tecniche per parallelizzare il codice:
macro-parallelizzazione: viene parallelizzato l'intero codice o gran 
parte di esso.
micro-parallelizzione: vengono parallelizzate solo determinate parti del 
codice (ad esempio alcune funzioni) mentre la parte restante viene 
eseguita sequenzialmente.
L'evoluzione del progetto, in ordine cronologico, ha seguito le seguenti 
strade:
1.macro-parallelizzazione dell'intero codice con CUDA
2.micro-parallelizzazione delle sole funzioni DCT e DFT con CUDA
3.micro-parallelizzazione delle sole funzioni DCT e DFT con la 
Compute Unified Device Architecture
 Discrete cosine transform
 Discrete Fourier transform
••2342348
5
libreria IPP
4.macro-parallelizzazione dell'intero codice attraverso il multi-
threading su processori multi-core.
 Acronimo di Integrated Performance Primitives, sono delle librerie matematiche ottimizzate 
per processori Intel.
59
2 IL GPU COMPUTING CON CUDA
 2.1 GPU computing
La GPGPU (General-Purpose computing on Graphics Processing Units) è un 
recente settore della ricerca informatica che ha come scopo l'utilizzo del 
processore della scheda grafica, la GPU, per scopi diversi dalla tradizionale 
creazione di un'immagine tridimensionale; in tale ambito di utilizzo la GPU 
viene impiegata per calcoli estremamente esigenti in termini di potenza di 
elaborazione, e per le quali le tradizionali CPU non hanno una capacità di 
elaborazione sufficiente.
Se consideriamo i primi anni del 2000 notiamo una feroce guerra tra Intel e 
AMD per la produzione di processori con frequenze sempre più elevate. In 
poco tempo queste salirono a dismisura, soprattutto con il famoso Pentium 
IV dell'Intel; molto presto vennero raggiunti i limiti dettati dalle leggi della 
fisica: basta pensare che tra il 2001 e il 2003 le frequenze delle CPU 
passarono da 1,5 a 3,0 Ghz mentre dal 2003 al 2005 la velocità massima è 
passata da 3,0 a 3,8 Ghz. Alcuni ricercatori avevano anche erroneamente 
6
ipotizzato la fine della legge di Moore, a causa di un interpretazione 
sbagliata della legge, la quale si basa sul numero di transistor presenti in una 
data superficie di silicio. Queste problematiche sono sorte in quanto per 
molto tempo più transistor ha significato più potenza di calcolo. Oltre tutto la 
situazione si complicò ulteriormente: i progettisti si resero conto che 
aumentare solo il fattore di produzione, lasciando inalterate le altre 
caratteristiche della CPU, non avrebbe portato a miglioramenti; ci sarebbero 
voluti troppi transistor per mantenere costante l'aumento delle prestazioni e 
tale soluzione era da scartare. 
Le prestazioni dei processori, e il numero di transistor ad esso relativo, raddoppiano ogni 
18 mesi.
610
Mentre Intel e AMD cercavano di trovare una soluzione ai loro problemi, i 
7
produttori di GPU continuavano a beneficiare della legge di Moore. 
Ma perché i problemi riscontati con le CPU non affliggevano le GPU? Queste 
ultime sono nate con uno specifico orientamento, quello della grafica, dove 
migliaia di operazioni vengono eseguite in parallelo senza necessità di dover 
spendere transistor per gestire la logica di controllo. La maggioranza delle 
operazioni, infatti, è estremamente ripetitiva e le condizioni per cui delle parti 
di codice vengono eseguite o meno sono molto rare. Nelle CPU la maggior 
parte dei transistor è destinata a gestire la logica di controllo mentre nelle 
GPU i core sono molto più semplici e quasi tutta l'area è spesa per 
implementarli.
Grazie alla spinta fornita dai nuovi videogiochi sempre più esigenti in termini 
di prestazioni, allo scopo di ottenere esperienze visive più verosimiglianti, le 
schede video hanno subito una forte innovazione che le ha rese dei 
dispositivi multi-thread e multi-core con prestazioni sempre più alte. Le CPU, 
al contrario delle GPU, sono state costruite con lo scopo di eseguire un 
insieme eterogeneo di operazioni e la loro architettura si è evoluta proprio 
per potersi adattare a tale necessità, mantenendo una certa staticità (ma 
anche un incremento di complessità che le ha rese meno prestanti) per 
evitare incompatibilità con software realizzati in precedenza; l'ultima 
soluzione per aumentare le prestazioni è stata quella di inserire un certo 
numero di core nella CPU fisica (si pensi al dual core, al quad core o ai nuovi 
processori i3, i5 e i7). I produttori di GPU invece, hanno potuto modificare 
l'hardware a proprio piacimento con l'unico vincolo di mantenere comune 
8
L'API per interfacciarsi ad esse.
Conviene davvero usare le GPU per eseguire calcoli matematici / scientifici? 
Basta guardare la figura riportata di seguito per trovare la risposta:
 La Graphics Processing Unit, è il microprocessore di una scheda video per computer o 
console
 Application Programming Interface
78
11
Grafico : confronto tra la potenza computazionale delle CPU e delle GPU
L'idea di usare gli acceleratori grafici per calcoli matematici non è recente, 
infatti se ne parla già dagli anni novanta, ma inizialmente tale utilizzo era 
molto primitivo. Ma nel 2003 si raggiunse un novo traguardo: la possibilità di 
effettuare calcoli di matrici sfruttando le GPU; nacque quindi il termine 
GPGPU.
Il punto fondamentale in questa direzione fu BrokGPU. Nel 2003 l'unico 
modo per poter accedere alle risorse computazionali delle GPU era usare 
una delle due API grafiche disponibili (Direct3D e OpenGL). I ricercatori 
impegnati nel progetto BrookGPU non erano esperti di programmazione 
grafica e di conseguenza si trovarono in grande difficoltà. Ma è proprio qui 
che entra in gioco Brook; quest’ultimo è un set di estensioni del linguaggio C 
che integra tutta la parte gestionale delle API 3D in un ambiente più 
famigliare di quello della grafica, gestendo la GPU come un coprocessore 
per calcoli paralleli. 
Il merito di questo progetto è quello di aver portato il GPGPU allo scoperto. 
Alcune persone sostenevano addirittura che la CPU sarebbe stata presto 
rimpiazzata dalle GPU; questo ovviamente non è successo.
Negli ultimi tempi le CPU hanno subito diversi cambiamenti e ora sono 
sempre più orientate al parallelismo (sempre più core e ampliamento delle 
112
9
unità SIMD), le GPU invece stanno diventando sempre più flessibili 
(supporto ai calcoli single-precision floating point e presto anche calcoli 
double-precision); E' possibile, quindi, che le due strade prima o poi 
raggiungano un punto di incontro; sembra infatti che in futuro le GPU 
assorbiranno le CPU come coprocessore matematico.
Il successo di Brook attirò l'attenzione di NVIDIA, la quale era interessata a 
questo progetto in quanto aveva la possibilità di espandere il proprio 
mercato in un'altra direzione; i ricercatori impegnati in Brook entrarono quindi 
nel team di sviluppo di NVIDIA. Poiché gli sviluppatori di NVIDIA 
conoscevano tutti i segreti delle loro GPU non c'era più motivo di utilizzare 
solamente le API grafiche, che potevano comunicare con l'hardware 
solamente attraverso i driver (con tutti i relativi problemi). E' in questo 
contesto che il team di sviluppo CUDA sviluppò una suite software in grado di 
comunicare direttamente con la GPU, dando vita all'omonimo linguaggio. 
2.2 CUDA 
2.2.1 Introduzione
L'acronimo GPGPU, come abbiamo appena visto, è conosciuto già da alcuni 
anni, quando NVIDIA non aveva ancora concesso l'accesso alle proprie 
schede video. Con il passare del tempo il poter utilizzare la potenza di 
calcolo delle GPU per scopi non legati alla grafica si è rilevata un'opportunità 
interessante e quando si è iniziato a vedere un certo interesse, soprattutto 
da parte di centri di ricerca e organismi universitari, NVIDIA ha finalmente 
realizzato CUDA. CUDA rappresenta una delle soluzioni più avanzate e 
semplici per sviluppare applicazioni che necessitano di lavorare con enormi 
moli di dati in parallelo, fornendo un notevole vantaggio in termini di tempo di 
calcolo. Lo svantaggio è che occorre un'accurata conoscenza 
Single Instruction, Multiple Data 
913
dell'architettura CUDA senza la quale, scrivere programmi efficienti risulta 
impossibile. Ma cos'è CUDA? CUDA è un modello di calcolo parallelo, un'API 
e un ambiente di programmazione che, come dice la stessa NVIDIA, ha lo 
scopo di facilitare l'esecuzione di calcoli matematici utilizzando linguaggi 
standard (per ora solo C e C++). Nella pratica si tratta di un serie di librerie C 
che permetto di compilare applicazioni in grado di interfacciarsi in maniera 
diretta con la GPU per sfruttarne al meglio la potenza di calcolo.
Quali sono i motivi che hanno spinto NVIDIA ha rilasciare la piattaforma 
CUDA? Negli ultimi anni la società di Santa Clara è diventata la più grande 
casa produttrice di schede grafiche, sbarazzando letteralmente la 
concorrenza (principalmente ATI); fino ad oggi NVIDIA è riuscita a piazzare 
sul mercato mondiale oltre 60 milioni di schede grafiche abilitate per CUDA. 
Un ulteriore domanda è: perché utilizzare una scheda grafica CUDA-
enabled al posto delle CPU tradizionali? Una GPU della famiglia GT200 (ad 
esempio la GT280 dal costo di 170 euro circa) riesce ad effettuare quasi 
1000 GFLOPS/s (foating point operation at second), mentre un Intel Core 2 
Duo di circa 3 Ghz arriva a malapena a 25 GFLOPS/s (il picco di 51,20 
GFLOPS/s è raggiunto dal processore Core i7). Se invece confrontiamo la 
velocità di trasferimento dati verso la memoria interna, con una GPU della 
famiglia G80 si arriva ai 100 GB/s mentre con una normale CPU si 
raggiungono a malapena i 15 GB/s. Ad esempio la GeForce 8800 GTX 
(scheda video di fascia bassa) possiede 16 multi-processori ognuno dei quali 
può eseguire al massimo 768 thread in parallelo per un totale di 12288 
thread eseguibili parallelamente! Il compilatore CUDA, per raggiungere tale 
numero dovrebbe assegnare un massimo di 10 registri per thread, ma in 
genere ne assegna un ventina, riducendo il numero effettivo di thread a circa 
4000 / 5000, un limite comunque molto superiore alle CPU in commercio. 
Con una CPU, per potersi minimamente avvicinare a tali prestazioni è 
necessario spendere decine di migliaia di euro (oltre alla CPU è necessario 
14
un scheda madre adeguata, memoria RAM di ultima generazione..) a fronte 
di qualche centinaia di euro necessari ad acquistare una scheda video di 
modeste prestazioni; quindi la riduzione dei tempi di calcolo, nell'ordine 
anche di cento volte, e il notevole risparmio economico rendono tale 
soluzione adatta a risolvere problemi di piccola e media entità.
 2.2.2 CUDA nella pratica
Quali sono gli utilizzi pratici di CUDA? Sono molteplici e nei più svariati 
campi: viene utilizzato per la previsione della struttura delle proteine, per 
simulazioni meteo, analisi delle immagini medicali, astrofisica, reti neurali, 
ricerche oceanografiche, fisica delle particelle, chimica quantistica, 
astronomia, acustica, simulazioni elettromagnetiche e in moltissimi altri 
settori. Invece quanto sono migliorati gli applicativi che adesso utilizzano 
CUDA? In alcuni test riguardanti la codifica video si è notata una riduzione 
media dei temi da alcune ore a decine di minuti! Test su Matlab hanno 
rilevato miglioramenti di 17 volte. Usando CUDA con l'algoritmo quicksort si è 
registrato un aumento della velocità di esecuzione fino a 10 volte, operazioni 
di ray tracing sono state accelerate fino a 16 volte, calcoli di fluidodinamica 
fino a 17 volte, simulazioni fisiche di deformazione di modelli tridimensionali 
fino a 20 volte, calcoli sulle proprietà delle molecole circa 4 volte, sistemi GIS 
(Geographic Information System) circa 36 volte. Da tali dati si evince che i 
miglioramenti sono tali da giustificare l'utilizzo di tale tecnologia a fronte di 
una spesa ridotta.
Va sottolineato il fatto che CUDA è particolarmente adatto all'esecuzione di 
una stessa operazione su migliaia di dati diversi; solo così è possibile 
ottenere un aumento di prestazioni simile a quello elencato di sopra.
Nel campo medico è degno di attenzione il progetto FASTRA realizzato 
dall'Università di Antwerp in Belgio: i ricercatori hanno realizzato un computer 
con una spesa modesta (sotto i 4000 euro), utilizzano quattro schede NVIDIA 
15
9800GX, una CPU AMD Phenom e 8 GB di RAM, per effettuare ricostruzioni 
tomografiche che in campo medicale vengono effettuate con macchinari dai 
costi troppo elevati per molti istituti; i tempi necessari per effettuare tali calcoli 
con una singola CPU sarebbero nell'ordine di settimane, con CUDA si è 
arrivati anche ad alcune ore!
Tali aumenti prestazionali possono rappresentare anche una minaccia: alcuni 
hacker hanno trovato in CUDA la soluzione per effettuare ricerche di 
10 
password utilizzando dizionari oppure metodologie di bruteforce; in alcuni 
casi sono riusciti a trovare le password WPA in tempi ragionevoli e le 
11 
password criptate con MD5in soli 5 secondi. 
2.2.3 Le basi del modello architetturale di CUDA
Alcuni programmatori potrebbero trovarsi spaesati nel lavorare con CUDA in 
quanto la terminologia utilizzata nella documentazione fornita da NVIDIA non 
coincide con quella utilizzata nella programmazione “tradizionale”. Ad 
esempio un thread CUDA non è sinonimo di thread per CPU, occorre quindi 
dare una serie di definizioni. 
Occorre innanzi tutto chiarire che in tale documentazione con il termine 
si intende la CPU mentre con il temine si intende la GPU. Il kernel in 
CUDA è una particolare funzione che viene invocata dall'host ed eseguita sul 
device; il kernel deve avere void come tipo di ritorno, non può essere 
ricorsivo, non può avere un numero di parametri variabile e non può usare 
variabili di tipo statico. Da un altro punto di vista il kernel può essere 
considerato come una parte di codice eseguita su un (griglia) di 
blocchi. Un grind può essere decomposto in , che vengono assegnati 
sequenzialmente ai vari multi-processori, e rappresentano un parallelismo a 
grana grossa. All'interno dei blocchi c'è l'unità di computazione 
Attacco che consiste nel provare tutte le chiavi possibili
E' un algoritmo crittografico di hashing che produce un output a 128 bit
1016
11
blocchi
grind
device
host
fondamentale, il thread, che rappresenta una parallelismo a grana molto 
fine. 
Figura : suddivisione in blocchi e in thread 
Un warp in CUDA è un gruppo di 32 thread e rappresenta la minima 
12
dimensione dei dati elaborati in SIMT da uno Streaming Multiprocessor; 
tuttavia NVIDIA consiglia di usare blocchi composti da un minimo di 128 
thread a un massimo di 256.
I thread CUDA a differenza di quelli delle CPU sono molto leggeri, di 
conseguenza il cambio di contesto avviene in tempi molto brevi; un thread è 
identificato da un indice univoco per tutto il kernel. Questi ultimi sono 
12
Single Instruction Multiple Thread
117
identificati da indici tridimensionali mentre i blocchi da indici bidimensionali. I 
kernel (le griglie) sono eseguiti sequenzialmente tra di loro (ovvero su una 
GPU può essercene uno e uno solo in esecuzione) ma sono lanciati in 
maniera asincrona, quindi una volta che la CPU lo lancia può eseguire altre 
parti di codice. I blocchi e i thread invece, sono eseguiti logicamente in 
parallelo; il numero di thread fisicamente eseguibile parallelamente dipende 
dalla loro organizzazione in blocchi e dalle risorse hardware occupate 
rispetto a quelle disponibili sul device.
Figura : CUDA dal punto di vista hardware
Dal punto di vista hardware abbiamo diversi cluster che NVIDIA chiama 
Texture Processor Cluster (TPC). Ogni TCP è costituito da un'unità texture 
e da due Streaming Multiprocessor (SM). Il numero di SM dipende dalla 
tipologia e fascia della scheda grafica. Ciascun Streaming Multiprocessor è a 
sua volta formato da 8 ( o 32 per le schede con compute capability 2.0) 
Stream Processor. Ognuno di questi processori può eseguire un operazione 
matematica fondamentale (addizione, moltiplicazione, ecc) su interi o su 
218