Tesi Robotica Analisi, progettazione e implementazione... | Page 154

i

i
“LP_Tesi” — 2013/10/17 — 18:27 — page 154 — #154

i

154

i

7. TERZA RELEASE

za, ma tale calo sarà ampiamente ripagato dalla possibilità di parallelizzare il
riempimento della matrice dei punteggi.
Prima di buttarsi a scrivere codice è stato necessario però capire il modo in cui la
matrice dei punteggi poteva essere riempita parallelamente, infatti esistono dei
vincoli sull’ordine in cui le celle vengono calcolate. Come ampiamente spiegato
in precedenza, una posizione della matrice può essere riempita solamente se le
posizioni di north, northwest e west sono state precedentemente riempite, ciò
implica che se si vogliono riempire contemporaneamente due righe adiacenti,
il riempimento della seconda deve essere ritardato di un ciclo di clock, ciclo
necessario al calcolo della casella di north relativo alla seconda riga. Inoltre se la
prima riga impiega n cicli di clock per essere completata, la seconda impiegherà
n + 2 cicli, questo perché un ciclo viene sprecato all’inizio per permettere il
calcolo dei north, mentre l’altro viene sprecato alla fine dato che il numero di
celle nelle righe aumenta di una unità ogni volte che si scende verso il basso.
Nel caso in cui si vogliano usare m riempitori, ammettendo che la prima riga
associata al primo riempitore sia lunga n, saranno necessari n + 2m cicli di
clock per riempirle tutte, questo perché gli m riempitori non si spostano alle
righe successive fino a quando l’ultimo ha finito. A questo punto ci si potrebbe
domandare perché non cominciare a riempire la riga m + 1 quando il riempitore
della prima riga ha terminato, c’è un motivo ben preciso, e va ritrovato nel modo
in cui le celle north vengono memorizzate.
Come detto in Sez:6.2.4 esiste una FIFO di nome ramNorth, questa coda è
di dimensioni pari alla larghezza dell’immagine. Volendo permettere al codice
di riempire m righe indipendentemente l’una dall’altra sarebbero necessarie m
ramNorth di dimensioni pari alla larghezza dell’immagine. L’obiettivo però è
quello di migliorare le prestazioni del sistema senza consumare ulteriore memoria, utilizzando quindi l’accorgimento di aspettare che tutte le righe finiscano
di essere scritte, solo una delle ramNorth richiederà uno spazio grande, ovvero
quella usata tra la comunicazione dall’ultimo a primo riempitore, tutte le righe
nel mezzo useranno invece delle FIFO al più grandi 2, questo perché il valore di
north per il riempimento di una cella viene utilizzato nel ciclo di clock successivo
a quello di creazione. Solo il primo e l’ultimo riempitore avranno a che fare con
la ramNorth grande, questo perché mentre l’ultimo crea valori per la fase successiva di riempimento, il primo utilizza i valori creati nella fase di riempimento
precedente.
Usando questa tecnica lo spazio di memoria su FPGA non viene utilizzato ulteriormente, certamente in questo modo la parallelizzazione non frazionerà in
maniera precisa il numero di cicli di clock impiegati, ma per immagini molto

i

i
i

i