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

i

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

i

120

i

6. SECONDA RELEASE

Per questione di implementazione nella prima release si era deciso di non tenere
conto della possibilità di biforcazioni nella fase di Backtrack, questa scelta non
aveva comportato gravi perdite alla resa dell’algoritmo dimostrando comunque
ottimi risultati. Tale scelta comporta la totale inutilità della codifica one-hot
per le direzione, infatti per ogni cella sono memorizzati tre bit, uno per ognuna
delle matrici gapNorth, gapWest e diag, questo allo scopo di sapere quando
una cella contenesse più di una direzione contemporaneamente. Data la scelta
fatta sono solo 3 le possibili direzioni percorribili (North, West e Diag) anziché
8 (North, West, Diag, Nort-West, North-Diag, West-Diag), e per memorizzare
3 direzioni occorrono solamente 2 bit anziché 3. Questo comporta la rimozione
delle 3 BRAM da 1 bit a elemento ciascuna in favore di una sola BRAM ad
elementi di 2 bit.
Quest’ultima decisione porta ad un ulteriore minimizzazione dello spazio richiesto,
portando alla seguente formulazione per il calcolo della memoria necessaria:
ScoreRAM = ( log(255 ∗ n) × n) bit
DirRAM = GN orthRAM +GW estRAM +DiagRAM = (2×n×n)/2+(2×n)/2 bit
T ot = 2RasterRAM + ScoreRAM + DirRAM
= 2(24 × n) + ( log(255 ∗ n) × n) + (n × n) + n
A questo punto è possibile calcolare i requisiti di memoria finali, i valori sono
mostrati in Tab:6.5. Al momento non risultano possibili altri metodi per la
riduzione dell’uso delle BRAM.
Spazio necessario (bit)
Spazio necessario (Byte)
Spazio necessario (KByte)

160 × 120
36000
4500
5

320 × 240
123520
15440
16

450 × 375
232200
29025
29

640 × 480
452480
56560
56

Tabella 6.5: Requisiti di memoria finali nella Seconda Release

6.1.2

Aumento frequenza di lavor