ROGETTO A RCHITETTURALE C APITOLO 4 P

C

APITOLO

4

P

ROGETTO

A

RCHITETTURALE

Nei capitoli precedenti è stata studiata la programmabilità del sistema e sono state fatte alcune scelte, quali l’approssimazione delle funzioni per il calcolo di alcuni coefficienti, che porteranno delle conseguenze nelle scelte architetturali. In questo capitolo il sistema viene descritto dal punto di vista della sua struttura, ovvero vedremo quali sono e come sono stati assemblati i vari pezzi che daranno vita al progetto finale. Seguirà una fase di verifica in cui si riporteranno i risultati della sintesi. Come tool di progettazione e simulazione è stato scelto Active - HDL 4.2 data la sua versatilità e attualità.

In questo ambiente sono possibili essenzialmente due tipi di descrizione per i circuiti: la prima è detta Behavioural o Comportamentale, in cui si descrivono in un’opportuna sintassi le funzionalità che deve avere il circuito e viene poi lasciata al tool di sintesi una certa libertà nella scelta dell’architettura interna. Si parla in tal caso di descrizione di processi. Questo tipo di descrizione, se da una parte è molto potente e semplice da utilizzare, dall’altra può rilevarsi sconveniente nel senso che potrebbe dar vita ad architetture molto complicate con la pericolosa conseguenza di occupare troppe risorse della FPGA su cui si vuole implementare

il progetto. L’altra possibilità di descrivere un circuito è la descrizione di Strutture, in cui si definiscono dei blocchi elementari come ad esempio Multiplexer, Flip-Flop, ecc. e poi si assemblano collegandole. Si tratta di un’approccio più a basso livello, ma che consente di avere sempre presente cosa si andrà ad ottenere al momento della sintesi. Purtroppo però non è facile descrivere un circuito con questo approccio, quindi la descrizione Behavioural risulta più veloce e pratica.

In questo lavoro sono stati alternati, a seconda dei casi e delle necessità, entrambi gli approcci. In ogni modo, con Active – HDL 4.2 un circuito viene dapprima dichiarato come Entity in cui si specificano il nome della rete e quello degli ingressi e delle uscite ed altri parametri. Poi si passa alla descrizione vera e propria. Sulla base di questo schema, dopo aver introdotto le scelte architetturali con un diagramma a blocchi del sistema complessivo, vengono infine presentate tutte le entity descritte in VHDL nell’ordine in cui esse entrano in gioco. Un’eccezione viene fatta per la macchina a stati che gestisce il funzionamento dell’intero sistema, il cui nome è Enable_Generator, che sarà presentata per ultima a completamento di tutta l’architettura. Il montaggio finale di tutte le entity costituirà il progetto completo da un punto di vista HDL.

Gli obiettivi che si intendono raggiungere in questa fase sono:

• fedeltà dell’architettura rispetto alla descrizione realizzata nell’algoritmo modificato C ret_soft_linear.c

• sintetizzabilità di tutte le parti descritte

• descrizione parametrica del sistema, in modo da rendere possibili eventuali modifiche o aggiornamenti successivi.

4.1 E

In questo paragrafo affronteremo la descrizione dettagliata dei blocchi che abbiamo visto in figura 45 (pag. 95) e per alcuni di essi vedremo la struttura interna. In seguito sarà affrontato il problema dell’implementazione del divisore dedicato per il calcolo della riflettanza.

A monte di tutte queste reti, è necessaria la presenza di una logica composta da altri blocchi che gestisca innanzitutto la raccolta delle scelte fatte dall’utente per quanto riguarda l’impostazione dei parametri regolabili, e che piloti opportunamente le memorie nella fase di preparazione del sistema e di elaborazione vera e propria. Si procederà quindi con l’illustrazione di questa logica, prima di parlare del resto.

4.1.1 ReteAlfa_par

Figura 48. Ingressi e uscite della rete Alfa_Par.

La rete combinatoria Alfa_par ha il compito di impostare il valore del parametro programmabile α in seguito alle scelte dell’utente. E’ possibile infatti, ottenere un’immagine di uscita a bassa, media o alta risoluzione. Tutto ciò dipende dal valore del parametro di ricorsività α del filtro RRF estrattore di luminanza, per il quale sono stati scelti, nella fase di studio di programmabilità del sistema, tre possibili casi. Dato che l’utente non è tenuto a conoscere i valori che α deve assumere, ma deve semplicemente azionare uno switch per scegliere tra risoluzione Low, Medium, High, la rete, ricevuto in ingresso il valore alfa_in su 2 bit, restituisce il dato alfa_out su 10 bit, che contiene l’opportuno valore di alfa. I casi possibili sono 3 più uno di errore, in cui l’uscita viene posta in alta impedenza ed il sistema non evolve. Affinché ciò sia possibile, l’uscita di questo circuito viene instradata anche verso la macchina a stati Enable_Generator, oltreché verso le reti per il calcolo dei coefficienti Fo e Fv, che sono funzioni di Alfa. Lo schema seguente chiarisce quanto appena enunciato a parole:

alfa_in = "01" alfa_out = "1000000000" -- alfa = 0.500 Risoluzione Low -- alfa_in = "10" alfa_out = "1100000000" -- alfa = 0.750 Risoluzione Medium -- alfa_in = "11" alfa_out = "1110011001" -- alfa = 0.900 Risoluzione High -- altrimenti alfa_out = "ZZZZZZZZZZ" -- alfa in alta impedenza --

Quanto detto si realizza in VHDL con un semplice costrutto Case all’interno di un processo attivato dall’ingresso alfa_in.

4.1.2 Acquisizione dati e riempimento ram_x e ram_y: Memories_Address_Generator (MAG)

Figura 49. Ingressi e uscite della rete Memories_Address_Generator.

Nella fase di inizializzazione del sistema, oltre alla lettura dei valori dei

parametri programmabili scelti dall’utente, avviene l’acquisizione del frame da processare. Dato che il VHDL non è in grado di lavorare sulle immagini in formato matriciale .img, si è scelto di convertire le immagini in formato .txt data l’architettura scelta per le ram. In ambiente Matlab è stata realizzata una funzione il cui nome è save_image_txt che riceve in ingresso il file di immagine.img e restituisce un file di uscita .txt che è generato scandendo la matrice sorgente in modalità raster per colonne, a partire dal primo pixel in alto a sinistra fino all’ultimo in basso a destra. Questa particolare scelta è stata adottata visto che è proprio questa la direzione della scansione che deve fare il filtro nella prima passata. Sostanzialmente si tratta di scandire una matrice m(i,j) dove i e j sono rispettivamente gli indici di riga e colonna, a partire dalla posizione m(1,1) e facendo scorrere con due cicli annidati prima l’indice i in modo da percorrere tutta la colonna, ed in seguito l’indice j per cambiare colonna.

Così si riesce a percorrere tutta la matrice. Il singolo pixel, che è un valore intero da 0 a 255 dove 0 rappresenta il valore del nero e 255 il bianco, una volta acquisito viene convertito su 8 bit per poi salvarlo in ram_x e ram_y.5 Il pixel successivo viene a sua volta convertito in stringa di bit e salvato nel file .txt nella riga seguente. Alla fine si ottiene un file di testo che se aperto, appare come una serie di righe ad 8 bit che, incolonnate una sull’altra, rappresentano i valori dei pixel; tali righe saranno trasferite nelle locazioni della ram.

Creato il file di testo per poter acquisire i dati da elaborare con il VHDL, entra in gioco il circuito Memories_Address_Generator, o semplicemente MAG, che serve per generare gli indirizzi per Ram e Rom di tutto il sistema durante la fase di avviamento dello stesso, in cui si acquisiscono i dati dell’immagine da elaborare caricandoli in Ram_X e Ram_Y e contemporanemente viene precaricata la Look-Up-Table Rom_Inversion per il calcolo del reciproco della somma (So + Sv + 1). Si tratta fondamentalmente dell’unione di due contatori identici, ma ognuno adattato alla ram da indirizzare. L’entity in questione dunque ne contiene al suo interno un’altra chiamata Memories_Counter, che è di fatto il vero contatore che genera numeri a partire da 0 fino ad un limite superiore programmabile che faremo coincidere con la dimensione della memoria da pilotare. Gli indirizzi sono dunque, semplicemente, valori interi progressivi, dato che le Ram e le Rom sono state descritte, come vedremo più avanti, come una collezione di locazioni di dimensione opportuna, strutturate secondo uno schema a pila o stack. Dunque Memories_Counter riceve in ingresso clock, reset asincrono, enable ed il particolare segnale in_mc di tipo intero che conterrà il valore raggiunto il quale in contatore si arresterà, mentre i segnali di uscita saranno l’indirizzo corrente durante la scansione, count_out, ed un segnale di fine conteggio out_mc su 1 bit. Da notare come si sia scelto di limitare il campo di variazione di eventuali segnali interi esplicitandone il range di valori possibili. Questo è importante nella fase di sintesi, in quanto il tool sintetizzatore riesce a calcolare perfettamente il numero di bit da riservare al segnale dichiarato come integer. Viceversa, la sintesi potrebbe risultare non ottimizzata con spreco di

5 _{La dimensione della cella elementare di ram_y è 18 bits a causa della presenza della parte}

risorse della FPGA. Tornando alla entity MAG, possiamo ora dire che i segnali di ingresso sono, oltre ad i soliti clock ed enable, due reset distinti, uno pilotato dall’esterno e l’altro gestito dalla macchina a stati Enable_Generator, dai quali attraverso una operazione logica di OR sarà ricavato il reset globale di questa rete, visto che il reset deve avvenire se almeno uno dei due segnali è attivo. Per quanto concerne dati in ingresso abbiamo lines e cols che corrispondono al numero di linee e colonne della matrice .img da processare, mentre i segnali in uscita sono un bit per segnalare alla macchina a stati la fine del conteggio per quanto riguarda le ram X ed Y ed i dati addr_x, addr_y ed addr_inv, interi convertiti in stringhe di bit per mezzo di una opportuna funzione, che indirizzeranno rispettivamente, come suggeriscono i nomi, le ram x ed y e la rom per il calcolo del reciproco di (So + Sv + 1 ). Ricevuti i segnali lines e cols, viene calcolata la dimensione della matrice (lines x cols) per mezzo di un moltiplicatore dedicato, che fornirà il limite superiore al primo contatore Memories_Counter, mentre il limite superiore per il secondo contatore, che gestisce la Lut per l’inversione, è fissato a 2441, dimensione della Lut stessa, che ovviamente è la stessa per ogni immagine da elaborare.

4.1.3 Pixel_Address_Conversion (PAC)

Una volta acquisiti tutti i dati si passa alla fase di elaborazione vera e propria che ha inizio con la lettura dei pixel che servono per cominciare i calcoli successivi. Si deve quindi accedere alle ram prima di poter poter iniziare l’elaborazione. Dato che l’immagine sorgente è stata convertita dal formato matriciale in cui si trovava ad un formato tipo stack, è necessario rivedere l’organizzazione del file di testo creato con la funzione save_image_txt per capire dove si trovi nella ram un certo pixel m(i,j) di cui vogliamo prelevare il valore.

Le righe del file di testo saranno in totale (lines x cols) e potremo rintracciare il singolo pixel con una semplice formula di conversione: se ad esempio volessimo ritrovare nel file di testo il valore m(5,6) dovremmo contare un numero di righe pari a (lines x 5 ) in modo da centrare la colonna esatta ed in seguito avanzare di ulteriori 6 righe. Questo perchè le colonne sono state scandite e salvate una dopo l’altra nel file di testo e dunque lines righe del file .txt corrispondono ad una colonna della matrice m. Su questo semplice ragionamento è stata pensata la rete Pixel_Address_Conversion che sarà ora presentata.

Anche in questo caso si tratta di una rete sincrona, pertanto sono presenti i segnali d’ingresso clock, reset, enable. In realtà la rete necessita di due pin di enable, uno per l’abilitazione vera e propria chiamato enable_pac e l’altro, enable_pac_ff, che serve per memorizzare i dati in appositi registi flip-flop all’uscita di questa entity. Come uscite, infatti, abbiamo gli indirizzi delle locazioni delle ram che devono essere lette per prelevare i dati che servono per calcolare i coefficienti So, Sv, Fo, Fv e poiché le operazioni che seguiranno per calcolare tali valori necessitano di un certo numero di cicli di clock, è necessario memorizzare gli indirizzi delle locazioni da leggere. Il PAC sarà abilitato con un impulso della durata di 1 ciclo di clock ogni volta che si inizierà ad elaborare un pixel dell’immagine sorgente. Ad ogni scatto la maschera 3 x 3 di scansione verrà centrata su un nuovo pixel e verranno forniti in uscita i quattro indirizzi per leggere i valori dei pixel argomento dei coefficienti S e F. Questi dati, mantenuti dai registri, andranno quindi verso un multiplexer 4 to 1 che sarà comandato da enable_generator. Vedremo in seguito quale sia il significato di questi quattro valori. Altri dati che la rete richiede in ingresso sono ovviamente il numero di righe e colonne della matrice ed inoltre il numero del ciclo che si sta effettuando.

Come già anticipato, il filtro estrattore di luminanza può funzionare scandendo la matrice fino a quattro volte in direzioni diverse. A seconda del numero del ciclo che si sta effettuando, cambiano gli argomenti per il calcolo dei coefficienti S ed F ma soprattutto cambia la direzione di scansione. Il PAC si compone sostanzialmente di un contatore detto line_col_counter che, come suggerisce il termine, scandisce immaginariamente la matrice m(i,j) variando gli indici di riga e di colonna. Si tratta quindi di un doppio contatore in cui l’indice j viene variato solo quando i è arrivato a fondo scala. Esso riceve in ingresso i soliti lines e cols e restituisce un segnale di raggiunto fondo scala ed i valori di riga e colonna correnti. Questi vengono letti dall’altra sottorete che si trova nel PAC, il cui nome è Matrix_to_Stack, che effettua la conversione degli indirizzi dei pixel dal formato matriciale a quello stack secondo quanto spiegato prima. Ricevuti in ingresso le dimensioni del frame da elaborare, (ancora lines e cols), l’informazione sul ciclo corrente e il numero di riga e colonna attuali, calcola i quattro indirizzi che poi saranno memorizzati in uscita e che costituiranno le uscite del PAC. Vediamo ora come sia possibile scandire la matrice m(i,j) in modalità raster per colonna nei quattro modi :

Ciclo 1 : From Top – Left to Bottom – Right

Il contatore line_col_counter è stato concepito proprio per scandire la matrice in questo modo, quindi il primo ciclo avviene normalmente.

Ciclo 2 : From Bottom – Right to Top – Left

Nel secondo ciclo cambia il verso di percorrenza sia delle righe che delle colonne. E’ sufficiente sostituire i valori riga e colonna correnti con i loro complementati. Ad esempio, se consideriamo il caso di una matrice di dimensione 4 x 4, volendo percorrere una colonna, l’indice di riga assumerà i valori: 1,2,3,4. Questa è l’uscita del contatore. A noi serve invece la sequenza: 4,3,2,1. ottenibile prendendo l’uscita del contatore e sostituendola con valore di fondo scala – l’uscita -1, ovvero: 4-0, 4-1, 4-2, 4-3. Applicando questa traslazione sia alla riga che alla colonna correnti, abbiamo realizzato il ciclo 2. Con i valori così ottenuti vengono calcolati gli argomenti per i coefficienti S e F.

Ciclo 3 : From Top – Right to Bottom – Left

Rispetto al ciclo 1 cambia solo il verso di percorrenza delle colonne. Complementiamo dunque la colonna corrente.

Ciclo 4 : From Bottom – Left to Top - Right

Stavolta bisogna complementare solo il valore della riga corrente, visto che le colonne vengono percorse dal basso verso l’alto, mentre le righe vengono scorse correttamente da sinistra verso destra.

Nella figura che segue, numero 50a, viene mostrata la direzione di scansione della matrice y(i,j) in base al ciclo che si sta effettuando. Le colonne vengono percorse secondo la direzione indicata dalle frecce all’interno delle matrici, mentre le frecce doppie in basso indicano il verso seguito nel cambio di colonna.

11 33 y y ⎛ ↓ _{↓ ⎟}⎞ ⎜ _⎟ ⎜ _⎟ ⎜ _{↓ ↓ ↓ ⎟} ⎜ ⎟ ⎜ ⎟ ⎜ _⎟⎟ ⎜ ↓ ↓ ⎝ ⎠ ⇒⇒⇒⇒⇒ 11 33 y y ⎛ ↑ _{↑ ⎟}⎞ ⎜ _⎟ ⎜ _⎟ ⎜ _{↑ ↑ ↑ ⎟} ⎜ ⎟ ⎜ ⎟ ⎜ _⎟⎟ ⎜ ↑ ↑ ⎝ ⎠ ⇐⇐⇐⇐⇐ 13 31 y y ⎛ ↓ ↓ ⎞_⎟ ⎜ _⎟ ⎜ _⎟ ⎜ _{↓ ↓ ↓ ⎟} ⎜ ⎟ ⎜ ⎟ ⎜ _⎟⎟ ⎜ ↓ ↓ ⎝ ⎠ ⇐⇐⇐⇐⇐ 13 31 y y ⎛ ↑ ↑ ⎞_⎟ ⎜ _⎟ ⎜ _⎟ ⎜ _{↑ ↑ ↑ ⎟} ⎜ ⎟ ⎜ ⎟ ⎜ _⎟⎟ ⎜ ↑ ↑ ⎝ ⎠ ⇒⇒⇒⇒⇒

Ciclo 1 Ciclo 2 Ciclo 3 Ciclo 4

Figura 50a. Direzione di scansione della matrice y per i quatto cicli.

4.1.4 Fase di elaborazione: accesso alle Ram

Con il prelievo dei dati dalle Ram X ed Y inizia la fase di elaborazione in cui saranno coinvolti tutti i blocchi del filtro. Si tratta di una fase ciclica nel senso che un pixel viene prelevato dalla ram, subisce un certo numero di operazioni, e viene quindi depositato nuovamente in memoria, da dove sarà nuovamente letto nel caso in cui il ciclo di scansione attuale non sia l’ultimo tra quelli previsti. Illustriamo dunque come è stato possibile simulare una ram in VHDL. Come già anticipato al momento di parlare della funzione di conversione da formato matriciale a quello di testo per un’immagine nell’ambiente Active, una ram in può essere semplicemente vista come una pila di locazioni a dimensione fissata, dunque un vettore di vettori nel senso che una locazione è di per sé un vettore di bit e la ram viene costruita mettendo insieme più locazioni. Nel nostro caso il numero di locazioni coincide con le dimensioni (in pixel) dell’immagine da processare anche se in via di principio è possibile fissare un numero massimo di locazioni per soddisfare il caso peggiore e poi occupare solo quelle che servono. Il problema non si pone invece se la dimensione del frame da sottoporre a filtraggio è sempre la stessa. Per la dimensione di locazione, si sono invece scelti 8 bit per la ram X dato che i pixel dell’immagine monocromatica sorgente assumono valori interi compresi tra 0 e 255 mentre per ram Y, memoria d’appoggio per i calcoli intermedi, la locazione è più grande visto che deve accogliere anche una parte frazionaria, che, per le scelte già motivate in precedenza6, assume il valore di 10 bit. In totale la locazione di ram Y è ampia pertanto 18 bit. Si è poi descritta la ram come rete sincrona con la seguente piedinatura di ingresso – uscita:

Pin di ingresso:

• File: serve per attivare lo stream su file di testo, per cicli di lettura e scrittura della memoria. E’attivo alto. Se disattivato si può accedere alle locazioni della memoria per leggere o scrivere un certo dato senza doverlo prelevare o scrivere su file. Questa funzionalità è utile solo nella fase di simulazione e non sarà sintetizzata.

6 _{Vedi capitolo 3 par. 3.1.1 pag. 72.}

• W_R: pin di write_enable o controllo lettura - scrittura: 0 per lettura, 1 per scrittura della memoria.

• Clk: ingresso del clock.

• Addr: bus indirizzi per accedere alla locazione desiderata.

• Data: piedino per l’ingresso dati per scrivere nelle locazioni della Ram. E’ utilizzabile se file = 0. La dimensione in bit è indicata dal parametro D. • Enable: abilitazione generale per tutti i componenti del circuito.

Pin di uscita:

• Q: piedino per prelevare dati dalla ram, nella fase di lettura. La dimensione della cella di memoria, in bit, è indicata dal parametro D.

• Ready: flag che se attivo segnala che la memoria ha completato lo stream su file.

Questa entity è stata descritta con dimensioni parametriche ed è stata instanziata con i nomi X ed Y regolando opportunamente i parametri a seconda del caso. Il funzionamento della ram così descritta è riassumibile in poche parole: nel caso di stream su file si deve porre ad 1 il segnale file per un ciclo di clock e quindi riportarlo a zero. La memoria reagisce scrivendo o leggendo su o da file il contenuto di tutte le sue locazioni scorrendole tutte dalla prima all’ultima, rispettivamente se il segnale di write_enable vale 1 oppure 0. Se invece non si vuole uno stream su sorgente o destinazione esterna alla ram, si tiene il segnale file a 0 e nel caso di una scrittura, si deve presentare sul bus indirizzi addr l’indirizzo della locazione e sul bus dati data il dato da scrivere, e porre write_enable alto. Al primo fronte di clock utile, nella locazione indirizzata da addr sarà scritto il dato presente su data. Per la lettura di una locazione bisogna presentare solo l’indirizzo e porre write_enable a 0 ed al primo fronte di clock in salita il dato desiderato sarà posto sul bus dati di uscita q. In questa fase un eventuale segnale sul bus dati in ingresso data viene ignorato. Al momento in cui le ram X ed Y vengono instanziate nella struttura finale, i loro bus addr sono connessi ad un mux 2 to 1 che riceve in ingresso l’uscita del Memories_Address_Generator e l’uscita di un mux 4 to 1 che riceve in ingresso le

4 uscite del blocco Pixel_Address_Conversion. Entrambi i MUX per ram X ed Y sono pilotati dalla macchina a stati enable_generator che in fase di start farà arrivare su addr l’uscita del MAG, altrimenti selezionerà uno dei quattro ingressi che arrivano al MUX a 4 vie.

4.1.5 Calcolo dei coefficienti F

Figura 52. Ingressi e uscite della rete Calcolo_Fo _Fv.

Per il calcolo dei coefficienti Fo ed Fv è necessario prelevare dati dalla ram Y a 18 bit. Ricordiamo la formula analitica dei coefficienti:

( 1, ) (1 ) ( , ) ( , 1) (1 ) ( , ) fo y i j y i j fv y i j y i j α α α α = − + − = − + −

dove y(i,j) è il pixel centrale della maschera di filtraggio mentre y(i-1,j) e y(i+1,j) sono rispettivamente il pixel precedente ed il successivo lungo la direzione orizzontale e y(i,j-1) ed y(i,j+1) sono il precedente ed il successivo lungo la direzione verticale. L’aspetto della relazione analitica suggerisce un’architettura consistente in un moltiplicatore con accumulatore, ed in effetti dopo aver memorizzato i dati α e y in ingresso per mezzo di una barriera di flip-flop, incontriamo un moltiplicatore che è stato descritto con l’algoritmo dello shift & add e che dà vita, in fase di sintesi, ad una cascata di sommatori opportunamente

shiftati. Vedremo in seguito nel dettaglio la struttura del moltiplicatore, essendo esso presente anche più avanti in un blocco dedicato. Lo studio della dinamica del coefficiente F7 ha permesso di dimensionare opportunamente tutta la rete, ed in particolare il moltiplicatore. A valle di quest’ultimo, troviamo tre registri di dimensione diversa che servono per memorizzare, nel caso di Fo, i valori: α y(i-1,j), α y(i,j) e y(i,j). Con un’opportuna politica di gestione dei segnali di

enable della rete si riesce a sincronizzare questi dati in modo che siano disponibili al momento opportuno per l’ultima parte della rete, l’entity combinatoria add_sub, che essendo provvista di un sommatore ed un sottrattore costruisce il termine F secondo la sua definizione. La rete prevede come segnali di ingresso il clock, vari enable e vari reset per tutti i livelli di registri. Il valore del parametro α opportunamente decodificato dalla rete alfa_par entra attraverso i fili in_alfa, mentre per mezzo di in_y giungono i valori dei pixel dalla ram_y. Dunque è necessario rendere disponibile il valore di y(i,j) su in_alfa e su in_y. Dopo un ciclo di clock si trasmette su in_y il valore del pixel precedente o successivo, a seconda del caso, ed infine quello centrale, dopo un ulteriore Tclk. Il moltiplicatore essendo stato descritto come rete combinatoria è in grado di fornire il prodotto entro un ciclo di clock, se si suppone di non spingere troppo la frequenza di funzionamento del sistema8. Ne segue che a partire dall’immissione del primo dato, dopo 1 Tclk viene campionato e memorizzato il valore di α y(i-1,j), al clk successivo sono disponibili i valori α y(i,j) e y(i,j). La rete add_sub, che è direttamente collegata all’uscita, è di tipo combinatorio, dunque risponde anch’essa entro 1 Tclk. In definitiva la latenza del circuito è 3 Tclk.

Per il calcolo di entrambi i coefficienti Fo ed Fv sarebbe stato possibile utilizzare una sola rete rendendola disponibile prima per il calcolo di un coefficiente, e poi per calcolare l’altro, con la conseguenza che il sistema globale sarebbe stato più lento. Volendo però cercare di limitare la latenza del sistema globale si è preferito, visto anche che le risorse richieste da questo blocco non sono eccessive, duplicare la rete, in modo tale che una sia dedicata al calcolo di Fo e l’altra al calcolo di Fv. Rimane però il problema dell’ingresso dei dati che comunque dipende dalla ram, che sappiamo non poter fornire più di un dato per

7 _{Vedi Capitolo 3 par. 3.1.2 pag. 74.}

ogni Tclk. Si è cercato dunque di ottimizzare la lettura dei dati per i coefficienti F e la soluzione adottata è stata quella di leggere prima il pixel adiacente a quello centrale per Fo, quindi il pixel centrale che serve sia per Fo che per Fv ed infine il pixel che mancava per il calcolo di Fv. Si intuisce che il calcolo di Fo terminerà 1 Tclk prima di quello di Fv, che ha ricevuto più tardi l’ultimo dato; sarà sufficiente sincronizzare i dati ottenuti per mezzo della solita macchina a stati Enable_Generator. In figura 53 è possibile vedere la struttura interna dei blocchi per il calcolo dei coefficienti F. Nella figura precedente ed in tutte le altre il parametro M di riferimento per la parte intera è fissato al valore 7.

4.1.6 Calcolo dei coefficienti S

Figura 54. Ingressi e uscite della rete Calcolo_So _Sv.

In contemporanea con il calcolo dei coefficienti F avviene la computazione dei coefficienti So ed Sv. Anche in questo caso si è preferito descrivere un circuito dedicato al calcolo del coefficiente S per poi duplicarlo in modo da ottimizzare la latenza del sistema. Nel capitolo precedente è stato ampiamente descritto come sia stato possibile approssimare l’espressione del coefficiente in questione, in questo paragrafo verranno semplicemente presentate le scelte architetturali operate per il blocco designato al calcolo di S.

Nell’algoritmo originale descritto in linguaggio C, il circuito per il calcolo dei coefficienti So ed Sv fa uso di un divisore per calcolare il quoziente tra due pixel x1 ed x2, rispettivamente il precedente ed il seguente del pixel centrale della maschera di filtraggio, lungo la direzione orizzontale nel caso di So e lungo la direzione verticale nel caso di Sv. Per evitare casi indefiniti e infiniti come il rapporto tra due zeri od un rapporto in cui il denominatore è nullo si preferisce incrementare di una unità i due pixel oggetto del rapporto. D’altro canto, per evitare di superare il valore 255, che necessiterebbe dell’allocazione di un bit ulteriore per la rappresentazione in binario, l’incremento dei pixel è selettivo, nel senso che viene effettuato solo se il valore letto è minore di 255. Abbiamo quindi un comparatore che confronta i pixel con la soglia 255 e pilotando i due mux in

uscita, decide se mandare al divisore a valle il valore effettivo del pixel oppure il valore incrementato di uno. Gli ipotetici divisore e dividendo vengono prima opportunamente ordinati attraverso un blocco scambiatore pilotato da un altro comparatore, in modo da avere in uscita un quoziente sempre maggiore od uguale ad 1, visto che abbiamo sfruttato la simmetria delle funzioni So, Sv al momento di costruire la LUT9. In una prima soluzione adottata, l’uscita del divisore andava a pilotare la LUT, la cui uscita è su 20 bit, 10 per la parte intera dato che il valore massimo da leggere nella memoria è 1000 ed altrettanti bit per la parte frazionaria, dato che quest’ultima è stata troncata alla terza cifra decimale al momento del progetto della LUT ottima, che prevede valori che sono interi se maggiori di 2, oppure valori con parte frazionaria troncata alla terza cifra, del tipo 1.x1x2x3 o 0.x1x2x3 dove questa volta con xi si vuole indicare una qualsiasi cifra decimale.

Ottenuti risultati soddisfacenti, si è poi scelto di fare a meno nella nostra architettura dei divisori poiché tali componenti appesantiscono notevolmente la sintesi.

4.1.6.1 Implementazione con rete SAR

L’indirizzo della Lut può essere generato attraverso una rete sincrona che, sulla base dell’algoritmo delle Approssimazioni Successive (SAR), genera il numero binario opportuno che identifica l’intervallo della LUT da leggere. Quest’ultima ha 32 intervalli e quindi l’indirizzo per pilotarla avrà dimensione pari a 5 bit. La rete SAR opera prendendo i due pixel x1 ed x2 opportunamente ordinati e incrementati, in modo che x1 sia maggiore od uguale ad x2, poi per mezzo di un comparatore confronta x1 con (x2⋅ soglia i-esima) dove soglia i-esima dipende

dal caso in cui ci troviamo. Il comparatore restituisce un valore alto se (x1 > x2 ⋅ soglia i-esima) o zero altrimenti. Sostanzialmente anziché calcolare

(x1 / x2) < soglia, consideriamo x1 < (x2 ⋅ soglia) e così evitiamo di utilizzare il divisore. Siccome si deve scegliere uno tra i 32 intervalli della Lut, in realtà la rete applica l’algoritmo di bisezione andando a scegliere per tentativi

(approssimazioni successive) l’intervallo di quantizzazione opportuno. L’algoritmo si fonda su un albero binario che definisce la bisezione. Nelle prossime figure 55 e 56 è possibile vedere lo schema dell’albero. Ad ogni ciclo di clock viene deciso un bit dell’indirizzo da generare, a partire dal più significativo fino all’ultimo. Questa rete impiega dunque 5 cicli di clock per fornire in uscita il dato valido. Le soglie i-esime vengono generate da una logica dedicata (Edge_Generator). Visto che la lut è semplicemente una rete combinatoria e che gli ingressi sono registrati con flip-flop, la latenza della rete per il calcolo di So e Sv è di 6 cicli di clock. Il circuito è stato implementato come macchina sincrona a stati che necessita di essere resettata ogni volta che si vuole calcolare un nuovo indirizzo di una word per la Lut.

Per motivi di spazio il disegno dell’albero suddetto è stato diviso in parte alta e parte bassa. Il primo confronto viene effettuato tra il pixel x1 e tra il termine (x2 ⋅ 1.029).

Se x1 è strettamente maggiore dell’altro valore, si entra nella parte alta dell’albero, altrimenti si percorre la parte bassa dell’albero binario. Giunti ad un nuovo nodo, si ragiona analogamente a prima confrontando x1 con x2 moltiplicato per la costante indicata sul percorso nelle figure 55 e 56, e si decide quindi se proseguire nel sottoramo superiore od inferiore. Il processo ha termine quando sono stati calcolati tutti i cinque bit della stringa che deve indirizzare la Lut. Sempre nelle figure esplicative dell’albero, i numeri che compaiono immediatamente dopo un nodo, indicano il valore attuale della stringa. Le cifre indicate con “x” corrispondono a bit il cui valore non è specificato e che saranno computate in seguito.

Figura 55. Parte bassa dell’albero Sar.

Nella tabella seguente viene chiarita l’associazione degli indirizzi binari all’intervallo della Lut che deve essere letto:

X1/X2 ∈ Valore LUT Indirizzo Sar Valore in decimale 1 1000 00000 0 ] 1.000 ; 1.001 ] 991 00001 1 ] 1.001 ; 1.002 ] 956 00010 2 ] 1.002 ; 1.003 ] 893 00011 3 ] 1.003 ; 1.004 ] 812 00100 4 ] 1.004 ; 1.005 ] 725 00101 5 ] 1.005 ; 1.006 ] 639 00110 6 ] 1.006 ; 1.007 ] 559 00111 7 ] 1.007 ; 1.008 ] 488 01000 8 ] 1.008 ; 1.010 ] 402 01001 9 ] 1.010 ; 1.012 ] 310 01010 10 ] 1.012 ; 1.014 ] 243 01011 11 ] 1.014 ; 1.016 ] 195 01100 12 ] 1.016 ; 1.018 ] 159 01101 13 ] 1.018 ; 1.023 ] 118 01110 14 ] 1.023 ; 1.029 ] 77 01111 15 ] 1.029 ; 1.036 ] 50 10000 16 ] 1.036 ; 1.049 ] 32 10001 17 ] 1.049 ; 1.062 ] 19 10010 18 ] 1.062 ; 1.075 ] 12 10011 19 ] 1.075 ; 1.120 ] 7 10100 20 ] 1.120 ; 1.180 ] 3 10101 21 ] 1.180 ; 1.240 ] 1.535 10110 22 ] 1.240 ; 1.300 ] 0.955 10111 23 ] 1.300 ; 1.400 ] 0.620 11000 24 ] 1.400 ; 1.500 ] 0.390 11001 25 ] 1.500 ; 1.600 ] 0.280 11010 26 ] 1.600 ; 1.750 ] 0.205 11011 27 ] 1.750 ; 3.000 ] 0.105 11100 28 ] 3.000 ; 60.000 ] 0.021 11101 29 ] 60.0000 ; 120.000 ] 0.003 11110 30 ] 120.0000 ; 180.000 ] 0.002 11111 31

Tabella 19. Soglie, valori e corrispondenza tra indirizzo di word e uscita rete Sar.

Nelle figure 57 e 58 disponibili nella prossima pagina vengono infine proposti gli schemi a blocchi dei circuiti Sar e Calcolo_So_Sv complessivo:

Figura 57. Schema a blocchi della logica Sar.

4.1.7 I moltiplicatori

Figura 59. Ingressi e uscite della rete Multiplier_Main_Reg.

Siamo giunti al livello dei due moltiplicatori che realizzano i prodotti So ⋅ Fo ed Sv ⋅ Fv. Si tratta di due circuiti identici per funzionalità e dimensionamento ed al solito si è preferito tenere separati i cammini dei coefficienti orizzontali da quelli verticali per non penalizzare le prestazioni di velocità del sistema.

Il moltiplicatore è stato descritto secondo l’algoritmo shift and add, molto comune nel caso di prodotti binari. Come sempre innanzitutto si incontra una barriera di flip-flop che costituiscono registri per memorizzare gli ingressi, pertanto il moltiplicatore come entity globale risulta essere una rete sincronizzata. Il moltiplicatore vero e proprio è invece una rete combinatoria. Sostanzialmente, ricevuti gli ingressi, che hanno una dimensione diversa in termini di bit a causa della dinamica dei coefficienti F ed S che come abbiamo visto nel cap. 3 non è la stessa, innanzitutto si procede con l’estensione dell’operando a dimensione minore aggiungendo ad esso degli zeri in testa affinché i fattori argomento della moltiplicazione siano della stessa lunghezza. Per fare un esempio sul funzionamento della rete, supponiamo di aver già effettuato l’estensione e di operare, per semplicità, con numeri a dimensione N = 2 bit, chiamiamoli num1 e num2. A questo punto num1 viene ulteriormente esteso aggiungendo in testa uno zero per dare vita ad una nuova grandezza che chiameremo num1_ext, mentre num2, dopo essere stato concatenato ad una stringa di zeri, la cui dimensione è

(N+2), va a far parte del valore product. Quest’ultimo è formato da due parti aventi la stessa dimensione ( pari a quella di num1_ext) che definiamo parte alta e parte bassa. Nel caso in questione parte alta e parte bassa hanno dimensione 3 bit. La variabile product fungerà da accumulatore per il risultato. L’algoritmo in questione infatti, prevede che se il bit meno significativo di product è 1, se ne aggiorni la parte alta con la somma tra parte alta e num1_ext e si esegua quindi uno shift verso destra di una posizione di tutto il vettore product. Il risultato di questa operazione è che il bit meno significativo viene eliminato e viene rimpiazzato in testa da uno zero. Nel caso in cui il test sul bit meno significativo desse come esito 0, verrebbe effettuata la sola operazione di shift. La serie somma e shift viene effettuata (N+1) volte, in modo da scorrere tutti i bit di num1_ext. Per capire come funziona l’algoritmo è sufficiente mettere in colonna due valori binari ed impostare la moltiplicazione. Il risultato finale deve essere prelevato negli (N+2) bit meno significativi di product o comunque in parte di essi, a seconda della dinamica del prodotto.

In questo progetto compaiono due moltiplicatori per So x Fo e Sv x Fv, e ce ne sono degli altri nel circuito per il calcolo di So per quanto riguarda la rete SAR.

Tutti sono stati descritti con l’algoritmo Shift and Add. Gli ingressi per il moltiplicatore completo di registri sono: clock, reset ed enable differenziati per i due ingressi dati, che sono in_f ed in_s, l’uscita è product.

4.1.8 I Sommatori

Figura 61. Ingressi e uscite della rete Adder2_reg.

Ricordando il diagramma a blocchi dell’architettura del filtro RRF, i sommatori sono due e si chiamano chiamati adder1 e adder2. Il primo ha il compito di calcolare la somma So ⋅ Fo + Sv ⋅ Fv + y(i,j) che costituisce il numeratore dell’espressione analitica del filtro RRF. Sono dunque necessari tre ingressi. La presenza di y(i,j) a questo livello rende conto della ricorsività del filtro. Adder2,

presente nel ramo di destra dello schema a blocchi, calcola la somma (So + Sv + 1) e prevede pertanto due soli ingressi, essendo il terzo fisso ad 1.

Entrambi i sommatori in questione ad anche gli altri presenti nelle sottoreti sono stati descritti come reti combinatorie in VHDL nel modo più semplice possibile, affinché sia il tool di sintesi a scegliere l’architettura migliore per queste entity. La realizzazione sarà effettuata per mezzo di adder di tipo ripple carry out, come riportato nelle due figure che seguono.

Figura 63. RTL Schematic di Adder2

4.1.9 Calcolo del termine a denominatore di y(i,j)

I dati nella catena di sinistra sono ormai giunti all’ingresso del blocco finale per il calcolo della luminanza, e vengono memorizzati da una barriera di flip-flop in risposta al segnale di enable dedicato pilotato dalla macchina a stati. Ancor prima però i dati che percorrono la catena di destra sono arrivati al blocco che viene presentato in questo paragrafo, vale a dire Rom_Inversion. Tale entity ha lo scopo di calcolare il valore reciproco di (So + Sv + 1) opportunamente amplificato di un fattore K come già giustificato nel capitolo precedente. Per semplicità, la quantità (So + Sv + 1) sarà d’ora in poi indicata con Z. Come suggerisce il nome dato al circuito, si tratta di una Rom, una memoria a sola lettura che viene precaricata

nella fase di inizializzazione del sistema con i valori della funzione 1 / Z pre-campionati. Nella fase di start avviene la scrittura delle locazioni della rom,

contemporaneamente all’acquisizione del frame da elaborare ed in seguito, come nel caso della lettura delle ram X e Y, sarà sufficiente presentare su opportuni pin l’indirizzo della locazione da leggere e porre il segnale write_enable a 0 per ottenere, al primo fronte di clock in salita, il valore approssimato di 1 / Z sull’uscita dati q_inv. Rom_Inversion comunica in fase di pre-carica con il blocco Memories_Address_Generator attraverso i pin add_out_inv ed enable_mag. Il segnale dav_inv serve invece per comunicare alla parte controllo che la fase di pre-carica è giunta al termine.

Vediamo adesso come avviene la scelta della locazione da leggere. Su addr_inv_out arriva il valore Z di cui si vuole ottenere il reciproco moltiplicato per K. Siccome la quantizzazione della funzione K / Z non è uniforme, non esiste una relazione immediata tra Z e l’indirizzo di locazione da leggere all’interno della Look-Up-Table. Z viene dunque inviato ad una sottorete combinatoria il cui nome è Rom_Addr_Gen. Quest’ultima implementa l’algoritmo di calcolo della word della Rom che si deve leggere e la sua uscita va ad uno dei 2 ingressi di un MUX 2 to 1 che, gestito dalla parte controllo, sceglie chi tra Memories_Address_Generator e l’uscita del sommatore adder2 debba indirizzare la Rom. Come già affermato nel Cap. 2, par. 2.4.6, Z può assumere valori compresi tra 1 e 2001 con estremi inclusi. Questo range è stato suddiviso in 2 sotto intervalli: da 1 a 50 in cui il passo di quantizzazione QP è pari a 0.1 e da 50 a 2001 in cui QP vale 1. Il primo sotto intervallo consiste di (50-1) / 0.1 = 490

locazioni, mentre nel secondo sotto intervallo ci sono (2001 – 50) = 1951 locazioni per un totale di 2441 valori campionati per K / Z. Ne segue che un primo test che Rom_Addr_Gen deve effettuare è una comparazione della parte intera di Z con il valore 50. Sarà dunque presente un comparatore del tipo “uguale o diverso”. Se Z > 50 dovrà essere letta la locazione di indirizzo: Int (Z) + “?”, dove con Int (Z) si è indicata la parte intera di Z. Per calcolare il valore incognito si può supporre di voler calcolare l’inverso di Z = 50.1. Si rende quindi necessario accedere al primo intervallo di quantizzazione a QP unitario. Prima di incontrarla, scorrendo tutte le locazioni dalla prima e considerando che si inizia a contare a partire da 0, quella utile sarà la numero 490. Dunque “?” = 490 – Int (Z) = 490 – 50 = 440. E’ poi necessario aggiungere il caso particolare in cui Z = 2001 che porterebbe a leggere la locazione di indirizzo 2441 che ovviamente non esiste dato che la numerazione va da 0 a 2440; in questo caso si impone la lettura della locazione numero 2440 andando dunque a comprendere l’estremo superiore del sotto intervallo di quantizzazione.

Se invece la comparazione con il valore 50 ha dato come risultato “minore” significa che Z < 50 e dunque si ricade nella zona a QP = (0.1). Con una batteria di comparatori a soglie fisse si estrae la parte decimale di Z, che indichiamo con Dec(Z) ed alla fine l’indirizzo di locazione che si deve leggere sarà dato dalla relazione: Int(Z) ⋅ 10 – 10 + Dec(Z). Il fattore moltiplicativo è dovuto al fatto che essendo QP = 0.1, supponendo di aumentare di una unità Z ci si deve spostare di 10 locazioni, la traslazione indietro di 10 locazioni è invece giustificata dal fatto che i valori da 0 a 0.9 non sono accettabili ed infine deve essere sommata la quantità Dec(Z) visto che la sua variazione coincide proprio con il QP.

if (Z > 50) then Rom Location <= Int (Z) + 440; else Rom Location <= Int(Z) x 10 – 10 + Dec(Z); end if;

Tabella 20. Esempio di corrispondenza tra numero da

invertire e locazione della rom in cui si trova il risultato.

in_z_inv ROM Location

1.000 0

7.750 67

384.000 824

2000.000 2441

4.1.10

Figura 65. Ingressi e uscite della rete Multiplier_y_reg.

Con il blocco Multiplier_y_reg si conclude il calcolo del filtro RRF estrattore di luminanza. Calcolata y(i,j), la parte controllo provvederà a salvare il pixel nella ram Y e poi sarà deciso se leggere nuovi dati per calcolare un nuovo valore di luminanza o se attivare il divisore di riflettanza per l’elaborazione finale del sistema. In ogni caso qui si apre il percorso di retroazione che porta le uscite ad aggiornare gli ingressi del sistema. L’entity in questione è un moltiplicatore del tutto analogo a quelli già descritti nel paragrafo 4.1.7 in conseguenza del fatto che è stato possibile riscrivere l’espressione di y(i,j) come prodotto anziché come quoziente10. In più viene effettuata un’operazione di shift verso destra di 12

locazioni, avendo ottenuto subito a valle del moltiplicatore K ⋅ y(i,j) con K = 4096 = 212. Con questa operazione a complessità circuitale nulla si riesce a

dividere per K abbattendo il coefficiente di amplificazione necessario per motivi di aritmetica del sistema. Un’ultima caratteristica di questa rete è la presenza di registri anche in uscita oltreché in ingresso, dato che si tratta del blocco di uscita del filtro RRF.

I segnali di ingresso sono pertanto clock, reset ed enable dedicati per i due ingressi e per l’uscita, in_num per il numeratore ed in_den per il denominatore di

y, mentre l’uscita è chiamata product ed è ovviamente su 18 bit in accordo con la dimensione delle locazioni di ram Y.

4.1.11 Calcolo della Riflettanza

Figura 66. Ingressi e uscite della rete Reflectance_Divider.

Originariamente al calcolo della riflettanza era stato dedicato un blocco a parte, un divisore che ricevute le immagini originale e di luminanza, calcolava il quoziente pixel a pixel delle due. Si è poi preferito inglobare tale calcolo nel progetto del filtro RRF per dare maggior compattezza al lavoro cercando di sfruttare le risorse già allocate ed anche per ottimizzare le prestazioni in termini di velocità per tutto il sistema.

In seguito alle considerazioni fatte nel par. 3.2.3, l’obiettivo è ora realizzare un divisore semplificato in grado di calcolare la riflettanza su 8 bit, di cui 2 per la parte intera, ed i restanti 6 per la parte frazionaria. La rete in questione si chiama Reflectance_divider. I suoi ingressi sono due pixel, che chiamiamo x ed y, prelevati uno dalla ram X e l’altro dalla ram Y, oltre al clock e vari enable per tutti i registri della rete, un reset globale e l’uscita r_out_reg opportunamente sincronizzata con un’altra barriera di flip-flop. Dopo essere stati campionati dai registri d’ingresso, i valori x ed y attraversano la rete combinatoria x_y_increase che li incrementa di una unità nel caso in cui nessuno dei due sia pari a 255.

Con questa operazione si vuole essere fedeli all’algoritmo C che prevedeva di calcolare la riflettanza come rapporto tra (x+1) e (y+1). L’incremento non avviene se uno dei due ingressi è pari al valore massimo rappresentabile su 8 bit per evitare overflow. Superata l’entity di incremento selettivo, si incontrano i blocchi difference_1, difference_2 e difference_3 che forniscono in uscita rispettivamente i valori (x–y), (x-2y), (x-3y) ed un bit di segno che vale 1 se la differenza calcolata è maggiore di zero. I 3 bit di segno vengono raccolti dalla rete ref_entire, decoder che sulla base della configurazione degli ingressi che riceve decide se il valore intero della riflettanza è 0, 1, 2 o 3. L’uscita di questa rete viene anche utilizzata come controllo per il MUX 4 to 1 che riceve in ingresso le 3 uscite delle reti difference e ed in più x estesa da 8 a 18 bit. E’ necessario, infatti, selezionare l’opportuno resto della prima parte della divisione per procedere con il calcolo della parte frazionaria della riflettanza. Gli ultimi 6 bit di essa vengono generati da 6 reti identiche istanziate una in cascata all’altra in grado ognuna di calcolare il bit i-esimo della parte frazionaria di r(i,j). Si tratta della rete combinatoria Ref_fractional che riceve in ingresso un resto su 18 bit, ipotetico divisore su 18 bit, e restituisce in uscita il bit i-esimo frazionario quoz_dec ed il resto resto_out che sarà instradato in ingresso all’eventuale rete Ref_fractional successiva. Sempre nel capitolo 3 si era assunto come limite superiore per la parte intera il valore 3, con parte frazionaria nulla. Dunque esiste un altro ingresso a 2 bit chiamato nop (no operate) blocca la rete ponendo quoz_dec a 0 nel caso in cui la parte intera della divisione sia pari a 3. Naturalmente è stato utilizzato il segnale di uscita di ref_entire come nop per tutti i blocchi Ref_fractional. Per calcolare il bit i-esimo della parte frazionaria di r(i,j) si prende il resto ricevuto in ingresso, ed in ogni caso lo si moltiplica per 2 shiftandolo di una posizione verso sinistra, poi lo si confronta con y. Se il nuovo resto è maggiore od uguale ad y, si pone il bit frazionario i-esimo ad 1, e si restituisce in uscita (resto – y), altrimenti il bit frazionario viene posto a 0 e non si aggiorna il resto. Tra un blocco Ref_fractional ed il successivo è stato interposto un registro a flip-flop in modo da sincronizzare il flusso di dati. Gli enable dei registri saranno attivati dalla parte controllo. Il concatenamento dei bit di uscita di Ref_Entire e dei blocchi Ref_fractional costituisce il risultato r(i,j). Tale calcolo deve essere ripetuto per ogni pixel

dell’immagine e dunque in questa fase torna ad essere attivo il Memories_Address_Generator che scorre le memorie X ed Y per leggerne tutte le locazioni. Riportiamo lo schema di funzionamento del decoder Ref_Entire.

(x-y) & (x-2y) & (x-3y) = “000” ⇒ Int [r(i,j)] = 0 (x-y) & (x-2y) & (x-3y) = “100” ⇒ Int [r(i,j)] = 1 (x-y) & (x-2y) & (x-3y) = “110” ⇒ Int [r(i,j)] = 2 (x-y) & (x-2y) & (x-3y) = “111” ⇒ Int [r(i,j)] = 3

Con il simbolo & si intende l’operazione di concatenazione tra bit, il cui risultato è una stringa di numeri binari.

Nella figura successiva viene illustrata l’architettura del divisore di riflettanza.

Figura 68. Rete per il calcolo della i-esima cifra della parte frazionaria della riflettanza.

4.2 P

:

E

_G

Possiamo immaginare tutti i blocchi che sono stati descritti finora come facenti parte di un macroblocco dal nome parte operativa. Questa, per poter operare secondo le proprie funzionalità, necessità di alcuni segnali di sincronizzazione che sono generati dalla entity Enable_Generator, il vero e proprio “cervello” di tutta l’architettura, dato che gestisce i segnali di enable ed altri controlli di tutte le altre reti del sistema. Potremmo definire il circuito in questione come la parte controllo, in opposizione al resto. Enable_Generator può essere vista come una macchina a stati finiti con un certo numero di stati, opportunamente codificati, che vengono percorsi ciclicamente e che corrispondono a precise azioni dei vari blocchi della parte operativa. A seconda dello stato in cui ci si trova, alcune reti sono abilitate ed altre no ed in seguito ad una transizione di stato, altre reti ricevono l’abilitazione mentre altre se la vedono negare.

4.2.1 Ingressi e uscite della parte controllo

Vista la grande importanza che la rete in questione riveste, essa è in stretto contatto in pratica con tutte le altre entity del sistema. Questo comporta un gran numero di ingressi ed uscite. Per motivi di chiarezza conviene pertanto elencarle in forma schematica, omettendo il solito disegno con tutti i pin.

Segnali con nomi simili, che differiscono solo in parte, saranno accorpati nella forma: signal_name_a/b per indicare i 2 segnali signal_name_a, signal_name_b.

Pin di Ingresso:

clk: ingresso del clock di sistema.

reset: pin di reset globale, in grado di riportare la macchina a stati nello stato di reset Sres.

start_in: ingresso per il segnale start che deve essere fornito dall’utente per iniziare il processing del frame attuale. Se rimosso, alla fine dell’elaborazione del frame corrente, il sistema rimane in attesa e può cominciare ad elaborare un nuovo frame solo dopo l’arrivo di un nuovo impulso su start.

alfa_in(1…0): il valore di alfa codificato su 2 bit deve essere controllato in modo da evitare la configurazione errata “00”, nel qual caso la macchina a stati resta ferma nello stato di reset.

cycles_in(1…0): in binario, il numero dei cicli di filtraggio da effettuare. Viene confrontato con un valore interno, incrementato alla conclusione di ogni ciclo. Con un test si può decidere se effettuare una nuova scansione o terminare il processo.

dav_x, dav_y,dav_inv: segnali di data valid provenienti dalle ram X,Y e rom inversion. Si esce dalla fase di precarica e si comincia la scansione vera e propria del frame quando questi segnali assumono il valore logico alto.

count_pac_end: pin attraverso il quale la rete Pixel_Address_Conversion comunica alla macchina a stati che il frame attuale è stato interamente scandito, ovvero il ciclo corrente è stato ultimato. Al verificarsi di questa condizione, si può

effettuare un test sul valore attuale del ciclo per capire se, oltre al ciclo corrente, è stato terminato tutto il processo di calcolo della luminanza.

end_y_in: segnale pilotato da Memories_Address_Generator in fase di calcolo della riflettanza. Quando assume il valore logico alto, il calcolo della riflettanza è terminato e di conseguenza il segnale di uscita frame_r_valid assume il valore 1.

Pin di Uscita:

cycle_out(1…0): il valore del contatore interno di ciclo viene reso disponibile per la rete Pixel_Address_Conversion (PAC) le cui uscite sono funzione del valore assunto dalla variabile ciclo corrente.

enable_pac, enable_pac_ff, reset_pac: segnali di enable e reset per PAC. enable_mag, reset_mag: enable e reset per Memories_Address_Generator. enable_ctrl_mux4_x, enable_ctrl_mux4_y: controlli per i multiplexer 4 to 1 a monte di ram_X e Y.

enable_ram_X, enable_ram_Y: abilitazioni per le ram X ed Y.

addr_x_ctrl, addr_y_ctrl: controlli per i mux 2 to 1 a monte di ram_X e Y. file_x, file_y: attivazione stream su file per le memorie X ed Y.

w_r_x, w_r_y : controlli write_enable per ram X ed Y, rispettivamente. enable_fo/fv_in, enable_fo/fv_ff1, enable_fo/fv_ff2, enable_fo/fv_ff3: enable per reti di calcolo coefficienti Fo ed Fv.

enable_so/sv_in1,enable_so/sv_in1a, enable_so/sv_in2,enable_so_sar: abilitazioni per le reti dedicate al calcolo dei coefficienti So e Sv.

reset_so/sv_sar: reset per le reti Sar presenti nei blocchi di calcolo per So e Sv. enable_m1/m2_in1,enable_m1/m2_in2: abilitazione per i registri a monte degli ingressi 1 e 2 di Multiplier_1 e Multiplier_2.

enable_a1_in1,enable_a1_in2,enable_a1_in3: segnali di abilitazione per i 3 ingressi di Adder1.

enable_a2_in1,enable_a2_in2: segnali di abilitazione per i 3 ingressi di Adder2. enable_inv, file_inv, w_r_inv: abilitazione, attivazione stream su file, controllo write_enable per la rom di inversione.

enable_m_in_num, enable_m_in_den, enable_m_out: abilitazione degli ingressi e dell’uscita del moltiplicatore per il calcolo finale di luminanza.

frame_y_valid: segnalatore di calcolo luminanza terminato. Attivo alto. frame_r_valid: segnalatore di calcolo riflettanza terminato. Attivo alto. enable_ref_div: enable per gli ingressi del divisore di riflettanza.

reset_ref_div: pin di reset per il divisore di riflettanza.

enable_ref_fract_ffin/ff0/.../ff5: abilitazioni per i registri della parte del divisore di riflettanza relativi alla parte frazionaria.

4.2.2 Stati della parte controllo

La macchina a stati in questione deve coordinare il funzionamento del sistema in modo che esegua sostanzialmente 3 tipi di operazioni: inizializzazione e precarica dei dati, elaborazioni per il calcolo dell’uscita di luminanza, ed elaborazioni per il calcolo del segnale di riflettanza. A parte la prima fase, che viene eseguita spendendo un solo stato (S0), le altre consistono in più stati che si ripetono ciclicamente, dato che gli algoritmi di calcolo di luminanza e riflettanza devono essere ripetuti per tutti i pixel dell’immagine11. Se non ci sono particolari condizioni di transizione, ogni stato perdura per un solo ciclo di clock. Terminato il calcolo per l’ultimo dei pixel da elaborare, la macchina esce dal loop di stati e si porta in uno stato di attesa (S40) nel quale si attende l’arrivo di un impulso sul segnale di start_in. Verificatosi questo evento, si può tornare in S0 per acquisire nuovi dati e successivamente elaborarli.

Enable_Generator possiede in totale 42 stati, in cui è compreso lo stato Sres di reset. Questo stato serve ad imporre che al momento dell’avvio la macchina a stati cominci ad evolvere da una configurazione nota. Potrebbe infatti succedere, all’accensione, che la macchina si porti in uno stato aleatorio con conseguenze facilmente immaginabili per l’elaborazione dei dati. Imponendo un breve impulso di reset asincrono all’avvio di tutto il sistema, Enable_Generator e tutte le altre

reti sincrone si porteranno nei rispettivi stati di reset, per rimanerci finché il segnale di reset non viene disattivato.

Al solito, per motivi di chiarezza, conviene elencare gli stati in forma schematica, nell’ordine in cui essi si verificano, e dando anche una breve descrizione del loro significato. Per completezza sarà riportato anche un diagramma a palle della macchina a stati.

Stato Evento

Condizione di uscita

Sres Stato di reset Rilascio del reset S0 Fase di start, inizializzazione del

sistema con caricamento delle LUT e della ROM per l'inversione

Risposta di ram_x, ram_y, rom_inv per mezzo dei segnali dav (data_valid)

S1 Abilitazione per 1 ciclo di clock del circuito pac per generare indirizzo del pixel da prelevare

Nessuna

S2 Reset dei contatori mag, campionamento uscite pac Nessuna S3 Lettura pixel x(i-1,j) e y(i-1,j) per

calcolo So e Fo Nessuna

S4 Lettura pixel x(i+1,j) e y(i,j) per calcolo So e Fo, campionamento primo pixel per calcolo So e Fo

Nessuna

S5 Lettura pixel x(i,j-1) e y(i,j-1) per calcolo Sv e Fv.

Inizio calcolo So e Fo, campionamento dati in ingresso a Sv e ingresso 3 di adder 1

Nessuna

S6 Lettura pixel x(i,j+1) e y(i,j) per calcolo Sv e Fv. Prosegue calcolo So, Sv, Fo, campionamento dati in ingresso a Fv

Nessuna

S7 Termina calcolo di Fo, campionato

su ingresso 1 di multiplier 1 Nessuna S8 Termina calcolo di Fv, campionato

su ingresso 1 di multiplier 2 Nessuna

S9 Prosegue calcolo di So ed Sv Nessuna S10 Prosegue calcolo di So ed Sv Nessuna S11 Termina calcolo di So, campionato

su ingresso 2 di multiplier 1 e ingresso 1 di adder 1

S12 Sar_ So in reset.

Campionamento So x Fo su ingresso 1 di adder1

Nessuna

S13 Termina calcolo di Sv, campionato su ingresso 2 di multiplier 2 e ingresso 2 di adder 1 Nessuna S14 Sar_ Sv in reset. Campionamento Sv x Fv su ingresso 1 di adder1 Nessuna

S15 Campionamento dato in ingresso a blocco inversione

Campionamento ingresso num di multiplier_y

Nessuna

S16 Prosegue calcolo inversione Nessuna S17 Fine calcolo inversione, dato

campionato su ingresso den di multiplier_y. Calcolo uscita di luminanza

Nessuna

S18 Campiono uscita di luminanza Nessuna S19 Scrittura uscita di luminanza in ram

Y

Se pac non è a fondo scala ritorno in S1. Se pac è a fondo scala e cicli non ultimati passaggio a S20 e incrememento contatore cicli; se pac è a fondo scala e cicli ultimati passaggio a S21

S20 Stato di reset del pac Ritorno in S1 S21 Cicli ultimati: abilitazione di ram Y

per la scrittura su file, transizione di segnale file ad 1. Segnale di fr_y_valid ad 1

Nessuna

S22 Rimozione segnale file Scrittura dati

Nessuna

S23 Attesa termine di scrittura dati Transizione del segnale dav_y ad 1 S24 Lettura di 1 pixel da ram X e Y Nessuna

S25 Campionamento dati su ingressi divisore riflettanza e inizio calcolo riflettanza (parte intera)

Nessuna

S26 Inizio calcolo di parte frazionaria di riflettanza: campionamento ingressi per parte frazionaria

Nessuna

S27 Calcolo cifra 1 parte frazionaria Nessuna S28 Calcolo cifra 2 parte frazionaria Nessuna S29 Calcolo cifra 3 parte frazionaria Nessuna

S30 Calcolo cifra 4 parte frazionaria Nessuna S31 Calcolo cifra 5 parte frazionaria Nessuna

S32 Fine calcolo riflettanza:

campionamento uscita

Nessuna S33 Scrittura dato in ram_X Nessuna S34 Attesa di un ciclo di clock per la

scrittura (per evitare problemi con il successivo incremento di addr_X e Y)

Nessuna

S35 Abilitazione di mag per incrementare indirizzi di ram_X e Y

Nessuna

S36 Verifica di calcolo riflettanza ultimato su tutto il frame.

Abilitazione ram_X per eventuale scrittura su file successiva

Se dav_y passa ad 1(mag a fondo scala) avanzamento a S37, altrimenti ritorno in S24 per calcolare la riflettanza tra 2 nuovi pixel

S37 Segnale file_x ad 1 per abilitare scrittura di ram_X su file.

Segnale di frame_r_valid ad 1

Nessuna

S38 Rimozione di file_x

Inizio scrittura su file di uscita

Nessuna S39 Attesa della fine della scrittura su

file

Transizione di dav_x al valore logico alto. Altrimenti attesa

S40 Stato finale: attesa di un nuovo frame da elaborare

All’arrivo di un impulso su start_in, si torna in S0 per acquisire nuova immagine

Tabella 21. Stati, eventi principali e transizione allo stato successivo per la parte controllo.

Come anticipato, in figura 69 nella pagina che segue è riportato il diagramma a palle della macchina a stati. E’ stata omessa per ogni stato l’indicazione della possibilità di fermare l’avanzamento della macchina. Ciò può essere effettuato semplicemente ponendo il segnale di enable globale a 0. Dunque, tale pin deve essere pilotato con un segnale fissato costantemente al valore logico alto, pena l’interruzione del funzionamento di tutto il sistema. Dato che il diagramma non fornisce informazioni circa la codifica e decodifica degli stati, tali argomentazioni saranno trattate più avanti.

Figura 69. Diagramma a palle per la macchina a stati Enable_generator

4.2.3 Stima di latenza e throughput del sistema

In questo paragrafo viene fornita una stima di latenza e throughput di tutto il sistema, due importanti parametri attraverso i quali è possibile valutare le prestazioni dello stesso. Prima di vedere le stime vere e proprie, ricordiamo brevemente le due definizioni.

Si definisce latenza il tempo, espresso in cicli di clock, che intercorre tra il momento della lettura del dato da processare (un pixel dell’immagine in questo caso) e il momento in cui lo stesso dato raggiunge l’uscita dopo aver subito tutti i passaggi di elaborazione. Si tratta di sommare i tempi di attraversamento delle reti che si trovano una in cascata all’altra. Per throughput invece si intende la

frequenza, anch’essa espressa in cicli di clock, di elaborazione dei dati (ad esempio, un pixel ogni t cicli di clock, con t pari al throughput).

Si può concludere che al fine della stima della velocità del sistema, è preferibile cercare di aumentare il valore del throughput anche a discapito della latenza, dato che quest’ultima dà i maggiori effetti durante l’elaborazione del primo dato, ma quando il sistema è entrato in regime, è invece il throughput a farla da padrona. Sarebbe stato dunque molto importante cercare di implementare un’architettura di tipo pipeline a percorsi paralleli per poter elaborare più dati contemporaneamente allo scopo di incrementare il throughput, ma sfortunatamente, sulla base dell’algoritmo ret_soft.c del retinex che ci è stato fornito, si è concluso che questo è impossibile, dato che prima di prelevare nuovi dati dalla ram Y è necessario attendere che siano stati scritti i risultati dei calcoli precedenti.

Inoltre, dato che il sistema globale può essere scisso in due sottosistemi, ovvero il primo per il calcolo della luminanza ed il secondo per il calcolo della riflettanza, saranno calcolate stime dei parametri sopra citati per entrambi, e poi si procederà al loro calcolo per il sistema completo.

Si tratta in ogni caso di elaborare un frame di dimensione N = (dimx x dimy), dove dimx indica il numero delle colonne o dimensione orizzontale, mentre dimy rappresenta il numero delle righe o dimensione verticale.

4.2.3.1 Latenza e throughput di luminanza

Osservando la tabella degli stati, si nota che si devono percorrere gli stati S3 – S19 che corrispondono al prelevamento di un pixel dalle memorie ed alla riscrittura dello stesso in seguito all’elaborazione. In totale occorrono 17 cicli di clock dato che tutti gli stati in questione perdurano per un solo Tclk. In realtà questo è vero solo per il primo pixel. Per i successivi è necessario transitare anche per gli stati S1 e S2 dovendo calcolare nuovi indirizzi per i pixel da prelevare.

Dunque la latenza vale 17 Tclk laddove si intenda come dato elaborato il singolo pixel, mentre se consideriamo tutto il frame di dimensione N, la latenza totale vale ovviamente 17Tclk + (N*-1) ⋅ 19Tclk ed è dunque dipendente dalle

dimensioni dell’immagine. Come costante moltiplicativa compare N* = (dimx –1) (dimy – 1) dato che per il calcolo della luminanza la cornice

esterna del frame viene ignorata (il sistema non elabora il bordo e si dice pertanto “edge- preserving”) ed il –1 è dovuto al fatto che la latenza relativa al primo pixel dell’immagine è già stata considerata nel termine 17Tclk. Se poi consideriamo come variabile anche il numero dei cicli da effettuare, la formula completa per la latenza di frame è:

[17Tclk + (N*-1) ⋅ 19Tclk] + (Nc –1)⋅ N* ⋅ 19Tclk + [(Nc – 1 ) ⋅ 1Tclk]

in cui il primo termine è relativo al primo ciclo ed il secondo agli eventuali cicli successivi. Essi sono leggermente diversi poiché soltanto nel primo ciclo la latenza relativa al primo pixel è di 17 Tclk, altrimenti è di 19 Tclk.

L’ultimo termine invece tiene conto dello stato di reset per il contatore PAC che deve essere azzerato alla fine di ogni ciclo. Il reset non avviene al primo ciclo e pertanto compare il coefficiente moltiplicativo (Nc –1).

Trascurando i tempi di reset del pac che nel caso peggiore saranno di 3 Tclk e la differenza nel calcolo di latenza tra primo ciclo e cicli successivi, possiamo approssimare la latenza di luminanza con l’espressione semplificata:

Latenza_lum = Nc ⋅ N* ⋅ 19Tclk

Nella tabella 22 sono riportati esempi di calcoli di latenza al variare della dimensione di frame, assumendo Tclk pari a 100 ns ovvero considerando un clock a 10 Mhz. Dimensione Frame (N) Numero di cicli (Nc) Latenza di luminanza (sec) 385 x 513 2 0.738 385 x 513 4 1.476 513 x 513 2 0.996 513 x 513 4 1.992 800 x 600 2 1.818 800 x 600 4 3.363

Per quanto riguarda il throughput, poiché tra l’elaborazione di un pixel e del successivo trascorrono 19 Tclk, esso vale 1/(19 Tclk).

4.2.3.2 Latenza e throughput di riflettanza

Nel caso del primo pixel si devono percorrere gli stati S24 – S34 per un totale di 11 Tclk. Per i pixel successivi è necessario transitare anche sugli stati S35 e S36 per incrementare i contatori. Gli stati da S20 a S23 servono invece per operazioni di scrittura su file della ram.

La formula esatta per la stima della latenza di riflettanza sarebbe:

Latenza_ref = 11 Tclk + (N-1) ⋅ 3 Tclk

dove il primo addendo si riferisce all’elaborazione del primo pixel ed il secondo è relativo ad i pixel successivi, pertanto è ovvio il motivo della presenza del coefficiente moltiplicativo (N-1).

Tuttavia la formula può essere semplificata in:

Latenza_ref = N ⋅ 13 Tclk

trascurando il fatto che per il primo pixel si risparmiano 2Tclk.

Come fatto in precedenza, vediamo nella tabella 23 alcune stime di latenza di riflettanza al variare della dimensione di frame, assumendo al solito fclk pari a 10 Mhz. Si noti che rispetto al caso della luminanza non compare la colonna relativa al numero di cicli di scansione, poiché il calcolo della riflettanza richiede sempre e solo una scansione del frame.

Dimensione Frame (N) Latenza di riflettanza (sec) 385 x 513 0.258 513 x 513 0.342 800 x 600 0.624

Tornando ad osservare le tabelle 22 e 23 si può concludere che il calcolo della luminanza richiede generalmente più tempo rispetto al calcolo della riflettanza e questo è ancor più vero se consideriamo che Nc, se possibile, deve essere posto a 4 al fine di limitare il rumore di fase sull’immagine di uscita.

Possiamo dunque concludere che la scelta di mettere in cascata le operazioni per il calcolo della luminanza e della riflettanza può essere considerata valida. Se proprio si volesse ottimizzare la latenza globale si potrebbe ideare un’architettura di tipo pipeline per rendere contemporanei i due processi. La latenza globale nel nostro caso risulta pari, trascurando gli stati dedicati agli stream su file esterno, alla somma delle latenze di luminanza e riflettanza. In simboli:

Latenza Globale = Nc ⋅ N* ⋅ 19Tclk + N ⋅ 13 Tclk ≅ N⋅Tclk⋅ (Nc ⋅ 19 + 13)

Nel caso di frame 600 x 800, 4 cicli di scansione e clock a 10 Mhz il tempo di elaborazione risulta pari a (3.636 + 0.624) sec = 4.260 sec.

Gli stati S37 - S40 si riferiscono alle operazioni di salvataggio dei dati su file, pertanto non entrano in gioco in queste considerazioni, anche perché la lettura e scrittura su file sono solo dei modi per simulare l’acquisizione dei dati e per poter verificare i risultati intermedi delle elaborazioni, ma in pratica non esistono in un sistema implementato su FPGA.

Resta da stimare il throughput per il calcolo della riflettanza; tra l’elaborazione di un pixel e del successivo trascorrono 13 Tclk, dunque il throughput di riflettanza è pari a 1/(13 Tclk).

Non ha invece senso valutare un throughput globale poiché abbiamo considerato il calcolo di luminanza e riflettanza come operazioni separate.

4.2.4 Codifica e decodifica degli stati

La macchina a stati Enable_Generator ha il ruolo di parte controllo per il sistema trattato in questo lavoro. Si tratta, come già detto in precedenza, di una macchina a stati finiti, sincrona, le cui uscite dipendono sia dagli attuali ingressi che dallo stato corrente. Come da definizione, si tratta quindi di una macchina di Moore.