Uno strumento per la compilazione hardware di un linguaggio ad automi cellulari per sistemi riconfigurabili

0.1. INTRODUZIONE 2tazione), ottenuto dalla variazione del grafo del 
usso di dati, per poter eettuarela compilazione in hardware in modo diretto. Esso fornisce uno strumento per dellepossibili ottimizzazioni e, in astratto, per la rappresentazione del circuito digitalesequenziale prodotto, ladove gran parte della letteratura giunge alla produzione dicircuiti combinatori. Oltre che a sfruttare i meccanismi logici di base per l'elabo-razione via hardware e possibile interpretarlo mediante software. Tale grafo nonviene ottenuto direttamente, ma mediante delle istruzioni, appositamente create,che consentono di rendere modulare il livello architetturale, inserendo, di volta involta, sul grafo e quindi sul circuito, automaticamente, solo i componenti richiesti,e connettendoli opportunamente fra loro. In tal modo si eettua una selezione deglielementi utili per una particolare computazione eliminando ridondanze sul circuitonale: viene incorporato solo cioche serve in una specica elaborazione. La tradu-zione in hardware viene descritta nei dettagli, presentando i componenti necessari acostruirlo e le tecniche utilizzate per descrivere questi ultimi mediante un linguaggiodi descrizione dell'hardware (VHDL) che ore astrazioni e generalizzazioni moltopotenti.Due esempi vengono eettivamente compilati e ne viene ottenuto il relativo cir-cuito in tempi brevi e, ovviamente, senza la necessita di un ulteriore intervento dialcun progettista hardware: il life e la simulazione di un incendio. Per essi vienedisegnata la rappresentazione della parte dati del grafo di computazione, e un trattodi simulazione assieme alle corrispondenti istruzioni.L'esposizione e organizzata nel seguente modo:Cap. 1) Viene qui illustrata la problematica della compilazione hardware, le interpre-tazioni che si possono dare delle descrizioni di alto livello, vengono espostii lavori di I. Page, da cui la tesi trae spunto, pur con modiche sostanziali,presentate alcune strutture dati utilizzate comunemente per la descrizione diun processo di computazione, presentato il componente hardware su cui verracomposto il circuito digitale nale.
0.1. INTRODUZIONE 3Cap. 2) Si espone il modello di calcolo degli automi cellulari, il linguaggio di cui sieettuera la compilazione, costruito come un'estensione del C,vengono quindiesposte una serie di ricerche che conducono, per lo piu, a produrre logica com-binatoria. Viene, quindi, presentata l'architettura della macchina (CAREM)per cui il compilatore produrra l'opportuno modulo di computazione.Cap. 3) Vengono spiegati i motivi che portano alla produzione di hardware sequenziale,illustrata una struttura dati che permette di rappresentare in modo completoil processo di computazione e che puo essere utilizzata per modellarlo (il grafodi computazione), viene illustrato l'obiettivo della tesi, cioe individuato il mo-dulo che il compilatore dovra produrre. In gura 3.4 viene presentata l'interastraticazione del processo di compilazione: il compilatore produrraungrafo,per mezzo di opportune istruzioni e da tale dal grafo ricaverala-architettura,descritta per mezzo del VHDL.Cap. 4) Viene illustrata la sintassi utilizzata nella modellazione del Carpet, in realtaun suo sottoinsieme, e gli strumenti (flex, bison) usati per il parsing e laprima compilazione.Cap. 5) E senz'altro il capitolo piu corposo: le istruzioni intermedie, uno strumentoper modularizzare la costruzione del grafo, vengono illustrate in ogni detta-glio, mettendono in rilievo la relazione che hanno con la -architettura. Es-se rappresentano il modo che ha il compilatore per comporre l'architetturadell'hardware nale, permettendo di scegliere i componenti e di stabilirne leconnessioni ogni volta che si specica un nuovo programma.Cap. 6) Viene qui illustrato il linguaggio utilizzato per le descrizioni dei circuiti digitali:il VHDL. Per sommi capi vengono specicati i tipi di costrutti utilizzati perla sintesi ed i criteri generali seguiti nello specicarli.Cap. 7) Una volta compresa la funzione delle istruzioni intermedie, e che il Carpetdev'essere espresso mediante esse, viene presentata la soluzione al problema
0.1. INTRODUZIONE 4della specica delle espressioni, originato dall'assenza di uno stack (strutturadinamica), e il conseguente ridimensionamento delle entita coinvolte nel com-puto delle stesse. Vengono quindi specicati i criteri scelti per la composizionedella -architettura.Cap. 8) In questo capitolo, anch'esso abbastanza corposo, vengono presentati i com-ponenti preprogettati (quindi statici o espressi in modo parametrico, cioe infunzione della dimensione dell'I/O), relativi al controllo ed alla esecuzione delleoperazioni di elaborazione: operatori aritmetici, relazionali, booleani.Cap. 9) Qui vengono mostrati i modelli di composizione del le VHDL: la descrizionecomplessiva. I componenti di instradamento, il componente di vicinato, leproblematiche inerenti le attivazioni e viene mostrato il modo in cui e statoarontato il relativo problema del rientro del controllo.Cap. 10) Inne due esempi sono stati eettivamente compilati e simulati sia a livellofunzionale, sia in seguito a sintesi (cioe con gli opportuni ritardi): il `Life',e la modellazione di un incendio. L'eetto dei ritardi viene assorbito dallaparticolare strategia di attivazione scelta, permettendo di usare l'informazionequando essa e gia assestata, pertanto vengono mostrate delle simulazioni fun-zionali con le corrispondenti istruzioni intermedie. Vengono, quindi, presentatii gra relativi, permettendo di farsi un'idea delle -architetture prodotte. Sonospecicati i ritardi massimi di alcuni componenti, individuando, in tal modo,ipunti di ineÆcienza localizzabili nell'instradamento.Cap. 11) Si traggono le conclusioni del lavoro e vengono proposti alcuni possibili sviluppiper il livello architetturale e l'hardware.
3.6. GLI STRUMENTI E L'AMBIENTE DI COMPILAZIONE 49
Vhdl
Istruzioni IntermedieCodice Carpet
Descrizione LogicaMappaturaCollocazione eInstradamentoRicavodeitempiCongurazioneSimulazione Fisica.
Grafo di computazione Simulazione funzionale
Xilinx Foundation
Modelsim
flex,bisonMVintermediaMVCarpetMVVHDL
Figura 3.4: Straticazione della produzione della descrizione
Capitolo 10Gli esempi implementati
Il codice prodotto dal compilatore e stato fatto processare sia da un tool di simu-lazione (ModelSim), che da un tool di sintesi (Xilinx Foundation, si tratta inrealta di una suite: un insieme di strumenti per l'analisi e la sintesi). I risultatidi entrambi sono paragonabili: l'eetto dei ritardi viene assorbito dall'attivazionedierenziata della parte controllo e della parte dati. I tempi di produzione dei ri-sultati sono decisamente dierenti: il circuito prodotto anche per piccoli programmioccupa facilmente l'intero FPGA. Tuttavia questo non pare un serio problema: colpassare del tempo aumenta la concentrazione di componenti sui Chip ed e facilmenteimmaginabile che la tecnica utilizzata sia passibile di ottimizzazioni oltre che di svi-luppi. Di seguito vengono presentati due esempi completamente sintetizzati: sonostati scelti perche mostrano la realizzazione dei costrutti fondamentali dei linguaggiimperativi, dunque la completezza del metodo, anche se, considerando le istruzionisottostanti, e facile che anche solo uno di essi utilizzi tutti i meccanismi di base(istruzioni intermedie).10.1 Il LifeE l'applicazione per eccellenza degli automi cellulari: rappresenta un modello disviluppo di popolazioni di cellule. Il vicinato equellodiMoore.
10.2. L'INCENDIO 11610.1.1 Le regoleLa regola di transizione si basa sul conteggio di celle `vive' attorno alla cella centrale.1. Se una cella eviva:(a) Se il numero di celle vive attorno ad essa e inferiore a 2, la cella muoredi solitudine.(b) Se il numero di celle vive attorno ad essa e superiore a 3, la cella muoredi sovraollamento.2. Se una cella e morta: se il numero di celle vive attorno ad essa e esattamentepari a 3, la cella rinascera alla prossima generazione.Ovviamente per i casi non elencati la cella manterra il proprio stato.10.1.2 Il programmaViste le dimensioni accettabili, il programma viene qui presentato per intero (g. 10.1).Lo stato e rappresentato da una variabile a due bit (viene indicato sempre il segno),eilvalore `0' codica una cella morta, mentre qualsiasi altro valore codica il valorecella viva. Si noti come le variabili vengano inizializzate (e importante farlo sempre),ecomeilvalore delle celle vivevenga ricavato mediante un ciclo sul vettore di vici-nato. Le variabili destinate a contenere i valori della somma vengono dimensionateal valore massimo possibile (dlog2(8 + 1zero)e +1segno = 4 + 1).10.2 L'incendioSi tratta di modellare lo sviluppo di un incendio sul territorio. Anche qui il vicinatoe quello di Moore.
10.2. L'INCENDIO 117cadef{dimension 2;radius 1;state(int#2 val);neighbour moore [] ([0,1] N,[1,1] NE,[1,0] E,[1,-1] SE,[0,-1] S,[-1,-1] SO,[-1,0] O,[-1,1] NO);}int#5 sum,i;{ sum=0;for (i=0;i<8;i=i+1){if (moore[i]_val!=0){sum=sum+1;}}if (cell_val==0){if (sum==3){cell_val=1;}}else{if(sum>3||sum<2){cell_val=0;}}} Figura 10.1: Programma Carpet per Life10.2.1 Le regoleGli stati, stavolta sono quattro: un albero in amme, un albero verde, un alberobruciato, il terreno. Ecco le regole di transizione:1. Se un albero e in amme, si spegne: diventa albero bruciato.2. Se un albero e verde e nell'intorno c'e un albero in amme, allora s'incendiaanch'esso.Anche qui il vicinato e quello di Moore.
10.3. I RISULTATI 11810.2.2 Il programmaMuta il numero di bit necessari a rappresentare lo stato (g. 10.2). L'albero incadef{dimension 2;radius 1;state(int#3 ground);neighbour moore [] ([0,-1] N,[1,-1] NE,[1,0] E,[1,1] SE,[0,1] S,[-1,1] SO,[-1,0] O,[-1,-1] NO);}{ if ((cell_ground==1)&&(N_ground==3||NE_ground==3||E_ground==3||SE_ground==3||S_ground==3||SO_ground==3||O_ground==3||NO_ground==3)){cell_ground=3;}else{if (cell_ground==3){cell_ground=2;}}} Figura 10.2: Programma Carpet per Incendioamme viene codicato con il valore `3', l'albero bruciato con il valore `2', l'alberoverde con il valore `1' e il terreno e rappresentato mediante il valore `0'.10.3 I risultatiE possibile passare al compilatore alcuni parametri, inizialmente utilizzati per il suodebugging, per ottenere informazioni sui programmi tradotti. Mediante l'opzione`-instr'vengono emesse sullo standard output le istruzioni in sequenza, assieme alrelativo segnale di controllo, mentre specicando `-nodes' si hanno informazioni suinodi e le etichette. In tal modo e possibile costruire i gra ad essi relativi, anche sel'operazione non e automatica, quindi piuttosto laboriosa, e porta, anche per piccoli
10.3. I RISULTATI 119programmi, a strutture intricate e quindi visualizzabili con una certa diÆcolta. Inomi del le VHDL nale sono stati allungati (spesso sono preceduti dal presso`alias_'), per evitare che vi siano con
itti con i nomi utilizzati nei programmiCarpet.Vengono presentate alcune simulazioni relative ad una singola computazione,dal momento che attualmente non sono state eettuate le modiche alla macchinaCAREM per poter montare dei blocchi sequenziali, quindi non e ancora possibileeettuare la simulazione complessiva.10.3.1 Il LifeIl grafo relativo al programma Life viene mostrato in gura 10.4, vista la quantitadi connessioni non sono stati indicati gli insiemi di attivazione, informazione che ecomunque possibile attingere dai dati di debugging.La durata della computazione puoesserevalutata in base al numero delle istruzio-ni che generano una variazione nel 
usso di controllo, cioe considerando il numerodei segnali alias_ctrl_<num> e considerando che, per ogni componente attivatobisogna aggiungere nc +1cicli di clock.Il numero di istruzioni per tale programma e di 113. In gura 10.3 vengonoalias_ctrl_0: set({{const_0->bus_1}{bus_1->alias_stack_reg_1}})...alias_ctrl_6: set({{alias_stack_reg_1->bus_1}{bus_1->i}})alias_ctrl_7: act({{i}})alias_ctrl_8: set_label(___for_statements_label_0)alias_ctrl_8: set({{i->bus_1}{bus_1->alias_stack_reg_1}})alias_ctrl_9: act({{alias_stack_reg_1}})alias_ctrl_10: set({{const_8->bus_1}{bus_1->alias_stack_reg_2}}).... Figura 10.3: Istruzioni Lifemostrate alcune istruzioni in parte coinvolte nel ciclo di calcolo della somma iniziale.Si noti come l'istruzione 8 venga etichettata come l'inizio del ciclo for e come il
10.3. I RISULTATI 120segnale di controllo passi piu volte per essa. In gura 10.5 viene mostrato il trattodi computazione ad esse relative. La simulazione si riferisce al caso in cui una cellaviva in un vicinato di Moore sia circondata da una sola altra cella vivaecosmuoiadi solitudine.10.3.2 L'incendioAnche in questo caso viene dato il grafo ricavato dalle informazioni di etichette,senza specicare gli insiemi di attivazione (g. 10.7). In questa computazione vienefatto rilevare l'eetto di un salto condizionato mediante le istruzioni in gura 10.6.alias_ctrl_150: set({{alias_stack_reg_1->bus_1}})alias_ctrl_151: jz(bus_1,___else_label_1)...alias_ctrl_157: act({{moore_write_buf_var}})alias_ctrl_158: act({{moore_write}})alias_ctrl_159: jmp(___end_if_label_1)alias_ctrl_160: set_label(___else_label_1)alias_ctrl_160: set({{const_8->bus_1}{bus_1->moore_read_buf_dir}})... Figura 10.6: Istruzioni IncendioL'esempio si riferisce ad un albero in amme che, anche se circondato da unincendio, termina la propria combustione.10.3.3 Il ciclo di clock.In ogni grafo di 
usso viene indicato il tempo minimo per il ciclo di clock suggeritodal tool, in seguito al computo del ritardo massimo su tutto il circuito digitale.Come si puo notare si tratta di tempi enormi in rapporto ai componenti utilizzati(accanto ad ognuno viene indicato il ritardo massimo stimato dalla sintesi del singolocomponente e il numero di blocchi logici di base che lo costituiscono), il che fapensare che tale ritardo massimo non sia da cercarsi nella logica di calcolo, quantonella logica di instradamento: si badi al numero di connessioni che giungono al bus1
10.3. I RISULTATI 121e si consideri il gran numero di or relativi ad ogni insieme di attivazione. Sara suquesti elementi che un intervento di ottimizzazione dovra agire.
10.3. I RISULTATI 122
Input
Output+ ==
> < !=
neighread
data
neighwrt
 =13:178nsClb =7  =8:935nsClb =2
 =11:317nsClb =3 =10:781nsClb =3 =7:413nsClb =7
 =13:270nsClb =7
Clb =1539Periodo minimo =396:272ns
#0
x y
z
x y
z
x y
z
x y
z
x y
z
x y
z
#1 #2 #3 #8
i sum
sr1 bus1 bus2
dirvar
data var
sr2
sr3
sr4
bus3
Figura 10.4: Grafo dei dati per il programma Life
10.3. I RISULTATI 123
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
UU
1
0
0
0
0
1
0
0
 
u
s
2
0
0
 
u
s
3
0
0
 
u
s
4
0
0
 
u
s
c
l
k
s
t
a
r
t
e
r
r
o
r
r
e
s
e
t
i
n
p
u
t
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
o
u
t
p
u
t
UU
1
0
0
0
s
t
o
p
a
l
i
a
s
_
c
t
r
l
_
0
a
l
i
a
s
_
c
t
r
l
_
1
a
l
i
a
s
_
c
t
r
l
_
2
a
l
i
a
s
_
c
t
r
l
_
3
a
l
i
a
s
_
c
t
r
l
_
4
a
l
i
a
s
_
c
t
r
l
_
5
a
l
i
a
s
_
c
t
r
l
_
6
a
l
i
a
s
_
c
t
r
l
_
7
a
l
i
a
s
_
c
o
n
t
r
o
l
_
a
g
g
r
e
g
a
t
e
_
0
a
l
i
a
s
_
c
t
r
l
_
8
a
l
i
a
s
_
c
t
r
l
_
9
a
l
i
a
s
_
c
t
r
l
_
1
0
a
l
i
a
s
_
c
t
r
l
_
1
1
a
l
i
a
s
_
c
t
r
l
_
1
2
a
l
i
a
s
_
c
t
r
l
_
1
3
a
l
i
a
s
_
c
t
r
l
_
1
4
a
l
i
a
s
_
c
t
r
l
_
1
5
a
l
i
a
s
_
c
t
r
l
_
1
6
a
l
i
a
s
_
c
t
r
l
_
1
6
_
f
a
l
s
e
a
l
i
a
s
_
c
t
r
l
_
1
7
a
l
i
a
s
_
c
t
r
l
_
1
8
a
l
i
a
s
_
c
t
r
l
_
1
9
a
l
i
a
s
_
c
t
r
l
_
2
0
a
l
i
a
s
_
c
t
r
l
_
2
1
a
l
i
a
s
_
c
t
r
l
_
2
2
a
l
i
a
s
_
c
t
r
l
_
2
3
a
l
i
a
s
_
c
t
r
l
_
2
4
Figura 10.5: Andamento della computazione del componente Life
10.3. I RISULTATI 124
Input
Output&& ==
neighread
data
neighwrtClb =2 =10:035ns Clb =2 =10:403ns
Clb =2 =10:403ns
Clb =4210Periodo minimo =566:238
#0 #1 #2 #3 #4#5 #6 #7 #8
bus1sr1 bus2
sr2
sr3
sr4
x y
z
x y
z
dirvar
data
var
bus3
x y
z
Figura 10.7: Grafo dei dati per il programma dell'Incendio
10.3. I RISULTATI 125
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
U
U
U
1
1
0
0
1
0
0
5
0
 
u
s
1
0
0
 
u
s
1
5
0
 
u
s
2
0
0
 
u
s
c
l
k
s
t
a
r
t
e
r
r
o
r
r
e
s
e
t
i
n
p
u
t
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
o
u
t
p
u
t
U
U
U
1
1
0
0
1
0
s
t
o
p
a
l
i
a
s
_
c
t
r
l
_
1
5
0
a
l
i
a
s
_
c
t
r
l
_
1
5
1
a
l
i
a
s
_
c
t
r
l
_
1
5
1
_
f
a
l
s
e
a
l
i
a
s
_
c
t
r
l
_
1
5
2
a
l
i
a
s
_
c
t
r
l
_
1
5
3
a
l
i
a
s
_
c
t
r
l
_
1
5
4
a
l
i
a
s
_
c
t
r
l
_
1
5
5
a
l
i
a
s
_
c
t
r
l
_
1
5
6
a
l
i
a
s
_
c
t
r
l
_
1
5
7
a
l
i
a
s
_
c
t
r
l
_
1
5
8
a
l
i
a
s
_
c
t
r
l
_
1
5
9
a
l
i
a
s
_
c
t
r
l
_
1
6
0
a
l
i
a
s
_
c
t
r
l
_
1
6
1
a
l
i
a
s
_
c
t
r
l
_
1
6
2
a
l
i
a
s
_
c
t
r
l
_
1
6
3
a
l
i
a
s
_
c
t
r
l
_
1
6
4
a
l
i
a
s
_
c
t
r
l
_
1
6
5
a
l
i
a
s
_
c
t
r
l
_
1
6
6
a
l
i
a
s
_
c
t
r
l
_
1
6
7
a
l
i
a
s
_
c
t
r
l
_
1
6
8
a
l
i
a
s
_
c
t
r
l
_
1
6
9
a
l
i
a
s
_
c
t
r
l
_
1
7
0
a
l
i
a
s
_
c
t
r
l
_
1
7
1
a
l
i
a
s
_
c
t
r
l
_
1
7
2
a
l
i
a
s
_
c
t
r
l
_
1
7
3
a
l
i
a
s
_
c
t
r
l
_
1
7
4
Figura 10.8: Andamento della computazione del componente Incendio