CEB NT - 97 / 02

16 / 5 / 1997



Proposta su


USO DI reti cellulari PER LA Selezione di eventi
 
 

I.D'Antone
 
 

Istituto Nazionale di Fisica Nucleare

Bologna,Italy


 
 


1. Introduzione
 
 

Nei sistemi di trigger per calorimetri, gli algoritmi di clustering per la localizzazione dell'energia depositata fanno riferimento a tecniche di elaborazione su array bidimensionali. I candidati sono selezionati con opportune regole sui valori di energia depositata in ogni cella. Come nell'analisi delle immagini si hanno da elaborare pixels con diversi valori di grigio. L'energia e' spesso quantizzata in un opportuno numero di bit, scelto in base all'efficienza voluta dal sistema di trigger.

In passato sono state adottate diverse soluzioni analogiche e digitali, tra cui architetture di calcolo parallelo, come array sistolici o automi cellulari. Ad esempio, recentemente, per il pretrigger del calorimetro elettromagnetico di un esperimento ad HERA, la selezione e' stata realizzata con un automa cellulare appartenente alla classe I di Wolfram [1], con celle a quattro stati. L'algoritmo e' stato effettuato usando quattro volte lo stesso automa cellulare, sintetizzato in una FPGA, per ottenere una elaborazione completa entro 96ns.

Le celle degli automi cellulari sono generalmente a pochi bits e quindi spesso e' richiesto il partizionamento dell'algoritmo in piu' automi.

Recentemente stanno trovando interessanti applicazioni nella elaborazione delle immagini, specie quelle in movimento, le reti neurali cellulari (CNN), la cui architettura viene considerata una evolutione degli automi cellulari (CA).
 
 
 
 

2. Reti cellulari
 
 

2.1 Automi cellulari
 
 

Gli automi cellulari (CA) sono stati concepiti originalmente da Ulam e Von Neumann nel 1940s per
 
 

fig.1


 
 


fornire una struttura formale allo studio dei sistemi complessi. I CAs sono sistemi dinamici in cui lo spazio e il tempo sono discreti [1].

Un automa cellulare consiste di una griglia regolare di celle (fig1), ciascuno delle quali può trovarsi in un numero limitato di k stati possibili, aggiornati in modo sincrono in passi di tempo discreti secondo a un'unica legge di interazione locale. Lo stato di una cella è determinato dagli stati precedenti di un intorno circostante di celle.
 
 
 
 

2.2 Reti neurali cellulari
 
 

Le reti neurali cellulari (CNN) sono delle strutture intrinsecamente parallele ed analogiche e pertanto si pongono quali strumenti di elaborazione veloci per sistemi organizzati a matrice, come le immagini. Inoltre, a differenza delle reti neurali classiche, si possono realizzare piu' facilmemte in VLSI, in quanto le interazioni con i vicini sono localizzate in un intorno limitato.
 
 

La prima formulazione del modello di rete neurale cellulare (CNN) è riportata in letteratura del 1988 e si deve al prof. L. O. Chua.

Le CNN, costituiscono un particolare tipo di reti neurali artificiali, e possiedono quali caratteristiche peculiari, la capacità di processare le informazioni in modo asincrono parallelo e tempo continuo. Dal punto di vista computazionale, una CNN bidimensionale può essere considerata come una matrice MxN.

Una cella di una rete neurale cellulare può essere implementata attraverso un insieme, localmente interconnesso, di circuiti elettrici elementari (unità della CNN) ciascuno costituito da elementi lineari, come condensatori, resistenze, generatori indipendenti e generatori pilotati, e non lineari implementati anch’essi con generatori pilotati non lineari

Ogni singola cella è in grado di interagire in modo diretto con le celle ad essa adiacenti ed indirettamente con tutte le altre, in base all’effetto di propagazione nel tempo degli "stimoli".

In fig. 2 è rappresentato il circuito elettrico equivalente di una generica cella C(i,j) di CNN [2].

Fig.2

Struttura circuitale di una cella di CNN


Gli indici u, x e y, indicano rispettivamente ingresso, stato ed uscita (quest’ultima rappresentabile mediante una funzione lineare a tratti) del circuito. La "comunicazione" tra la cella C(i,j) e le celle vicine C(k,l) è affidata ai generatori pilotati (in tensione) rappresentati nella suddetta figura.


L’evoluzione dinamica dello stato di una cella C(i,j) di CNN, è retto da un sistema di equazioni differenziali del tipo:
 
 

(1)

con dove ed rappresentano rispettivamente il numero di righe e di colonne della CNN e con rappresentante l’insieme di celle che risiedono nell’intorno di raggio r della cella C(i,j) .

Valgono inoltre le seguenti relazioni:

(2)

con , per quanto riguarda l’uscita della cella;

(3)

con , per quel che riguarda l’ingresso della cella. I parametri A, B e la corrente I vengono denominati "templates". Gli elementi di A e B hanno la funzione di pesi per le equazioni di stato e agiscono come veri e propri operatori di convoluzione, realizzando rispettivamente un feedback in uscita ed un controllo in ingresso; le templates giocano un ruolo fondamentale nelle funzionalità delle CNN, in quanto consentono di realizzare una vera e propria operazione di programmazione delle reti neurali cellulari. Le templates possono essere ottenute per tentativi o ricorrendo a delle apposite librerie già esistenti. Sono attualmente in fase di studio dei metodi di definizione delle templates mediante tecniche di ottimizzazione basate sull’uso degli algoritmi genetici.

La costante di tempo del circuito equivalente di una cella di CNN, e quindi dell’intera rete, essendo trascurabile il tempo di propagazione degli stimoli, dipende dai parametri R e C definiti per lo più dalla tecnologia di integrazione utilizzata (VLSI) e generalmente è compresa tra qualche microsecondo e qualche nanosecondo; tale pertanto, è l’ordine di grandezza dell’intervallo di tempo necessario al raggiungimento della stabilità a regime del suddetto circuito (convergenza della rete neurale cellulare, esistono delle condizioni sufficienti perché ciò sia garantito analiticamente). E’ facile quindi intuire come il processamento dei segnali mediante strutture siffatte nel caso pratico, sia pressoché istantaneo; questa caratteristica, unitamente a quelle sopra menzionate, fa sì che le CNN trovino, come detto, un ottimo campo di impiego nella elaborazione delle immagini in tempo reale [5]. Esistono gia' in letteratura templates per effettuare le classiche elaborazioni su immagini: edge detection, shadow, hole filler, ecc.
 
 
 
 

3. Confronto tra varie architetture cellulari
 
 

Considerando i CA e le CNN come paradigmi di calcolo parallelo e' possibile fare un confronto con altre architetture parallele. Confrontando per esempio con gli array sistolici SA (systolic architecture) si ha:
 
 

data specification
 
 

CA logic value(1-4 bits) truth table

SA numerical values(8-32 bits) numerical algorithm

CNN analog values cloning templates (analog software).
 
 

Per alcune applicazioni e' possibile esportare le regole di progetto dei CA nel progetto delle CNN in modo da ottenere la stessa funzionalita'.
 
 
 
 

4. Le reti cellulari come generatori pseudo-random
 
 

Come i CA anche le CNN possono generare caos deterministico. Lo studio dei sistemi caotici ha recentemente catturato l'attenzione dei ricercatori in quanto permette di spiegare quei fenomeni deteministici in cui l'evoluzione dipende fortemente dai valori iniziali, quello che con espressione caratteristica e' stato chiamato "effetto farfalla".

Lo studio di queste reti cellulari, nella realizzazione digitale, puo' pertanto essere utile come alternativa ai generatori di pattern pseudo-random nelle tecniche di Built-In Test per VLSI.

Per testare moderni chip VLSI o per superare i problemi creati dai package SMD (Surfase Mounted Devices) o dai moduli multi chip sui circuiti stampati si rende indispensabile un buon sistema di test. Per avere quindi un sistema che possa accedere fisicamente ai segnali di input/output su una scheda o dentro ad un chip si usa una tecnica detta Boundary-Scan che consiste nell'introduzione di test point (Boundary-scan cells) su ogni I/O per rendere osservabile e controllabile ogni pin [6].

Quando la catena di celle e' molto lunga e il test potrebbe richiedere molto tempo si usa integrare dentro ogni chip la circuiteria per la generazione e la valutazione della risposta di test (BIST, Built-In Self Test). Per avere inoltre rapidamente un alto fault-coverage, cioe' una frazione alta dei possibili failures che la tecnica puo' rivelare, si e' dimostrata conveniente la generazione pseudorandom dei pattern. Quindi nella tecnica BIST si usano LFSR per generare i pattern e analizzatori di firma (Signature Analyzer) per valutare la risposta del circuito sotto test.

Recentemente sono stati utilizzati automi cellulari per le tecniche di test di circuiti VLSI. I CA si comportano meglio dei classici LFSRs (Linear Feedback Shift Registers) in quanto non mostrano la correlazione di bit dovuta allo shifting degli LFSRs.
 
 
 
 
 
 

5. Proposte di attivita'
 
 

Attualmente molte universita' e centri di ricerca sono impegnati nella implementazione hardware di CNN, mediante tecnologia VLSI. A tal riguardo si ricorda che diversi produttori di circuiti integrati, quali la S.G.S.-Thomson, sono impegnati in tal senso.

L'elemento chiave per ottenere la programmabilita' in una CNN e' rappresentato dalla realizzazione di generatori di corrente controllati in tensione (VCCS) a guadagno selezionabile. Sono state proposte varie soluzioni per la realizzazione di queste reti: alcuni hanno usato amplificatori operazionali a transconduttanza (OTA), altri hanno associato tutte le variabili alle correnti per non avere la combinazione di variabili corrente e variabili tensione, altri ancora hanno tentato con dispositivi ottici. Molti gruppi nel mondo sono attivi in questo settore di ricerca, ma soltanto pochi di essi realizzano effettivamente nuovi chip neurali cellulari. I chip presentati sono per matrici con alcune centinaia di celle.
 
 

Alcune possibili attivita' che possono essere svolte nella nostra sezione per acquisire il know-how su queste tecnologie cellulari, per poterle applicare efficacemente ad esperimenti futuri:
 
 

- realizzazione chip VLSI analogico di una matrice CNN.
 
 

- costruzione di un simulatore per il calcolo dei templates relativi a problemi di selezione eventi

nella fisica delle particelle
 
 

- realizzazione digitale per elaborazioni con piu' di 7 bit (un circuito analogico con precisione

all'1% equivale a circa 7 bit). Comparazione con automi cellulari.
 
 

- studio di tecniche di Built-In Test per VLSI realizzate con reti cellulari.
 
 

- ecc…
 
 

Per concludere bisogna sottolineare un altro utilizzo di queste reti cellulari, anche se non e' strettamente legato alla applicazione indicata in questa proposta, che ci permette di intuire le potenzialita' offerte da queste reti. Far evolvere una rete cellulare si e' dimostrato come uno dei piu' potenti sistemi per studiare la vita artificiale e per capire come l'ordine e l'informazione emergono dalla cooperazione collettiva.
 
 
 
 

Riferimenti
 
 

[1] S.Wolfram, Universality and complexity in cellular automata, Physica D, 10:1-35, 1984
 
 

[2] L. O. Chua and L. Yang, Cellular neural networks: theory, in IEEE Transactions on circuits and systems, vol.35, no, 10, pp. 1257-1259, october 1988.
 
 
[3] P.Kinget, M.Steyaert, A programmable analog Cellular Neural Network Cmos chip for high

speed image processing, IEEE Journal of Solid-State Circuits, Vol.30, no.3, March 1995
 
 

[4] S. Zhang et al., Quantitative Analysis for Linear Hybrid Cellular Automata and LFSR as Built-

In Self-Test Generators for Sequential Faults, J. of Electronic Testing: Theory and Applications,

Vol. 6, pp. 255 - 258, 1995 .

[5] R. Das et al., Evolving Globally Synchronized Cellular Automata, Proceedings of the Sixth

International Conference on Genetic Algorithms, April 5, 1995.
 
 

[6] IEEE Std 1149.1-1990, IEEE Standard Access Port and Boundary-Scan Architecture.
 
 


Page edited by Bisi Fabio