Progettazione di un Sistema Per l'Evoluzione Intrinseca di...

POLITECNICO DI MILANO

FACOLTA DI INGEGNERIA

CORSO DI LAUREA IN INGEGNERIA INFORMATICA

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

PROGETTAZIONE DI UN SISTEMA PERL’EVOLUZIONE INTRINSECA DI CIRCUITI SU

FPGA

Relatore: Prof.ssa Donatella SCIUTO

Correlatore: Ing. Fabio CANCARE

Tesi di Laurea di Primo Livello di:

Davide Basilio BARTOLINI

Matricola n. 701665

Matteo CARMINATI

Matricola n. 700313

ANNO ACCADEMICO 2008-2009

Alle nostre famiglie.

Ringraziamenti

I ringraziamenti, in queste occasioni, finiscono quasi sempre per essere banali e

piuttosto melensi; d’altro canto e giusto e doveroso, oltre che piacevole, ringra-

ziare le persone da cui si e ricevuto qualcosa. Anche se, per indole, sono piuttosto

avaro in quanto a moine e smancerie, so apprezzare l’affetto delle persone che

mi sono vicine. Ci tengo, quindi, a ringraziare qui Giuseppe, mio padre, per il

supporto e la fiducia; Silvana, mia madre, per l’affetto e la pazienza; Giulia, mia

sorella, per essersi prestata (seppur brevemente, ma come biasimarla) alla corre-

zione grammaticale di questo elaborato. Un ringraziamento particolare va a Mat-

teo, che si e provato un vero amico nel sopportarmi durante la collaborazione per

questa tesi. Un grazie per l’affetto va anche agli amici di vecchia data (in partico-

lare a Elisa e Michele) che, occupato nel terminare questo lavoro, ho ultimamente

un po’ trascurato.

Davide

Il primo e il piu sentito grazie va ai miei genitori, Patrizia e Gianmario, che in

ogni istante hanno creduto in me e in ogni momento di difficolta hanno saputo

aiutarmi e spronarmi. Grazie anche a tutto il resto della mia famiglia che mi e sta-

ta vicina nonostante la mia poca disponibilita e reperibilita, soprattutto in questi

ultimi mesi. Un ringraziamento speciale va a Valeria, che e riuscita a sopportar-

mi e supportarmi in tutti questi giorni: la sua comprensione e il suo sorriso mi

hanno permesso di affrontare ogni momento importante con tranquillita e con la

necessaria leggerezza. Un ringraziamento all’amico, compagno di studi e di te-

si, Davide, per la costante simpatia e disponibilita. Grazie anche ai “ragazzi” di

Progetti e ai titolari, che mi offrono una grande occasione di crescita e sono stati

iii

comprensivi in questo periodo piuttosto concitato. Grazie a tutti gli amici (quelli

della ex Quinta B, Dany, gli ex colleghi e colleghe) e a tutte quelle persone che

a modo loro hanno contribuito, anche minimamente, a farmi vivere serenamente

questi primi tre anni universitari.

Matteo

Infine, alcuni ringraziamenti comuni. Per prima cosa un sentito grazie va al Re-

latore, Prof.ssa Donatella Sciuto, e all’Ing. Fabio Cancare, Correlatore e amico,

per la disponibilita, la pazienza e i preziosi consigli e correzioni; ringraziamo an-

che Marco Castagna e Matteo Renesto, che hanno lavorato prima di noi a questo

progetto. Grazie anche a Irene, nonna di Davide, per la simpatia e l’ottimo cibo

offertoci durante la scrittura di questa tesi. Come ultima cosa, ma non per im-

portanza, vorremmo ringraziare i nostri compagni di corso (tra cui, soprattutto,

Davide, per la sua indole ingegneristica; Marco, per la sua indole ben poco inge-

gneristica; Stefania, per essersi sobbarcata la quota di ansia di tutti; Andrea, per

gli spunti origamo-culinar-danzanti), per la simpatia e il divertimento (talvolta alle

loro spalle) che ci hanno offerto in questi tre anni.

Milano, 22 Luglio 2009

Indice

Indice v

1 Introduzione 11.1 Introduzione all’evolvable hardware . . . . . . . . . . . . . . . . 2

1.2 Algoritmi Genetici . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3 Dispositivi riconfigurabili . . . . . . . . . . . . . . . . . . . . . . 7

1.4 Struttura della tesi . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Strumenti 112.1 Field Programmable Gate Array . . . . . . . . . . . . . . . . . . 11

2.1.1 Cenni generali sulla struttura . . . . . . . . . . . . . . . . 11

2.1.2 FPGA utilizzata . . . . . . . . . . . . . . . . . . . . . . . 12

2.2 Architettura utilizzata . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2.1 Struttura generale . . . . . . . . . . . . . . . . . . . . . . 16

2.2.2 HwIcap . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.3 Controller EHW . . . . . . . . . . . . . . . . . . . . . . 21

2.3 Strumenti software per lo sviluppo . . . . . . . . . . . . . . . . . 24

2.3.1 EDK . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.3.2 Altri strumenti software . . . . . . . . . . . . . . . . . . 26

3 Stato dell’arte 293.1 Primi esperimenti con FPGA . . . . . . . . . . . . . . . . . . . . 29

3.2 Evoluzione Hardware su FPGA Virtex-2 e Virtex-2 PRO . . . . . 33

3.2.1 Circuiti Virtuali Riconfigurabili . . . . . . . . . . . . . . 34

v

3.2.2 Manipolazione del bitstream . . . . . . . . . . . . . . . . 37

3.3 Evoluzione hardware su FPGA Virtex-4 . . . . . . . . . . . . . . 43

3.3.1 Analisi del bitstream . . . . . . . . . . . . . . . . . . . . 43

3.3.2 Architettura proposta . . . . . . . . . . . . . . . . . . . . 49

3.3.3 Ulteriori tentativi . . . . . . . . . . . . . . . . . . . . . . 55

4 Sistema Evolutivo 57

4.1 Rappresentazione e strutture dati . . . . . . . . . . . . . . . . . . 57

4.1.1 Popolazioni e individui . . . . . . . . . . . . . . . . . . . 58

4.1.2 Rappresentazione delle celle . . . . . . . . . . . . . . . . 58

4.1.3 Altri tipi di dato . . . . . . . . . . . . . . . . . . . . . . . 60

4.2 Evoluzione ed operatori genetici . . . . . . . . . . . . . . . . . . 60

4.2.1 Popolazione e individui . . . . . . . . . . . . . . . . . . . 60

4.2.2 Elitismo . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.2.3 Mutazione . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.2.4 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . 64

4.3 Controller EHW . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

4.3.1 Utilizzo dell’area riconfigurabile . . . . . . . . . . . . . . 65

4.3.2 Valutazione degli individui . . . . . . . . . . . . . . . . . 66

4.4 Interfaccia HwIcap . . . . . . . . . . . . . . . . . . . . . . . . . 67

4.4.1 Calcolo degli indirizzi . . . . . . . . . . . . . . . . . . . 68

4.4.2 Generazione del bitstream parziale . . . . . . . . . . . . . 68

4.4.3 Riconfigurazione degli individui . . . . . . . . . . . . . . 69

4.4.4 Validazione dei dati . . . . . . . . . . . . . . . . . . . . . 70

5 Risultati Sperimentali 71

5.1 Sintesi dell’architettura . . . . . . . . . . . . . . . . . . . . . . . 71

5.2 Modalita di svolgimento degli esperimenti . . . . . . . . . . . . . 74

5.3 Analisi temporale del ciclo . . . . . . . . . . . . . . . . . . . . . 75

5.4 Evoluzione di un generatore di parita . . . . . . . . . . . . . . . . 76

6 Conclusioni 796.1 Sviluppi futuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

Elenco delle Figure 83

Elenco delle Tabelle 85

Bibliografia 87

Capitolo 1

Introduzione

In questo lavoro di tesi si propone un sistema hardware e software basato su FPGA

capace di realizzare l’evoluzione di circuiti in base ad una specifica comportamen-

tale. Il sistema, realizzato su una FPGA Xilinx Virtex-4, e in grado di operare in

modo autonomo direttamente sul dispositivo embedded, senza necessita di con-

trollo da parte di una workstation esterna durante l’evoluzione. Questa caratteri-

stica e la principale novita introdotta da questa tesi rispetto alle architetture basate

sullo stesso chip presenti in letteratura e apre la strada allo sviluppo di dispositivi

in grado di auto-ripararsi in caso di guasti e di adattarsi in modo autonomo a va-

riazioni dell’ambiente di lavoro.

In questo Capitolo introduttivo vengono proposte alcune nozioni riguardo al filone

di ricerca dello evolvable hardware (Sezione 1.1), all’interno del quale si pone il

lavoro svolto; in seguito, la Sezione 1.2 fornisce una breve introduzione per quan-

to riguarda gli algoritmi genetici e la Sezione 1.3 presenta una visione d’insieme

dei dispositivi riconfigurabili maggiormente utilizzati per la realizzazione di siste-

mi di evoluzione hardware.

Viene proposto, infine, un riassunto per temi principali dei Capitoli che compon-

gono questa tesi (Sezione 1.4).

1

CAPITOLO 1. INTRODUZIONE

1.1 Introduzione all’evolvable hardware

Non e facile definire con precisione il concetto di Hardware Evolvibile. Molti

ricercatori hanno provato a dare delle definizioni piu o meno formali, ma spes-

so contrastanti. In letteratura si possono trovare definizioni piuttosto generiche:

“Per hardware evolvibile si intende uno schema, ispirato dal modello di evoluzio-

ne naturale, per il design automatico di sistemi hardware” [1] ed altre piu precise

e categoriche che distinguono tra hardware evoluto e hardware evolvibile: “Con

il termine hardware evolvibile ci si riferisce ad hardware in grado di cambiare

la propria architettura e il proprio comportamento dinamicamente e in maniera

autonoma interagendo con l’ambiente. Idealmente questo processo di interazione

e cambiamenti dovrebbe essere continuo e durare per tutto il periodo di funzio-

namento del sistema.” [2] e “Il termine hardware evoluto indica un dispositivo

hardware la cui configurazione e stata ottenuta attraverso un processo evoluti-

vo terminato una volta identificata una soluzione ritenuta soddisfacente.” [2].

Se non e fondamentale dare una definizione generica di hardware evolvibile, e

invece importante comprendere le caratteristiche principali che distinguono i va-

ri approcci, in particolare la classificazione del tipo di evoluzione intrinseca ed

estrinseca. La differenza risiede fondamentalmente nel procedimento di valuta-

zione degli individui: nel primo caso le configurazioni candidate vengono valutate

in hardware (implementandole direttamente sul dispositivo a cui sono destinate),

nel secondo invece le configurazioni candidate vengono valutate simulandole tra-

mite strumenti software. La scelta di un’evoluzione di tipo intrinseco permette di

ottenere una valutazione piu accurata che tiene conto anche delle caratteristiche

fisiche del dispositivo utilizzato, cosa che non e possibile fare nel caso di valuta-

zione estrinseca poiche una simulazione dettagliata richiederebbe la costruzione

di un modello computazionalmente troppo complesso. D’altro canto l’evoluzione

intrinseca comporta una notevole perdita di tempo dovuta alla continua necessita

di riconfigurare il dispositivo ed alla difficolta del processo stesso. Con l’evoluzio-

ne estrinseca e necessario riconfigurare il chip solo al termine del ciclo evolutivo

(la valutazione avviene per mezzo di una simulazione esterna, con un notevole ri-

sparmio di tempo), tuttavia e possibile che, a causa delle approssimazioni imposte

2


dalla simulazione, si ottengano dei circuiti che presentano un comportamento non

esattamente coincidente con quello voluto una volta implementati su dispositivi

reali.

Piu intuitivamente si puo pensare all’evoluzione hardware come al naturale pun-

to di incontro tra algoritmi evolutivi e dispositivi riconfigurabili. Gli algoritmi

evolutivi possono essere infatti sfruttati per generare una configurazione ottimale

(rispetto ad un certo compito) di un dispositivo hardware. La Figura 1.1 fornisce

Figura 1.1: Visione ad alto livello di un sistema hardware evolvibile.

uno schema di un generico sistema hardware evolvibile. Tipicamente il processo

evolutivo inizia con la generazione casuale una popolazione di possibili soluzio-

ni, cioe di possibili configurazioni del dispositivo utilizzato. Ognuna di queste

soluzioni, detta individuo, viene processata attraverso una funzione di fitness: ne

viene cioe valutata l’aderenza rispetto ad uno specifico comportamento. E proprio

questa misura di bonta che guida il processo evolutivo attraverso l’applicazione

dei classici operatori genetici, in un processo ciclico che ha come scopo la sele-

zione della soluzione piu aderente possibile alla specifica fornita. La creazione

delle generazioni successive avviene tramite l’utilizzo di una serie di operatori il

3


cui compito fondamentale e quello di rimescolare e mutare il materiale geneti-

co delle soluzioni “genitori”, scelte in modo casuale con probabilita direttamente

proporzionale al loro fitness; viene cosı creata una nuova popolazione che vie-

ne a sua volta sottoposta al ciclo di valutazione. Si puo decidere di arrestare il

processo evolutivo una volta ottenuta una soluzione che soddisfa certi requisiti

(Hardware Evoluto), oppure farlo continuare anche durante il funzionamento del

sistema (Hardware Evolvibile). Nel caso si voglia realizzare un sistema in grado

di proseguire la sua evoluzione anche durante il funzionamento (ad esempio per

recuperare funzionalita in seguito a guasti o per adattarsi a variazioni dell’ambien-

te di lavoro) e necessario adottare un modello di evoluzione intrinseco (rendendo

in una certa misura il dispositivo capace di evolvere in maniera autonoma). Nel

caso di realizzazione di circuiti evoluti si puo invece ricorrere ad un modello evo-

lutivo estrinseco, che non e limitato dalle risorse presenti sul dispositivo utilizzato,

che in genere non e in grado di offrire grande potenza di calcolo.

Una caratteristica molto importante dell’uso di algoritmi evolutivi nell’evoluzione

hardware e che questi sono tipicamente indipendenti dal dispositivo che si intende

far evolvere e non sono in possesso di alcuna informazione sul suo funzionamen-

to (fatto salvo il riscontro fornito dalla funzione di fitness). Quello che viene

fatto evolvere e quindi il comportamento del circuito e non direttamente la sua

struttura. Diventa allora fondamentale la definizione di una funzione di fitness

in grado di promuovere il comportamento migliore al fine di dirigere il processo

evolutivo verso soluzioni ottimali. Ottimali e non ottime proprio perche la con-

figurazione finale non e generalmente la migliore possibile, ma rappresenta un

buon compromesso tra tempo di ricerca e qualita. Inoltre, nel caso particolare

di evoluzione on-line (cioe in cui il processo evolutivo continua anche durante il

funzionamento del sistema) vengono garantite proprieta di resistenza ai guasti e

di adattamento ai cambiamenti dell’ambiente, caratteristiche che sono raramente

presenti in architetture sviluppate con tecniche classiche. Appurati i vantaggi, si

deve considerare anche una caratteristica negativa di questo approccio: il risultato

del processo evolutivo risulta spesso di difficile interpretazione e analisi, proprio

perche l’evoluzione sfrutta particolarita trascurate durante la fase di modellazione

4


dell’architettura. Nonostante il campo degli algoritmi evolutivi sia piuttosto am-

pio, ci si sofferma ora sulla descrizione della terminologia e della teoria alla base

degli algoritmi genetici, di cui si e fatto uso nello sviluppo di questo sistema.

1.2 Algoritmi Genetici

John Holland [3] fu il primo ad introdurre il concetto di Algoritmo Genetico (AG),

prendendo spunto per la terminologia e per i meccanismi evolutivi dal mondo de-

gli esseri viventi. Da un punto di vista biologico, le caratteristiche peculiari di

ogni essere vivente sono contenute nel suo DNA, raggruppato in cromosomi il cui

contenuto varia da individuo a individuo. L’insieme di tutti i cromosomi, cioe di

tutto il materiale genetico di un individuo, e detto genoma. Il genoma di un indi-

viduo, cioe il suo profilo genetico, caratterizza il genotipo dell’individuo stesso.

A suo volta il genotipo, manifestandosi fisicamente, da origine al fenotipo, ovvero

alle caratteristiche fisiche e comportamentali dell’individuo. Durante la creazio-

ne di un nuovo individuo (ad esempio nella riproduzione sessuata negli uomini),

il figlio si presenta come una ricombinazione del materiale genetico dei genitori:

questo meccanismo prende il nome di crossing over (o crossover). Inoltre i nuovi

individui vanno talvolta incontro ad un processo di mutazione durante il quale i

mattoncini elementari del DNA vengono modificati rispetto a quelli originari dei

genitori. Tali cambiamenti sono spesso frutto di errori di copia, ma possono dare

origine a dei vantaggi per l’individuo che li subisce: sara la selezione naturale

(che viene rappresentata dalla valutazione del fitness) a valutare la bonta di queste

modifiche in relazione all’ambiente in cui l’individuo vive (al compito che deve

svolgere).

In ambito informatico, gli algoritmi genetici sono delle tecniche di ottimizzazio-

ne stocastica che si basano sul concetto di popolazione, in cui il ruolo del DNA

viene svolto dalla codifica scelta per le soluzioni candidate per un certo problema.

Allo stesso modo il crossover non e altro che la creazione di un nuovo individuo

utilizzando delle parti del codice binario che rappresenta il genotipo dei genitori,

mentre la mutazione consiste semplicemente nell’inversione di uno o piu bit del-

5


l’individuo.

L’ Algoritmo 1, di seguito rappresentato, ricalca in pseudocodice la struttura di

un algoritmo genetico standard. Tipicamente viene mantenuta in memoria l’at-

Algoritmo 1 Algoritmo Genetico Standard1: t← 0

2: InizializzazioneCasuale(P(t))

3: Valutazione(P(t))

4: while not Terminazione(P(t)) do5: t← t +1

6: P(t)← Selezione(P(t−1))

7: Crossover(P(t))

8: Mutazione(P(t))

9: Valutazione(P(t))

10: end while11: return P(t)

tuale popolazione di individui (soluzioni candidate) e ad ogni iterazione del ciclo

viene creata una nuova generazione, originata dall’evoluzione della popolazione

precedente (negli algoritmi genetici standard la cardinalita delle popolazioni e co-

stante). In particolare, durante ciascuna iterazione, ogni individuo della nuova

popolazione viene generato a partire dagli individui della generazione precedente

tramite l’uso degli operatori gia accennati (mutazione e crossover) e quindi valu-

tato. L’operatore di crossing over e utilizzato, in concomitanza con gli altri due,

per realizzare la fusione del materiale genetico: ricevuti in ingresso i genotipi dei

due individui vengono prodotti in uscita due figli, ottenuti ricombinando il ma-

teriale genetico dei genitori. Per questo operatore l’implementazione tipica, ma

non l’unica possibile, e quella chiamata a punto singolo: viene scelto casualmen-

te un punto che individua il punto di taglio dei cromosomi genitori. L’operatore

di crossover viene applicato con una certa probabilita p: cio significa che con

probabilita (1− p) i figli saranno identici ai genitori. L’operatore di mutazione

si limita invece a inserire delle modifiche casuali all’interno degli individui della

6


nuova generazione, a partire da individui scelti casualmente tra quelli della ge-

nerazione precedente; anch’esso si applica con una certa probabilita p ad ogni

bit. La probabilita di riproduzione dell’individuo cosı generato dipende dal suo

fitness e da quello degli individui della sua generazione: gli individui con fitness

piu alto avranno probabilita piu elevata di riprodursi. E inoltre possibile utilizzare

un operatore di elitismo, che permette di trasportare, senza alcuna modifica, nella

nuova generazione una certa percentuale dei candidati migliori della generazione

precedente. Questi meccanismi assicurano la proliferazione di soluzioni ottimali

e l’aumento del fitness medio tra gli individui.

Gli algoritmi genetici si sono dimostrati particolarmente adatti alla risoluzione di

problemi caratterizzati da un grande numero di parametri e con funzioni obiettivo

che presentano molti punti di minimo (o massimo) locali. Esempio di tali fun-

zioni sono proprio le funzioni di fitness per la valutazione del comportamento dei

circuiti da evolvere. Queste caratteristiche hanno fatto sı che in molti esperimenti

svolti nel campo dello hardware evolvibile ci si sia basati proprio sugli algoritmi

genetici.

1.3 Dispositivi riconfigurabili

La gamma di dispositivi hardware riconfigurabili presenti in commercio e piut-

tosto ampia. Affinche essi siano adatti ad ospitare un processo evolutivo e pero

necessario che godano di alcune fondamentali proprieta: flessibilita e rapidita di

riconfigurazione (soprattutto se si intende implementare un processo di evoluzio-

ne intrinseca, come descritto nella Sezione 1.1), riconfigurabilita parziale (per

limitare ulteriormente i tempi di riconfigurazione) e auto-riconfigurazione (carat-

teristica necessaria nel caso si voglia realizzare un System-On-Chip in grado di

implementare autonomamente il processo evolutivo).

Una prima grossa distinzione tra i dispositivi sfruttati per evoluzione hardware e

quella tra dispositivi digitali (in primis Field Programmable Gate Array, o FPGA),

analogici (ad esempio Field Programable Analogue Array, o FPAA), dispositivi

misti analogico/digitali (come FIPSOC [4] o l’Evolvable Motherboard [5]) e altri

7


dispositivi “non convenzionali”, utilizzati per l’evoluzione In Materio [6, 7, 8].

I primi esperimenti effettuati nel campo dello hardware evolvibile (Sezione 3.1)

sono stati svolti utilizzando come supporto delle FPGA e la maggior parte degli

studi in quest’ambito continuano a sfruttare prevalentemente questa categoria di

dispositivi. I motivi di questo vasto utilizzo di sistemi digitali va ricercato nella

loro facile reperibilita sul mercato (si tratta di dispositivi commerciali), nella loro

vasta dotazione di risorse riconfigurabili a bordo e nella loro architettura general

purpose. Tuttavia, secondo molti ricercatori, questa grande flessibilita limiterebbe

le performance ottenibili con questi dispositivi: sono quindi stati proposti anche

approcci alternativi non realizzabili utilizzando FPGA convenzionali.

Tenuti in considerazione tutti gli svantaggi (che nel caso specifico non sembra-

no essere particolarmente rilevanti e soprattutto non sembrano inficiare il lavoro

svolto) e i vantaggi appena esposti, si e deciso di sviluppare questo lavoro di te-

si utilizzando come supporto hardware un dispositivo digitale, in particolare una

FPGA della famiglia delle Virtex-4 [9].

1.4 Struttura della tesi

Nel Capitolo 2, dedicato agli Strumenti, vengono elencati e descritti tutti i dispo-

sitivi hardware e software che sono stati utilizzati nel corso del lavoro qui esposto.

Vengono dapprima introdotte le caratteristiche generali del dispositivo hardware

su cui e stato svolto il progetto (la FPGA) e gli specifici componenti dell’archi-

tettura alla base del sistema evolutivo (interfaccia HwIcap e Controller EHW).

Vengono infine presentati gli strumenti software utilizzati per lo sviluppo, l’im-

plementazione e i test (EDK [10], iMPACT [11], FPGA Editor [12]).

Segue il Capitolo 3, dedicato allo stato dei lavori di ricerca fin qui svolti nel cam-

po dell’hardware evolvibile. L’area di ricerca incentrata sull’hardware evolvibile

e un settore ancora relativamente giovane, ma esistono gia in letteratura numero-

si articoli scientifici ad essa dedicati (ad esempio, per una introduzione pratica,

si veda [2]). Si e quindi cercato di esporre in modo piuttosto sintetico, ma al-

lo stesso tempo completo, gli approcci sin qui documentati, a partire dai primi

8


esperimenti di Thompson basati su FPGA Xilinx XC6200, passando per i sistemi

che utilizzano FPGA Virtex-2 e Virtex-2 PRO (Circuiti Virtuali Riconfigurabili e

manipolazione diretta del bitstream), fino agli ultimi esperimenti con le Virtex-4.

Tra questi, a conclusione del Capitolo, viene introdotto il lavoro esposto in [13]

nell’ambito della riconfigurazione dinamica su Virtex-4: in particolare l’analisi

del formato del bitstream (non documentato da Xilinx, societa produttrice della

scheda) e lo sviluppo di un’architettura adatta all’implementazione di un sistema

evolutivo.

Il Capitolo 4, e dedicato piu dettagliatamente alla descrizione del sistema svilup-

pato per far evolvere circuiti logici su FPGA. Innanzitutto viene esposto l’algo-

ritmo genetico, in particolare le strutture dati scelte e gli operatori utilizzati nel

corso del ciclo evolutivo. Viene poi fornita una descrizione di come e stato possi-

bile interfacciarsi con l’HwIcap, per la riconfigurazione parziale del dispositivo, e

con il Controller EHW, per l’interazione con gli individui allocati sulla FPGA.

Alcuni esperimenti svolti sul sistema descritto nei Capitoli precedenti sono esposti

nel Capitolo 5, in cui vengono presentati nei dettagli i risultati ottenuti effettuan-

do alcuni cicli di test sulla FPGA su cui e stata istanziata l’architettura sviluppata.

Viene anche proposto un confronto con i risultati ottenuti da una architettura simi-

le, basata pero su evoluzione estrinseca (ovvero simulata); e cosı possibile valutare

i reali vantaggi ottenibili grazie alle caratteristiche innovative del sistema proget-

tato.

Il documento si conclude con il Capitolo 6, in cui si sintetizzano i punti notevoli

dei Capitoli precedenti. La ricerca nel campo dell’hardware evolvibile e ancora

agli inizi e rimangono molti aspetti da analizzare e molte direzioni in cui spin-

gere la ricerca; al termine vengono quindi proposti dei possibili sviluppi futuri e

accennati degli spunti di ulteriore approfondimento sull’argomento.

9


10

Capitolo 2

Strumenti

In questo capitolo vengono presentate le caratteristiche generali degli strumenti

hardware e software utilizzati. In particolare, nella Sezione 2.1, vengono presen-

tate la struttura generale di una FPGA e alcune caratteristiche tecniche del partico-

lare chip utilizzato. Nella Sezione 2.2 viene esposta l’architettura utilizzata per il

sistema evolutivo, presentando le caratteristiche dei vari componenti. Infine, nella

Sezione 2.3 si tratta degli strumenti software usati per lo sviluppo, in particolare

EDK (Sottosezione 2.3.1).

2.1 Field Programmable Gate Array

2.1.1 Cenni generali sulla struttura

Una FPGA (o Field Programmable Gate Array) e un dispositivo elettronico ca-

ratterizzato dalla presenza al suo interno di componenti logici e connessioni pro-

grammabili. In particolare i circuiti interni possono essere riprogrammati, tramite

una opportuna stringa di bit (o bitstream) di configurazione, in modo da imple-

mentare i principali dispositivi logici noti, sia combinatori (porte logiche AND,

OR e anche funzione piu complesse) che sequenziali (flip-flop o altri circuiti piu

complessi). Anche le connessioni tra i vari blocchi possono essere programma-

te, in modo da ottenere il routing desiderato per i segnali. La struttura interna di

una FPGA (Figura 2.1) e tipicamente composta da una matrice regolare di blocchi

11

CAPITOLO 2. STRUMENTI

Figura 2.1: Organizzazione interna di una FPGA.

riconfigurabili, o CLB (Configurable Logic Blocks), dei quali quelli sul contor-

no della matrice si occupano anche di gestire i segnali di Input/Output. I CLB

costituiscono l’unita base configurabile e sono collegati tra loro tramite una re-

te anch’essa configurabile secondo le necessita dell’utente; ogni CLB puo essere

programmato in modo da implementare uno qualsiasi tra i circuiti (combinatori

o sequenziali) supportati dalla FPGA. Internamente ogni CLB e formato da (tipi-

camente 4) slice e ogni slice puo contenere a sua volta diversi componenti logici

(come multiplexer, bistabili o altro) a seconda del modello di FPGA considerato.

Tipicamente all’interno delle slice sono present delle LUT (Look Up Tables); una

LUT opera come una funzione logica che, avendo N bit in ingresso, permette di

assegnare un valore all’unica uscita binaria per ciascuna delle 2N possibili confi-

gurazioni degli ingressi. Una rappresentazione fedele di una LUT e una tabella

con 2N righe e N + 1 colonne (N per gli ingressi e una per l’uscita).

2.1.2 FPGA utilizzata

Lo sviluppo del sistema evolutivo proposto si e basato sul design architetturale

proposto da Marco Castagna in [13], progettato per una FPGA Xilinx Virtex-4.

12


In particolare la board utilizzata e una Evaluation Platform della Xilinx, modello

ML403, equipaggiata con un chip XC4VFX12-FF668-10.

Evaluation board

La scheda utilizzata per l’implementazione dell’architettura e lo svolgimento dei

test di evoluzione e della famiglia ML40x Evaluation Board, presente nel labo-

ratorio di microarchitetture. Come si puo leggere nella guida per l’utente della

Xilinx [14], pur non essendo una board di alto livello, la ML403 offre, oltre alla

logica di controllo per il chip della FPGA, svariate possibilita di connessione; tra

queste quelle maggiormente sfruttate durante questo lavoro sono:

• La porta seriale RS-232, utilizzata per la visualizzazione dell’output su

terminale seriale con Baud-Rate di 9600Bps.

• La porta di configurazione JTAG, utilizzata con l’apposito cavo USB per

configurare il chip con l’architettura utilizzata, per caricare in memoria il

software da eseguire e per controllare l’avvio e l’interruzione dell’esecuzio-

ne da parte del processore.

Caratteristiche tecniche del chip

Il chip di cui dispone la scheda utilizzata offre tutti i vantaggi introdotti dalla fa-

miglia Virtex-4 ed e costruito con un processo produttivo a 90nm.

Alcuni esempi delle potenzialita del chip sono la disponibilita di BRAM con fre-

quenza di funzionamento di 500MHz, l’integrazione di un processore PowerPC

405 con frequenza di clock massima di 300MHz e il ridotto consumo di potenza

rispetto alle generazioni precedenti. Il chip supporta inoltre una grande quantita

di interfacce di I/O (Ethernet, RGB, audio, . . . ), solo alcune delle quali (elencate

poco sopra) sono state realmente utilizzate ai fini della creazione del framework

evolutivo.

Da un punto di vista architetturale, il chip si presenta come una classica matrice

di CLB di dimensioni 64X24, ogni CLB contiene 4 slice e ogni slice e compo-

sta di due LUT (dette LUTF e LUTG) e di alcuni altri componenti logici, come

13


bistabili e multiplexer; la Tabella 2.1 elenca le risorse configurabili presenti sulla

Virtex-4 utilizzata. Le quattro slice di ogni CLB sono raggruppate in due colonne

Tabella 2.1: Risorse disponibili sulla FPGA XC4VFX12-FF668-10.

Matrice di CLB slice LUT

64X24 5472 10944

e vengono distinte in SLICEM (quelle appartenenti alla colonna sinistra di ogni

CLB) e SLICEL (appartenenti alla colonna di destra); le differenze tra i due tipi

di slice non sono interessanti ai fini dell’architettura evolutiva, che utilizza com-

ponenti presenti in entrambi. Uno schema della struttura di un CLB presente sul

chip e visibile in Figura 2.3. Ogni CLB e connesso a quelli adiacenti per mezzo

di interconnessioni locali e puo accedere alle risorse globali della FPGA tramite

il collegamento ad una switch matrix; sono inoltre presenti dei data path inter-

ni ai blocchi che permettono, utilizzando dei multiplexer disponibili all’interno

delle slice, di combinare fino a 16 LUT (appartenenti a due CLB) per realizzare

funzioni a 8 ingressi.

Indirizzamento delle risorse

Per l’identificazione delle risorse la Xilinx propone nei suoi tool uno spazio di

indirizzamento per ogni tipologia di componente (CLB, slice, . . . ). Per ogni com-

ponente che appartiene ad uno schema di numerazione vengono definite due coor-

dinate (X, Y) che ne indicano la posizione all’interno della matrice; in particolare

(come si puo vedere in Figura 2.2) il componente con coordinate (X, Y) = (0, 0) si

trova in basso a sinistra. La Figura 2.3 mostra la struttura interna (descritta poco

sopra) riferita al CLB con coordinate (0, 0); si possono notare le quattro slice,

divise per colonne e le connessioni locali e verso la switch matrix. Una cosa da

tener presente e, che per quanto riguarda la riconfigurazione, viene utilizzato uno

spazio di indirizzamento diverso da quello basato su (X, Y) e appena esposto. Esi-

ste chiaramente un isomorfismo tra i diversi spazi di indirizzamento e la biiezione

tra i due e nota grazie al lavoro di analisi svolto in [13], che verra esposto nella

Sezione 3.3.

14


Figura 2.2: Collocazione delle risorse di un certo spazio di indirizzamento in dipendenza

dalle coordinate (X, Y).

Configurazione e riconfigurazione

Tutte le risorse della FPGA programmabili da parte dell’utente vengono configu-

rate per mezzo di una memoria volatile che viene scritta all’accensione del dispo-

sitivo o quando si procede ad una riconfigurazione. Questa memoria di configu-

razione e costituita da celle che definiscono le funzioni implementate dalle LUT,

il routing dei segnali (ovvero la topologia delle connessioni) e ogni altro aspetto

del design creato dall’utente. Per la scrittura della memoria di configurazione si

fa uso di una serie di comandi e istruzioni che, insieme ai dati da scrivere in me-

moria, costituiscono il bitstream di configurazione della FPGA. Diverse interfacce

(JTAG, SelectMAP o Slave/Master Serial) possono essere utilizzate per inviare il

bitstream alla scheda; in particolare, durante questo lavoro, e stata utilizzata l’in-

terfaccia JTAG con l’apposito cavo USB. Per la riconfigurazione e stata invece

utilizzata l’interfaccia HwIcap, che opera da controllore per la porta denominata

ICAP (ovvero Internal Configuration Access Port). La struttura del bitstream di

15


Figura 2.3: Struttura interna del CLB con coordinate (X, Y) = (0, 0) delle FPGA della

famiglia Xilinx Virtex-4.

configurazione per la Virtex-4, studiata sempre in [13], e esposta nella Sezione 3.3,

a cui si rimanda per maggior dettaglio.

2.2 Architettura utilizzata

2.2.1 Struttura generale

L’architettura su cui ci si e basati (sviluppata all’interno del gruppo di ricerca

HERA, ovvero Hardware Evolution over Reconfigurable Architecture) cerca di

coniugare le prime prove effettuate da Marco Castagna [13] con il lavoro di ri-

cerca svolto successivamente da Matteo Renesto [15]. I componenti fondamentali

che caratterizzano il sistema proposto sono gli stessi utilizzati nell’architettura

originaria. Gli individui soggetti al processo evolutivo sono ubicati in una regio-

ne riconfigurabile e la loro riconfigurazione avviene per mezzo dell’interfaccia

HwIcap (si rimanda alla Sottosezione 2.2.2 per ulteriori dettagli). L’interfaccia

16


tra l’applicazione (che viene eseguita sul PowerPC presente sulla scheda) e l’area

evolvibile e fornita dal Controller EHW (Evolvable HardWare). La comunica-

zione tra i vari componenti e garantita dalla presenza di un bus PLB al quale

i componenti stessi sono opportunamente connessi. In Figura 2.4 si puo vede-

re una rappresentazione grafica dell’architettura qui presentata. Se l’architettura

Figura 2.4: Schema a blocchi dell’architettura HERA.

proposta in [13] permetteva di far evolvere solo un individuo per volta, quella qui

presentata garantisce la possibilita di mantenere fino a 16 (utilizzando FPGA piu

capienti anche fino a 32) individui contemporaneamente sulla scheda e permette

quindi di riconfigurare un individuo mentre si valutano gli altri. Cio rappresenta

un notevole vantaggio dal punto di vista del tempo necessario per la convergenza

dell’algoritmo evolutivo (il tempo di riconfigurazione e un serio collo di bottiglia

alle prestazioni in termini di velocita) e garantisce il conseguimento di un risultato

ottimale in tempi piu brevi. Tale miglioramento e stato possibile grazie all’utilizzo

della versione 4.0 del Controller EHW, la cui struttura e proposta in [15].

Sono proprio questi due componenti, l’interfaccia HwIcap e il Controller EHW,

17


a caratterizzare l’architettura utilizzata e la loro trattazione verra quindi ulterior-

mente approfondita.

2.2.2 HwIcap

Il controller HwIcap e un componente disponibile sulla Virtex-4 ed e istanziabi-

le sulla FPGA come un IP-CORE disponibile nelle librerie messe a disposizione

dalla Xilinx nella categoria FPGA Reconfiguration. Esso infatti permette al pro-

cessore presente sulla scheda di leggere e scrivere la memoria di configurazione

della FPGA a run-time attraverso la porta di accesso alla configurazione interna

(Internal Configuration Access Port o ICAP); l’utente puo quindi scrivere pro-

grammi che modificano la struttura e le funzionalita della logica implementata

mentre questa e in funzione. L’HwIcap offre l’interfaccia necessaria a trasferire

bitstream alla e dalla porta ICAP e un insieme di funzioni per il controllo dello

stato della configurazione delle risorse sulla FPGA.

Piu nei dettagli l’interfaccia si compone di una memoria di scrittura FIFO, nella

quale sono memorizzate le configurazioni e dalla quale il processore legge per tra-

sferire i dati all’ICAP, e da una memoria di lettura (sempre FIFO), dove vengono

salvate le configurazioni lette dalla scheda tramite l’ICAP. Dei dieci registri inter-

ni che costituiscono il componente e opportuno citare, oltre al Write FIFO (WF)

e al Read FIFO (RF) i seguenti:

• Size Register (SR): contiene il numero di parole da 32 bit che devono essere

trasferite dall’ICAP alla memoria di lettura.

• Control Register (CR): determina la direzione del flusso di dati attraverso

due bit che, se scritti, attivano rispettivamente il processo di scrittura e let-

tura dalla scheda. Permette inoltre, attraverso altri due bit, di fare un clear

delle memorie FIFO e di resettare tutti i registri del componente.

• Status Register (SR): controlla lo stato del processo di lettura/scrittura, evi-

denziando eventuali errori di configurazione o disallineamento di dati. Al

suo interno e presente un bit, denominato bit Done, che viene portato a 1

18


ogni volta che la configurazione o la lettura sono stati portati a termine con

successo.

La Figura 2.5 schematizza quanto appena appuntato, fornendo una rappresenta-

zione schematica della struttura del modulo HwIcap. Il controllo dell’HwIcap a

Figura 2.5: Diagramma a blocchi della struttura del modulo HwIcap (fonte: [16])

livello software puo avvenire in due modi sostanzialmente differenti. Il primo

metodo, piu semplice e effettivamente utilizzato nel lavoro di implementazione

(Sezione 4.4), sfrutta le funzioni di lettura e scrittura messe a disposizione dalle

librerie Xilinx. A basso livello esso si compone di tre semplici passi:

• Selezione dell’azione da eseguire tramite scrittura nel registro di controllo:

– Scrivendo 0x00000001 nel CR si da inizio alla scrittura.

– Scrivendo 0x00000000 nel CR si fa partire la lettura.

• Scrittura del bitstream di configurazione nel registro Write FIFO o lettura

del bitstream dal registro Read FIFO.

• Controllo dello stato della lettura o della configurazione tramite lo Status

Register.

19


Nelle Figure 2.6 e 2.7 si puo vedere l’andamento temporale dei vari segnali du-

rante le operazioni di lettura e scrittura tramite la porta ICAP.

Figura 2.6: Grafico temporale dei segnali durante un ciclo di lettura (fonte: [16])

Figura 2.7: Grafico temporale dei segnali durante un ciclo di scrittura (fonte: [16])

Il secondo metodo, piu complesso, permette una gestione migliore e piu ot-

timizzata delle operazioni sfruttando gli interrupt. I segnali di interrupt generati

dall’HwIcap sono gestiti dall’ISC (Interrupt Service Controller), che offre anche

la maggior parte delle piu comuni funzionalita per la gestione degli stessi. L’abi-

litazione o meno del servizio di interrupt e affidata al primo bit del registro GIE

(Global Interrupt Enable Register). L’HwIcap e in grado di generare diversi se-

gnali di interrupt da inviare alla CPU a seconda dei bit abilitati nell’IP Interrupt

Status Register (IPISR). I tipi di interrupt possibili sono quattro e possono essere

generati nei seguenti casi:

• Se la memoria di lettura FIFO e piena.

• Se la memoria di scrittura FIFO e vuota.

• Se la dimensione della parte occupata di memoria Read FIFO e maggiore

della meta delle dimensioni della memoria stessa.

20


• Se la dimensione della parte occupata di memoria Write FIFO e maggiore

della meta delle dimensioni della memoria stessa.

Un terzo registro, IP Interrupt Enable Register (IPIER), permette di specificare,

tipo per tipo, quali interrupt si vogliono abilitare e quali si vuole restino disabili-

tati.

2.2.3 Controller EHW

Oltre all’interfaccia HwIcap l’altro modulo di rilievo dell’architettura e costitui-

to dal Controller EHW. Questo componente si occupa di gestire l’area riconfi-

gurabile dedicata agli individui in evoluzione fornendo la logica di controllo e i

collegamenti al PowerPC tramite bus PLB. La versione di riferimento per questa

trattazione e la 4.0, che rappresenta uno sviluppo (realizzato da Matteo Renesto

[15]) del componente originalmente sviluppato da Marco Castagna [13].

Area riconfigurabile

Nell’architettura HERA l’area della FPGA e divisa in due Sezioni: una parte sta-

tica che contiene il PowerPC, la BRAM e parte della logica di controllo (colonne

di sinistra della matrice) e una zona riconfigurabile, che viene gestita dal Con-

troller EHW e contiene le soluzioni candidate dell’algoritmo genetico (colonne di

destra). Nelle prime versioni (in particolare nel Controller EHW proposto in [13])

l’area riconfigurabile offre spazio per istanziare, in un dato istante, un solo indivi-

duo, che occupa una colonna di 32 slice (indifferentemente SLICEM o SLICEL)

ed e definito da una Hard Macro; la descrizione dettagliata della struttura dell’in-

dividuo si puo trovare nel Capitolo 3. La struttura degli individui e stata mantenuta

nei successivi sviluppi ed e la medesima che viene utilizzata dal sistema evolutivo

sviluppato in questo lavoro di tesi. La possibilita di allocare individui nell’area

riconfigurabile, invece, si e notevolmente ampliata nelle successive versioni del

componente (Figura 2.8), permettendo di allocare, nella versione 4.0, un massi-

mo di 32 individui contemporaneamente nell’area riconfigurabile. Per avere la

possibilita di istanziare piu di un individuo nell’area riconfigurabile e stato inse-

21


Figura 2.8: Confronto tra la vecchia (sinistra) e la nuova (destra) area riconfigurabile con

Management Logic.

rito un layer di controllo, denominato Management Logic, che redireziona i dati

in ingresso verso l’individuo selezionato e raccoglie i dati di output rendendoli

disponibili al PowerPC sul bus PLB.

Management Logic

Osservando il modulo della Management Logic da un punto di vista esterno (ov-

vero come una scatola nera, come illustrato in Figura 2.9) si hanno i seguenti

segnali in ingresso:

• Input Data: e un segnale di 32 bit che viene trasportato in ingresso all’indivi-

duo selezionato. Utilizzando gli individui definiti dalla Hard Macro sopra-

citata solo gli ultimi 8 bit sono realmente utilizzati ponendoli sul datapath

in ingresso all’individuo.

• Ehw Unit Address: e un segnale di 8 bit che serve per selezionare uno

specifico individuo. Vista la dimensione del segnale, il numero massimo

teorico di individui indirizzabili e pari a 28 = 256.

• Ehw Control: e un segnale di controllo utilizzato per notificare quando l’ap-

plicazione seleziona un nuovo individuo e sara quindi necessario avviare la

22


Figura 2.9: Management Logic Black Box

computazione con i dati in ingresso o quando i dati sono pronti sui registri

dell’individuo e il calcolo dell’output deve iniziare.

In uscita dalla Management Logic ci sono invece i seguenti segnali:

• Output Data: e un segnale a 32 bit che contiene l’output fornito dall’indivi-

duo selezionato. In particolare, per gli individui utilizzati, gli 8 bit di output

sono i meno significativi dei 32 e i restanti 24 sono utilizzati come bit di

verifica.

• Ehw Unit Address: e un segnale a 8 bit, analogo a quello omonimo in in-

gresso. Contiene l’indirizzo dell’ultima unita che ha terminato il calcolo

dell’uscita.

• Ehw Final State: il bit piu importante di questo segnale e l’ultimo, utilizzato

come bit di validita. Quando l’ultimo bit e a 1 significa che il contenuto

dell’Output Data e realmente il risultato in uscita dall’individuo, quando e

a 0 significa che il valore di output non e ancora stabile.

Generazione dinamica delle specifiche VHDL

Per rendere il componente comodo da utilizzare con diverse configurazioni dell’a-

rea evolvibile e stato creato uno script Python che e in grado di generare, partendo

23


da dei file VHDL di base, tutte le specifiche necessarie per implementare l’IP-

CORE utilizzando un tool come EDK. Lo script funziona leggendo le informazio-

ni di base da alcuni file VHDL predefiniti e chiedendo all’utente quanti individui

intende istanziare nell’area riconfigurabile. L’output fornito dallo script e costi-

tuito da dei file VHDL che contengono la specifica per tutta la Management Logic

e da un file UCF che contiene i vincoli di area, specifici per questo componente,

da applicare all’architettura in fase di sintesi con EDK.

2.3 Strumenti software per lo sviluppo

2.3.1 EDK

L’ambiente di sviluppo scelto e EDK [10]. EDK, acronimo di Embedded Develo-

pement Kit, e stato utilizzato sia per implementare, sintetizzare, e caricare su sche-

da l’architettura hardware, che per progettare e sviluppare l’algoritmo genetico e

la comunicazione con la board. Questo strumento integra, infatti, un’interfaccia

per la creazione del design hardware e un editor per la scrittura di applicazioni da

far girare sul processore. EDK presenta una perfetta compatibilita con la scheda

utilizzata: il software e infatti fornito da Xilinx, societa produttrice della Virtex-4.

La versione utilizzata e la 9.2 (opportunamente aggiornata con l’ultimo service-

pack e la patch per l’abilitazione della riconfigurazione dinamica).

Il Base System Builder wizard, che viene presentato appena lanciato il software,

permette di creare una semplice architettura di base. Innanzitutto e necessario

selezionare una evaluation board equipaggiata con una FPGA Xilinx, il proces-

sore da utilizzare (PowerPC o MicroBlaze), le dimensioni e i tipi di memoria di

cui si vuole fare uso (Sdram, bram) e, se necessario, ogni altro componente uti-

le di cui la scheda e dotata; e possibile connettere, in un momento successivo,

ulteriori componenti al processore attraverso i bus di comunicazione presenti nel-

l’architettura. I componenti possono essere scelti tra una vasta libreria proposta

da Xilinx (l’HwIcap, utilizzato per la riconfigurazione parziale, ne rappresenta un

esempio), oppure creati ad hoc e quindi importati nel sistema (cosa che e stata fat-

24


ta per il Controller EHW). Di seguito si elencano in breve i comandi da eseguire

per provvedere, dopo aver dato le specifiche per l’architettura da sintetizzare, alla

creazione e al caricamento del file di configurazione per la FPGA.

• Libgen: a partire dal file MSS (Microprocessor Software Specification)

genera e configura in automatico le librerie ed i driver dei dispositivi per

l’architettura.

• Generate Netlist: crea una rete logica di porte e interconnessioni (la netlist),

mediante l’utilizzo dello strumento di sintesi Xst. Il risultato e un file NGD

(Native Generic Database) che contiene tutte le informazioni sul progetto e

sui suoi componenti.

• Generate Bitstream: genera il file di configurazione da caricare sulla FPGA.

• Compile Sources: si occupa della compilazione dei file che contengono il

codice che dovra essere eseguito dal processore.

• Update Bitstream: si occupa dell’inizializzazione della memoria delle istru-

zioni sulla FPGA.

• Download: carica il design prodotto sulla FPGA.

Tutti questi passi vengono eseguiti in maniera automatica dall’ambiente di svi-

luppo e portano alla configurazione del chip con un file binario prodotto a partire

dalle specifiche del design fornite a EDK.

Come accennato in precedenza, EDK offre anche un ambiente di sviluppo per

applicazioni software da far girare sul processore della FPGA. Due applicazioni

in linguaggio C vengono automaticamente create una volta completata la sinte-

si dello hardware: una per il test dell’architettura appena generata e una per il

test della memoria, entrambe personalizzabili a piacere. Ulteriori applicazioni

possono ovviamente essere create successivamente direttamente nell’ambiente di

sviluppo principale (Xps [10]) o utilizzando una versione modificata di Eclipse

(xps sdk [10]), orientata piu specificatamente alla programmazione (in linguag-

gio C) di software per il processore incluso nel chip della FPGA. La compilazione

25


dei sorgenti porta alla generazione di un file eseguibile dal processore (*.elf ). Una

sola delle applicazioni presenti puo essere contrassegnata per essere inizializzata

sulla bram. Nel caso le dimensioni del file .elf siano eccessive e tale file non pos-

sa essere contenuto nella bram, l’eseguibile deve essere scaricato manualmente in

una memoria piu capiente, tramite una console XMD. Per svolgere tale operazione

e sufficiente digitare alcuni semplici comandi in una shell XMD:

• Connect ppc hw: permette di connettersi al processore (un PowerPC nel

nostro caso).

• Dow elfName.elf: effettua il download dell’eseguibile nella DDRram.

• Run/stop: rispettivamente per lanciare e fermare l’esecuzione del program-

ma.

Ambienti operativi utilizzati

Vista la disponibilita dei software sviluppati dalla Xilinx sia per ambiente Win-

dows che per ambiente *nix, e stato possibile utilizzare EDK anche su Linux (in

particolare su una distribuzione Gentoo installata su un portatile con architettura

x86 64). Questa versatilita ha permesso (senza dover acquistare ulteriore soft-

ware proprietario) di utilizzare due macchine diverse per la programmazione (il

portatile appena citato) e la verifica (una workstation del laboratorio di microar-

chitetture con ambiente Windows) tramite terminale seriale dell’output da scheda.

Sempre l’utilizzo di due macchine con i tool della Xilinx ha permesso, quando

questo si e rivelato utile, di effettuare sintesi parallele di architetture simili con

piccole varianti, in modo da velocizzare i tempi di test per l’individuazione della

disposizione ottimale dei componenti.

2.3.2 Altri strumenti software

Vari altri software sono stati utilizzati nel corso di questo lavoro di tesi, anche

se meno intensivamente di EDK. iMPACT [11], tool sviluppato dalla stessa Xili-

nx, e stato talvolta sfruttato per caricare il file di configurazione dell’architettura

26


(download.bit) sulla scheda (operazione che puo comunque essere eseguita all’in-

terno di EDK). Per avere un’idea della struttura reale dell’area riconfigurabile e

stato invece utilizzato FPGA Editor [12], anch’esso sviluppato da Xilinx. FPGA

Editor permette, come detto, di rappresentare graficamente il sistema interessato,

ma anche di eseguire una serie di funzioni piu o meno complesse su di esso (dal

semplice esame dello stato dei segnali, al Place&Route di componenti critici del

sistema, alla completa progettazione di una architettura con un controllo a basso

livello). Nel nostro caso, FPGA Editor e stato unicamente utilizzato per verifica-

re la corretta disposizione dei diversi componenti, per sincerarsi del rispetto dei

vincoli imposti nel file .ucf e verificare quindi che non ci fossero dannose sovrap-

posizioni tra i vari componenti. Infine vale la pena citare alcuni semplici software

per la comunicazione tramite seriale, quali HyperTerminal e uCon, che hanno

permesso, utilizzando una connessione attraverso la porta seriale, di visualizzare

l’output del software in esecuzione sulla scheda.

27


28

Capitolo 3

Stato dell’arte

Il capitolo seguente riassume le principali attivita di ricerca note nell’area del-

l’hardware evoluto ed evolvibile su FPGA. L’esplorazione di questo campo e co-

minciata piuttosto di recente, verso la fine del secolo scorso, ma ha gia portato alla

luce dei risultati interessanti che incentivano ulteriori lavori di ricerca. Qui si da

una panoramica degli studi documentati fino ad oggi in letteratura: dai primi espe-

rimenti riguardanti l’evoluzione intrinseca svolti da Thompson (Sezione 3.1), pas-

sando per le successive sperimentazioni su Virtex-2 e Virtex-2 PRO (Sezione 3.2),

fino a trattare (nella Sezione 3.3) dei recenti approfondimenti sulla manipolazione

del bitstream delle Virtex-4 documentati in [13].

3.1 Primi esperimenti con FPGA

Come accennato nell’introduzione, fu Adrian Thompson [17, 18, 19], durante la

seconda meta degli anni ’90, ad interessarsi per primo a temi riguardanti l’evolu-

zione hardware su dispositivi riconfigurabili quali le FPGA. Il dispositivo scelto

da Thompson per i suoi esperimenti [18] fu una FPGA della famiglia XC6200,

prodotta dalla Xilinx (Figura 3.1). Thompson scelse questa scheda come base

evolutiva per una serie di ragioni, tra cui la sua facile reperibilita commerciale e la

presenza di alcune caratteristiche decisamente interessanti per l’evoluzione di cir-

cuiti hardware: un’ottima interfaccia di accesso alla memoria di configurazione,

29

CAPITOLO 3. STATO DELL’ARTE

la possibilita di riconfigurabilita parziale, l’elevata velocita di riconfigurazione, il

formato del bitstream completamente aperto e l’assenza di configurazioni di rou-

ting illegali. Quest’ultima caratteristica e particolarmente importante per l’esperi-

Figura 3.1: Struttura della FPGA Xilinx XC6200.

mento condotto da Thompson, che ebbe la possibilita di lasciare che l’evoluzione

esplorasse la massima ampiezza dello spazio delle soluzioni, senza preoccuparsi

di eventuali sequenze dannose per il chip all’interno del bitstream di configura-

zione.

Per il suo primo esperimento Thompson decise di lavorare sul bitstream corrispon-

dente ad un area di 10x10 blocchi riconfigurabili (Configurable Logic Block), con-

figurando le altre celle per produrre un valore costante, e sottoporlo direttamente

30


al processo evolutivo facendo uso di un algoritmo genetico standard. Il caso di

studio a cui applico la sua idea fu l’evoluzione di un discriminatore di tono in

grado di fornire in uscita un valore alto (+5V) nel caso in cui all’ingresso fosse

presente un’onda quadra ad alta frequenza (10KHz) e un valore basso (0V) nel

caso in cui fosse posta in ingresso un’onda quadra a bassa frequenza (1KHz). Il

circuito a cui si voleva giungere sarebbe dovuto essere in grado di discriminare

correttamente l’ingresso senza far uso di alcuna fonte esterna di clock.

L’obiettivo di Thompson, come detto, era quello di lasciare la massima liberta al

processo evolutivo per riuscire a sfruttare le caratteristiche peculiari del substrato

di silicio su cui era implementata la scheda; per ottenere questo la scelta ovvia e

stata quella di basare il processo evolutivo su un modello intrinseco. L’evoluzio-

ne avveniva quindi caricando sulla FPGA ogni individuo (attraverso l’inserimento

nella memoria di configurazione del bitstream corrispondente) e valutandone il

comportamento rispetto agli ingressi forniti. Il segnale di ingresso veniva appli-

cato su un piedino del chip predefinito ed era composto da 10 intervalli di durata

500ms, scelti con una distribuzione casuale, ma in modo che 5 fossero l’onda qua-

dra a 10KHz e gli altri 5 l’onda a 1KHz. Durante la fase di valutazione l’uscita

veniva valutata su un altro piedino predefinito e il suo valore veniva digitalizzato e

inviato ad un calcolatore per poterne valutare l’andamento. La funzione di fitness

implementata e quella proposta nella Equazione 3.1, dove con S1 e S10 sono indi-

cati gli intervalli in cui l’ingresso era rispettivamente a 1KHz e a 10KHz, mentre

it corrisponde al valore dell’integratore alla fine dell’intervallo t.

f =1

10

∣∣(k1 ∑t∈S1 it)−(k2 ∑t∈S10 it

)∣∣ con

{k1 = 1/30730.746

k2 = 1/30527.973(3.1)

La funzione scelta per valutare gli individui non specifica quale sia il valore de-

siderato in uscita per le due onde in ingresso, ma valuta la differenza tra i valori

medi delle uscite nei momenti in cui si presentano in ingresso i due segnali cam-

pione. Questa scelta e in linea con l’idea di Thompson di un percorso evolutivo

composto da piccoli passi incrementali, il meno possibile vincolato, in modo da

sfruttare al massimo tutte le caratteristiche del dispositivo utilizzato [17].

Le caratteristiche scelte per l’evoluzione furono:

31


• Cardinalita della popolazione pari a 50 individui.

• Probabilita di crossover del 70%.

• Probabilita di mutazione per ogni bit tale che il numero di mutazioni per

genotipo fosse in media 2.7.

• Elitismo per il miglior individuo di ogni generazione.

L’algoritmo e stato lasciato evolvere per 5000 generazioni e, ad evoluzione com-

pletata, il circuito corrispondente al miglior individuo e stato testato per un tempo

superiore rispetto a quello usato nell’evoluzione in modo da eliminare il contri-

buto dei disturbi e determinare esattamente quali CLB influissero effettivamente

sull’uscita. Alla fine del processo di generazione e testing, Thompson e perve-

nuto ad una soluzione funzionante utilizzando un numero decisamente limitato di

risorse rispetto a quelle disponibili. Il piu grande vantaggio ottenuto con l’utiliz-

zo di un algoritmo genetico e stato quello di astrarre dal comportamento tipico

della scheda presa in esame, utilizzando in modo differente i transistor (usati dal-

la soluzione selezionata non soltanto in zona di saturazione, come sarebbe tipico

per il dispositivo digitale sottostante). D’altro canto e inevitabile che il circuito

cosı ottenuto dipenda fortemente dalle caratteristiche dell’area di silicio utilizzata

e dalle sue proprieta fisiche, soprattutto dalla temperatura. In merito a cio e stato

verificato un decadimento di circa il 7% delle prestazioni implementando lo stes-

so circuito su di un’area differente della medesima FPGA. Lo stesso Thompson,

con il collega Lyzell, ha svolto ulteriori studi per tentare di limitare questa ecces-

siva specializzazione delle soluzioni rispetto alle specifiche condizioni fisiche di

evoluzione e alla specifica area di silicio utilizzata. L’evoluzione delle soluzioni

candidate e stata realizzata introducendo delle variabilita nelle condizioni al con-

torno (temperature d’esercizio variabili, diverse aree di silicio e varie condizioni

di alimentazione elettrica) e definendo un sistema di evoluzione definito Evolva-

tron [20]. Le conclusioni a cui sono giunti [21] dimostrano che e possibile far

evolvere individui che, arrivando comunque a risolvere il problema del caso di

test, sviluppano delle buone caratteristiche di resistenza a questo tipo di disturbi.

32


3.2 Evoluzione Hardware su FPGA Virtex-2 e Virtex-

2 PRO

Un lavoro analogo a quello svolto da Thompson non e piu realizzabile con i dispo-

sitivi moderni, infatti la Xilinx ha deciso di abbandonare la produzione di schede

riconfigurabili della famiglia XC6200 e le nuove FPGA in commercio non pre-

sentano alcune delle caratteristiche sfruttate in questi primi esperimenti. Come e

ovvio per un’azienda presente sul mercato, la Xilinx ha seguito, nello sviluppo

dei propri chip, criteri di decisione basati sull’opportunita commerciale e questi le

hanno imposto di togliere dalle nuove generazioni di FPGA proprio alcune delle

caratteristiche che le rendevano uno strumento cosı adatto all’implementazione

di circuiti hardware evolvibili. In particolare le nuove schede in commercio non

offrono piu un formato del bitstream aperto, che consentiva una facile manipola-

zione anche a basso livello dei componenti logici implementati. Nel 1998 e nato

il progetto Virtex, che ha portato alla produzione di chip tecnologicamente piu

avanzati, ma con alcune caratteristiche che ne rendono piu difficoltoso l’utilizzo

per l’evoluzione hardware. In primo luogo, come si accennava in precedenza,

il formato del bitstream e chiuso, ovvero non e noto come siano codificate le

informazioni relative ai circuiti implementati sul chip. Questa mancanza di in-

formazione rende necessario, nel caso in cui si voglia operare un’evoluzione gate

level (a basso livello), un pesante lavoro di ingegneria inversa per arrivare alla

decodifica del formato del bitstream. In secondo luogo l’introduzione del routing

multi-direzionale, che permette una maggiore flessibilita nel processo di riconfi-

gurazione, comporta pero la possibilita di caricare su scheda configurazioni illega-

li, che possono dare luogo al cortocircuito degli ingressi, danneggiando in modo

permanente il chip della FPGA. Per poter sfruttare le nuove possibilita introdotte

dalla famiglia Virtex si e dovuto cercare di ovviare a questi ostacoli e a questo

scopo i ricercatori hanno intrapreso due strade differenti. Da una parte la crea-

zione di Circuiti Virtuali Riconfigurabili (Virtual Reconfigurable Circuit o VRC),

realizzati con una struttura programmabile che utilizza le risorse della FPGA ma

si pone a piu alto livello, introducendo un layer di sicurezza e astrazione tra il

33


dispositivo logico riprogrammabile e il chip; dall’altra la manipolazione, diretta o

tramite API, del bitstream.

3.2.1 Circuiti Virtuali Riconfigurabili

La tecnica dei Circuiti Virtuali Riconfigurabili, proposta da Sekanina nel 1999

[22], propone di implementare un secondo layer riconfigurabile sulla FPGA, il

cui comportamento puo essere definito modificando il contenuto di una memoria

di configurazione; questo permette al progettista di scegliere a proprio piacimento

la relazione tra i singoli bit della memoria di configurazione e il comportamento

del circuito. L’approccio sopra descritto trova le sue basi in una particolare tecni-

ca chiamata Cartesian Genetic Programming (CGP) e si basa su una sua versione

semplificata, sviluppata da Miller [23] e altri. Un circuito hardware, che possiamo

anche chiamare “programma”, e visto come un insieme di nodi (o celle) disposti in

righe e colonne per formare un rettangolo di dimensioni note. Ogni nodo realizza

una particolare funzione logica. In questo modo e possibile realizzare il circuito

virtuale programmando direttamente il genotipo, senza bisogno di trasformarlo

nel bitstream di riconfigurazione della FPGA per poterlo implementare.

L’idea e quindi quella di sviluppare un circuito in modo che sia composto da

una serie di elementi programmabili, una rete di connessioni anch’esse program-

mabili, una memoria di configurazione e una porta di accesso a tale memoria.

Circuiti cosı organizzati permettono un’evoluzione di tipo funzionale: sebbene

questo approccio non abbia le potenzialita di “esplorazione” dello spazio delle

configurazioni tipiche dell’evoluzione a livello delle porte logiche, ha il vantaggio

di permettere un’evoluzione in tempi ridotti e un’elevata adattabilita e rapidita nel

processo di riconfigurazione. Una interessante caratteristica dei Circuiti Virtuali

Riconfigurabili, che li ha resi molto utilizzati tra i ricercatori, e quella di essere

implementati utilizzando un linguaggio di descrizione harware (HDL) o addirittu-

ra in C. Questo rende la definizione di VRC molto flessibile e portabile su diversi

dispositivi. Il processo di definizione di tale circuito puo essere sintetizzato in

quattro passi principali:

34


• Definizione della singola cella: in particolare occorre soffermarsi sui pro-

blemi di definizione dell’unita logica (quindi della funzione svolta dalla cel-

la) e dell’unita di controllo del routing, responsabile dell’instradamento dei

segnali.

• Creazione di una gerarchia di cella: questo passo e utile per creare un singo-

lo schema complessivo composto da diverse celle elementari; questi schemi

saranno successivamente composti per creare schemi di dimensioni ancora

maggiori.

• Sintesi logica: il codice HDL scritto nei due punti precedenti viene ora

sintetizzato al fine di produrre una rappresentazione a livello delle porte

logiche (dipendente dall’architettura della FPGA scelta).

• Place and route: il circuito virtuale viene infine collocato sulla scheda e ne

viene eseguito il routing.

Gli esempi piu significativi di architetture basate su VRC sono stati proposti da

Sekanina [22, 24, 25] e da Glette-Torresen [26, 27]. Sekanina ha utilizzato i VRC

nel campo dell’image processing, implementando un filtro 3 × 3 da applicare a

immagini in scala di grigi. Particolare e l’uso che Sekanina fa del processore a

disposizione sulla board: il PowerPC e utilizzato per generare nuove soluzioni

candidate e questo permette di implementare diversi algoritmi evolutivi e diversi

generatori di numeri casuali in modo abbastanza semplice; la popolazione in evo-

luzione viene memorizzata sfruttando le BRAM disponibili sulla FPGA.

Anche Glette e Torresen hanno implementato tutto il sistema evolutivo su un’u-

nica FPGA; essi pero, a differenza di Sekanina, hanno sfruttato il processore per

implementare completamente l’algoritmo evolutivo. Questa scelta li ha costretti a

riadattare un algoritmo genetico standard, per tener conto dei vincoli (principal-

mente per quanto riguarda la memoria disponibile) imposti dalle limitate risorse

rese disponibili da PowerPC e FPGA. Anche i loro esperimenti hanno utilizzato

come casi di studio problemi di image processing e il circuito base da loro pro-

posto permette di realizzare 8 diverse funzioni logiche (somma, sogliatura alta,

range, confronto, AND, OR, media e dimezzamento).

35


I vantaggi principali dei Circuiti Virtuali Riconfigurabili risiedono nella loro adat-

tabilita e nella rapidita di riconfigurazione. I sostenitori dei VRC ritengono, infatti,

che i sistemi di riconfigurazione parziale (come l’Internal Configuration Access

Port, offerta dalla Xilinx), necessari per un’evoluzione con manipolazione del bi-

tstream, non offrano prestazioni accettabili. D’altro canto, gli svantaggi dei VRC

sono riassumibili con la maggiore richiesta di area (dovuta all’utilizzo di un li-

vello di astrazione sulle risorse della FPGA), la limitata esplorazione delle risorse

fisiche e la minore resistenza ai guasti.

In Figura 3.2 si puo vedere la struttura tipica di un VRC, in particolare quello pro-

posto da Sekanina. Si puo notare come questo offra un livello di astrazione sulle

risorse della FPGA.

Figura 3.2: Struttura del VRC proposto da Sekanina [28].

36


3.2.2 Manipolazione del bitstream

Un approccio alternativo a quello dei VRC di fronte alla chiusura del formato

del bitstream e stato quello di proseguire con la manipolazione della stringa di

configurazione. La scelta di operare in questo modo comporta ovviamente del

lavoro aggiuntivo a causa della mancanza di informazione riguardo alla codifica

del bitstream. Sono stati sviluppati due approcci alla manipolazione del bitstream

di cui uno si pone ancora ad un livello di astrazione superiore, utilizzando come

strumento di riconfigurazione un set di API Java denominato JBits, mentre l’altro

si propone di trattare direttamente il bitstream della FPGA.

JBits: API Java per la manipolazione del bitstream

JBits e una libreria, scritta in linguaggio Java, che offre una utile interfaccia di

configurazione per la manipolazione del bitstream delle schede appartenenti al-

la famiglia Virtex. La versatilita offerta da questo strumento rappresenta il suo

maggior vantaggio: le classi Java sono infatti in grado di operare sia su bitstream

generati utilizzando i tools della Xilinx, sia su quelli letti direttamente da un dispo-

sitivo, permettendo la modifica dinamica della configurazione della FPGA. JBits

offre un modello di programmazione rappresentabile tramite un array bidimensio-

nale di CLB, ognuno dei quali e indirizzato da un numero di riga e da un numero

di colonna. Occorre notare, tuttavia, che questa soluzione non impedisce, in gene-

rale, di creare configurazioni illegali. Per evitare di danneggiare il dispositivo un

possibile modo di operare e modificare solo le risorse di interesse (tipicamente le

funzioni logiche che definiscono i vari componenti di base) dopo averle corretta-

mente riconosciute all’interno del bitstream (questo puo essere fatto modificando

un bitstream valido di partenza dopo aver compreso la posizione e la struttura del-

le sezioni di interesse). Una volta generata una configurazione valida e possibile

inviarla alla FPGA facendo uso di una apposita interfaccia, denominata XHWIF,

fornita direttamente da Xilinx. La stessa interfaccia puo essere utilizza anche per

recuperare il bitstream di una configurazione presente sulla scheda.

Tra i primi ricercatori che utilizzarono l’API appena descritta per l’evoluzione

hardware si possono trovare Levi e Guccione. Gli studi dei due si concentraro-

37


no nello sviluppo di un intero framework dedicato a tale scopo, noto con il no-

me di GeneticFPGA [29]. In Figura 3.3 e data una rappresentazione del flusso

evolutivo implementato da questo framework. Il flusso evolutivo proposto e cosı

Figura 3.3: Rappresentazione del flusso evolutivo proposto in [29].

sintetizzabile:

• Generazione del bitstream che rappresenta la soluzione candidata su cui si

vuole operare.

• Caricamento su scheda ed evoluzione dell’individuo con operatori genetici.

• Lettura del nuovo genotipo evoluto e sua analisi con gli strumenti offerti da

JBits.

Il primo punto e necessario per generare il genotipo (bitstream) che codifica il

fenotipo dell’individuo da evolvere. La generazione viene attuata utilizzando del-

le classi offerte da JBits, che permettono anche di inserire delle strutture statiche

prima di scaricare la configurazione sulla scheda. Una volta caricato l’individuo

sulla scheda e realizzata l’evoluzione, la configurazione viene estratta e analizzata

facendo uso della API JBits. In tal modo e possibile dare un punteggio all’indivi-

duo e continuare la valutazione della popolazione.

38


Altri ricercatori hanno cercato di ovviare alla particolare lentezza che ha mostrato

l’implementazione proposta da Levi-Guccione. Tra questi il lavoro piu interessan-

te e quello dovuto agli studi di Tyrrell nel campo della robotica autonoma [30].

L’architettura proposta da Tyrrell presenta un tempo di riconfigurazione sensi-

bilmente inferiore a quella utilizzata da Levi e Guccione, poiche e in grado di

sfruttare la riconfigurazione parziale. Infatti essa richiede di modificare (con l’uso

di JBits) soltanto il contenuto delle tabelle di definizione delle funzioni logiche

(Look Up Tables o LUT) e non tutto il bitstream. Tale architettura non e, pero,

priva di difetti, riscontrabili in una struttura di interconnessioni tra le LUT troppo

semplificata e nell’assenza di elementi di memoria.

Nonostante il largo uso che i ricercatori hanno fatto della libreria JBits, essa pre-

senta delle notevoli limitazioni [31]: l’impossibilita di effettuare evoluzione on

chip (poiche le piattaforme embedded non sono supportate), l’incompatibilita con

altri linguaggi di descrizione hardware, il supporto ridotto ad un numero piuttosto

limitato di chip e board e un supporto limitato da parte della stessa Xilinx.

Manipolazione diretta del bitstream

Per le ragioni appena esposte alcuni ricercatori hanno deciso di adottare altre solu-

zioni per la manipolazione del bitstream a partire dalle FPGA della serie Virtex-2.

Di particolare interesse sono le tre tecniche sfruttate da Upegui e Sanchez [31].

La prima tecnica si basa sulla riconfigurazione Module Based [32]: tale approccio

impone di effettuare un design altamente modularizzato, in cui l’unita minima di

riconfigurazione e rappresentata dai singoli moduli (permettendo una evoluzione

a grana grossa adatta a strutture modulari, quali le reti neurali). I vincoli imposti

dalla struttura basata su moduli sono numerosi e fissano a priori molte caratteri-

stiche delle soluzioni (ad esempio, per l’evoluzione di una rete neurale, bisogna

rispettare il numero degli strati che la compongono, fissato a priori, e sono fissati

anche i segnali di connessione tra gli strati e quelli di ingresso/uscita). In que-

sto ambito un algoritmo evolutivo puo quindi al massimo effettuare una sorta di

esplorazione architetturale alla ricerca della miglior disposizione dei moduli. La

scelta dei moduli avviene, solitamente, all’interno di una libreria di moduli gia

39


sintetizzati, poiche sarebbe impraticabile lasciare che l’algoritmo modifichi libe-

ramente la descrizione in HDL di ogni modulo.

La seconda tecnica si basa sul flusso di riconfigurazione Difference Based [33]

e permette un’evoluzione piu fine. Essa consente infatti di modificare porzioni

ridotte del design, come la configurazione di una singola CLB o addirittura di

una sola LUT all’interno di questa. Requisito indispensabile per eseguire questa

tecnica e fornire una descrizioni in linguaggio HDL del sistema, includendo delle

hard macro che definiscano la porzione del dispositivo che si intende riconfigura-

re. L’idea proposta dai due ricercatori prevede che l’algoritmo evolutivo generi il

contenuto delle LUT da riconfigurare e quindi venga invocato uno script capace

di generare il bistream parziale da caricare sulla FPGA.

Bisogna notare che i due approcci citati si basano sui flussi di riconfigurazione

parziale proposti dalla Xilinx (Module Based e Difference Based) [34] e sfruttano

dei tool appositamente prodotti per questi flussi.

L’ultima tecnica proposta e anche la piu interessante ai fini di questo lavoro di tesi.

Essa consiste infatti nella manipolazione diretta del bitstream, ottenuta evolvendo

unicamente il contenuto delle LUT, dopo aver definito a priori uno schema di inter-

connessione (hard macro), senza utilizzare alcuno strumento intermedio. Poiche,

come detto, la struttura del bitstream della Virtex-2 utilizzata da Upegui e San-

chez era sconosciuta, l’ostacolo principale e rappresentato dall’identificazione del

contenuto delle LUT all’interno del bitstream stesso. Nella documentazione della

Xilinx si trovano indicazioni solo sul fatto che il bitstream sia diviso in una serie

di colonne, ognuna delle quali e suddivisa in un certo numero di frame (che sono

l’unita minima di riconfigurazione). Gran parte degli sforzi di Upegui e Sanchez

si sono quindi concentrati nel lavoro di ingegneria inversa della stringa di confi-

gurazione, effettuato operando dei confronti tra bitstream ottenuti sintetizzando

circuiti differenziati da piccole modifiche nella configurazione delle sole LUT. Il

lavoro di reverse engineering ha permesso di individuare all’interno del bitstream

le sezioni che codificano le LUT presenti nei CLB della Virtex-2, consentendo

quindi di effettuare, dopo aver definito una struttura base di interconnessione, una

evoluzione mirata con la modifica incrementale delle sole sezioni di interesse.

40


In merito alla definizione dell’architettura di base per la manipolazione diretta del

bitstream si puo inoltre notare, tra le varie proposte presenti in letteratura, una

certa analogia con le strutture dei Circuiti Virtuali Riconfigurabili; ad esempio

Tufte e Haddow [35, 36] hanno proposto una struttura cellulare per Virtex-E (la

cui struttura e visibile nella Figura 3.4). Al contrario dei VRC, in cui le singo-

le celle vengono progettate astraendo rispetto alla tecnologia implementativa, in

questo secondo caso la struttura e l’ubicazione delle celle dipende strettamente

dalle proprieta della specifica FPGA. Questa differenza e affatto non trascurabi-

Figura 3.4: Rappresentazione della struttura cellulare proposta in [35, 36]

le, dal momento che permette di sfruttare la riconfigurazione parziale, una volta

nota la posizione della risorsa da manipolare all’interno del genotipo (ovvero del

bitstream parziale di configurazione).

Sono noti diversi test effettuati implementando la stessa struttura tramite Circuiti

Virtuali Riconfigurabili e tramite manipolazione diretta del bitstream: il risultato

e stato che in media la prima soluzione occupa 5 volte lo spazio occupato dalla

seconda. In particolare alcuni test sono stati condotti, ancora da Upegui [37], im-

plementando una struttura simile a quella cellulare proposta da Tufte. La struttura

proposta si compone di celle, connesse a quelle adiacenti, che offrono in uscita

sui quattro lati uno tra i quattro ingressi o lo stato interno della cella, definito in

termini dei segnali di ingresso e del valore di un Flip-Flop interno. Utilizzando

un approccio di manipolazione diretta ogni cella richiede 4 slices di una Virtex-2

per l’implementazione e puo quindi essere mappata in un solo CLB. La stessa cel-

la, implementata secondo il paradigma dei VRC in seguito alla creazione di una

opportuna descrizione HDL, e risultata richiedere 18 slices, ovvero 5 CLB della

41


Virtex-2. Ulteriori test svolti su questa struttura sono consistiti nell’assemblare

una griglia di 5×6 celle del tipo descritto e nell’utilizzo dell’interfaccia di ricon-

figurazione Icap. La riconfigurazione parziale richiede, in questo caso, la modifica

di 24 frame (4 per ogni colonna dell’array) per la parte relativa alle connessioni

e di 6 frame (un frame per colonna) per cambiare il contenuto della regola della

cella. L’evoluzione e resa possibile dall’utilizzo di un processore MicroBlaze (im-

plementato sulla FPGA), dallo sfruttamento della memoria BRAM interna per il

codice dell’algoritmo evolutivo e di una SRAM esterna per la memorizzazione dei

genotipi. Per permettere l’accesso allo stato delle celle da parte del processore,

infine, sono state implementate delle interfacce ad-hoc.

Una simile tecnica di manipolazione diretta del bitstream porta i suoi migliori

vantaggi se applicata ai bitstream delle FPGA della serie Virtex-4 e successive;

su questi chip e infatti possibile sfruttare la possibilita di riconfigurazione 2D che

essi offrono. Come si vede dalla Figura 3.5, la riconfigurazione 2D permette di

modificare solo alcune parti di una colonna, dando la possibilita di allocare diver-

si individui all’interno della stessa colonna di CLB. Con le vecchi Virtex, invece,

volendo riconfigurare una certa porzione di una colonna si era comunque obbli-

gati a riprogrammarla tutta. Gli esperimenti fin qui menzionati utilizzano FPGA

Figura 3.5: Possibile allocazione degli individui con (a destra) e senza (a sinistra)

possibilita di configurazione 2D.

42


che permettono solo una riconfigurazione monodimensionale, ovvero e necessario

riconfigurare un’intera colonna di CLB per volta. La riconfigurazione bidimen-

sionale invece offre la possibilita di riconfigurare anche una sola cella senza dover

riconfigurare l’intera colonna di CLB. I vantaggi apportati dalla riconfigurazio-

ne bidimensionale sono sostanzialmente due: bitstream di dimensioni ridotte e

migliore sfruttamento dell’area della FPGA. Questo secondo punto in particolare

puo consentire di implementare simultaneamente piu individui sulla scheda, ef-

fettuando una valutazione parallela delle soluzioni candidate con una riduzione

notevole dei tempi di evoluzione. Queste possibilita sono ampiamente esposte in

[13] e riassunte nella prossima Sezione 3.3.

3.3 Evoluzione hardware su FPGA Virtex-4

La piu importante fonte di ispirazione e di informazioni per lo sviluppo di questo

lavoro di tesi (e la base architetturale su cui e stato sviluppato l’algoritmo geneti-

co) e il lavoro documentato in [13]. Gli studi di quest’ultimo si sono concentrati

sulla comprensione, seppur parziale, della struttura del bitstream di configurazio-

ne della FPGA scelta (Virtex-4, XC4VFX12) attraverso un’opera di analisi. E

stata quindi proposta una possibile architettura per il sistema evolutivo in grado di

sfruttare la riconfigurazione bidimensionale offerta dal dispositivo scelto.

3.3.1 Analisi del bitstream

Come noto l’unita minima di riconfigurazione per le Virtex (e quindi anche per la

Virtex-4) e costituita dal frame: la memoria di configurazione del chip XC4VFX12

utilizzato si compone di 3.848 frame, ognuno dei quali e composto da 41 parole

da 32 bit. Oltre che da questi frame un bitstream completo incorpora alcuni co-

mandi necessari per controllare la logica di configurazione, che e costituita da un

processore di pacchetti (che controlla il flusso di dati provenienti dall’interfaccia

di configurazione e lo dirige verso i vari registri di configurazione), un set di regi-

stri (che controllano il processo di configurazione e riconfigurazione) e una serie

43


di segnali il cui funzionamento e legato al contenuto dei registri stessi.

Ogni pacchetto di configurazione e costituito da un header di 32 bit e dai dati di

payload di lunghezza variabile. Sono possibili due tipi di pacchetto:

• Pacchetto di Tipo 1: viene utilizzato per le operazioni di lettura e scrittura

dei registri di configurazione.

• Pacchetto di Tipo 2: e un’estensione dei pacchetti di Tipo 1 e viene utiliz-

zato per la scrittura di blocchi particolarmente lunghi (ad esempio nel caso

di riconfigurazione di diversi frame durante la stessa operazione).

I pacchetti di Tipo 2 sono sempre preceduti da un pacchetto di Tipo 1 nel qua-

le e specificato l’indirizzo a partire dal quale scrivere i dati contenuti nel suc-

cessivo pacchetto di dati. I registri che vengono utilizzati durante il processo

riconfigurativo sono:

• Frame Address Register (FAR): contiene l’indirizzo del frame da configu-

rare. L’indirizzamento e composto di 5 campi e, una volta impostato, puo

essere incrementato automaticamente dal processo di configurazione.

• Legacy Output Register (LOUT): puo essere utile in fase di debug, per

ottenere informazioni sul frame attualmente in uso.

• Frame Data Register - Input (FDRI): e il registro in cui vanno scritte i reali

dati da inserire nella memoria di configurazione.

Fra i tre registri citati quello che contiene i campi piu interessanti ai fini del lavoro

svolto da M. Castagna [13] e il FAR, la cui struttura e mostrata in Tabella 3.1.

La struttura di un bitstream di configurazione completo e composta delle seguenti

parti:

• Alcune parole iniziali di carattere generale contenenti informazioni quali il

nome del file, la data di creazione e il modello della FPGA.

• Una parola fittizia (0xFFFFFFFF) seguita dalla parola di sincronizzazione

(0xAA995566), utilizzata per allineare il parser di pacchetti.

44


Tabella 3.1: Struttura del registro FAR.

Campo Bit Descrizione

Top/Bottom 22Seleziona i frame appartenenti alla meta

superiore o inferiore del dispositivo.

Tipo di Blocco 21:19

I tipi disponibili sono: CLB/IO/CLK (000),

block RAM Interconnect (001), block

RAM content (010), CFG CLB (011) e

CFB BRAM (100).

Row Address 18:14

Seleziona una riga di frame. Tale indi-

rizzo aumenta allontanandosi dal centro del

dispositivo.

Major Address 13:6

Seleziona una colonna di risorse. La colon-

na piu a sinistra ha indirizzo pari a 0 e viene

incrementato andando verso destra.

Minor Address 5:0Seleziona un particolare frame all’interno di

una colonna.

• Una prima serie di pacchetti, costituenti il preambolo, usati per effettuare

l’inizializzazione del processo di configurazione.

• La codifica dell’area da da configurare (indirizzato al registro FDRI), che e

il contenuto vero e proprio della memoria di configurazione.

• Una serie finale di pacchetti per le operazioni di finalizzazione del processo

di configurazione e avvio del normale funzionamento del dispositivo.

Per quanto riguarda le operazioni di riconfigurazione parziale la struttura del bi-

tstream si presenta in modo leggermente differente rispetto ad una configurazione

completa, poiche viene interessata solo una parte del dispositivo e non viene in-

terrotto il funzionamento della parte restante.

La parte piu interessante del lavoro di analisi qui presentato e quella riguardante

la ricerca, a basso livello, della codifica del contenuto delle LUT all’interno della

memoria di configurazione (questa informazione non e infatti documentata dalla

45


Xilinx). L’approccio con il quale si e tentato di raggiungere questo obiettivo e

stato quello di generare dei design molto semplici a cui apportare piccole modifi-

che: il loro confronto ha permesso di dedurre un ridotto numero di regole per la

costruzione di tali bitstream a partire dal contenuto desiderato per le LUT. Ovvia-

mente nel corso di tale confronto non sono state prese in considerazione tutte le

differenze, ma solo quelle relative all’effettivo contenuto della memoria di confi-

gurazione. Le relazioni che legano l’indirizzo della slice (in termini di coordinate

X e Y) e il contenuto del frame sono mostrate dalle equazioni seguenti.

Ma jor = Ma jor(X) =⌊x

2

⌋+Ad j(X) (3.2)

Ad j(X) =

1 se 0≤ X ≤ 23

3 se 24≤ X ≤ 31

4 se 32≤ X ≤ 47

(3.3)

Minor = Minor(X) =

{21 se X e pari

19 se X e dispari(3.4)

Row = Row(Y ) =

1 se 0≤ Y ≤ 31

0 se 32≤ Y ≤ 95

1 se 96≤ Y ≤ 127

(3.5)

Top/Bottom = Top/Bottom(Y ) =

{1 se 0≤ Y ≤ 63

0 se 64≤ Y ≤ 127(3.6)

Questa analisi ha permesso di identificare il frame che configura una slice di coor-

dinate note. Il passo successivo e stato quello di capire quali fossero gli effettivi

byte di codifica delle LUT all’interno del frame che contiene la slice di apparte-

nenza. Si e scoperto che la posizione dei byte di interesse all’interno del frame e

funzione della sola coordinata Y e che l’andamento del valore del valore del byte

del frame all’interno del quale inizia il byte ricercato (ByteStart) presenta una forte

regolarita. Per le slice appartenenti alla parte superiore della FPGA (Top/Bottom

= 0) e per lo stesso tipo di LUT tale valore cresce ad intervalli regolari di 5 byte e

questo schema resta valido fino ad arrivare alla LUT con coordinata Y tale che Y

% 32 = 15. Dalla LUT successiva si ripete ancora la sequenza ma con un offset di

una parola di 32 bit. Per quanto riguarda i due frame appartenenti alla meta infe-

46


riore del dispositivo e possibile osservare lo stesso schema, ma in ordine inverso.

In definitiva il mattone costitutivo del bitstream e rappresentato da un blocco di 5

byte, all’interno del quale si trovano i contenuti della LUTF e della corrispondente

LUTG (che occupano in totale 4 byte), mentre gli 8 bit rimanenti si trovano prima

della LUTF, dopo la LUTG o tra esse a seconda dei risultati ottenuti applicando

queste formule:

TopByteStart(Y,LUT ) = 5 · (Y %32)+Ad jLUT (LUT )+Ad jY (Y ) (3.7)

Ad jLUT (LUT ) =

{0 se LUT == FLUT

2 se LUT == GLUT(3.8)

Ad jY (Y ) =

{4 se Y %32 > 15

0 se Y %32≤ 15(3.9)

ByteStart(Y,LUT ) =

TopByteStart(Y,LUT ) se Y ≥ 64

162−TopByteStart(Y,LUT )

−Ad jG(LUT ) se Y ≤ 63

(3.10)

Ad jG(LUT ) =

{0 se LUT == FLUT

1 se LUT == GLUT(3.11)

In particolare le formule precedenti permettono di calcolare il ByteStart (Equa-

zione 3.10), ovvero il byte del frame di configurazione entro cui inizia la codifica

della LUT che si vuole localizzare.

Se si e interessati a conoscere non solo il byte, ma anche il primo bit di contenuto

della LUT si possono usare le seguenti equazioni per calcolare BitStart, ovvero il

bit di inizio della codifica della LUT all’interno del frame che la contiene.

Ad jBit(Y,LUT ) =

7 se LUT == GLUT & Y ≥ 64

1 se LUT == GLUT & Y ≤ 63

0 altrimenti

(3.12)

BitStart(Y,LUT ) = 8 ·ByteStart(Y,LUT )+Ad jBit(Y,LUT ) (3.13)

In Figura 3.6 si puo vedere una rappresentazione grafica della struttura del bi-

tstream di configurazione per un frame della meta superiore del chip. Risultati

sperimentali hanno infine permesso di affermare che i bit di configurazione delle

47


Figura 3.6: Rappresentazione della struttura di un frame della meta superiore di una

Virtex-4 (Top/Bottom = 0) secondo l’analisi presentata in [13].

slice della parte inferiore del dispositivo hanno ordine invertito rispetto a quelli

della meta superiore.

Un discorso a se merita la parola centrale (ovvero la ventesima) di ogni frame.

Essa viene ricalcolata ogni qual volta vengano apportate delle modifiche al frame

di configurazione e funziona da parola di controllo. Il formato binario di questa

checkword dipende dal contenuto delle LUT del frame e viene calcolato in modo

incrementale per ogni bit posto a 1. In particolare e stato appurato che il calcolo

viene effettuato come XOR bit a bit di un certo numero di checkword “locali’ che

possono essere calcolate per ogni bit posto a 1 all’interno delle LUT del frame.

Per riuscire a calcolare la parola centrale e quindi sufficiente comprendere come

avviene il calcolo delle parole di controllo per i singoli bit. Dopo svariati test sono

stati raggiunti i seguenti risultati:

• I primi 11 bit della checkword locale funzionano da indice per la coordinata

Y della slice contenente la LUT che contiene il bit in questione. L’indice

ha un valore di partenza di 704, che corrisponde al bit 0 del frame, e viene

incrementato come descritto nelle formule dalle Equazioni dalla 3.14 alla

3.16.

• Il dodicesimo bit e un controllo di parita dispari sui precedenti 11.

Il calcolo delle checkword locali puo procedere quindi riutilizzando la formula

per il calcolo del BitStart e la posizione del bit di interesse all’interno della LUT

48


che lo contiene (BitPos):

CheckWordBase = 704+ calcolaBitStart(Y,LUT )+BitPos (3.14)

CheckWordAd j = 32 se y%32 > 7 (3.15)

CheckWord = CheckWordBase +CheckWordAd j (3.16)

Una volta note tutte le checkword per i bit alti del frame si puo procedere allo

XOR bit a bit per il calcolo dei primi 11 bit della parola centrale e al controllo di

parita per l’impostazione del dodicesimo bit (posto a 1 in caso di parita dispari dei

valori alti nei primi 11 bit); i rimanenti 20 bit della parola rimangono a 0.

Bisogna notare che i risultati esposti sono validi per frame che appartengono alla

meta superiore del dispositivo (Top/Bottom = 0). I calcoli sono comunque analo-

ghi, con piccole modifiche di simmetria, per quanto riguarda la meta inferiore del

dispositivo.

3.3.2 Architettura proposta

Gli ottimi risultati ottenuti nell’analisi del bitstream, che hanno portato ad indi-

viduare la codifica delle LUT all’interno dei frame di configurazione, possono

essere sfruttati in un processo evolutivo. Il lavoro di ricerca documentato in [13] e

concentrato soprattutto sulla definizione della struttura hardware dell’area ricon-

figurabile e dei meccanismi che consentono di poterla manipolare, piuttosto che

nell’implementazione dell’algoritmo evolutivo e dei dettagli ad esso legati (atti-

vita che e alla base di questo lavoro di tesi). L’architettura ivi proposta e composta

da:

• Un PowerPC: il processore si occupa dell’esecuzione dell’algoritmo evolu-

tivo, della creazione delle informazioni necessarie per la riconfigurazione

della porzione evolvibile del sistema e della valutazione degli individui.

• L’interfaccia HwIcap: componente sviluppato dalla Xilinx per l’interfac-

ciamento con la logica di configurazione della FPGA, fornita dalla Internal

Configuration Access Port.

49


• Il Controller EHW: interfaccia per l’I/O degli individui implementati nel-

l’area riconfigurabile.

Per il sistema esposto in [13] si e deciso di realizzare una soluzione basata sulla

manipolazione del bitstream piuttosto che sfruttare i Circuiti Virtuali Riconfigu-

rabili. Questa scelta e dovuta al fatto che l’uso dei VRC richiede un maggior

numero di risorse e garantisce una minore resistenza ai guasti, pur offrendo una

maggiore rapidita di configurazione. Si possono notare notevoli analogie tra que-

sta architettura e quella implementata da Upegui e Sanchez [31] (in particolare

ci si riferisce al terzo metodo, basato su una manipolazione piu a basso livello

del bitstream); la principale differenza risiede nel diverso dispositivo utilizzato:

una Virtex-4 in questo caso, una Virtex-2 PRO nel caso analizzato in precedenza.

Per quanto riguarda l’architettura qui esposta non sono stati utilizzati i tool della

Xilinx, ma l’implementazione e avvenuta direttamente su scheda. Per evitare di

danneggiare la FPGA caricando delle configurazioni illegali e per semplificare il

processo di analisi, la strategia e stata quella di modificare solo il contenuto delle

LUT, mantenendo una struttura prefissata di collegamento tra le celle (definita con

una Hard Macro). La scelta di quali connessioni utilizzare e stata fatta a priori al

momento del design della porzione evolvibile del sistema e il routing dei segnali

risulta quindi statico durante l’evoluzione. La capacita di modificare la funzione

calcolata dalle LUT operando direttamente sul bitstream e stata acquisita grazie al

lavoro di analisi del formato di configurazione esposto in precedenza.

L’architettura proposta e stata progettata tenendo conto della tipologia e della di-

sposizione delle risorse disponibili sulla FPGA, delle caratteristiche principali del-

l’algoritmo evolutivo (pur provvisorio e limitato all’evoluzione estrinseca) che si

e utilizzato e del tipo di applicazione per la quale ci si proponeva di utilizzare il

circuito da realizzare. Il sistema evolvibile e stato progettato anche e soprattutto

per poter sfruttare una caratteristica molto importante della Virtex-4 gia accennata

in precedenza: la riconfigurabilita bidimensionale; questo progetto risulta essere

il primo presente in letteratura a sfruttare questa funzionalita offerta dalle nuove

schede della famiglia Virtex. Per poter sfruttare tutte le possibilita offerte del pro-

cesso evolutivo sono stati pensati tre livelli gerarchici: un livello basso, nel quale

50


vengono modificatii singoli bit delle LUT, un livello medio, nel quale vengono

modificati contemporaneamente tutti i bit di una LUT, un livello alto, che permet-

te di aggregare piu LUT in strutture complesse.

Analizzando un po’ piu nei dettagli l’architettura proposta in [13] si puo notare

come, ad alto livello, la struttura e un array bidimensionale di celle, ognuna con

quattro ingressi e una uscita da un bit, connesse tra di loro e organizzate in quattro

righe e n colonne. Tutte le colonne condividono lo stesso segnale di clock. Una

struttura simile era gia presente in letteratura: la novita di quella proposta consiste

nel fatto che le singole celle non sono piu connesse alle altre quattro adiacenti

lungo le direzioni cardinali, ma l’architettura e organizzata in colonne e ogni cella

appartenente alla colonna x e connessa alle uscite delle quattro celle appartenen-

ti alla colonna x − 1 (o direttamente agli ingressi per le celle appartenenti alla

colonna 0). Ogni cella si configura come una funzione logica a cinque ingressi:

quattro sono i segnali in ingresso alla cella, il quinto e rappresentato dallo stato

interno della cella, memorizzato sfruttando uno dei flip-flop presenti nelle slices

della FPGA. Per realizzare il generatore di funzioni a cinque ingressi e necessario

collegare due LUT (una LUTF e una LUTG) a quattro degli ingressi (quelli pro-

venienti dall’esterno) mediante un multiplexer controllato dal quinto ingresso (lo

stato proveniente dal flip-flop). Sia le due LUT sia il multiplexer a cinque ingressi

sono disponibili in una singola slice (Figura 3.7) e questo permette (come limite

teorico, senza considerare i problemi di routing dei segnali) di allocare quattro

celle per ogni CLB. Per definire il comportamento di una singola cella sono ne-

cessari 32 bit: 16 per la codifica della funzione implementata dalla LUTF e 16 per

quella che comanda la LUTG. Quanto esposto porta ad avere una cella di dimen-

sioni 4 volte piu piccole rispetto a quelle proposte in letteratura. Le singole celle

costituiscono il livello piu basso della gerarchia. Il livello superiore e rappresen-

tato da una colonna di celle: ogni colonna puo essere a sua volta vista come una

cella con quattro segnali di ingresso, quattro segnali di uscita e uno stato interno

di quattro bit.

Altra interessante caratteristica di questa architettura e l’allocazione fisica di tutte

le celle di primo livello sulla stessa colonna di slice. In questo modo, e possibile

51


Figura 3.7: Rappresentazione della struttura di una cella dell’architettura proposta in [13].

riconfigurare un’intera colonna o addirittura un intero individuo modificando un

unico frame della FPGA. L’architettura esposta poco sopra conta pero su un input

molto ridotto di soli 4 bit. Per aumentare il numero di bit in ingresso e stata pro-

posta un’architettura modificata che presenta colonne composte da 8 celle, la cui

struttura interna non e stata modificata rispetto a quanto esposto in precedenza.

Le soluzioni proposte per il collegamento delle colonne sono svariate, in Figu-

ra 3.8 sono riportati i due esempi piu interessanti. Lo schema ad alto livello scelto

per implementare il design con datapath da 8 bit collega le celle con coordinata

Y pari ai 4 bit meno significativi in uscita dalla colonna precedente (o dell’in-

gresso nel caso delle celle della colonna 0) e quelle con coordinata Y dispari ai

4 bit piu significativi. Questa soluzione consente di avere uno schema di collega-

mento identico per ogni colonna di celle, il che permette di poter scambiare due

colonne indipendentemente dalla loro posizione all’interno dell’individuo senza

necessita di modificare i collegamenti. Inoltre, anche in questo caso, e sufficiente

riscrivere un unico frame per riconfigurare un’intera colonna (vengono utilizzate

8 slice, cioe una per ogni cella, delle 32 contenute in un frame). Nella Figura 3.9

si puo vedere una rappresentazione della struttura dell’individuo; sono evidenziati

52


Figura 3.8: Esempi di possibili collegamenti tra le colonne.

i collegamenti tra le celle delle diverse colonne. Sono state testate diverse alloca-

zioni degli individui sopra definiti sulla scheda. Tra le disposizioni sperimentate

ne sono emerse due in particolare: una prima allocazione orizzontale consiste nel

posizionare le colonne di celle su colonne di slice adiacenti. In questo modo ogni

colonna che compone l’individuo appartiene ad un frame differente dalle altre e

puo essere riconfigurata indipendentemente da esse. Sulla scheda utilizzata e con

la suddetta disposizione, e possibile impilare fino a quattro colonne di altrettanti

individui per ogni frame e per riconfigurare un individuo allocato usando questa

soluzione e necessario scrivere n frame, dove n e il numero di colonne che lo com-

pongono. Il vantaggio e che, manipolando un solo frame, e possibile riconfigurare

fino a quattro individui (ovvero una colonna di ognuno di quelli impilati all’inter-

no del frame riconfigurato); se si alloca un numero ridotto di individui, tuttavia, si

perde buona parte del vantaggio ottenibile andando a riconfigurare piu soluzioni

candidate in parallelo. Il secondo schema di allocazione proposto e verticale, cioe

tutte le colonne di un individuo sono allocate sulla stessa colonna di slice. Se si

53


Figura 3.9: Struttura dell’individuo con datapath a 8 bit.

sceglie un individuo formato da quattro colonne, questa configurazione ha il van-

taggio di contenere tutto l’individuo in un solo frame, quindi solo questo frame

dovra essere riscritto nel caso l’individuo voglia essere riconfigurato. In generale,

per riconfigurare un individuo composto da n colonne, sara necessario riscrivere

n/4 frame.

L’ultima parte di [13] tratta della progettazione di un componente che funga da

interfaccia in grado di gestire i segnali di controllo necessari per il funzionamento

del design proposto, di sottoporre il dato di ingresso al circuito e recuperare il dato

54


in uscita e di inviare e ricevere i dati di ingresso e uscita verso il PowerPC. Tale

componente, denominato Controller EHW, e un IP-core in grado di interfacciarsi

con il PowerPC tramite il bus PLB. Il funzionamento del componente e piuttosto

semplice: letto un segnale di ingresso di 8 bit il componente lo instrada verso l’in-

dividuo allocato sulla board; dopo 4 cicli di clock il segnale di uscita (anch’esso

di 8 bit) avra un valore stabile, pari a cio che e stato computato dall’individuo.

3.3.3 Ulteriori tentativi

In letteratura e davvero ridotto il numero di lavori relativi all’evoluzione a grana

fine su Virtex-4 o successive (che permettono di sfruttare la riconfgurabilita bidi-

mensionale). In [38] Rafla descrive un framework evolutivo basato su Virtex-4 e

progettato per la Computer Vision, in particolare per l’image processing. Tuttavia

nel documento non sono spiegati i dettagli implementativi del sistema; oltretut-

to l’autore afferma, erroneamente, che con la FPGA utilizzata non e possibile

effettuare riconfigurazione interna. Altro lavoro interessante per gli argomenti

qui trattati e [39]. In esso vengono presentate tre diverse soluzioni al problema

dell’evoluzione intrinseca su FPGA:

• un sistema basato su riconfigurazione a basso livello run-time;

• un sistema che utilizza la libreria JBits;

• un sistema che si caratterizza per l’utilizzo di piu schede (Multi-Board).

I primi due sistemi proposti effettuano una evoluzione gate-level, mentre il terzo

propone una evoluzione a livello funzionale. Per i nostri scopi il sistema piu in-

teressante risulta essere il primo; sfortunatamente pero esso viene solo accennato

nel documento, poiche la non conoscenza del formato del bitstream non ne ha

permesso l’implementazione. Gli altri due sistemi sono stati infatti studiati come

soluzione ai problemi scaturiti dal primo tentativo.

Come gia accennato, il lavoro in [13] (il cui contenuto e stato riassunto in questo

Capitolo) risulta quindi essere il piu importante finora in questo ambito e merita

quindi di essere preso come base di partenza per questo lavoro di ricerca.

55


56

Capitolo 4

Sistema Evolutivo

La trattazione presentata in questo capitolo riguarda il cuore del lavoro svolto per

questa tesi: viene infatti esposto quanto e stato fatto per la progettazione e l’ef-

fettiva implementazione del sistema evolutivo. Nella Sezione 4.1 vengono trattate

le strutture dati utilizzate per la rappresentazione delle popolazioni di soluzioni

candidate da far evolvere; successivamente (Sezione 4.2) si passa a presentare

l’implementazione dell’algoritmo evolutivo utilizzato. Infine le Sezioni 4.3 e 4.4

trattano, rispettivamente, dell’utilizzo del Controller EHW e dell’interfaccia di

riconfigurazione HwIcap.

4.1 Rappresentazione e strutture dati

Per realizzare un software che potesse essere il piu possibile flessibile e parametri-

co si e scelto di modellare gli individui in memoria a un livello logico piu leggibile

e strutturato rispetto al bitstream che li rappresenta su scheda.

Sono stati quindi creati degli opportuni tipi e strutture di dati che rappresentano

le generazioni a vari livelli (dalla popolazione ai bit di codifica delle Look Up Ta-

bles) e si e scelto di effettuare le operazioni genetiche su questi oggetti strutturati,

in modo da avere un controllo ad alto livello sul processo di evoluzione.

57

CAPITOLO 4. SISTEMA EVOLUTIVO

4.1.1 Popolazioni e individui

Una popolazione e rappresentata come una struttura dati che permette di specifi-

care il numero progressivo della generazione corrispondente durante l’evoluzione

e contiene un vettore di individui. La rappresentazione degli individui ha richiesto

qualche decisione sulla loro struttura, valutata anche in base alle possibilita offerte

dallo hardware utilizzato. In particolare ogni individuo e formato da una matrice

di celle contenenti ognuna due Look Up Tables (LUT), che codificano i circuiti

che costituiscono fisicamente l’individuo su scheda (per una spiegazione piu esau-

stiva in merito si veda la Sottosezione 2.1.2). La matrice di celle e suddivisa in

moduli (un modulo corrisponde ad una colonna della matrice) e la sua dimensione

e del tutto parametrica ed esprimibile in dimensione (DIM MODULO) e numero

(DIM INDIVIDUO) dei moduli (Figura 4.1). La struttura dati di ogni individuo

permette inoltre di memorizzare il fitness calcolato durante l’evoluzione.

4.1.2 Rappresentazione delle celle

Data la struttura dell’individuo, e stato necessario trovare una rappresentazione ef-

ficace per le due LUT presenti in ogni cella. Vista l’assenza in C di un tipo di dato

binario o booleano si e scelto di rappresentare le LUT di ogni cella accorpandole

in un’unica stringa di 32 bit, rappresentata con un intero senza segno (denominato

int32), utilizzando i bit piu significativi per le LUTF e i bit meno significativi per

le LUTG (Figura 4.2). La scelta di definire un tipo apposito e stata dettata dalla

iniziale necessita di sviluppare il codice su una architettura (x86 64) diversa da

quella della fpga (powerpc) in modo che, in caso di diversita nella dimensione

dei tipi primitivi, sarebbe bastato modificare la definizione dell’int32, senza altre

conseguenze sul codice.

Per la manipolazione diretta dei singoli bit delle LUT (necessaria, ad esempio,

per estrarre un certo bit da una LUT o per operare mutazioni a basso livello) sono

state definite delle opportune funzioni che sfruttano gli operatori bitwise del C.

In particolare sono state implementate funzioni che permettono di leggere, impo-

stare a 1 o a 0 o invertire un certo bit di una LUT. In questo modo la gestione

58


Figura 4.1: Rappresentazione gerarchica di un individuo.

Figura 4.2: Rappresentazione di una cella su di un int32.

di qualsiasi operazione sulle celle puo essere fatta operando a piu livelli: a basso

livello, direttamente sui singoli bit di codifica, oppure ad alto livello, modificando

direttamente tutta una LUT o addirittura entrambe le LUT di una cella.

59


4.1.3 Altri tipi di dato

Durante l’implementazione del codice, sempre nel tentativo di limitare le riper-

cussioni in caso di diverse rappresentazioni con il cambio di architettura, e stato

ritenuto opportuno definire altri due tipi di dato per codificare una stringa di 16 bit

(int16) e un singolo byte.

4.2 Evoluzione ed operatori genetici

L’evoluzione delle soluzioni candidate avviene all’interno di un ciclo che si ripete

fino al raggiungimento di una delle condizioni di terminazione (raggiungimen-

to del numero massimo di generazioni, presenza di un individuo con fitness pari

o superiore ad una certa soglia o individui troppo simili tra loro, ovvero varianza

troppo bassa all’interno della popolazione), valutate rispetto a valori di soglia defi-

niti a seconda del contesto evolutivo. Il seguente Algoritmo 2 e una trascrizione in

pseudocodice dell’algoritmo genetico implementato in linguaggio C per il sistema

evolutivo, che viene trattato piu nel dettaglio nella prossima Sottosezione 4.2.1.

4.2.1 Popolazione e individui

Oltre alla dimensione degli individui e possibile specificare la cardinalita delle

popolazioni, che si mantiene costante durante l’evoluzione.

Da un punto di vista dell’algoritmo genetico l’evoluzione comincia con la crea-

zione di una prima popolazione, le cui celle vengono inizializzate in modo casuale

(eventualmente si puo scegliere di inizializzarle a partire da un set predefinito di

configurazioni), e con il calcolo del fitness degli individui cosı generati. Dopo

questa fase di inizializzazione puo cominciare il ciclo di evoluzione, che prevede

l’utilizzo dei classici operatori genetici di elitismo, mutazione e crossover.

Da un punto di vista implementativo si e cercato, per quanto possibile, di otti-

mizzare l’esecuzione, evitando inutili copie di dati durante l’evoluzione. Questa

ricerca si e scontrata con il problematico supporto da parte del processore della

FPGA per l’allocazione dinamica della memoria. La soluzione che e stata per-

60


Algoritmo 2 Pseudo-codice del ciclo evolutivo utilizzato.1: pop← newPopolazione()

2: nextPop← newPopolazione()

3: InizializzazioneHwIcap()

4: InizializzazioneCasuale(pop)

5: Valutazione(pop)

6: while (numGenerazione() < nMaxGenerazioni &&

bestFitness(pop) < maxFitness &&

varianza(pop) > minVarianza) do7: Elitismo(pop,nextPop)

8: Crossover(pop,nextPop)

9: Mutazione(pop,nextPop)

10: Valutazione(nextPop)

11: pop← nextPop

12: end while13: return pop

61


corsa e di istanziare in modo separato le strutture dati e dei puntatori ad esse,

in modo da poter eseguire dei semplici reindirizzamenti dei puntatori piuttosto

che delle dispendiose copie. In fase di inizializzazione vengono quindi dichiarate

due popolazioni, delle quali una e la reale prima generazione e l’altra e utilizzata

per compilare la generazione successiva durante l’evoluzione. Al termine di ogni

iterazione del ciclo evolutivo i puntatori alle due strutture vengono scambiati, in

modo che la nuova popolazione attuale punti alla struttura appena generata e la

struttura dati della vecchia popolazione venga utilizzata per essere riempita con

gli individui della generazione ancora successiva. Allo stesso modo anche all’in-

terno di una popolazione gli individui sono istanziati come puntatori a strutture

dichiarate separatamente, in modo da facilitare il riordino della popolazione stes-

sa in base al fitness degli individui, utile per lo sfruttamento dell’elitismo.

Ad ogni ciclo evolutivo gli individui della generazione attuale evolvono in quella

successiva utilizzando le classiche operazioni genetiche di elitismo, mutazione e

crossover. Inizialmente alcuni individui vengono copiati per elitismo, mentre per

tutti gli altri possono avvenire sia la mutazione che (a coppie) il crossover.

4.2.2 Elitismo

Il supporto all’elitismo e implementato in modo molto semplice nel ciclo evolu-

tivo. Ad ogni iterazione la prima cosa che viene fatta e copiare gli N migliori

individui della vecchia popolazione in quella nuova. Il numero Nelite degli indivi-

dui scelti per elitismo dipende dalla costante PERC ELITISMO, che indica la di-

mensione dell’elite di individui che sopravvivono, in percentuale sulla cardinalita

della popolazione; in particolare si ha:

Nelite = |Popolazione| ∗PERC ELIT ISMO (4.1)

4.2.3 Mutazione

Grazie alla struttura modulare della rappresentazione degli individui l’implemen-

tazione del classico operatore genetico di mutazione permette di operare, a se-

conda delle necessita, a diversi livelli. Assegnando alla costante LIVELLO MUT

62


uno tra gli opportuni valori predefiniti e possibile scegliere fra cinque granularita

di mutazione; in particolare (in ordine crescente di finezza):

• livello modulo (costante LIVELLO MODULO):

La mutazione dell’individuo avviene reinizializzando in modo casuale uno

tra i moduli dell’individuo.

• livello cella (costante LIVELLO CELLA):

L’individuo viene mutato con una nuova inizializzazione casuale di una sua

cella (ovvero di due sue LUT adiacenti).

• livello bit:

Questo livello permette la mutazione a granularita piu fine, invertendo i bit

delle LUT dell’individuo; sono possibili tre diverse scelte:

– un singolo bit (costante LIVELLO BIT):

L’individuo mutato presenta un unico bit invertito rispetto all’indivi-

duo mutante.

– un bit per modulo (costante LIVELLO MODULO BIT):

Viene invertito un singolo bit per ogni modulo dell’individuo.

– un bit per cella (costante LIVELLO CELLA BIT):

La mutazione inverte un bit all’interno di ogni cella dell’individuo.

Le diverse scelte che vengono operate a seconda del livello scelto (ovvero la scel-

ta della sezione o del bit da modificare) sono fatte in maniera casuale, sfruttando

la funzione pseudo-random offerta dal linguaggio C rand(). Vista l’assenza sulla

board utilizzata di un orologio di sistema, non e stato possibile utilizzare (co-

me viene in genere fatto) la funzione time() per l’inizializzazione della rand();

si e quindi scelto di utilizzare una combinazione lineare di indirizzi di variabili

precedentemente istanziate in modo da ottenere, tra le diverse esecuzioni, valori

ragionevolmente casuali.

Come richiesto da qualsiasi algoritmo genetico e possibile anche definire la proba-

bilita con cui, individuo per individuo, avviene la mutazione; questa impostazio-

63


ne viene fatta assegnando alla costante PROB MUTAZIONE un valore decimale

compreso tra 0 (nessuna mutazione) e 1 (mutazione certa per ogni individuo).

4.2.4 Crossover

Il crossover avviene per coppie di individui della popolazione; due individui fanno

da genitori e vengono sezionati lungo una certa linea. L’operazione, se avviene,

genera due figli, ottenuti affiancando in modo alternato le quattro porzioni otte-

nute dal taglio degli individui genitori. Anche in questo caso, come per la muta-

zione, e possibile operare su piu livelli, che permettono di scegliere la modalita di

sezionamento degli individui genitori:

• livello modulo (costante LIVELLO MODULO):

Il taglio avviene lungo un modulo; quindi gli individui figli sono costituiti

da una giustapposizione dei moduli degli individui genitori.

• livello cella (costante LIVELLO CELLA):

La linea di sezione puo attraversare un modulo all’altezza di una qualsiasi

delle sue celle.

In Figura 4.3 sono rappresentati graficamente i due diversi tipi di tracciato della

linea di taglio per il crossover. Sempre in modo analogo alla mutazione, anche per

il crossover c’e una costante a cui assegnare uno tra i valori sopracitati per la scelta

della granularita (LIVELLO CROSS) e una costante (PROB CROSSOVER) in

cui indicare la probabilita di esecuzione del crossover per ogni coppia di individui;

nel caso in cui il crossover non venga eseguito i due figli, nella nuova generazione,

coincidono con gli individui genitori della vecchia generazione.

4.3 Controller EHW

Perche l’algoritmo evolutivo, implementato come descritto nella Sezione prece-

dente, possa funzionare correttamente e necessario valutare il funzionamento dei

64


Figura 4.3: Modalita di esecuzione del taglio degli individui genitori a seconda della

granularita scelta.

circuiti che costituiscono il fenotipo delle soluzioni candidate (ovvero degli indi-

vidui in evoluzione); per fare cio e stata utilizzata l’interfaccia fornita dal Con-

troller EHW. Questo componente (il cui funzionamento e descritto nella Sottose-

zione 2.2.3) offre una interfaccia di Input/Output verso e dagli individui presenti

sulla FPGA.

4.3.1 Utilizzo dell’area riconfigurabile

L’algoritmo genetico implementato non sfrutta per ora le possibilita offerte dal

Controller EHW in merito alla riconfigurazione e valutazione concorrente di in-

dividui diversi. Si e comunque deciso, in vista di sviluppi futuri, di sfruttare la

65


possibilita di avere piu di un individuo caricato sulla FPGA. Sono stati dunque

attuati i seguenti accorgimenti:

• Sono stati istanziati due array contenenti le coordinate X e Y delle posizioni

del CLB contenente la prima slice del frame entro cui vanno codificati gli

individui nella zona riconfigurabile.

• A partire dal primo individuo valutato durante il processo evolutivo si uti-

lizzano in sequenza i frame indicati nei due array di coordinate.

Questo modo di operare consente, se si utilizza un numero di individui al piu pari

al numero di individui gestibili tramite il Controller EHW, di avere contempo-

raneamente sulla scheda tutte le soluzioni candidate della popolazione che viene

processata in quel momento. Per ora non ci sono evidenti vantaggi da questo

punto di vista, ma il framework e gia pronto a supportare sviluppi in termini di

parallelizzazione delle operazioni di valutazione e riconfigurazione.

4.3.2 Valutazione degli individui

Chiaramente la valutazione delle performance dei singoli individui viene fatta se-

condo una certa funzione di fitness, che e pero del tutto dipendente dall’appli-

cazione per cui si mette in atto il processo evolutivo e va quindi riprogettata a

seconda di cio che si desidera ottenere. In particolare questa consiste tipicamente

in una valutazione del valore dato in uscita dalla soluzione candidata in dipenden-

za da cio che le viene fornito in ingresso.

Da un punto di vista generale e invece interessante l’utilizzo fatto delle funzioni C

offerte dal driver del Controller EHW per gestire le operazioni di ingresso e uscita

degli individui. A questo scopo sono state scritte due apposite funzioni che effet-

tuano le operazioni di basso livello richieste dal componente, esponendo al ciclo

evolutivo un’interfaccia di alto livello verso le operazioni di comunicazione con

le soluzioni candidate presenti sulla scheda. La funzione di invio dell’ingresso ad

un certo individuo opera come segue:

• Viene azzerato il registro di controllo (EHW Control) della Management

Logic per iniziare una nuova operazione.

66


• Si pone in EHW Unit Address l’indirizzo (numero progressivo da 0 a N−1,

dove N e il numero di individui supportati) dell’individui a cui inviare i dati.

• Sul registro Input Data viene scritto l’input desiderato.

• Si pone a 1 il valore dell’ultimo bit del registro EHW Control, avvisando

la Management Logic che il dato in ingresso e pronto e deve essere inviato

all’individuo precedentemente indirizzato.

Gli individui utilizzati richiedono 4 cicli di clock per la stabilizzazione dell’uscita,

una volta fornito loro il dato in ingresso; dopo questo tempo il software si occupa

di leggere l’output dato dall’individuo al momento analizzato in questo modo:

• Si attende la certezza della validita dell’output verificando che il bit numero

8 del registro Final State sia a 1.

• L’uscita fornita dall’individuo viene letta dal registro Output Data.

Per come si opera non e necessario verificare che l’output letto sia effettivamente

stato prodotto dall’individuo che si vuole considerare; questa verifica potrebbe

rendersi necessaria in futuro nel caso di valutazione parallela delle soluzioni.

La parte che rimarra fissa tra le varie implementazioni della funzione di fitness

dovra quindi utilizzare le funzioni di I/O sopra esposte fornendo agli individui un

ingresso di interesse e valutando secondo i criteri evolutivi scelti l’uscita fornita.

4.4 Interfaccia HwIcap

Una volta definita la struttura degli individui (sia da un punto di vista logico che

da un punto di vista circuitale) e necessario, per il funzionamento dell’algoritmo

genetico, che sia possibile riprogrammare la FPGA con gli individui che vengono

via via generati, in modo che l’evoluzione possa realmente avvenire. Per fare que-

sto e stata utilizzata l’interfaccia di riconfigurazione HwIcap offerta dalla Xilinx

per la Virtex-4, che permette la riconfigurazione parziale di uno o piu frame. La

struttura scelta per gli individui si accorda perfettamente con questa possibilita e

permette di riconfigurare esattamente ogni individuo posto sulla scheda.

67


4.4.1 Calcolo degli indirizzi

Prima di passare all’HwIcap il bitstream vero e proprio, contenente la configu-

razione desiderata, e necessario calcolare la parola di configurazione del registro

FAR in funzione delle coordinate X e Y del frame che si desidera riconfigurare.

Le regole che permettono di eseguire il calcolo correttamente vengono analizza-

te in [13] e sono riportate all’interno della Sottosezione 3.3.1. Nella parte soft-

ware e stata quindi implementata una funzione che calcola il valore degli indirizzi

Top/Bottom, Row, Major e Minor in base alla posizione (X, Y) della prima slice

del frame da riconfigurare. Una volta calcolate, tutte queste variabili vengono uti-

lizzate come input per la funzione di scrittura dei frame, fornita dalla Xilinx con

la libreria del componente HwIcap.

4.4.2 Generazione del bitstream parziale

Alla funzione di libreria per la riconfigurazione va (ovviamente) fornito in input

anche il bitstream che controlla la configurazione del frame. Visto che si ha la

necessita di riconfigurare un solo frame il bitsream che viene generato e un bi-

tstream parziale. Anche in questo caso la conoscenza della struttura del bistream

con il posizionamento delle varie LUT e della parola centrale e documentata in

[13] ed e stato necessario implementare del codice che generasse effettivamente

questa struttura a partire dalla rappresentazione di alto livello del contenuto delle

celle degli individui. Questa fase ha richiesto un certo impegno per riuscire a com-

prendere con precisione la codifica delle informazioni utilizzata all’interno delle

parole del bitstream parziale e a realizzare una effettiva traduzione del genotipo

dell’individuo.

Un primo problema incontrato durante l’implementazione e stato quello della di-

versa organizzazione in blocchi tra la rappresentazione di una singola cella (co-

stituita dalla sua coppia di LUT) e il bitstream finale usato per la riconfigurazione

parziale. Il mattone elementare del bitstream e un blocco di 5 bytes, mentre le

LUT sono salvate in un’unica parola di 4 byte: ci saranno quindi degli spazi tra il

contenuto di una LUTG e quello di una LUTF. La posizione del contenuto delle

68


LUT all’interno dei 5 byte e dato dalle formule esposte nella Sottosezione 3.3.1.

E’ stato quindi necessario scrivere una funzione che calcolasse il bitStart (fun-

zione solo della coordinata y e del tipo di LUT). Inoltre prima di poter generare

il bitstream parziale si deve calcolare la parola centrale del frame in funzione

del contenuto di tutte le LUT: ogni volta che il frame viene modificato la parola

centrale viene ricalcolata facendo lo XOR degli effetti relativi al valore di ogni

singolo bit. Per effettuare tutto cio e stato necessario implementare una serie di

funzioni che fanno un pesante utilizzo degli operatori bitwise del C. Una volta

calcolate tutte le informazioni necessarie si puo procedere alla generazione del

bistream parziale e alla sua scrittura su scheda.

4.4.3 Riconfigurazione degli individui

La funzione che scrive sulla board la stringa di configurazione si articola in tre

fasi:

• Il bitstream viene calcolato secondo i dettagli prima esposti.

• Viene letto il frame attualmente sulla scheda nella posizione in cui si vuole

andare a riconfigurare.

• Il frame letto viene modificato inserendo il frame appena calcolato e quindi

riscritto sulla scheda.

E’ stato scelto di operare in questo modo per mantenere un approccio conservati-

vo, infatti si e notato che la lettura di un frame restituisce un array di dimensioni

doppie rispetto a quelle che ci si aspetta. Analizzando il contenuto del buffer di

lettura si vede che il frame che si trova realmente sulla scheda e ubicato nella se-

conda meta dell’array, mentre nella prima meta si trova un certo numero di parole

corrispondente alla dimensione di un altro frame. Non e stato verificato se queste

parole aggiuntive siano solo un riempitivo per necessita interne ai tool della Xili-

nx o se il loro contenuto codifichi qualche informazione relativa al frame letto; e

stato quindi deciso, come detto, di effettuare una lettura preventiva e di riutilizzare

69


lo stesso buffer per la scrittura, lasciando invariata la parte iniziale e sostituendo

solo il contenuto della seconda parte, che contiene il frame da scrivere.

4.4.4 Validazione dei dati

Per essere certi che cio che viene scritto sulla scheda sia esattamente cio che viene

calcolato dall’applicazione, e stata implementata una funzione di verifica e valida-

zione dei dati. Questa funzione non fa altro che confrontare il bitstream calcolato

logicamente con quello presente fisicamente sulla scheda. Viene quindi riletta di-

rettamente dalla scheda la stringa di configurazione appena scritta e la si confronta

bit a bit con quella generata a partire dal contenuto delle LUT presente in memo-

ria. In molte delle prove effettuate durante il periodo di sviluppo dell’algoritmo e

stato attivato questo meccanismo di validazione e si e constatato che talvolta alcu-

ni bit risultano differenti da come ci si aspetta. Ulteriori approfondimenti hanno

appurato che i bit differenti sono posizionati anche all’interno del contenuto delle

LUT e vanno quindi a modificare la configurazione effettiva del dispositivo. Si e

inoltre notato che le anomalie rilevate variano con il variare degli individui con-

figurati e dipendono quindi dal bitstream scritto. Un’altra dipendenza emersa e

rispetto alla specifica architettura caricata sulla scheda; diverse sintesi di archi-

tetture equivalenti (o con piccole variazioni) hanno infatti dato risultati diversi in

termini di affidabilita della scrittura (talvolta presentando gli errori detti e talvolta

non presentandone affatto). A causa di questa variabilita del fenomeno non e stato

possibile effettuare ulteriori test per appurarne le reali cause e si e deciso di tra-

scurarlo (visto il ridotto impatto generato), utilizzando per la configurazione della

scheda un’architettura che si sia provata affidabile (ovvero sia esente da errori di

riconfigurazione).

70

Capitolo 5

Risultati Sperimentali

In questo Capitolo vengono presentate alcune analisi sperimentali svolte sul si-

stema evolutivo. Viene dapprima proposta una sintesi delle operazioni di adatta-

mento dell’architettura gia proposta all’interno del gruppo HERA che si sono rese

necessarie per ottenere un sistema funzionante (Sezione 5.1); in seguito si defi-

nisce la specifica architettura utilizzata per i successivi test (Sezione 5.2). Infine

vengono proposti alcuni dati sperimentali relativi al funzionamento del sistema

evolutivo tra cui, per prima cosa, viene esposta una semplice analisi temporale

(Sezione 5.3), utile per valutare le attuali prestazioni del sistema. Come ulterio-

re punto di validazione e stata realizzata l’evoluzione intrinseca di un generatore

di parita pari, in modo analogo a quanto fatto nell’esperimento proposto in [13],

basato pero su evoluzione estrinseca realizzata con un simulatore software; que-

st’analogia permette di effettuare un confronto tra i rispettivi risultati e di trarre

qualche conclusione sul lavoro svolto.

5.1 Sintesi dell’architettura

Durante la sintesi dell’architettura per i test (effettuata con EDK, vedere la Sotto-

sezione 2.3.1) si sono riscontrati alcuni problemi legati ad alcune scelte progettuali

effettuate nei lavori precedenti. In particolare ci sono state difficolta in merito alla

definizione dei vincoli di area per i vari componenti, necessari per fare in modo

71

CAPITOLO 5. RISULTATI SPERIMENTALI

che nessuna parte di logica fosse implementata nell’area riconfigurabile. I vincoli

proposti in [13] per la sintesi della medesima architettura (ma senza il controllore

HwIcap e con un solo individuo nell’area riconfigurabile) non si sono rivelati ade-

guati. La sintesi del controllore HwIcap richiede infatti una grande porzione di

area del chip e si e dunque stati costretti ad allargare l’area dedicata alla logica di

controllo, pur dovendo stavolta mantenere l’area riconfigurabile abbastanza gran-

de per contenere 16 individui. Questo rilassamento dei vincoli ha pero portato

ulteriori problemi in merito alla modalita di espressione dei vincoli stessi.

In [13] si propone infatti di porre i vincoli (espressi nel file system.ucf di EDK)

come segue:

INST "/*" AREA_GROUP=All;

AREA_GROUP "All" RANGE=SLICE_X0Y0:SLICE_X23Y127;

In questo modo viene creato un AREA GROUP denominato All per tutta la lo-

gica e si indica al programma di mantenere l’area da esso occupata tra la slice

con (X ,Y ) = (0,0) e la slice con (X ,Y ) = (23,127); nel seguito dello stesso file

si procede ad istanziare l’individuo riconfigurabile nell’area lasciata libera dalla

logica. Come accennato sopra, anche allargando l’area adibita alla logica si sono

presentati problemi di funzionamento dell’interfaccia HwIcap dovuti a problema-

tiche legate alla sintesi architetturale. Facendo riferimento alla guida della Xilinx

sull’utilizzo dei vincoli di area ([40]) si e definita una nuova formulazione degli

stessi, definendo un AREA GROUP per la zona riconfigurabile e imponendo che

in questa zona non fossero poste parti di altri circuiti. I vincoli sono stati quindi

cosı espressi nel file system.ucf :

INST ".../Inst_ehw_core_logic_0/..."

AREA_GROUP="ehw_area";



...

72






AREA_GROUP "ehw_area"

RANGE="SLICE_X40Y0:SLICE_X46Y127";

AREA_GROUP "ehw_area" PLACE=CLOSED;

AREA_GROUP "ehw_area" MODE=RECONFIG;

Come si vede dal codice l’area riconfigurabile e assegnata all’AREA GROUP de-

nominato ehw area, che viene limitato tra la slice con (X ,Y ) = (40,0) e la slice

con (X ,Y ) = (46,127). viene inoltre imposto (con il vincolo PLACE=CLOSED)

che l’area riconfigurabile non possa essere usata per istanziare parti diverse da

quelle appartenenti al gruppo e che l’area stessa e utilizzata per la riconfigurazio-

ne (MODE=RECONFIG).

Una volta imposti i vincoli vengono istanziare le hard-macro degli individui al-

l’interno delle slice appartententi alla ehw area:


LOC = "SLICE_X40Y96:SLICE_X40Y127";







...





73






Grazie alla revisione dei vincoli di area e stato possibile sintetizzare una architettu-

ra funzionante, la quale presenta le caratteristiche di occupazione di area elencate

nella Tabella 5.1.

Tabella 5.1: Occupazione di area sulla FPGA da parte dell’intero sistema evolutivo.

Risorsa Occupati/e Liberi/e % Occupata

Slice 4372 5472 79%

Flip-Flop 3818 10944 44%

LUT 7672 10944 70%

5.2 Modalita di svolgimento degli esperimenti

Il sistema evolutivo utilizzato per i test e esattamente quello esposto nel Capito-

lo 4, che fa uso dell’interfaccia HwIcap per la riconfigurazione, del Controller

EHW per la gestione di Ingresso/Uscita degli individui e dell’algoritmo genetico

esposto per il controllo del processo evolutivo. In particolare sono stati utilizzati

individui formati da 4 moduli di 8 celle l’uno. Si e scelto di utilizzare un nume-

ro di individui per popolazione pari al numero di individui istanziabili nell’area

riconfigurabile, ovvero 16 (in questo modo tutti e soli gli individui di una popola-

zione sono presenti ad un certo istante sul chip).

Per ogni esperimento e stata implementata una opportuna funzione di valutazio-

ne che si occupa di presentare in ingresso agli individui una sequenza di input

considerata significativa per la loro evoluzione e valutare, per ogni ingresso, la

vicinanza del risultato ottenuto in uscita rispetto al valore desiderato. Nel caso

di evoluzione di un circuito sequenziale i dati in input vengono presentati agli in-

dividui sempre nello stesso ordine, mentre nel caso di evoluzione di un circuito

74


combinatorio si procede alla valutazione modificando ogni volta in modo casuale

l’ordine di presentazione dei valori, per evitare che il circuito faccia uso di in-

formazioni legate all’ordine di presentazione degli input. I parametri utilizzati

per l’evoluzione (ottenuti dopo alcune sperimentazioni ma probabilmente ancora

migliorabili) sono riassunti nella Tabella 5.2 (per il significato delle costanti di

granularita vedere le Sezioni 4.2.3 e 4.2.4). Si fa notare che le prestazioni non so-

no l’oggetto di maggior interesse in questi test (in futuro queste potranno di certo

essere notevolmente migliorate, ad esempio ottimizzando il codice e tarando al

meglio l’algoritmo genetico); qui si vogliono solo proporre alcuni dati riguardo

all’effettivo funzionamento del sistema di evoluzione intrinseca su Virtex-4.

Tabella 5.2: Parametri utilizzati per l’algoritmo genetico durante gli esperimenti

Parametro Valore

Numero individui 16

Perc. Elitismo 10%

Granularita Mutazione LIVELLO MODULO BIT

Prob. Mutazione 0,6

Granularita Crossover LIVELLO CELLA

Prob. Crossover 0,7

5.3 Analisi temporale del ciclo

Prima di passare ad un reale esperimento di evoluzione, e stata svolta (utilizzando

una apposita libreria C) una analisi temporale del sistema di cui vengono breve-

mente riportati i risultati in Tabella 5.3. L’inizializzazione della popolazione e

dell’interfaccia HwIcap vengono operate solo una volta all’inizio del ciclo, quindi

con un numero abbastanza grande di generazioni questi tempi sono trascurabili e

il tempo totale e dato (asintoticamente) dalle sole operazioni di riconfigurazione e

valutazione ripetute durante il ciclo evolutivo. Il tempo di riconfigurazione ripor-

tato in tabella dipende solo dal numero di frame da riconfigurare (in questo caso

ci si riferisce a individui di 8× 4 celle, che occupano un solo frame). Il tempo

75


Tabella 5.3: Tempi medi necessari per le operazioni del ciclo evolutivo.

Operazione Tempo [ms]

Inizializzazione delle popolazione 13,192

Inizializzazione HwIcap 0,147

Riconfigurazione di un individuo 9,391

Valutazione di un individuo 21,78×10−3

di valutazione in tabella e riferito alla verifica dell’uscita dato un certo ingresso;

per ottenere il tempo totale di valutazione per individuo, il tempo qui annotato

va quindi moltiplicato per il numero di volte che ogni candidata soluzione viene

valutata ad ogni ciclo. Dai dati in tabella si nota che il tempo dominante all’inter-

no del ciclo e quello di riconfigurazione; questo e composto dai tempi necessari

per il calcolo del frame e per la scrittura del frame sul chip. Anche questi tempi

intermedi sono stati misurati e si e trovato che circa il 90% del tempo di ricon-

figurazione e dovuto al calcolo del frame; la causa di cio e certamente la non

ottimizzazione del codice C dell’algoritmo evolutivo. In particolare il maggior

impiego di tempo e dovuto alla generazione (ripetuta molte volte per generare un

frame) della struttura-base di 5 byte del bitstream (vedere la Sottosezione 3.3.1)

a partire dalla rappresentazione di LUTF e LUTG in memoria. Questo e dovuto

all’algoritmo implementato, che utilizza diversi cicli annidati con molte operazio-

ni (assegnamenti, operazioni bitwise) all’interno. In merito a questo si vuole far

nuovamente notare che l’obiettivo di questo lavoro di tesi non e il raggiungimento

di alte prestazioni, ma piuttosto la realizzazione di un sistema-base funzionante.

Ci sono quindi ampi margini di miglioramento prestazionale, ad esempio tramite

ottimizzazione del codice o implementazione in hardware di alcune operazioni. I

risultati qui riportati sono quindi da vedere nell’ottica appena proposta.

5.4 Evoluzione di un generatore di parita

Per verificare le reali potenzialita del sistema e stata eseguita l’evoluzione di un

generatore di parita pari. Sono stati effettuati cicli evolutivi per circuiti con ingres-

76


si di dimensione crescente: prima si e evoluto un generatore di parita pari sensibile

a solo 5 degli 8 bit di ingresso, poi un altro sensibile a 6 bit in ingresso e cosı via

fino a considerare tutti e 8 i bit in ingresso. Per questo esperimento la funzione

di valutazione presenta agli individui una sequenza di 8 diversi ingressi in cui gli

eventuali bit non considerati sono invariabilmente uguali a 0, mentre i bit di inte-

resse variano. L’uscita viene valutata sull’ultimo bit dell’output dell’individuo e

il valore desiderato e 1 se sulla stringa di ingresso sono presenti un numero pari di

bit a 1, 0 altrimenti. In linea con quanto fatto nell’analogo esperimenti proposto

in [13] si e valutato ogni individuo proponendo la sequenza di ingresso (riordinata

ogni volta in modo casuale) per 15 volte, in modo da cercare di generare soluzioni

con comportamento combinatorio.

In Tabella 5.4 sono riportati (per i generatori di parita a 5, 6, 7, 8 bit) i dati me-

di ottenuti da 30 ripetizioni dell’esperimento; in particolare e riportato il numero

di generazioni necessario per ottenere una soluzione corretta al 100% (obiettivo

raggiunto in ognuna delle 30 ripetizioni del ciclo evolutivo) e il rispettivo tempo

di evoluzione. Vengono inoltre riportati, per un confronto, i dati riportati in [13]

(qui corredati anche dei tempi di evoluzione, la cui fonte e interna al gruppo HE-

RA) per il medesimo esperimento con l’uso di evoluzione estrinseca tramite un

framework di simulazione.

Si puo notare come sia il numero di generazioni necessarie che i tempi speri-

Tabella 5.4: Risultati degli esperimenti sull’evoluzione del generatore di parita (valori

medi su 30 ripetizioni) e confronto con i dati di evoluzione estrinseca.

Dati sperimentali Dati Simulazione [13]

N Bit5

6

7

8

N Gen Tempo [s]1245,7 242,9

1452,2 283,2

1491,3 290,8

1524,8 297,3

N Gen Tempo [s]198,5 7,9

231,7 18,3

238 37,6

243,3 76,8

mentali siano notevolmente piu alti rispetto a quelli ottenuti mediante evoluzio-

ne estrinseca e riportati in [13]. Per quanto riguarda la piu lenta convergenza

77


dell’algoritmo genetico in termini di numero di generazioni necessarie, la causa

principale della discrepanza con i dati di confronto e la grande differenza nelle

cardinalita delle popolazioni utilizzate (16 individui in questo lavoro, mentre 100

nell’esperimento di confronto). Per quanto riguarda i tempi, invece, il valore piu

elevato e dovuto (oltre che al maggior numero di generazioni necessarie) alla non

ottimizzazione del codice dell’algoritmo genetico e alla scarsa potenza di calcolo

del PowerPC di cui e dotata la Virtex-4 rispetto alle workstation usate durante la

valutazione estrinseca (una analisi temporale del ciclo evolutivo qui utilizzato e

proposta nella Sezione 5.3).

Un’altra osservazione che si puo fare sui dati e che il divario tra i risultati dell’evo-

luzione intrinseca rispetto a quelli dell’evoluzione estrinseca si riduce al crescere

del numero di bit considerati per il calcolo della parita. Questo e dovuto al fatto

che, con evoluzione estrinseca, e richiesto un tempo via via maggiore per la valu-

tazione di un certo individuo con un numero crescente di bit in ingresso; cio non e

invece vero se si opera con i circuiti delle soluzioni candidate realmente istanziati

sulla FPGA.

78

Capitolo 6

Conclusioni

In questo elaborato sono stati presentati i dettagli relativi alla progettazione e alla

sviluppo di un sistema per l’evoluzione intrinseca basato su FPGA. Per poter por-

tare a termine questo studio e stato necessario utilizzare le informazioni, presenti

in letteratura, relative all’analisi del bitstream della FPGA Virtex-4 utilizzata, il

cui formato non e documentato dalla casa produttrice. Il sistema realizzato sfrutta

(attraverso l’interfaccia HwIcap, fornita da Xilinx) la porta ICAP per effettuare la

riconfigurazione dinamica degli individui presenti sulla scheda (l’area riconfigu-

rabile ne puo contenere fino a un massimo di 32 per volta) e il Controller EHW

(IP-CORE realizzato appositamente all’interno del gruppo di ricerca HERA) per

implementare la comunicazione da e verso gli individui stessi. L’utilizzo di queste

risorse ha permesso di introdurre notevoli novita rispetto alle architetture finora

presentate in letteratura. In primo luogo e stato possibile sfruttare la possibilita

di riconfigurazione parziale 2D offerta dal chip Virtex-4 (pratica che permette un

notevole risparmio temporale rispetto alla riconfigurazione monodimensionale di-

sponibile sulle FPGA Xilinx fino alla Virtex 2-PRO); inoltre il sistema evolutivo

e in grado di operare l’evoluzione intrinseca delle popolazioni, cioe tutto il ciclo

evolutivo avviene autonomamente sul dispositivo embedded, senza necessita di

simulazioni esterne. La combinazione di questi due fattori rappresenta una novita

nel campo dell’evoluzione hardware e pone le basi per svariate possibilita di ulte-

riore ricerca.

79

CAPITOLO 6. CONCLUSIONI

Per il raggiungimento dei risultati esposti sono state riscontrate (e superate) diver-

se problematiche: in particolare ha richiesto un certo impegno la piena compren-

sione della rappresentazione delle LUT all’interno del bitstream parziale, neces-

saria per poter realizzare un’adeguata rappresentazione in memoria delle stesse

e, successivamente, la traduzione che permette di creare la stringa di riconfigura-

zione degli individui. Ulteriori intoppi sono stati causati dall’uso dell’HwIcap: le

specifiche di funzionamento fornite dalla guida per l’utente sono infatti in parte in-

complete ed e stato necessario analizzare con attenzione il codice C delle funzioni

di esempio proposte per la riconfigurazione prima di essere in grado di far operare

correttamente il componente. Neanche l’integrazione del Controller EHW e stata

banale: in questo caso si sono rese necessarie alcune revisioni del codice VHDL

del componente a causa di un suo malfunzionamento non emerso in precedenza.

Il sistema presentato e il primo del suo genere e di certo presenta alcune limitazio-

ni. Da un punto di vista fisico, il chip a disposizione (Xilinx Virtex-4 XC4VFX12-

FF668-10) non e molto capiente in termini di numero di blocchi configurabili:

questo fatto, unito alla necessita di istanziare l’interfaccia l’HwIcap (che e piutto-

sto pesante in termini di occupazione di area per la sintesi), ha richiesto la riformu-

lazione dei vincoli di area per i componenti e l’imposizione di un limite superiore

alla capienza dell’area riconfigurabile (32 individui al massimo). Certamente se

fosse stato possibile utilizzare un chip piu capiente si sarebbero potuti ottenere

risultati migliori con sforzo minore. Un altro fronte di possibili (e auspicabili)

miglioramenti e quello dei tempi di esecuzione dell’algoritmo (misurati e tabula-

ti nel Capitolo 5), che risultano piuttosto elevati soprattutto per quanto riguarda

il calcolo del frame di riconfigurazione; questo accade poiche non si e puntato

all’ottimizzazione del codice scritto, ma piuttosto alla produzione di un sistema

funzionante e robusto.

6.1 Sviluppi futuri

Come accennato poco sopra, lo sviluppo del sistema presentato in questo elabora-

to offre svariati spunti per lavori e sviluppi, sia nell’immediato futuro che a lungo

80


termine. Quelli considerati i piu importanti sono elencati di seguito:

• Provvedere all’ottimizzazione del codice dell’algoritmo genetico per ren-

dere piu rapida l’evoluzione. La maggior parte del tempo necessario a far

girare l’algoritmo e infatti speso per effettuare operazioni algebriche sui da-

ti in memoria e non per interagire coi componenti dell’architettura (a causa

della necessita di tradurre tra diverse rappresentazioni del genotipo). Una

revisione del codice di manipolazione delle stringhe di bit, con una con-

seguente riduzione della complessita computazionale, puo portare notevoli

vantaggi dal punto di vista temporale.

• Implementare la parallelizzazione del calcolo. La versione del Controller

EHW utilizzata permette di interagire con un massimo di 32 individui con-

temporaneamente sul chip; cio potrebbe essere sfruttato, per esempio, per

effettuare la valutazione di meta degli individui mentre l’altra meta viene

riconfigurata (la riconfigurazione 2D non influenza il funzionamento delle

celle non interessate dalla stessa). L’effetto sarebbe un ulteriore risparmio

di tempo nel ciclo evolutivo. Questo sviluppo non dovrebbe richiedere ec-

cessivi sforzi, in quanto il codice e l’architettura proposti in questo lavoro di

tesi sono gia stati predisposti per l’implementazione di questa funzionalita.

• Implementare in hardware alcune funzioni software. Si potrebbe pensare

di implementare direttamente in hardware pian piano tutte le funzioni del-

l’algoritmo evolutivo. Un primo passo potrebbe essere quello di integrare

nella logica la valutazione degli individui, quindi gli operatori genetici e in-

fine anche la generazione del bitstream parziale, arrivando a non sfruttare

(o a sfruttare solo marginalmente) il processore general purpose incluso sul

chip.

• Studiare piu approfonditamente l’utilizzo di sistemi analoghi a quello pro-

posto nell’ambito della fault tolerance e dell’adattamento a variazioni delle

caratteristiche ambientali. L’uso di algoritmi evolutivi, infatti, ben si presta

a reagire ai cambiamenti dell’ambiente di lavoro e a modificare la struttu-

81


ra interna del circuito per recuperare piena funzionalita in caso di guasti o

malfunzionamenti.

82

Elenco delle figure

1.1 Visione ad alto livello di un sistema hardware evolvibile. . . . . . 3

2.1 Organizzazione interna di una FPGA. . . . . . . . . . . . . . . . 12

2.2 Collocazione delle risorse di un certo spazio di indirizzamento in

dipendenza dalle coordinate (X, Y). . . . . . . . . . . . . . . . . 15

2.3 Struttura interna del CLB con coordinate (X, Y) = (0, 0) delle

FPGA della famiglia Xilinx Virtex-4. . . . . . . . . . . . . . . . . 16

2.4 Schema a blocchi dell’architettura HERA. . . . . . . . . . . . . . 17

2.5 Diagramma a blocchi della struttura del modulo HwIcap (fonte:

[16]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.6 Grafico temporale dei segnali durante un ciclo di lettura (fonte: [16]) 20

2.7 Grafico temporale dei segnali durante un ciclo di scrittura (fonte:

[16]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.8 Confronto tra la vecchia (sinistra) e la nuova (destra) area riconfi-

gurabile con Management Logic. . . . . . . . . . . . . . . . . . . 22

2.9 Management Logic Black Box . . . . . . . . . . . . . . . . . . . 23

3.1 Struttura della FPGA Xilinx XC6200. . . . . . . . . . . . . . . . 30

3.2 Struttura del VRC proposto da Sekanina [28]. . . . . . . . . . . . 36

3.3 Rappresentazione del flusso evolutivo proposto in [29]. . . . . . . 38

3.4 Rappresentazione della struttura cellulare proposta in [35, 36] . . 41

3.5 Possibile allocazione degli individui con (a destra) e senza (a si-

nistra) possibilita di configurazione 2D. . . . . . . . . . . . . . . 42

83

ELENCO DELLE FIGURE

3.6 Rappresentazione della struttura di un frame della meta superiore

di una Virtex-4 (Top/Bottom = 0) secondo l’analisi presentata in

[13]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.7 Rappresentazione della struttura di una cella dell’architettura pro-

posta in [13]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.8 Esempi di possibili collegamenti tra le colonne. . . . . . . . . . . 53

3.9 Struttura dell’individuo con datapath a 8 bit. . . . . . . . . . . . . 54

4.1 Rappresentazione gerarchica di un individuo. . . . . . . . . . . . 59

4.2 Rappresentazione di una cella su di un int32. . . . . . . . . . . . . 59

4.3 Modalita di esecuzione del taglio degli individui genitori a secon-

da della granularita scelta. . . . . . . . . . . . . . . . . . . . . . 65

84

Elenco delle tabelle

2.1 Risorse disponibili sulla FPGA XC4VFX12-FF668-10. . . . . . . 14

3.1 Struttura del registro FAR. . . . . . . . . . . . . . . . . . . . . . 45

5.1 Occupazione di area sulla FPGA da parte dell’intero sistema evo-

lutivo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

5.2 Parametri utilizzati per l’algoritmo genetico durante gli esperimenti 75

5.3 Tempi medi necessari per le operazioni del ciclo evolutivo. . . . . 76

5.4 Risultati degli esperimenti sull’evoluzione del generatore di parita

(valori medi su 30 ripetizioni) e confronto con i dati di evoluzione

estrinseca. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

85

ELENCO DELLE TABELLE

86

Bibliografia

[1] Jim Torresen. An evolvable hardware tutorial. In Jurgen Becker, Marco

Platzner, and Serge Vernalde, editors, FPL, volume 3203 of Lecture Notes in

Computer Science, pages 821–830. Springer, 2004. (Citato a Pagina 2).

[2] Garrison W. Greenwood and Andrew M. Tyrrell. Introduction to Evolvable

Hardware: A Practical Guide for Designing Self-Adaptive Systems (IEEE

Press Series on Computational Intelligence). Wiley-IEEE Press, 2006.

(Citato alle Pagine 2 e 8).

[3] John H. Holland. Adaptation in Natural and Artificial Systems: An In-

troductory Analysis with Applications to Biology, Control, and Artificial

Intelligence. The MIT Press, April 1992. (Citato a Pagina 5).

[4] Julio Faura, Chris Horton, Phuoc Van Duong, Jordi Madrenas, and Mi-

guel Angel Aguirre. A novel mixed signal programmable device with onchip

microprocessor. In in Proc. 19th IEEE Custom Integrated Circuits Conf.

(CICC, pages 103–106. IEEE Press, 1997. (Citato a Pagina 7).

[5] Paul Layzell. The ’evolvable motherboard’. a test platform for the research

of intrinsic hardware evolution. Cognitive Science Research Paper, 479,

1998. (Citato a Pagina 7).

[6] Simon Harding and Julian F. Miller. Evolution in materio : A real-time

robot controller in liquid crystal. In Jason Lohn, David Gwaltney, Gregory

Hornby, Ricardo Zebulum, Didier Keymeulen, and Adrian Stoica, editors,

Proceedings of the 2005 NASA/DoD Conference on Evolvable Hardware,

87

BIBLIOGRAFIA

pages 229–238, Washington, DC, USA, 29 June-1 July 2005. IEEE Press.

(Citato a Pagina 8).

[7] Simon Harding and Julian Francis Miller. Evolution in materio: Initial ex-

periments with liquid crystal. In Evolvable Hardware, pages 298–. IEEE

Computer Society, 2004. (Citato a Pagina 8).

[8] Julian F. Miller and Keith L. Downing. Evolution in materio: Looking

beyond the silicon box. In Evolvable Hardware, pages 167–176. IEEE

Computer Society, 2002. (Citato a Pagina 8).

[9] Xilinx Inc. Virtex-4 FPGA Configuration User Guide, 2008. (Citato a

Pagina 8).

[10] EDK User Guide, http://www.xilinx.com/ise/embedded/edk docs.htm. (Ci-

tato alle Pagine 8, 24 e 25).

[11] iMPACT User Guide, http://www.xilinx.com/itp/xilinx4/data/docs/pac/pac.html.

(Citato alle Pagine 8 e 26).

[12] Xilinx Inc. FPGA Editor Guide, 2000. (Citato alle Pagine 8 e 27).

[13] Marco Castagna. Progettazione di un sistema evolutivo hardware basato su

virtex-4. Master’s thesis, Politecnico di Milano, 2009. (Citato alle Pagine 9,

12, 14, 16, 17, 21, 29, 43, 44, 48, 49, 50, 51, 52, 54, 55, 68, 71, 72, 77 e 84).

[14] Xilinx Inc. ML401/ML402/ML403 Evaluation Platform User Guide, 2006.


[15] Matteo Renesto. A new ip-core to manage fpgas evolvable regions, July

2009. (Citato alle Pagine 16, 17 e 21).

[16] Xilinx Inc. XPS HWICAP (v1.00.a) User Guide, 2007. (Citato alle Pagine

19, 20 e 83).

[17] A. Thompson, I. Harvey, and P. Husbands. Unconstrained evolution and hard

consequences. In E. Sanchez and M. Tomassini, editors, Towards Evolvable

88

BIBLIOGRAFIA

Hardware: The evolutionary engineering approach, volume 1062 of LNCS,

pages 136–165. Springer-Verlag, 1996. (Citato alle Pagine 29 e 31).

[18] Adrian Thompson. An evolved circuit, intrinsic in silicon, entwined wi-

th physics. In Tetsuya Higuchi, Masaya Iwata, and Weixin Liu, editors,

ICES, volume 1259 of Lecture Notes in Computer Science, pages 390–405.

Springer, 1996. (Citato a Pagina 29).

[19] A. Thompson, P. Layzell, and R. S. Zebulum. Explorations in design space:

Unconventional electronics design through artificial evolution. IEEE Trans.

Evol. Comp., 3(3):167–196, 1999. (Citato a Pagina 29).

[20] Adrian Thompson. On the automatic design of robust electronics throu-

gh artificial evolution. In ICES ’98: Proceedings of the Second Interna-

tional Conference on Evolvable Systems, pages 13–24, London, UK, 1998.

Springer-Verlag. (Citato a Pagina 32).

[21] Adrian Thompson and Paul J. Layzell. Evolution of robustness in an electro-

nics design. In Julian F. Miller, Adrian Thompson, Peter Thomson, and Te-

rence C. Fogarty, editors, ICES, volume 1801 of Lecture Notes in Computer

Science, pages 218–228. Springer, 2000. (Citato a Pagina 32).

[22] L. Sekanina. Modeling of evolvable hardware. Master’s thesis, Brno

University of Technology, 1999. (Citato alle Pagine 34 e 35).

[23] Julian F. Miller, Dominic Job, and Vesselin K. Vassilev. Principles in the

evolutionary design of digital circuits - part II. Genetic Programming and

Evolvable Machines, 1(3):259–288, 2000. (Citato a Pagina 34).

[24] Zdenek Vasicek and Lukas Sekanina. Evaluation of a new platform for image

filter evolution. In AHS, pages 577–586. IEEE Computer Society, 2007.


[25] Lukas Sekanina. Evolutionary functional recovery in virtual reconfigurable

circuits. JETC, 3(2), 2007. (Citato a Pagina 35).

89

BIBLIOGRAFIA

[26] Kyrre Glette and Jim Torresen. A flexible on-chip evolution system im-

plemented on a xilinx virtex-ii pro device. In Juan Manuel Moreno, Jordi

Madrenas, and Jordi Cosp, editors, ICES, volume 3637 of Lecture Notes in

Computer Science, pages 66–75. Springer, 2005. (Citato a Pagina 35).

[27] Kyrre Glette, Jim Torresen, Moritoshi Yasunaga, and Yoshiki Yamaguchi.

On-chip evolution using a soft processor core applied to image recognition.

In AHS ’06: Proceedings of the first NASA/ESA conference on Adaptive

Hardware and Systems, pages 373–380, Washington, DC, USA, 2006. IEEE

Computer Society. (Citato a Pagina 35).

[28] Friedl S Sekanina L. On routine implementation of virtual evolvable devices

using combo6. In Proc. of the 2004 NASA/DoD Conference on Evolvable

Hardware, pages 63–70, 2004. (Citato alle Pagine 36 e 83).

[29] Delon Levi and Steve Guccione. GeneticFPGA: Evolving stable circuits

on mainstream FPGA devices. In Evolvable Hardware, pages 12–17. IEEE

Computer Society, 1999. (Citato alle Pagine 38 e 83).

[30] A.M. Tyrrell, R.A. Krohling, and Y. Zhou. Evolutionary algorithm for the

promotion of evolvable hardware. Computers and Digital Techniques, IEE

Proceedings -, 151(4):267–275, July 2004. (Citato a Pagina 39).

[31] Andres Upegui and Eduardo Sanchez. Evolving hardware by dynamical-

ly reconfiguring xilinx fpgas. In Juan Manuel Moreno, Jordi Madrenas,

and Jordi Cosp, editors, ICES, volume 3637 of Lecture Notes in Computer

Science, pages 56–65. Springer, 2005. (Citato alle Pagine 39 e 50).

[32] Xilinx. Two Flows for Partial Reconfiguration: Module Based or Small Bit

Manipulations. (Citato a Pagina 39).

[33] Xilinx. Difference-Based Partial Reconfiguration. (Citato a Pagina 40).

[34] Xilinx Inc., www.xilinx.com. XAPP 290: Two flows for Partial Reconfi-

guration: Module Based or Difference Based, September 2004. (Citato a

Pagina 40).

90

BIBLIOGRAFIA

[35] Pauline C. Haddow and Gunnar Tufte. Bridging the genotype-phenotype

mapping for digital fpgas. In Evolvable Hardware, pages 109–115. IEEE

Computer Society, 2001. (Citato alle Pagine 41 e 83).

[36] Gunnar Tufte and Pauline C. Haddow. Biologically-inspired: A rule-based

self-reconfiguration of a virtex chip. In Marian Bubak, G. Dick van Albada,

Peter M. A. Sloot, and Jack Dongarra, editors, International Conference on

Computational Science, volume 3038 of Lecture Notes in Computer Science,

pages 1249–1256. Springer, 2004. (Citato alle Pagine 41 e 83).

[37] Andres Upegui and Eduardo Sanchez. Evolving hardware with self-

reconfigurable connectivity in xilinx fpgas. In AHS ’06: Proceedings of

the first NASA/ESA conference on Adaptive Hardware and Systems, pages

153–162, Washington, DC, USA, 2006. IEEE Computer Society. (Citato a

Pagina 41).

[38] N. I. Rafla. Evolvable reconfigurable hardare framework for edge detection.

In Circuits and System MWSCAS07, 50th Midwest Symposium on,, pages

65–68, Coimbra, Portugal, August 2007. (Citato a Pagina 55).

[39] T. Kalganova C. Lambert and E. Stomeo. Fpga-based systems for evolva-

ble hardware. transactions on engineering. Computing and Technology, 12,

2006. (Citato a Pagina 55).

[40] Xilinx Inc. Constraints Guide. (Citato a Pagina 72).

91

BIBLIOGRAFIA

92

Documento generato con LATEX il 23 luglio 2009

93

Progettazione di un Sistema Per l'Evoluzione Intrinseca di...

Documents

Transcript of Progettazione di un Sistema Per l'Evoluzione Intrinseca di...