Costruzione della disparity space image
Algoritmo 8 Algoritmo ottimizzato per il calcolo della DSI (Versione 2, Parte 2)
6.1 Analisi dei tempi di elaborazione
Per avere una misura quantitativa dei miglioramenti ottenuti sono state messe a con-fronto le prestazioni degli algoritmi esistenti con quelle dei nuovi, in versione ottimiz-zata e non, su macchine diverse; il compilatore utilizzato `e stato in tutti i casi il GCC versione 3.3.5, con le seguenti opzioni attivate:
-O3 -finline-limit=1200 -DNDEBUG -maccumulate-outgoing-args -mno-align-stringops -minline-all-stringops -march=pentium4 -momit-leaf-frame-pointer -fforce-addr -falign-functions=4 -mfpmath=sse -funroll-loops -fprefetch-loop-arrays -msse2 -ffast-math
66
come si pu`o vedere, durante la fase di compilazione il codice viene automaticamen-te ottimizzato per l’esecuzione su Inautomaticamen-tel R Pentium4 R, dato che questo `e il processore installato a bordo del Terramax, ed anche quello impiegato nei test; le istruzioni uti-lizzate all’interno della versione ottimizzata manualmente sono comunque supportate da altre famiglie di processori (come l’AMD R AthlonXP R), anche se con questi non sono state fatte analisi delle prestazioni ottenibili.
Le tabelle 6.1 e 6.2 presentano i tempi medi di esecuzione per frame dei vari algo-ritmi, ottenuti elaborando una sequenza di 1500 immagini stereo, acquisita in ambienti urbani ed extraurbani, con una disparit`a massima di ricerca di 23 pixel; le macchi-ne utilizzate per i test sono state due: la prima equipaggiata con un processore Intel R Pentium4 R Mobile a 2.0 GHz, 512 KB di memoria cache e 700 MB di memoria RAM, mentre la seconda con un processore Intel R Pentium4 R a 3.0 GHz, 1024 KB di me-moria cache e 1 GB di meme-moria RAM.
Versione dell’algoritmo algoritmo risoluzione originale nuova nuova accelerata
VDI 41 ms 38 ms 7 ms
DSI 320*240 N/D 51 ms 23 ms
106*80 8 ms 8 ms 5 ms
OD 320*240 N/D 18 ms
106*80 1 ms 2 ms
totale 320*240 N/D 107 ms 48 ms
106*80 50 ms 48 ms 14 ms
Tabella 6.1: Tempi di esecuzione sulla prima macchina di test
Gli algoritmi analizzati sono quelli per il calcolo della V-Disparity image (VDI), della disparity space image (DSI) e dell’individuazione degli ostacoli (OD); i dati mancanti sono stati identificati con la sigla N/D, mentre le caselle corrispondenti ad incroci non significativi sono state lasciate vuote
Una prima analisi dei dati presentati mette in evidenza i benefici portati dall’utiliz-zo delle istruzioni SIMD messe a disposizione dai processori impiegati; risulta inoltre chiaro come il GCC, che pure `e in grado di produrre codice sequenziale altamente ottimizzato, non sia ancora in grado di sfruttare appieno il parallelismo offerto dalle
DSI 320*240 N/D 35 ms 15 ms
106*80 6 ms 5 ms 3 ms
OD 320*240 N/D 10 ms
106*80 1 ms 1 ms
totale 320*240 N/D 66 ms 29 ms
106*80 30 ms 27 ms 8 ms
Tabella 6.2: Tempi di esecuzione sulla seconda macchina di test
moderne CPU: l’intervento manuale a livello assembly diventa dunque indispensabile, e con ogni probabilit`a ci`o si ripeter`a ancora piuttosto a lungo, almeno nell’implemen-tazione di algoritmi complessi, come lo sono il calcolo della disparity space image e della V-Disparity image.
Mettendo a confronto i tempi totali di esecuzione delle versioni non ottimizzate manualmente con quelli ottenuti sfruttando in modo esplicito l’instruction set SSE si ottiene, su una stessa macchina, una riduzione del 55% circa nel caso si operi ad una risoluzione di 320x240 pixel, e addirittura del 70% circa alla risoluzone originaria di 106x80pixel (ci`o accade perch`e i tempi di calcolo della V-Disparity image vengono ridotti circa dell’80% ma, dal momento che questi dipendono soltanto dalla risoluzione dell’immagine acquisita, non sono soggetti a riduzioni dovute a sottocampionamenti, e nel secondo caso finiscono per avere una maggiore incidenza percentuale).
Esaminando nel dettaglio le prestazioni dei singoli algoritmi, il calcolo accelerato della disparity space image richiede in media un tempo pi`u piccolo del 50 − 55% ri-spetto alla versione normale, mentre, come si `e appena potuto vedere, nel caso della V-Disparity image tale diminuzione raggiunge l’80%: questo fenomeno `e spiegabile se si tiene conto del fatto che il secondo algoritmo risulta meno complesso, e non ri-chiede la presenza di sequenze condizionali nel suo innermost loop, che tendono ad interrompere il funzionamento di tipo pipeline del processore; nel calcolo dell’imma-gine di disparit`a, invece, `e necessario valutare, per ogni pixel, la posizione del minimo globale della funzione di correlazione, e validare la soluzione ottenuta: in questo modo
vengono introdotte istruzioni di salto che, al momento dell’esecuzione, risultano piut-tosto problematiche da gestire dall’unit`a di branch prediction della CPU, dal momento che danno luogo pattern irregolari.
Osservando attentamente le tabelle 6.1 e 6.2 si nota come per l’algoritmo di ob-stacle detection non sia stata prevista una versione ottimizzata: ci`o dipende essenzial-mente dal fatto che il principio su cui si basa prevede l’individuazione di aree del-l’immagine di disparit`a in cui i valori risultino costanti, e questa operazione non trova una semplice espressione in termini di operazioni SIMD; per l’implementazione si `e dunque scelto di affidarsi ad una formulazione ricorsiva del problema, col vantaggio di ottenere codice di pi`u semplice interpretazione; tale scelta `e stata giustificata anche dalla quota di tempo di esecuzione liberata grazie al miglioramento degli algor`ıtmi per il calcolo della V-Disparity image e della disparity space image: va comunque tenuto presente che, passando dalla risoluzione di 106x80 pixel ai 320x240 pixel della nuova versione, l’elaborazione risulta nove volte pi`u lenta, sintomo che il GCC non ha modo di parallelizzare alcuna operazione.
I test condotti hanno evidenziato che la seconda macchina riesce a ridurre i tempi di elaborazione del 30% circa, e questo `e un dato confortante, poich`e se cos`ı non fosse stato ci si sarebbe dovuti addentrare in un’analisi ancora pi`u approfondita dei meccanismi di trasferimento dei dati dalla memoria principale del sistema alla cache:
tali operazioni, infatti, risultano decisamente pi`u lente della maggior parte delle attivit`a di puro calcolo, e, se non se ne tiene adeguatamente conto, possono diventare un collo di bottiglia per le prestazioni del sistema. Questo fenomeno `e tipico degli elaboratori paralleli, in cui `e sempre presente il rischio di trasformare un problema intrinsecamente CPU-bounded in uno I/O-bounded.
Nel complesso, si pu`o infine affermare con sicurezza che il nuovo algoritmo riesce, a parit`a di tempo di esecuzione, a gestire immagini ad una risoluzione di 320x240 pixel, mentre quella originaria era di soli 106x80 pixel; tale risultato `e la media pesata tra porzioni di codice notevolmente pi`u veloci (l’immagine di disparit`a viene calcolata nel 50% del tempo, e quella di correlazione nel 20%), e altre decisamente pi`u lente (il rilevamento degli ostacoli risulta nove volte pi`u lento).
Se gli obiettivi in termini di velocit`a che ci si era inizialmente posti possono dirsi in
proposta in [15]: in questo articolo viene infatti presentato un sistema software per il calcolo dell’immagine di disparit`a paragonabile al nostro, sia per il tipo di algoritmo adottato che per la sua implementazione (realizzata impiegando l’instruction set SSE);
un confronto diretto resta difficoltoso per la mancanza di dettagli (ad esempio, non sono note le dimensioni delle finestre utilizzate per i confronti), ma i risultati (circa 25 ms per elaborare un fotogramma formato da 320x240 pixel, con una disparit`a massima di ricerca di 32 pixel, il tutto su un processore Intel R Pentium4 R a 2.26 GHz) non si discostano molto da quelle ottenibili in condizioni analoghe dal nostro codice, che impiega circa 40 ms a completare il medesimo calcolo.