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

i

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

i

6.2. IMPLEMENTAZIONE

i

145

Algoritmo 6.18 Regole per il Backtrack
1
2
3
4
5
6
7
8

(∗ conflict_free ="bt1,bt2,bt3" ∗)
rule bt1 (step==2 && fromMaybe(?, resp.wget())==NORTH);
size <=size−1;
addr<=addr−size;
divC<=row−1; modC<=col;
fout .enq(DirAddr{dir:BLUE,col:col,row:row});
step<=1;
endrule

9
10
11
12
13
14
15
16

rule bt2 (step==2 && fromMaybe(?, resp.wget())==NORTHWEST);
size <=size−1;
addr<=addr−size−1;
divC<=row−1; modC<=col−1;
fout .enq(DirAddr{dir:GREEN,col:col,row:row});
step<=1;
endrule

17
18
19
20
21
22
23

rule bt3 (step==2 && fromMaybe(?, resp.wget())==WEST);
addr<=addr−1;
divC<=row; modC<=col−1;
fout .enq(DirAddr{dir:RED,col:col,row:row});
step<=1;
endrule

la colonna del ciclo di clock precedente. Una volta che la richiesta di lettura è
stata effettuata, al ciclo di clock successivo, una delle regole presenti in Alg:6.18
gestisce questo valore. Le regole devono essere definite conflict free perché
il compilatore non è in grado di inferire la loro mutua esclusività. Ognuna delle
regole gestisce uno dei tre casi possibili, l’unica differenza che può essere notata
è l’aggiornamento dei registri divC e modC, nel caso di un NORTH il registro
divC (indice di riga) deve essere decrementato mentre modC (indice di colonna)
rimane invariato, nel caso di NORTHWEST entrambi devono essere decrementati perché il movimento è in diagonale, infine nel caso di WEST solo modC deve
essere decrementato.
Una volta che il Backtrack ha raggiunto l’estremità sinistra della matrice è
necessario effettuare una fase di post tracking per raggiungere l’elemento di
indice (0,0), a questo scopo sono state implementate le due regole presenti in
Alg:6.19 e Alg:6.20 . Mentre postTrackDiag gestisce il caso in cui il Backtrack
ha raggiunto il limite superiore sinistro della matrice, la regola postTrackNorth
gestisce il caso in cui il Backtrack ha raggiunto uno qualsiasi degli altri elementi

i

i
i

i