Università degli Studi di Bologna

FACOLTÀ DI SCIENZE MATEMATICHE, FISICHE E NATURALI

Corso di Laurea in FisicaMateria di Tesi: Laboratorio di Elettronica

PROGETTAZIONE DI UN PROCESSORE FUZZY

VELOCE A DUE INGRESSI DALLA DESCRIZIONE

VHDL AL LAYOUT FINALE

Tesi di Laurea di: Relatore: Chiar. mo

DAVIDE FALCHIERI Prof. ENZOGANDOLFI

Correlatori:

Prof. MASSIMO MASETTI

Dott. ALESSANDRO GABRIELLI

I SESSIONE

Anno Accademico 1996/97

Università degli Studi di Bologna

FACOLTÀ DI SCIENZE MATEMATICHE, FISICHE E NATURALI

Corso di Laurea in FisicaMateria di Tesi: Laboratorio di Elettronica

PROGETTAZIONE DI UN PROCESSORE FUZZY

VELOCE A DUE INGRESSI DALLA DESCRIZIONE

VHDL AL LAYOUT FINALE

Parole chiave: CAD elettronico, VHDL, Logica Fuzzy,Trigger, VLSI

Tesi di Laurea di: Relatore: Chiar. mo

DAVIDE FALCHIERI Prof. ENZO GANDOLFI

Correlatori:

Prof. MASSIMO MASETTI

Dott. ALESSANDRO GABRIELLI

I SESSIONE

Anno Accademico 1996/97

INDICE

INTESTAZIONE ....................................................................................1

INDICE...................................................................................................3

INTRODUZIONE...................................................................................7

CAPITOLO 1........................................................................................111.1 La logica fuzzy............................................................................111.2 Termini ricorrenti di logica fuzzy ................................................121.3 Insiemi e regole fuzzy .................................................................131.4 Sistemi fuzzy...............................................................................151.5 Le fasi di un sistema fuzzy ..........................................................16

1.5.1 La fuzzificazione ..................................................................171.5.2 L’inferenza ...........................................................................181.5.3 La defuzzificazione...............................................................201.5.4 Considerazioni finali.............................................................23

1.6 Tempo di elaborazione ................................................................231.7 Diversi tipi di implementazione dei sistemi fuzzy........................25

CAPITOLO 2........................................................................................272.1 Evoluzione nella progettazione dei circuiti integrati ....................272.2 Flusso di progetto........................................................................302.3 Il linguaggio VHDL.....................................................................33

2.3.1 Terminologia VHDL............................................................342.3.2 Esempi di progettazione VHDL............................................36

2.4 Generazione delle megacelle .......................................................392.5 Simulazione funzionale con Leapfrog Simulator..........................402.6 Sintesi del codice VHDL.............................................................41

2.6.1 Il processo di sintesi .............................................................422.6.2 Vincoli..................................................................................432.6.3 Libreria tecnologica ..............................................................44

2.7 Strumenti di simulazione .............................................................472.8 Simulazione circuitale con Verilog XL........................................482.9 Analisi temporale con Veritime ...................................................50

2.9.1 Dispositivi di memoria e vincoli temporali............................512.9.2 Come Veritime trova le violazioni temporali.........................532.9.3 Calcolo della lunghezza dei percorsi con Veritime................542.9.4 Visualizzazione delle violazioni con Veritime ......................56

2.10 Simulazione dei difetti di fabbricazione con Verifault XL .........582.11 Dallo schematic al layout ..........................................................61

2.11.1 Inclusione dei pad di I/O e di alimentazione........................612.11.2 Fase di posizionamento delle celle (placement)...................622.11.3 Fase di collegamento delle celle (routing) ...........................642.11.4 Verifica finale del progetto .................................................66

2.12 Riflessioni finali ........................................................................67

CAPITOLO 3........................................................................................693.1 Caratteristiche generali del processore fuzzy ...............................693.2 Il selettore di regole attive ...........................................................713.3 Il processo di fuzzificazione ........................................................723.4 Organizzazione della memoria delle regole .................................743.5 Funzionamento del processore.....................................................763.6 Fasi di pipeline............................................................................783.7 Generazione del layout del processore.........................................803.8 Trattamento dei segnali di I/O .....................................................843.9 Test del chip HEPE96 .................................................................853.10 Il processore fuzzy HEPE97......................................................883.11 Caratteristiche principali di HEPE97 .........................................89

CAPITOLO 4........................................................................................934.1 Note alla lettura del codice VHDL ..............................................944.2 Il selettore degli intervalli Int_Selector ........................................954.3 Il generatore di indirizzi Rule_Add_Gen .....................................99

4.4 Il generatore di indirizzi Address_Generator .............................1014.5 Il blocco circuitale Core ............................................................103

4.5.1 La memoria delle regole Ramrule .......................................1044.5.2 Le look-up table Rammf_X0 e Rammf_X1.........................1074.5.3 Il blocco di minimo Minimum ............................................1084.5.4 Il blocco moltiplicatore Alpha_Product_Wallace ................1094.5.5 Funzionamento del blocco Core vero e proprio...................112

4.6 Il blocco di defuzzificazione Consequent ..................................1184.6.1 Il blocco per la moltiplicazione Mult7x4fast ......................1184.6.2 Il blocco per la divisione Divider .......................................1194.6.3 Il blocco Consequent vero e proprio ...................................120

4.7 Il blocco Processor ....................................................................1224.8 Dallo schematic al layout ..........................................................1264.9 Fase di placement e di routing ..................................................129

CONCLUSIONI..................................................................................135

APPENDICE A...................................................................................137APPENDICE B...................................................................................141BIBLIOGRAFIA.................................................................................173

INTRODUZIONE

L’oggetto di questo lavoro di tesi riguarda l’uso delle tecniche più avanzate perla progettazione di un processore fuzzy veloce (più avanti verrà spiegato l’effettivosignificato di queste parole) in tecnologia digitale CMOS VLSI (VLSI sta per VeryLarge Scale of Integration e CMOS sta per Complementary Metal OxideSemiconductor).

Questo lavoro si inserisce all’interno della ricerca “fuzzy” per la realizzazionedi una famiglia di processori veloci da utilizzare in esperimenti di fisica delle alteenergie (HEPE) finanziato dal gruppo V dell’INFN.

Infatti negli esperimenti di fisica delle alte energie è richiesto un hardwareveloce che sappia distinguere fra i vari eventi nucleari quelli interessanti e rigettiquelli non significativi. Si parla di trigger di I o II livello se la decisione deve esserepresa rispettivamente in un tempo inferiore ai 100 ns o dell’ordine delmicrosecondo.

Fino ad ora tali trigger sono stati realizzati utilizzando o semplici circuiticombinatori o DSP che sono veloci ma poco flessibili.

Ad un primo processore fuzzy progettato e realizzato nel ’94 (HEPE1000) èseguito il chip HEPE96, una versione più veloce a 4 ingressi, portato a termine etestato all’inizio del ’97. La caratteristica principale di questi processori è l’altavelocità di elaborazione che ne permette l’utilizzo in trigger di II livello.

Io ho collaborato alla fase finale di realizzazione del layout di HEPE96 e allafase di test dello stesso. In più ho curato tutte le fasi di progettazione del chipHEPE97, un processore fuzzy a 2 ingressi che oltre ad aumentare ulteriormente lavelocità, avvicinandosi ai tempi richiesti per un trigger di I livello, presenta un’areaed un consumo molto ridotti. Questo ultimo nato sarà inviato alle fonderia ES2 neiprossimi giorni per la realizzazione dei primi esemplari prototipo. Una voltaultimato il processore sarà testato con l’ASIC Tester LV500, una macchina indotazione al Laboratorio di Tecnologie Subnucleari che permette di controllarel’effettivo funzionamento dei chip costruiti.

Il laboratorio di ricerca presso il quale è stato realizzato il lavoro utilizzaalcune workstation della Sun Microsystems sulle quali viene fatto girare la versione9405 del CAD elettronico Cadence Design Framework II, un ambiente di lavorointegrato costituito da diversi programmi che permettono la progettazione completadi un circuito elettronico integrato, dalla descrizione con il linguaggio VHDL finoalla composizione del layout pronto per essere realizzato su silicio. CadenceDFWII fornisce gli strumenti per la progettazione e la simulazione funzionale ecircuitale di ogni singolo blocco in modo gerarchico così che risulta possibileprogettare e testare i singoli blocchi in modo separato.

La tesi è stata così strutturata:

l’ Introduzione presenta le motivazioni che hanno condotto alla progettazionedi vari processori fuzzy da parte del gruppo di ricerca presso il quale ho operato inrelazione alle future applicazioni nella fisica delle alte energie.

Il Capitolo 1 descrive brevemente come è nata e come funziona la logicafuzzy e le diverse piattaforme che possono essere utilizzate per fare funzionare unalgoritmo fuzzy.

Il Capitolo 2 illustra brevemente l’evoluzione dei metodi di progettazione dicircuiti elettronici, dal full-custom fino agli ultimi linguaggi descrittividell’hardware. Inoltre presenta in dettaglio la successione dei passi logici che ilprogettista deve seguire nella progettazione di un circuito integrato affinché ilprodotto finale abbia buone probabilità di funzionare correttamente una voltarealizzato fisicamente su silicio. Vengono descritte le fasi di stesura del codiceVHDL, la simulazione funzionale della descrizione VHDL, la sintesi, lasimulazione circuitale e la successiva generazione del layout finale nell’ordinepreciso in cui devono essere eseguite per affrontare qualsiasi progetto.

Il Capitolo 3 presenta l’architettura del processore fuzzy a 4 ingressi HEPE96,le sue caratteristiche di funzionamento ed i risultati dei test effettuati sui prototipicon l’ASIC Tester LV500. Inoltre viene presentata l’architettura del nuovoprocessore fuzzy HEPE97 a due ingressi sottolineando le differenze con il chipprecedente e le prestazioni globali ottenute.

Il Capitolo 4 presenta in dettaglio tutti i blocchi logici in cui è stato suddivisoil processore HEPE97 descrivendo per ognuno di questi la successione dei passilogici relativi al flusso di progetto. Di ogni blocco è presentata la descrizioneVHDL, lo schema circuitale ed i risultati delle relative simulazioni. Lo stesso valeper il blocco più alto nella gerarchia, cioè il blocco processore che contiene al suointerno tutti gli altri blocchi e li temporizza adeguatamente tramite la logica dicontrollo. Da qui si passa poi alle fasi della generazione del layout fino allapresentazione del layout finale ottimizzato al meglio e pronto per la consegna allafonderia.

Le Conclusioni presentano un riepilogo del lavoro svolto e le prospettivefuture relativamente alla progettazione di processori sempre più veloci ed utilizzatiregolarmente nella parte elettronica di controllo di esperimenti di fisica delleparticelle.

L’ Appendice A riporta un glossario dei termini tecnici inglesi utilizzati.

L’ Appendice B riporta per esteso il codice VHDL relativo alla progettazioneintegrale del processore HEPE97. Questa scelta permetterà di utilizzare tale tesianche come strumento didattico fornendo un set organico di istruzioni VHDLrelative ad un progetto completo di un processore.

Si fa presente che durante la tesi sono state utilizzati molti vocaboli tecnicidirettamente in linguaggio originale (inglese) poiché la traduzione in italianoavrebbe richiesto l’uso di più parole che, oltre ad appesantire il linguaggio,avrebbero difficilmente precisato il significato del termine tecnico usato.

Per tali termini abbiamo comunque dato una spiegazione la prima volta chevengono utilizzati oltre a riportarli in ordine alfabetico in apposito glossario posto inAppendice A.

CAPITOLO 1

1.1 La logica fuzzy

La seguente descrizione della logica fuzzy non vuole essere una trattazioneesaustiva e formale dell’argomento, ma si limita ad accennare alle caratteristiche piùinteressanti in relazione alle sue possibili applicazioni.

La logica tradizionale introdotta da Aristotele è di tipo bivalente, non lasciaspazio cioè ad ambiguità: un oggetto è classificato o bianco o nero, o caldo ofreddo, o pieno o vuoto, senza alcun grado di sfumatura nella sua descrizione. Ciòsignifica che il grado di appartenenza di un oggetto ad un insieme è o 0 o 1, non visono soluzioni intermedie. Questa schematizzazione della realtà è molto riduttiva epuò portare a vere e proprie conclusioni assurde. Vediamo l’esempio dellatemperatura di una stanza: la logica tradizionale classifica la temperatura comebassa sotto i 15 °C, normale fra 15 e 25 e alta oltre i 25 °C. In questo modo latemperatura di 25 °C viene considerata normale, mentre la temperatura di 25.1 °C èconsiderata alta: è ovvio che una demarcazione così netta non ha senso visto che ledue temperature differiscono di un solo decimo di grado. Occorre perciò unademarcazione più sfumata fra gli insiemi se si vuole ottenere una descrizione piùaderente alla realtà.

Una logica multivalente a tre valori (0, 0.5, 1) fu proposta negli anni venti dalmatematico polacco Jan Lukasiewicz. In questo periodo anche lo sviluppo dellateoria quantistica ed i conseguenti paradossi (principio di indeterminazione diHeisenberg, ambiguità della posizione di una particella elementare) diedero impulsoai tentativi di superare i limiti della logica tradizionale.

La logica fuzzy [1] è stata introdotta nel 1965 dall’ingegnere armenotrasferitosi a Berkeley Lofti A. Zadeh come un ulteriore tentativo di rendere lalogica più aderente alla realtà. Nella logica fuzzy un elemento appartiene ad un datoinsieme con un grado di appartenenza compreso fra 0 e 1. Questo significa ancheche uno stesso oggetto può appartenere a due insiemi diversi con differenti gradi diappartenenza: ad esempio la temperatura di una stanza può appartenere all’insieme“Temperatura Calda” con un grado di verità di 0.7 e all’insieme “TemperaturaMedia” con il valore 0.3. In questo modo viene violato il famoso principio di noncontraddizione della logica aristotelica secondo cui un elemento non puòappartenere contemporaneamente a due insiemi diversi.

L’introduzione della logica fuzzy quindi modifica sostanzialmente tutti iprincipi che stanno alla base della logica tradizionale.

L’uso degli insiemi fuzzy permette una descrizione più aderente della realtà :lo stesso linguaggio naturale di uso comune si basa su concetti fuzzy del tipo caldo,freddo, alto, basso, forte, ecc., e fornisce una descrizione adeguata della realtà

anche se è dotato di una precisione limitata. La logica fuzzy quindi si proponeprincipalmente come il mezzo attraverso cui tentare una descrizione quantitativa dellinguaggio naturale. A differenza dei sistemi tradizionali i sistemi basati sulla logicafuzzy sono capaci di elaborare regole fuzzy del tipo :

se la temperatura è alta allora apri la finestra

senza il bisogno di un modello matematico che regoli il comportamento daintraprendere in base al valore esatto della temperatura di una stanza. È per questomotivo che un sistema fuzzy progettato per risolvere un determinato problema èmolto più trasparente e facile da implementare del corrispondente sistema basatosulla logica tradizionale.

Le prime applicazioni pratiche di questa teoria sono iniziate solo in annirecenti. Attualmente si assiste ad un moltiplicarsi di queste applicazioni, inparticolare nell’ambito di sistemi di controllo fuzzy, in vari settori: dal controllo diimpianti e processi industriali alla gestione di apparecchi elettrodomestici, allaregolazione automatica di macchine fotografiche e telecamere, fino al controllo diimpianti di trasmissione e frenatura degli autoveicoli. Oltre al sistemi di controllo idue settori che di più hanno assistito all’introduzione di questa metodologia sonoquelli riguardanti i sistemi di “pattern recognition” e di “information retrieval”.

Un particolare curioso è che i primi a cogliere i vantaggi dei sistemi fuzzysono stati i giapponesi: probabilmente la mentalità orientale e la filosofia buddistasono più ricettive dei concetti fuzzy di quanto lo sia la mentalità occidentale,fortemente ancorata alla filosofia aristotelica.

1.2 Termini ricorrenti di logica fuzzy

La logica fuzzy ha introdotto con sé una nuova terminologia per definire tuttigli elementi della logica. È bene dunque precisare il significato dei termini piùimportanti in quanto d’ora in avanti verranno usati molto spesso.

• Variabile linguistica (variabile fuzzy) : è la variabile descrittiva impiegata inun processo (temperatura, velocità, ecc.).

• Universo del discorso : è il campo di esistenza della variabile linguistica. Inpratica equivale all’insieme di tutti i possibili valori che la variabile puòassumere.

• Insieme fuzzy (Fuzzy Set) : è l’insieme delle coppie ordinate costituite dai valoridella variabile linguistica e dai corrispondenti gradi di appartenenza ad unadeterminata funzione di appartenenza.

• Term Set : è l’insieme di tutti gli insiemi fuzzy associati a una variabile.• Funzione di appartenenza (Membership Function, MF) : è la funzione che,

descrivendo in modo analitico la forma di un insieme fuzzy, permette di associaread ogni valore di una variabile linguistica un determinato grado di appartenenza.

• Grado di appartenenza : valore che definisce l’appartenenza di una variabilelinguistica all’insieme fuzzy corrispondente per mezzo di un numero compresofra 0 e 1 utilizzando il valore attuale della variabile. Il processo che porta acalcolare il grado di appartenenza si chiama fuzzificazione.

• Regola fuzzy : istruzione del tipo “Se la Premessa è ... allora la Conclusione è…” che permette di associare gli ingressi alle uscite.

• Inferenza : procedimento attraverso il quale in base al grado di verità dellapremessa viene attivato l’insieme fuzzy di uscita.

• Defuzzificazione : processo di calcolo del valore di uscita (crisp) di un sistemafuzzy in base alla somma dei contributi di tutte le regole.

1.3 Insiemi e regole fuzzy

Un esempio di insiemi fuzzy è riportato in fig. 1.1: l’insieme di tutti i possibilivalori che può assumere la variabile Temperatura è stata suddivisa in tre insiemi, lezone Temperatura Bassa, Media e Alta. In questo modo una temperatura di 16 °C èconsiderata al tempo stesso come una temperatura bassa e come una temperaturamedia con due diversi gradi di ambiguità. È importante sottolineare che il grado diappartenenza non è una probabilità. Quando si dice che la temperatura è alta conuna probabilità del 50 % significa che questo evento si verifica 50 volte ogni 100eventi. Quando invece si dice che la temperatura appartiene all’insieme“Temperatura alta” con un grado di verità di 0.5 significa che questo fatto ha ungrado di ambiguità del 50 %. Nel primo caso si ha una misura della frequenzastatistica di un evento, nel secondo caso si ha la misura di un fatto deterministico maambiguo.

Fig. 1.1: Insiemi fuzzy associati alla variabile temperatura.

Essendo gli insiemi strutturati in questo modo la logica fuzzy si presta aformalizzare il ragionamento umano in modo quasi immediato: un uomo perdecidere se è il caso o meno di aprire la finestra e rinfrescare la stanza non habisogno di conoscere con precisione il valore della temperatura interna istante per

grad o d iapp artenenzaα

tem peratu ra( C )

P icco la M ed ia A lta

istante ma gli basta sapere se la temperatura è bassa, media o alta. Il comportamentoverrà di conseguenza. Qualsiasi problema può essere descritto con una serie diregole del tipo:

se(x è basso) e (y è alto) allora (z è medio);

Noti il grado di appartenenza di x all’insieme fuzzy “basso” e di y all’insieme“alto” l’implicazione allora definisce in che modo viene attivata la conclusionerelativa all’insieme fuzzy per la variabile z di uscita. Dopo avere calcolato icontributi delle regole fuzzy che formalizzano un problema un opportuno processodi defuzzificazione avrà il compito di dare un valore ben definito (crisp) all’uscita z.

Il punto di forza della logica fuzzy sta proprio nella capacità di manipolaremisure ambigue, indefinite, approssimative, cioè fuzzy. Il bisogno della logicatradizionale di misure precise è spesso dovuto, non ad una reale necessità diprecisione, ma ad una sua impossibilità di manipolazione di grandezze sfumate.Inoltre una misura precisa può comportare notevoli sforzi, come del resto la suaelaborazione, e la maggior parte delle volte la precisione raggiunta è molto superiorea quella effettivamente necessaria per gli scopi che il sistema si prefigge. In questicasi la logica fuzzy può essere la soluzione ideale come spesso afferma Zadehquando sottolinea che una delle potenzialità di detta metodologia è implicita nellafrase “Exploit the Tolerance for Imprecision”. Per questo motivo la logica fuzzy èmolto indicata nella soluzione di problemi complessi dove non è noto un precisoalgoritmo che lega gli ingressi all’uscita. In questi casi è molto efficace lamodellazione del processo tramite descrizioni qualitative e quantitative.

Fig. 1.2 : Pendolo invertito.

1.4 Sistemi fuzzy

I sistemi fuzzy costituiscono l’effettiva implementazione della logica fuzzy perla soluzione di problemi complessi che sono difficilmente formalizzabili con unalgoritmo tradizionale. Di tali problemi spesso non si conosce una soluzione

cop p ia

ango lov eloc ita '

analitica oppure è talmente complicata che non vale la pena determinarla. Alcontrario il sistema fuzzy si distingue per la semplicità delle regole che descrivono ilproblema, regole che devono essere fornite da un esperto. Ne è un esempio classicoil problema del pendolo invertito (vedi fig. 1.2): un pendolo è fissato per la suaestremità inferiore ad un carrello mobile sull’asse orizzontale; lo scopo è dimantenerlo in equilibrio fornendo un’adeguata coppia equilibratrice coppia in baseall’angolo angolo formato dall’asta con la verticale e alla velocità angolare velocità.

Il modello matematico di questo problema consiste in un sistema non lineare didue equazioni differenziali del quarto ordine; usando la logica fuzzy invece questoproblema è risolto perfettamente usando sole 15 regole. Le regole usate sonosemplici e dettate dal senso comune, ad esempio:

• se l’angolo è circa 0 e la velocità è circa 0 allora la coppia è circa 0;• se l’angolo è piccolo e la velocità è circa 0 allora la coppia è piccola e negativa;• se l’angolo è piccolo e negativo e la velocità è circa 0 allora la coppia è piccola

e positiva.

In questo come in molti altri casi l’uso di un sistema fuzzy è molto piùconveniente rispetto agli algoritmi tradizionali.

1.5 Le fasi di un sistema fuzzy

Per costruire un sistema fuzzy dotato di ingressi e uscite ( vedi fig. 1.3)occorre definire gli insiemi fuzzy delle variabili di ingresso e le regole cheassociano gli ingressi alle uscite. Fatto questo la struttura logica del ragionamentofuzzy è la seguente:

1) Lettura delle variabili di ingresso.

fu zz i f icaz io n e

in fe ren za

le ttu ra d el le v a r iab il i d i in g resso

co m p o siz io n ee

d e fu zz if icaz io n e

reg o lefu zzy

le d u e fas iso n o

r ip e tu te p e ro g n i reg o la

u sc ita c risp

Fig. 1.3 : Le fasi di un sistema fuzzy.

2) Lettura della regola ed individuazione :

• delle variabili di ingresso coinvolte dalla regola e dei rispettivi insiemifuzzy ;

• dell’insieme fuzzy del conseguente delle regole.

3) Fuzzificazione delle variabili di ingresso rispetto agli insiemi fuzzy letti nellaregola.

4) Calcolo del grado di verità della premessa della regola e inferenza sull’insiemefuzzy coinvolto della variabile d’uscita.

5) Composizione di tutti gli insiemi fuzzy di uscita coinvolti e defuzzificazione, cioèconversione in un ben determinato valore numerico (detto valore crisp).

I passi 2-3 sono ripetuti per tutte le regole del sistema fuzzy.

L’architettura generale di un sistema fuzzy contiene quindi al suo interno unabase di dati che descrive gli insiemi fuzzy, una base di dati per le regole fuzzy, ilblocco per la fuzzificazione, un blocco per l’inferenza ed uno per ladefuzzificazione. Queste sono le caratteristiche generali di un qualsiasi sistemafuzzy: il modo specifico con cui ognuno di questi blocchi viene implementatodipende dal particolare algoritmo fuzzy scelto. I prossimi paragrafi descrivono i tipidi algoritmi più usati nella costruzione di un sistema fuzzy.

1.5.1 La fuzzificazione

Supponiamo di avere un sistema fuzzy costituito da tre variabili d’ingresso X0,X1 e X2 ed un’uscita Z ognuna delle quali possiede le tre funzioni di appartenenzaPiccolo, Medio e Alto della fig. 1.4.

Fig. 1.4: Processo di fuzzificazione della variabile in ingresso X0.

grad o d iapp artenenzaα

p icco lo m ed io a lto

0 .85

0 .25

0 1 8 12 7

La regola tipica di questo sistema fuzzy sia di questo tipo:

se (X0 è Piccolo) e (X1 è Medio) e (X2 è Alto) allora (Z è Medio) (1.1)

dove si è fatta l’ipotesi che l’unico connettivo usato fra gli antecedenti èl’AND, cioè questa regola ha un peso se e solo se ognuno dei tre antecedenti (X0 èPiccolo), (X1 è Medio) e (X2 è Alto) è verificato. Se invece del connettivo AND siusa il connettivo OR la regola :

se (X0 è Piccolo) o (X1 è Medio) o (X2 è Alto) allora (Z è Medio) (1.2)

è attivata nel caso in cui uno solo dei tre antecedenti si verifichi.La prima operazione che deve compiere il sistema fuzzy consiste

nell’individuare i fuzzy set delle variabili d’ingresso in funzione del valore attualedelle variabili stesse (valore delle variabili nell’istante desiderato) e calcolarne ilgrado di appartenenza per ogni insieme. Si supponga che l’universo del discorso diX0 sia l’intervallo [0, 127] e che il valore attuale della variabile d’ingresso X0 sia18.

Fuzzificare X0 significa calcolare, per ogni insieme fuzzy, il suo grado diappartenenza, quindi dalla figura risulta che:

• il grado di appartenenza di X0 all’insieme Piccolo è 0.85;• il grado di appartenenza di X0 all’insieme Medio è 0.25;• il grado di appartenenza di X0 all’insieme Alto è 0.

Il grado di appartenenza che è interessante ai fini della regola (1.1) è il primo,cioè il grado di appartenenza all’insieme Piccolo.

1.5.2 L’inferenza

La seconda fase consiste prima di tutto nel determinare il grado di veritàdell’intera premessa θ in base ai gradi di verità α determinati per ogni antecedentenella regola.

In letteratura si trovano diversi metodi per tenere conto del contributo di piùantecedenti : per semplicità riporteremo di seguito solo il metodo più utilizzato.

Nell’ipotesi che gli α corrispondenti della regola (1.1) siano α1, α2 e α3 ilgrado di verità della premessa è dato da:

θ = MIN (α1, α2, α3) (1.3)

in quanto il connettivo usato fra gli antecedenti è l’AND logico.Nel caso della regola (1.2) dove il connettivo usato è l’OR disgiuntivo il grado

di verità della premessa è dato dalla formula :

θ = MAX(α1, α2, α3) (1.4)

Una volta calcolato il grado di verità θ della premessa deve essere calcolatol’effetto di θ sulla conclusione della regola. Infatti il grado di veritàdell’affermazione (Z è Medio) dipende dal grado di verità della premessa : tanto piùla premessa è vera, tanto più lo sarà la conclusione e viceversa.

Esistono vari metodi di inferenza fuzzy, qui di seguito verranno descritti i piùfamosi: il metodo “Min-Max”, il metodo “Max-Dot”, il metodo di inferenza diYager ed i metodi di Sugeno di ordine 0 e di ordine 1.

Il metodo d’inf erenza “Min-Max” [2]

La funzione di appartenenza dell’uscita Z viene troncata superiormente alvalore θ. Così se la funzione di appartenenza di Z è di forma triangolare, come infig. 1.5, una volta eseguita l’inferenza questa viene ridotta ad un trapezio di altezzaθ.

Il metodo d’inf erenza “Max-Dot” [2],[3]

Questo metodo si differenzia dal primo nel momento in cui si va a calcolarel’insieme fuzzy di uscita. Mentre il metodo “Min-Max” tronca la funzione diappartenenza individuata dalla regola fuzzy al valore θ, con questo metodo lafunzione di appartenenza viene moltiplicata per il medesimo valore, comportandoperciò non l’effetto di troncamento ma di riduzione di tutta la figura (vedi fig. 1.5).

Fig. 1.5: Visualizzazione dei metodi di inferenza “Min-Max”, “Max-Dot” e diYager.

Il metodo d’inf erenza di Yager [4]

Θ Θ Θ

Z Z ZZL Z i R Z

M ed io M ed io M ed io

M I N D O T YA G E R

Il metodo d’inferenza di Yager calcola il valore della funzione di appartenenzadell’uscita crisp Zi in base ai valori ZL e ZR che sono ottenuti, vedi fig. 1.5,dall’intersezione della funzione di appartenenza dell’uscita con la retta orizzontaleindividuata dal valore di verità della premessa θ. Zi è dato semplicemente dallamedia fra i due valori ottenuti ZL e ZR.

I metodi d’inferenza di Sugeno di ordine 0 e di ordine 1 [5]

Questo approccio che semanticamente si allontana un po’ dalla logica fuzzy haassunto un ruolo importante nella costruzione di sistemi automatici capaci diprodurre algoritmi fuzzy partendo da esempi e non dalla conoscenza di un esperto.Si è anche visto che le soluzioni ottenute non alterano sensibilmente la qualità deisistemi che utilizzano anche per le variabili di uscita gli insiemi fuzzy. In questocaso Sugeno suggerisce più possibilità : le più usate sono note come metodo diSugeno ordine 0 e Sugeno ordine 1.

Nel metodo di Sugeno ordine 0 ogni regola ha come conseguente un valorecrisp della variabile d’uscita fissato. Questo è il metodo che sarà usato all’internodei processori fuzzy HEPE96 e HEPE97.

Nel metodo d’inferenza di Sugeno di ordine 1 invece il valore Z non è unvalore fisso ma è una combinazione lineare degli ingressi. Ad esempio se gliingressi del sistema fuzzy sono X e Y l’uscita per ogni regola è data dalla seguenteformula :

Z = a + b*X + c*Y (1.5)

dove a, b e c cambiano da regola a regola.

1.5.3 La defuzzificazione

La precedente fase ha permesso di associare ad ogni regola attivata dal gruppodi valori in ingresso un insieme fuzzy o un valore crisp in uscita. A questo puntorisulta necessario comporre i contributi delle singole regole e successivamenteestrarre il valore crisp dell’uscita. Stessa cosa andrà fatta sui valori crisp Zi ottenutiper ogni regola.

Anche in questo caso vi sono diversi metodi di composizione; essi vengonogeneralmente scelti in base ai metodi di inferenza utilizzati nella fase precedente.Qui di seguito sono spiegati i tre metodi più comuni che sono normalmente associatirispettivamente ai metodi inferenziali “Min-Max”, “Max-Dot” e di Yager-Sugeno.

Metodo di composizione “Maximum”

Questo metodo, generalmente associato al metodo inferenziale “Min-Max”,costruisce l’insieme finale di output mediante l’unione di tutti gli insiemi fuzzydelle variabili di uscita, cioè sovrapponendo tutte le funzioni di appartenenzatroncate (vedi fig. 1.6) .

Fig. 1.6: Composizione delle regole con il metodo “Maximum”.

Metodo di composizione “Sum”

Il metodo di composizione associato al metodo d’inferenza “Max-Dot” è ilmetodo Sum. Esso consiste in una somma algebrica delle funzioni di appartenenzache rappresentano gli insiemi delle variabili di uscita calcolati nella fase precedente(fig. 1.7).

Fig. 1.7: Composizione delle regole con il metodo “Sum”.

Per i primi due metodi, invece, ottenuto un unico insieme fuzzy,rappresentante di tutti gli insiemi fuzzy associati alle regole attivate, si dovràtradurre quest’ultimo in un valore numerico mediante il processo di defuzzificazionevero e proprio. Anche stavolta sono mostrati i due metodi più famosi: il metodo delcentro dell’area (center of gravity) ed il metodo “height”.

0 127

1

Z

α

0 127Z

1α

Il metodo del centro dell’area

Questo metodo, che probabilmente è il più usato, consiste nel calcolare ilbaricentro dell’insieme fuzzy finale (vedi fig. 1.8) : questo valore crisp costituisce ilvalore dell’uscita desiderata del sistema fuzzy.

0 127

1

Z

α

valore crisp di uscita

Fig. 1.8 : Metodo di defuzzificazione del centro dell’area.

Il metodo “height”

Questo secondo metodo di defuzzificazione, generalmente applicato nel casodell’utilizzo del metodo inferenziale “Max-Dot”, sceglie come valore crisp d’uscital’ascissa dell’elemento dell’insieme finale di uscita con il più alto grado diappartenenza, cioè l’ascissa corrispondente al massimo della funzione diappartenenza finale (vedi fig. 1.9).

Metodo di defuzzificazione relativo agli insiemi d’uscita crisp

Ottenuto il valore crisp Zi per ogni regola del sistema fuzzy, il metodo dicomposizione delle regole di Yager e di Sugeno somma fra loro tutti questi valoriottenuti pesandoli con il rispettivo valore del grado di verità della premessa θi.Nella pratica la formula usata nel metodo di defuzzificazione è la seguente :

(1.6)

zeta outZi i

i_

*=

∑∑

Θ

Θ

Fig. 1.9 : Metodo di defuzzificazione “height”.

1.5.4 Considerazioni finali

In sostanza per costruire un algoritmo fuzzy occorre scegliere :

• le variabili di ingresso e uscita ;• gli insiemi fuzzy per tutte le variabili ;• l’insieme di regole che associano gli ingressi alle uscite.

Occorre quindi scegliere :• quali operatori associare ai connettivi AND e OR relativi alle premesse delle

regole ;• il metodo di inferenza ;• il metodo di defuzzificazione.

Una volta che sono state prese queste decisioni l’algoritmo fuzzy risultaperfettamente definito.

1.6 Tempo di elaborazione

Il flusso di dati all’interno di un sistema fuzzy, qualunque sia l’algoritmoscelto fra quelli presentati, è di tipo top-down, cioè lineare dagli ingressi alle uscitesenza istruzioni di salto. Per questo motivo quando un sistema fuzzy vieneimplementato in hardware viene usata tipicamente un’architettura di tipo “pipeline”,cioè strutturata in vari blocchi che uno dopo l’altro elaborano i risultati del bloccoprecedente. Così il blocco della fuzzificazione elabora i valori degli ingressi e li dàin ingresso al blocco dell’inferenza che procede al calcolo mentre i nuovi valori diingresso vengono fuzzificati dal blocco precedente. In questo modo possono essereraggiunte velocità di elaborazione molto alte.

Si può affermare che il tempo necessario a produrre una uscita relativa ad unset di variabili di ingresso dipende da:

• tempo dovuto alla fuzzificazione;

0 127Z

1α

valore crisp d'uscita

• tempo necessario a processare tutte le regole (equivalente al tempo di elaborazione di una regola per il numero di regole);

• tempo necessario ad aggregare i contributi delle regole;• tempo dovuto alla defuzzificazione.

Una grossa frazione del tempo globale di elaborazione degli ingressi è dovutoquindi al processo di inferenza delle regole: va sottolineato però che il numero diregole che danno un contributo non nullo all’uscita, dette per questo motivo regoleattive, è di solito molto minore del numero totale di regole utilizzato dal sistema.

Per questo motivo conviene processare soltanto le regole attive. Tutte quelleregole contenenti antecedenti il cui grado di verità α è 0 danno ovviamente uncontributo nullo all’uscita (poiché i metodi usati per l’inferenza sono il minimo ed ilprodotto) perciò è inutile prenderle in considerazione. Vediamo quanto si puòguadagnare processando solo le regole attive: in un sistema fuzzy con N variabili iningresso e K insiemi fuzzy per ognuna di queste variabili l’insieme completo di tuttele possibili regole è KN (questo è il numero massimo, un problema concreto peròpuò essere descritto con un numero di regole molto minore). I valori reali assuntidalle N variabili d’ingresso rendono attive un sottoinsieme delle possibili KN regole.Nell’ipotesi che al massimo si possano sovrapporre fra loro due insiemi fuzzyadiacenti il numero di regole attive si riduce a 2N, nell’ipotesi in cui si potesserosovrapporre 3 insiemi adiacenti il numero di regole attive sarebbe 3N. Per questimotivi la selezione di regole attive permette di diminuire molto il tempo globale dielaborazione degli ingressi. Infatti se si considera un sistema fuzzy con 4 ingressi e7 insiemi fuzzy per ogni ingresso il numero totale di regole è 74=2401, mentre ilnumero di regole attive è di sole 24=16.

1.7 Diversi tipi di implementazione dei sistemi fuzzy

I sistemi fuzzy consentono generalmente di risolvere con semplicità problemiche altrimenti richiedono una sofisticata logica di controllo e, in certi casi, offronola possibilità di risolvere nuovi problemi, prima difficilmente affrontabili.

Nella realizzazione pratica si hanno tre modalità di implementazione:

• la prima prevede lo sviluppo del sistema fuzzy in un linguaggio ad alto livello (adesempio il linguaggio C o C++) e di farlo funzionare poi su un microprocessoretradizionale. Questa soluzione è interessante quando l’economicità complessivadel sistema è più importante della velocità di elaborazione.

• la seconda associa ad un microprocessore convenzionale, che tipicamentegestisce l’interfaccia col mondo esterno, un coprocessore ottimizzato per lecomputazioni fuzzy, il che consente ovviamente elaborazioni più rapide.

• la terza utilizza hardware fuzzy dedicato (digitale, analogico o ibrido, cioèanalogico - digitale) e consente le più elevate prestazioni in termini di velocità.

Il primo chip fuzzy fu realizzato nel 1985 da AT&T ed elaborava 16 regolesemplici alla velocità di 0.08 milioni di inferenze logiche al secondo (MFLIPS=

Mega Fuzzy Logic Inferences Per Second).Oggi sono disponibili a livellocommerciale processori fuzzy fino a 20 milioni di regole fuzzy al secondo. Si stimache il mercato attuale dei microprocessori fuzzy abbia un valore dell’ordine di unmiliardo di dollari, ma si ritiene che esso aumenterà notevolmente nei prossimi annie si prevede che almeno il 50 % dei microcontrollori incorporeranno funzioni dilogica fuzzy.

Un esempio famoso di questo tipo di applicazione è il coprocessore fuzzyWARP 2.0 [6] (WARP sta per Weight Associative Rule Processor) della SGS-Thomson, associabile al microcontrollore standard ST9. WARP 2.0 comprende lefunzioni di fuzzificazione, associazione I/O e defuzzificazione e può eseguire 32regole con 5 ingressi e un’uscita in 1.85 µs.

Se la velocità non è ancora sufficiente occorre utilizzare un processorededicato che sia calibrato sulla specificità dell’algoritmo fuzzy da eseguire. Dati gliingressi da analizzare il processore deve essere in grado di portare avanti tuttal’elaborazione in base al sistema fuzzy memorizzato in una RAM o ROM interna.Nel caso di una ROM il sistema fuzzy memorizzato rimane fisso mentre nel caso diuna RAM o di una ROM programmabile (PROM) qualsiasi sistema fuzzydesiderato dall’utente può essere caricato all’interno.

Una soluzione del genere presenta caratteristiche di maggiore compattezza evelocità, ma il problema vero sta nel fatto che sul mercato non si trovano processoridi questo tipo. Le applicazioni industriali dei processori fuzzy sono molto sviluppatee tuttora in continua crescita soprattutto nel campo del controllo e delriconoscimento di immagini dove il vincolo principale non è la velocità ma ilrisparmio. Per applicazioni in cui la velocità è l’obiettivo primario come larealizzazione di trigger per esperimenti di fisica delle alte energie l’unica soluzionepossibile è quella di progettare interamente un processore fuzzy cercando diutilizzare tutti gli accorgimenti che ne accelerino i tempi di esecuzione.