POLITECNICO DI MILANO

HERA: HERA: Hardware EvolutionHardware Evolutionover Reconfigurableover Reconfigurable

ArchitecturesArchitectures- 3dDresd 2008 - - 3dDresd 2008 -

DDynamic ynamic RReconfigurability econfigurability inin EEmbeddedmbedded SSystemsystems DDesignesign

Marco Castagna: marco.castagna@dresd.org

22

OutlineOutline

Evolvable Hardware: definizioniCaratteristiche dell’EHWApprocci all’evoluzione hardwareRisultati ottenuti

Lavoro svolto: Contest GECCO 2008Descrizione del problemaPerchè EHW?Descrizione dei vincoli di progettazione degli individuiDescrizione degli individuiProcesso EvolutivoRisultati

HERA evolutive frameworkArchitettura principaleEsempi di istanze utilizzate

33

Evolvable Hardware: definizioniEvolvable Hardware: definizioni

Hardware riconfigurabileHardware riconfigurabile

Algoritmi EvolutiviAlgoritmi Evolutivi

++

44

•FlessibilitàFlessibilità

•EfficienzaEfficienza

A patto di…A patto di…sapere esattamente sapere esattamente cosacosa si vuolesi vuole

ottenute ottenute autonomamenteautonomamente

Evolvable Hardware: vantaggiEvolvable Hardware: vantaggi

55

Evoluzione Evoluzione Gate Gate LevelLevel

Evoluzione Evoluzione Functional Functional LevelLevel

potente ma…potente ma…

Approcci all’evoluzione Approcci all’evoluzione hardwarehardware

66

Risultati ottenutiRisultati ottenuti

7

GECCO 2008 contest: descrizione del GECCO 2008 contest: descrizione del problema problema

•“Evolvere un agente in grado di raccogliere il maggior numero di risorse di due tipi diversi disposte su una mappa con altezze variabili e zone non oltrepassabili”

7

8

GECCO 2008 contest: descrizione del GECCO 2008 contest: descrizione del problema problema

•Informazioni disponibili all’agente:Griglia 5x5 delle altezze delle posizioni attorno a quella attualeQuantità raccolte delle due risorseRisultato dell’ultima mossa (raccolto 1, raccolto 2, niente)Passi di simulazione rimanenti

8

In output l’agente fornisce la “posizione relativa” della prossima cella in cui spostarsi.

0 1 2 3 4

5 6 7 8 9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24

99

Scoprire fino a che punto queste tecniche possono essere usate per risolvere problemi “complessi” con una specifica di alto livello.

Dotare il controllore evoluto delle caratteristiche che contraddistinguono l’Hardware Evolvibile: fault tolerance e reattività ai cambiamenti d’ambiente.

Testare il nostro framework di evoluzione

Perché è quello che facciamo :P

Motivazioni: Perché EHW?Motivazioni: Perché EHW?

1010

Vincoli di progettazione degli individui:Vincoli di progettazione degli individui:

Idea base: progettare gli individui in modo che sia possibile evolverli/implementarli su una FPGA.

Dimensione (genotipo/area occupata) massima fissata e semplice struttura di connessioniBlocchi base molto semplici

Cartesian Genetic Programming:Cartesian Genetic Programming:

Griglia rettangolare di ROWSxCOLS “blocchi base” connessi tra di loroUn singolo elemento finale a rappresentare

l’output

1111

Descrizione degli individuiDescrizione degli individui

Ogni blocco può avere 2, 1 o 0 ingressi.

Ogni ingresso può essere:Uno dei dati disponibili direttamente all’individuo.L’uscita di uno dei blocchi appartenenti alle 5

colonne che lo precedono.

1212

Descrizione degli individuiDescrizione degli individui

Ogni blocco base può implementare:Semplici operazioni matematiche (+,-,*,/...)Semplici operazioni di confronto (CMP, MIN,

MAX...)Semplici operazioni di “memoria” (flip-flip,

media...)Costanti

L’output finale è il residuo modulo 24 dell’uscita dell’ultimo blocco (incrementata di 1 se >=12).

13

Processo evolutivo adottatoProcesso evolutivo adottato

13

Evoluzione incrementale con due funzioni di fitness differenti.

1)Evoluzione parallela di 10 popolazioni (GA standard con migrazione degli individui migliori) usando la funzione di fitness “visits”.

2)I 10 migliori individui di ogni popolazione sono stati usati come popolazione di partenza per l’evoluzione usando la funzione di fitness “contest”.

Ogni individuo è stato testato (simulato in software) su 2 mappe differenti e 10 punti di inizio casuali per ogni mappa. Lo score finale è la media delle 20 esecuzioni.

1414

Risultati ottenutiRisultati ottenuti

1514

Risultati ottenutiRisultati ottenuti

1614

Risultati ottenutiRisultati ottenuti

1715

HERA evolutive framework: architettura baseHERA evolutive framework: architettura base

EA-Core Controller

Valutatore

Start/Stop/Get Info

Info Evoluzione

Richiesta Valutazione

Scores

Inizializzazione/Get Info

Informazioni Valutazione

1816

HERA evolutive framework: architettura baseHERA evolutive framework: architettura base

EA-Core:EA-Core:Implementa l’algoritmo evolutivo utilizzatoEventualmente memorizza gli individuiRiceve i comandi dal controllerInvia le informazioni sull’evoluzione al controllerRichiede e recupera le valutazioni al valutatore

Controller:Controller:•Front-end del framework, riceve e mostra informazioni da/all’utente riguardo il processo evolutivo•Ferma il processo evolutivo qualora lo ritenga necessario

Valutatore:Valutatore:•Valuta gli individui determinandone il fitness•Riceve la richiesta di valutazione ed eventualmente i genotipi degli individui da valutare

1917

Istanza 1: SimpleCoreIstanza 1: SimpleCore

SimpleCore CLController

ValutatoreGECCO

2018

Istanza 2: MultiPopCore e Valutatore Istanza 2: MultiPopCore e Valutatore distribuitodistribuito

MultiPopCore

CLController

ValutatoreDistribito

(nodo centrale)

SimpleCore

SimpleCore

SimpleCore

V.D.(nodo periferico)

GECCO Val.

V.D.(nodo periferico)

GECCO Val.

V.D.(nodo periferico)

GECCO Val.

2119

FineFine

- Domande? -- Domande? -