Tesi Robotica Analisi, progettazione e implementazione...

i i “LP_Tesi” — 2013/10/17 — 18:27 — page 139 — #139 i 6.2. IMPLEMENTAZIONE i 139 l’indirizzo 0, questo perché nella prima riga è presente un solo elemento e al passo successivo bisogna andare per forza alla riga successiva. La regola esegue i normali passi dell’algoritmo, ovvero prima controlla se ci si trova in una situazione di gap semplice o gap esteso, controllando se nel passo successivo ci sia stato gap, successivamente calcola il valore da dare alla cella attualmente considerata assegnandogli il massimo fra il massimo parziale calcolato nel ciclo di clock precedente e memorizzato in maxu e il valore della casella a sinistra, contenuto in cWest. A questo punto la regola ricalcola il massimo parziale fra la cella a nord west e la cella a nord aggiornando il registro maxu, il valore di west viene quindi aggiornato al valore del massimo perché nel ciclo successivo il valore appena calcolato sarà a sinistra di quello che si andrà a considerare costituendo appunto il west. La regola r3 spara solo nel caso in cui l’indirizzo si trovi sulla diagonale, in questo caso infatti la casella di nord non è presente e bisogna fare attenzione a quali valori vengono utilizzati, per quanto riguarda il resto si comporta esattamente come r2. A questo punto possono essere presentate le altre tre regole che calcolano i punteggi all’interno della matrice (Alg:6.13). La rule r4 si occupa di tutte le caselle precedenti alla diagonale, questo caso deve essere trattato a parte perché nella cella successiva non è presente il valore di north e infatti il registro maxu viene semplicemente settato al valore di north west. La rule r5 invece riempie tutte le altre celle della matrice, applicando letteralmente l’algoritmo. In ﬁne la regola rlast come appunto dice il nome spara nel momento in cui l’indirizzo è arrivato all’ultima casella, infatti step vale 1 una volta che viene aggiornato dalla regola pre1, regola che come visto in Alg:6.11 indica il raggiungimento del penultimo elemento, questa distinzione è stata fatta per poter permettere alla fase successiva di cominciare, infatti una volta che la FIFO result viene svuotata può partire il Backtrack. La FIFO result viene svuotata dalle regole r6 e r7 (Alg:6.14), come si può vedere la rule r6 prende l’elemento in testa alla FIFO e lo passa al ﬁlo req, questo ﬁlo esce all’esterno del modulo e va a settare i valori della BRAM cache. Successivamente la FIFO result viene svuotata e l’indirizzo di scrittura contenuto n

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