La ricerca si è svolta sotto la supervisione del professor Marco Vanneschi ed in collaborazione con il professor Fabrizio Baiardi, presso il Dipartimento di Informatica dell'Università di Pisa. Essa ha come oggetto la definizione e l'implementazione di meccanismi di concorrenza per il supporto a tempo di esecuzione dei sistemi PQE2000. Uno degli aspetti più interessanti del progetto PQE2000 riguarda la ricerca di una tecnologia avanzata nello sviluppo del software di base. Uno degli obiettivi del progetto è quello di poter sviluppare programmi paralleli in modo indipendente dall'architettura. Il compito di ottimizzare l'uso delle componenti della macchina deve essere delegato, quindi, a potenti strumenti di compilazione. Per questo motivo, il livello microkernel dell'architettura dei sistemi PQE2000 deve comprendere, oltre ai meccanismi di tipo message passing, meccanismi di concorrenza di tipo memoria virtuale condivisa. Questi possono offrire, infatti, un supporto più efficiente per comunicazioni non strutturate, condivisione di dati e scambio di informazioni per il bilanciamento del carico.

I meccanismi di concorrenza che permettono la condivisione di pagine di informazioni tra un insieme di processi paralleli cooperanti sono argomento principale di questa ricerca.

Inizialmente è stato definito un insieme Op_Memory di operazioni per dichiarare ed operare su uno spazio di memorizzazione comune organizzato come un insieme di pagine; le pagine hanno dimensione variabile e sono indirizzate mediante un indirizzo logico globale, identificato con un valore intero non negativo [1]. L'insieme Op_Memory comprende sia operazioni che garantiscono un accesso sincronizzato in lettura e/o scrittura alle pagine di memoria condivisa, sia operazioni di accesso non sincronizzato. I meccanismi per implementare le sincronizzazioni sono trasparenti agli utenti delle operazioni dell'insieme Op_Memory. Utilizzando le operazioni con accesso sincronizzato, perciò, gli utenti non devono effettuare controlli di consistenza durante l'accesso alle informazioni di una pagina. L'esistenza di operazioni di accesso non sincronizzato permette di migliorare l'efficienza delle applicazioni, in tutti quei casi in cui i controlli di consistenza possono essere delegati a strumenti di programmazione di tipo statico ed in cui è possibile provare, sempre mediante opportuni strumenti di programmazione, l'assenza di interferenze sui dati condivisi.

L'architettura PQE2000 è caratterizzata dall'integrazione di macchine MIMD di tipo general purpose a grana medio-grossa, con macchine di tipo SIMD/PIM a grana fine. Per implementare le operazioni di gestione di uno spazio di memoria virtuale condivisa è stata utilizzata, inizialmente, la componente MIMD dell'architettura PQE2000. Su questa componente è stata definita una macchina astratta strutturata a livelli, come supporto a tempo di esecuzione delle funzioni di Op_Memory.

La macchina astratta di livello più basso è costituita dalle librerie del coprocessore di comunicazione Elan. A partire da questa macchina, è stato definito l'insieme Semaphors, che comprende le funzioni per implementare i meccanismi di sincronizzazione, e l'insieme Shared_Memory, che comprende le funzioni per la gestione a basso livello della memoria condivisa. Le funzioni di Shared_Memory implementano il supporto della libreria Op_Memory.

A livello Shared_Memory lo spazio di memorizzazione comune è caratterizzato da blocchi di memoria allocati nelle aree di memoria private dei processi dell'applicazione. L'indirizzo logico di questi blocchi è costituito dalla coppia (identificatore del processo, indirizzo logico locale al processo). Le funzioni di Shared_Memory utilizzano le funzioni dell'insieme Semaphors per implementare le operazioni di sincronizzazione e le librerie del processore Elan per implementare le operazioni di lettura e scrittura di blocchi di memoria. In particolare, per quanto riguarda la lettura e la scrittura su blocchi di memoria remota sono state utilizzate le operazioni DMA, messe a disposizione dalla libreria Elan Widget. A livello Shared_Memory non compare ancora l'organizzazione a pagine della memoria condivisa. Perciò questo livello rende trasparente alle funzioni del livello superiore sia i meccanismi di protezione degli accessi alle pagine condivise, che quelli di traduzione da indirizzo logico globale della pagina, al suo indirizzo di allocazione nella memoria privata di un processo. L'interfaccia fra l'insieme Shared_Memory e l'insieme Op_Memory è gestita da una funzione che utilizza strutture dati, inizializzate in fase di dichiarazione delle pagine condivise. Ogni utente, infatti, prima di poter utilizzare lo spazio di memoria comune, deve dichiarare le pagine che vuol condividere mediante la funzione O_Share di Op_Memory. Nell'esecuzione di questa funzione avviene lo scambio, la ripartizione e l'allocazione delle pagine di memoria comune dichiarate da ogni processo. Viene, inoltre, costruita la tabella di traduzione delle pagine (TTP), utilizzata dalla funzione interfaccia per tradurre gli indirizzi globali delle pagine.

Tutte le altre funzioni dell'insieme Op_Memory hanno una struttura standard: esse invocano prima la funzione interfaccia e quindi le funzioni di lettura, scrittura e sincronizzazione, appartenenti all'insieme Shared_Memory.

L'implementazione delle funzioni dell'insieme Op_Memory e delle funzioni di accesso dell'insieme Shared_Memory è illustrata nel documento [1].

L'implementazione delle funzioni di sincronizzazione dell'insieme Shared_Memory e delle funzioni dell'insieme Semaphors è illustrata, invece, nel documento [2].

L'insieme Semaphors è utilizzato per implementare il supporto a tempo di esecuzione dei meccanismi di sincronizzazione; esso comprende sia funzioni che consentono accessi indivisibili a locazioni di memoria remota, tipo Lock e Unlock, sia funzioni per operare su strutture dati di tipo Semaforo, come Wait e Signal. Queste funzioni sono state implementate utilizzando le librerie del coprocessore di comunicazione [3],[4]. Queste librerie offrono operazioni primitive per gestire il tipo evento, definito per sincronizzare i processi, ed operazioni atomiche con cui ogni processo può leggere ed aggiornare, in modo indivisibile, locazioni di memoria remote. Un evento è una locazione di memoria il cui contenuto specifica lo stato in cui esso si trova. Con le primitive a disposizione un processo può sospendersi su un evento, può interrogare il suo stato, può modificarlo. Non esistono, però, primitive per sospendere un processo su un evento remoto e per gestire liste di processi sospesi. Per questo motivo le operazioni tipo Wait e Signal sono state implementate completamente a software.

Il documento [2] analizza e valuta, in termini di prestazioni, implementazioni alternative dei meccanismi di sincronizzazione che utilizzino queste funzionalità.

Tutte le funzioni dell'insieme Op_Memory sono state testate utilizzando il sistema PQE2000 messo a disposizione dal centro di calcolo del centro Enea della Casaccia, Roma. È disponibile, inoltre, un manuale utente per la libreria Op_Memory [5]; esso descrive le istruzioni per compilare ed eseguire applicazioni parallele che utilizzano la libreria; il manuale descrive, inoltre, la sintassi, i parametri e la semantica di ogni funzione di Op_Memory, le costanti e le variabili dell'ambiente di sviluppo, la gestione degli errori e una serie di esempi di programmazione.

Le funzionalità per la gestione di uno spazio di memoria comune virtuale sono state in seguito aumentate, introducendo la possibilità di dichiarare una pagina globale come unione di altre pagine [6] e definendo nuove funzioni di accesso [7]. Esse permettono di accedere ed operare su posizioni contigue di una pagina di memoria comune senza interferire sul contenuto del resto della pagina. Le sezioni sono identificate con un displacement ed un offset.

Il progetto PQE2000 prevede di utilizzare i meccanismi di concorrenza di tipo memoria virtuale condivisa non solo per il supporto di linguaggi di programmazione concorrente, ma anche per quello dei costrutti previsti da interfacce standard, quale ad esempio MPI. Attualmente è in corso una implementazione preliminare delle funzioni MPI, che riguardano le operazioni collettive e la gestione dei comunicatori, utilizzando la memoria virtuale condivisa. In particolare, considerando MPI allo stesso livello di macchina astratta di Op_Memory, è stato deciso di utilizzare il livello Shared_Memory come supporto per entrambi, Questa implementazione deve permettere di valutare i vantaggi derivati dall'utilizzo delle memoria virtuale condivisa rispetto all'uso di funzionalità basate sullo scambio di messaggi.

I risultati ottenuti fino a questo punto della ricerca, permettono di affermare che le prestazioni delle funzioni definite per la gestione della memoria comune virtuale non sono del tutto soddisfacenti quando occorre utilizzare operazioni di sincronizzazione. Questo è dovuto al fatto che le funzioni a livello Semaphors, implementate con le librerie messe a disposizione dall'architettura PQE2000, richiedono una forte interazione fra processore principale e processore di comunicazione. Questo aspetto, oltre ad avere un impatto negativo sulle prestazioni, limita il processore di comunicazione a semplice servente del processore principale. Un interessante sviluppo della ricerca è, allora, quello che prevede una implementazione dei meccanismi di sincronizzazione mediante il codice del coprocessore di comunicazione e non mediante le librerie messe attualmente a disposizione dall'architettura PQE2000. In questo modo, infatti, il processore di comunicazione può gestire tutta la parte che riguarda lo scambio di informazioni per la sincronizzazione senza ritardare l'esecuzione del processore principale. Questa strategia, oltre a diminuire gli overhead dovuti all'interazione fra processore principale e processore di comunicazione, sfrutta più efficientemente il parallelismo sul nodo.

Un altro interessante sviluppo della ricerca è quello che estende anche alla componente SIMD/PIM dell'architettura PQE2000 la possibilità di accedere alle pagine della memoria virtuale condivisa.

Riferimenti

I linguaggi paralleli strutturati permettono la scrittura di programmi paralleli a partire da un insieme di pattern tipici di parallelismo (gli skeleton); questa caratteristica limita la struttura delle computazioni parallele che possono essere definite dal programmatore a quelle ottenibili instanziando e annidando gli skeleton nel linguaggio. Tipici skeleton sono: il pipe, che modella il funzionamento di una cascata di processi paralleli relativi a stadi successivi della computazione, e il farm, che astrae il comportamento di un insieme di worker funzionalmente equivalenti che cooperano per eseguire un insieme di task.

La limitazione imposta dai linguaggi basati su skeleton viene sfruttata all'interno del supporto e del compilatore per dare una soluzione efficace a problemi (come il mapping, lo scheduling, la scelta della granularità) in generale intrattabili per computazioni parallele con struttura arbitraria. La tecnica utilizzata per ottenere questo risultato si basa sull'utilizzazione di reti parametriche di processi dette template di implementazione. Per ogni skeleton è definito un insieme di template che implementano le istanze dello skeleton utilizzando diverse strategie. Ogni template è parametrico rispetto ai dati in ingresso e in uscita allo skeleton, al numero di risorse utilizzate e alla granularità della computazione eseguita. Inoltre, per ogni template è definito un modello analitico di prestazioni che permette di derivare stime accurate del comportamento della rete al variare dei parametri in gioco.

Il template e il modello vengono utilizzati dal compilatore del linguaggio per derivare reti di processi ottimizzate per una particolare istanza degli skeleton ammessi nel linguaggio.

I problemi principali da risolvere per derivare un sistema basato su skeleton, come quello proposto dall'ambiente integrato SKIE di PQE-2000, sono i seguenti:

- progettare strategie efficienti per implementare ogni skeleton sulla architettura target e sviluppate i corrispondenti template parametrici,

- derivare i modelli analitici di prestazioni per ogni template,

- definire una strategia automatizzabile per la composizione (annidamento) di template e derivare modelli analitici relativi alla composizione.

Il seminario presenta il lavoro svolto per la soluzione di questi problemi nell’ambito del linguaggio di coordinamento dell'ambiente integrato SKIE. In questo caso il target per la compilazione degli skeleton è rappresentato dalla interfaccia standard MPI, presente sulla piattaforma PQE-2000.

In particolare il seminario illustrerà le varie attività svolte che sono riassunte nei seguenti paragrafi.

DEFINIZIONE MACCHINA ASTRATTA

È stata studiata l'interfaccia standard MPI ed è stato individuato un insieme di primitive che fosse abbastanza flessibile da riuscire ad esprimere al meglio i vari template e, allo stesso tempo, abbastanza piccolo da poter essere studiato approfonditamente dal punto di vista delle prestazioni e portato agevolmente su altre piattaforme.

Questo studio ha permesso di definire una macchina astratta molto semplice e versatile che comprende un sottinsieme piccolo delle comunicazioni punto a punto ed alcune comunicazioni collettive MPI. Ogni operazione della macchina astratta è stata analizzata, per ragioni di portabilità, sia su piattaforma CS-2 (con 7 nodi) che su piattaforma Fujitsu AP-1000 (con 128 nodi). Dagli studi effettuati sono stati derivati dei costi utilizzati per derivare i modelli analitici dei template.

STUDIO DEI TEMPLATE PER COSTRUTTI FARM E PIPE

Sono state sviluppate strategie di implementazione per farm e pipeline con quantità variabile di risorse, con granularità variabile e con carico sbilanciato fra i vari task in esecuzione. Le strategie sviluppate sono state implementate in template prototipo sulla macchina astratta discussa precedentemente. Per ogni template è stato sviluppato il corrispondente modello analitico che è stato testato e validato sulle macchine target suddette.

SVILUPPO METODOLOGIA PER L'ANNIDAMENTO DEI TEMPLATE

Relativamente ai template sviluppati è stata derivata una metodologia automatizzabile che permette di costruire l'implementazione di programmi contenenti skeleton pipe e farm arbitrariamente annidati a partire dai template sviluppati. La metodologia è stata poi dettagliata e validata tramite lo sviluppo di un cross-compilatore prototipo che, accettando programmi scritti con un annidamento qualsiasi di farm/pipe e moduli sequenziali, instanzia opportunamente i template consultando i modelli analitici derivati. Questo ha permesso di effettuare un vasto insieme di test sulla metodologia proposta e di dettagliare e sperimentare gli aspetti relativi alla rappresentazione interna dei template e alle procedure automatiche di generazione del codice.

VALIDAZIONE ESTENSIVA DEI TEMPLATE

Utilizzando il prototipo sono stati effettuati un gran numero di esperimenti che ci hanno permesso di validare i modelli analitici e le strategie dei template in presenza di elevati livelli di annidamento. I risultati sono stati soddisfacenti sia per quanto riguarda la stabilità dei modelli che per la performance assoluta delle reti di processi generate. Tramite una accurata ottimizzazione dei canali di comunicazione l'overhead dovuto alle gestione delle reti generate è molto basso rispetto a implementazioni ad hoc delle stesse istanze dello skeleton. Inoltre lo scarto fra tempi predetti e misurati è di solito molto basso (sotto il 5%).

DERIVAZIONE DI STRATEGIE DI OTTIMIZZAZIONE

Infine, sempre utilizzando il prototipo per le sperimentazioni, sono state messe a punto un insieme di ottimizzazioni per costrutti annidati che potranno poi esser utilizzate nel compilatore SKIE ``full-features''. In particolare, abbiamo derivato regole per stabilire la granularità ottimale in presenza di annidamenti, regole per stabilire il numero ottimale di worker per istanze di farm con annidamento arbitrario, ed euristiche per bilanciare gli stadi dei costrutti pipe.

La componente SIMD del progetto PQE2000 verrà basata sul calcolatore a parallelismo massiccio APEmille, attualmente in fase di sviluppo da parte dell'INFN presso le sezioni di Pisa e Roma. La più piccola unità di calcolo disponibile in APEmille è la Processing Board (PB) che contiene 8 unità logico-aritmetiche in virgola mobile.

Ognuna di queste schede usa un link proprietario per le comunicazioni fra i differenti nodi i calcolo. Per le normali operazioni di I/O e di controllo viene invece usato il bus standard CompactPCI (CPCI). Un gruppo di quattro PB condivide un unico bus CPCI ed è chiamato Processing Unit (PU).

Per il controllo delle diverse PU di cui sarà formato, APEmille utilizzerà un insieme di calcolatori detti host, ognuno connesso ad un singolo bus CPCI. Questi calcolatori saranno normali PC industriali su singola scheda inseribili in rack ed utilizzeranno il sistema operativo Linux.

La principale caratteristica che la rete di comunicazione dei calcolatori host di APEmille deve avere è la bassa latenza. Tale richiesta deriva dalla necessità di dover effettuare particolari operazioni sulla macchina con la minima differenza di tempo tra le differenti PU. Una elevata banda passante permetterebbe inoltre rapide operazioni di I/O come il caricamento di dati e/o programmi.

Nonostante le comunicazioni fra le componenti MIMD e SIMD di PQE2000 siano strutturalmente diverse, il raggiungimento di elevate prestazioni nella rete di computer host di APEmille permetterà di acquisire conoscenze di base sulle problematiche inerenti le connessioni fra le due componenti di PQE2000.

Mentre in una prima fase di sviluppo potrà essere possibile usare tecnologie standard e ampiamente diffuse come ethernet o fast-ethernet per facilitare un più agevole debugging del software di sistema, la configurazione definitiva prevede l'uso di schede di comunicazione appositamente sviluppate presso il laboratorio DESY di Zeuthen.

Caratteristica principale di queste schede è quella di implementare un protocollo di comunicazione specifico direttamente in hardware consentendo una gestione del traffico sulla rete più veloce e senza carico per il sistema operativo. Queste schede di comunicazione useranno un bus parallelo di ampiezza ridotta con velocità superiore a 100 MByte/s. Ogni scheda avrà due canali di comunicazione: uno in ingresso ed uno in uscita. La topologia della rete sarà quella di un anello: ogni PC sarà collegato ai due adiacenti a formare un circolo chiuso nel quale i dati fluiranno sempre nello stesso verso.

L'attività svolta in questo primo anno di studio si è fondamentalmente concentrata sull'implementazione di device drivers per schede PCI in ambiente Linux e l'analisi delle loro prestazioni utilizzando diversi tipi di schede PCI già disponibili e simili al modello definitivo.

In particolare l'attività svolta si è sviluppata sui seguenti punti:

1. Scrittura di un driver generico per il chip che implementerà l'interfaccia verso il bus PCI sulle schede di comunicazione;
2. Analisi delle prestazioni del kernel di Linux con questo driver;
3. Scrittura di un driver specifico a bassa latenza ottimizzato per le schede di comunicazione di APEmille e prime analisi su di esso.

I test effettuati su questi driver ci hanno permesso di misurare alcuni tempi caratteristici riguardanti le interazioni di basso livello fra hardware PCI e sistema operativo in un PC standard. Le varie misure che hanno permesso una prima serie di stime sulle prestazioni che sarà possibile ottenere nelle comunicazioni fra APEmille e il mondo esterno sono state:

• Latenza di un interrupt sul bus PCI e suoi tempi di gestione all'interno del kernel di Linux;
• Banda passante realmente visibile da una applicazione verso device sul bus PCI;
• Banda passante e latenza del solo hardware;
• Overhead imposto dai diversi tipi di driver e dalle loro interazioni con il sistema operativo.

L'attività futura sarà finalizzata allo sviluppo di un driver per la scheda definitiva particolarmente ottimizzato per le comunicazioni di APEmille ed alla sua integrazione nel sistema operativo. Il driver dovrà avere il minimo impatto sulla latenza delle comunicazioni e tenere conto della particolare struttura della rete e del protocollo utilizzato.

L'alta velocità di comunicazione permessa dall'hardware imporrà lo studio di una struttura particolare per il software. In particolare per il raggiungimento di bassi valori di latenza si potranno utilizzare strutture che ottimizzino il flusso dei dati dalle applicazioni all'hardware.

La futura disponibilità delle reali schede di comunicazione Flink permetterà inoltre di effettuare misure di latenza e banda passante fra diversi host, verificando così le reali prestazioni della rete in diverse situazioni di traffico.

 La partecipazione al workshop verterà sui risultati dello studio concernente l’introduzione di comunicazioni "morbide" in APEmille, studio che è stato oggetto del primo anno della borsa di studio.

 Tali comunicazioni rappresentano un ampliamento delle funzionalità di routing già presenti in APEmille in quanto realizzano una modalità più generale di instradamento dei messaggi. Infatti, mentre le comunicazioni "rigide" attualmente implementate in APEmille modellano un pattern di comunicazione in cui l’indirizzo relativo del nodo destinatario rispetto al nodo mittente deve essere uguale per tutti i nodi comunicanti, le comunicazioni "morbide" consentirebbero ai nodi di comunicare in maniera indipendente l’uno dall’altro, dal momento che ognuno potrebbe scegliere arbitrariamente il nodo destinatario per i propri messaggi.

 Durante il primo anno della borsa di studio, è stato pertanto studiato un algoritmo per realizzare le comunicazioni "morbide", ottenuto come una variante di risultati già noti in letteratura; tale algoritmo effettua lo smistamento dei messaggi secondo la tecnica di switching store-and-forward (i messaggi sono interamente memorizzati in buffer dei nodi di comunicazione prima di essere instradati sui links successivi) e dirotta i messaggi (misrouting) se non v’è spazio sufficiente per essi (ovvero li instrada su un link di comunicazione che li allontana momentaneamente dalla loro destinazione).

L’algoritmo proposto è stato simulato per varie configurazioni della macchina (grandezza e numero dei buffer contenuti in ogni nodo di comunicazione, differenti politiche di selezione nel dirottamento dei messaggi) e per vari pattern di comunicazione.

La presentazione al workshop verterà pertanto sugli aspetti seguenti:

• introduzione generale sugli aspetti salienti della comunicazione in macchine parallele e, in particolare, SIMD;

• esposizione dell’algoritmo studiato in relazione ai risultati noti in letteratura;
• risultati delle simulazioni effettuate su pattern di traffico di particolare interesse, quale quello generato dalla FFT.

 L’esposizione dell’algoritmo sarà accompagnata da una breve panoramica dei risultati già noti nel campo delle comunicazioni "morbide" del tipo store-and-forward con misrouting e, inoltre, saranno messe a confronto le prestazioni dell’algoritmo in relazione a quelle di algoritmi già noti.

 La discussione dei risultati delle simulazioni relative alla FFT sarà preceduta da un’illustrazione di alcuni aspetti implementativi della FFT su una macchina parallela, e in particolar modo sulle problematiche relative alla gestione del pattern di traffico generato dal calcolo della FFT su una macchina di tipo SIMD.

L’analisi dei risultati (ottenuti con una serie di simulazioni effettuate su una configurazione realistica della macchina) metterà in rilievo come variano le prestazioni nel calcolo della FFT al variare di fattori quali il numero e la grandezza dei buffers sui nodi di comunicazione permettendo un primo confronto tra adozione di comunicazione "morbide" e adozione di comunicazioni "rigide".

 Nella parte finale dell’intervento saranno date delle indicazioni sui miglioramenti che si intende apportare all’algoritmo allo scopo di una reale implementazione dello stesso nelle future versioni di APEmille; in particolare, verrà proposta e discussa l’adozione di una tecnica di switching alternativa, in cui l’instradamento dei messaggi è effettuato non appena i dati di testa, contenenti le informazioni di routing, arrivano sui nodi di comunicazione, senza attendere che l’intero messaggio sia memorizzato.

Introduzione

Le equazioni differenziali alle derivate parziali costituiscono uno strumento fondamentale nella modellizzazione matematica di molti fenomeni di varia natura. Le equazioni ellittiche di tipo Poisson, fra queste, oltre a descrivere di per sé alcuni di questi fenomeni, sono anche il nucleo computazionale per la risoluzione di equazioni più complesse.

Negli scorsi decenni l'attività di ricerca volta all'individuazione di metodi ed algoritmi per una risoluzione numerica efficiente ed accurata delle equazioni di tipo Poisson ha individuato tre classi di metodi: Fast Poisson Solvers, metodi iterativi e metodi Multigrid.

L'attenzione è stata rivolta ai metodi della classe dei Fast Poisson Solvers (FPS), considerata anche l'efficienza con la quale questi ultimi sono stati implementati in importanti packages di programmi numerici per la risoluzione di problemi ellittici, quali ELLPACK e FISHPACK.

I FPS sono metodi diretti nati per la risoluzione numerica di problemi al contorno per l'equazione di Poisson e poi estesi ad una classe più ampia di problemi differenziali ellittici (equazione di Helmholtz, equazioni ellittiche separabili). L'appellativo Fast è legato al fatto che tali metodi permettono di risolvere il problema discreto associato al problema differenziale con una complessità computazionale dell'ordine di , dove è la dimensione del problema discreto, inferiore rispetto a quella dei metodi classici ().

La classe dei FPS è costituita da algoritmi basati sui metodi di: Analisi di Fourier (FA), Riduzione Ciclica a Blocchi (BCR), Marching Generalizzato (GM). Essa può essere estesa aggiungendo ai metodi sopra elencati metodi che sono combinazioni di alcuni di essi. La più classica di tale combinazione è l'algoritmo denominato FACR (Fourier Analisys-Cyclic Reduction). 

Attività svolta

Alcune analisi effettuate sull'efficienza di implementazioni parallele degli algoritmi di FPS [2] hanno permesso di evidenziare una sostanziale equivalenza fra i diversi algoritmi. Si è quindi scelto di implementare il metodo di Fourier Analysis considerato che quest'ultimo meglio si presta ad una implementazione parallela.

Nella parallelizzazione dell'algoritmo di Fourier Analysis si individuano due fasi distinte: una fase di calcolo (calcolo di DFT e IDFT multiple, risoluzione di sistemi tridiagonali multipli), per la quale è utilizzabile software sequenziale, e una fase di comunicazione fra processi (fase di trasposizione globale dei dati).

Gli elementi di software sviluppati utilizzano strategie di message passing per la comunicazione fra processi. Il software sviluppato soddisfa le esigenze di portabilità dal momento che si è utilizzato per il message passing software ampiamente diffuso quale Basic Linear Algebra Communication Subprograms (BLACS), disponibile oltre che per lo standard proposto MPI, per i sistemi di comunicazioni nativi delle più diffuse macchine parallele.

Sono stati effettuati esperimenti sull'accuratezza della soluzione calcolata e sull'efficienza della strategia di parallelizzazione dell'algoritmo di FA. Gli esperimenti effettuati su macchine MIMD quali Intel iPSC/860 hanno dato soddisfacenti risultati in termini di efficienza dell'algoritmo.

Attività da svolgere

Le esperienze fin qui acquisite saranno trasferite nell'ambiente PQE2000, i cui prototipi sono disponibili al CPS dai primi di gennaio nell'ambito C3P. In particolare, in tempi brevi, si intende implementare e valutare il software sviluppato sulla sola componente MIMD per un confronto delle prestazioni con architetture quali Intel iPSC/860 ed IBM SP.

Si intende inoltre riorganizzare e implementare l’algoritmo sviluppato in modo da utilizzare al meglio la combinazione delle parti SIMD e MIMD mediante il software previsto per PQE2000 (SkIE, HPF). 

Referenze

[1] B.L. Buzbee, G.H. Golub, and C.W. Nielsen, On Direct Methods for Solving Poisson’s Equations, SIAM J. Num. Anal., 4, 1970,627-656.

[2] D. di Serafino, A. Murli, and F. Perla, A Fast Poisson Solver for Distributed Memory Multiprocessors, Concurrency Practice & Experience , 4(7), 1992,499-508.

In una simulazione dinamica di sistemi coulombiani (come soluzioni acquose o plasmi) o gravitazionali lo sforzo computazionale più rilevante è dato dal calcolo delle interazioni di coppia a lungo raggio.

Quando il numero di particelle cresce in maniera rilevante il calcolo diretto esplicito delle interazioni può diventare proibitivo, e d'altra parte non è possibile applicare tagli (al potenziale di ogni particella nel sistema devono contribuire tutte le altre): si deve quindi ricorrere a metodi approssimati.

I metodi più comuni fanno ricorso a griglie o a strutture gerarchiche ad albero. Il Fast Multipole si pone fra questi ultimi e si basa sullo sviluppo del potenziale di campo in armoniche sferiche.

Il box computazionale viene partizionato ricorsivamente in celle in una struttura ad albero. All'interno di ogni cella del livello di suddivisione più fine vengono calcolati i coefficienti dell'espansione di multipolo dati dalle cariche contenute, arrestandosi all'ordine prescelto. Tramite una serie di trasformazioni di questi coefficienti, sfruttando l'albero in maniera efficiente, si arriva a determinare per ogni celletta un'espansione a convergenza locale che ne descrive il campo all'interno dovuto a tutte le cariche che stanno oltre le cellette vicine. Per ogni particella si valuta quindi il campo usando questa espansione e si calcolano direttamente i contributi dei primi vicini.

Il vantaggio di questo metodo rispetto agli altri è quello di avere un andamento migliore in termini di prestazioni (è un algoritmo di ordine N) e di riuscire a controllare esattamente l'errore compiuto nell'approssimazione.

I suoi principali campi d'applicazione sono: Dinamica Molecolare, Astrofisica, Fluidodinamica. Ci si è soffermati principalmente sul primo ed in particolare sullo studio di sistemi molecolari d'interesse biologico come le proteine.

L'algoritmo permette di aumentare le scale dei tempi caratteristici delle simulazioni di questi sistemi consentendo di analizzarne proprietà altrimenti non stimabili.

 E' stata analizzata un'implementazione dell'algoritmo Fast Multipole su PQE2000.

Il calcolo delle forze per questi sistemi può essere fatto completamente utilizzando un'architettura SIMD come quella tipica del progetto APE.

Sono state affrontate le problematiche connesse con il mapping della struttura ad albero sui nodi della macchina. L'algoritmo presenta parti di calcolo (come le interazioni dirette fra celle prime vicine e il calcolo di espansioni di multipolo) che sono intrinsecamente parallele, mentre in altri punti (come nel calcolo delle espansioni a convergenza locale) sono necessari trasferimenti di dati tra i nodi.

E' stato studiato uno schema per una gestione ottimizzata di questi trasferimenti utilizzando le comunicazioni sincrone tipiche dell'architettura di PQE2000. Si è anche visto come siano possibili soluzioni che usano schemi di comunicazione asincrone.

Un altro aspetto importante nell'implementazione dell'algoritmo è il load balancing: nell'evoluzione dinamica del sistema le particelle si sposteranno dalle rispettive celle e quindi anche dai rispettivi nodi. E' cruciale quindi, sia per ragioni di efficienza, sia per effettuare il calcolo dei multipoli e delle interazioni dirette in SIMD, che prima di ogni passo d'integrazione ogni nodo contenga uno stesso numero, opportunamente bilanciato, di particelle.

Questo può essere fatto utilizzando particelle fittizie che non influiscono in alcun modo sul campo e trasferendo le particelle tra i nodi, simulando comunicazioni asincrone per mezzo di quelle sincrone, ricorrendo alle comunicazioni asincrone quando queste saranno disponibili, o riorganizzando la mappatura delle particelle sui nodi di calcolo tramite la parte MIMD della macchina.

E' anche possibile combinare tra loro queste tecniche per trovare un giusto equilibrio fra l'efficienza del calcolo e la velocità dell'operazione di bilanciamento.

Un altro aspetto interessante implementabile sull'architettura è la possibilità di studiare contemporaneamente lo stesso sistema in condizioni differenti usando per ognuna un sottoinsieme distinto della macchina.

Infine si è studiata l'implementazione delle operazioni fondamentali dell'algoritmo ad un elevato livello di astrazione per mezzo di librerie ZZ/Tao di tipi e operatori; tale libreria, operando sulle espansioni di multipolo e locale può essere parametrizzata nell'ordine dello sviluppo scelto, in modo da generare automaticamente un codice inline il più efficiente possibile.

La tolleranza dei guasti o fault tolerance è uno dei problemi di maggiore interesse nella realizzazione di sistemi di calcolo a parallelismo massiccio. Infatti a causa di guasti che possono interessare i componenti della macchina, la computazione in corso può non giungere a terminazione o può essere portata a termine compromettendo la correttezza dei risultati. Si rende quindi necessario dotare il sistema di opportuni strumenti hardware e software, che permettano di rilevare e confinare i componenti guasti e ripristinare la computazione in uno stato corretto.

Le tecniche più note per realizzare la fault tolerance sono quelle che si basano sulla ridondanza delle risorse hardware del sistema, cioè sulla duplicazione o più in generale sulla replicazione di unità. Queste tecniche risultano pertanto molto dispendiose e la loro applicazione è in generale limitata a sistemi destinati ad eseguire computazioni assai critiche. Un approccio alternativo è quello che va sotto il nome di system level diagnosis. Tale approccio realizza la fault tolerance impiegando per piccole frazioni di tempo le unità che compongono il sistema (in una architettura completamente distribuita i processori e la loro memoria locale e la struttura di interconnessione) e supponendo che ogni unità sia capace di eseguire un test sulle unità ad essa connesse. In generale la strategia di test è la seguente:

1. Tutte le unità del sistema eseguono un medesimo programma di test;
2. Le uscite prodotte da unità adiacenti sono confrontate mediante comparatori;
3. I risultati prodotti dai comparatori, dette sentenze, sono accumulati in appositi registri di stato.

 L’insieme di tutte le sentenze costituisce la sindrome del sistema. È noto dalla teoria che data una sindrome è possibile individuare le unità guaste tenendo conto della possibilità che le sentenze possono essere invalidate da guasti nei comparatori. L’individuazione dei guasti, chiamata diagnosi, è affidata ad un osservatore esterno il quale ricevute le sentenze applica ad esse un algoritmo detto algoritmo di diagnosi.

Nell’ambito del progetto PQE2000 l’istituto IEI del CNR e la sezione dell’INFN di Pisa hanno in corso un progetto per realizzare la fault tolerance per la componente SIMD di PQE2000, rappresentata dal calcolatore APEmille, applicando metodologie di auto-diagnosi.

I comparatori necessari per eseguire i test ed altri supporti hardware sono stati integrati nel chip di comunicazione Cheetah. Pertanto l’attività svolta in questo primo anno di studio è stata fondamentalmente concentrata sulla introduzione di queste funzionalità nel chip Cheetah e sulla loro verifica.

 In particolare l’attività si è articolata nei seguenti punti:

• Studio della strategia di diagnosi per APEmille e definizione dei relativi algoritmi;
• Definizione dei vettori di test per il chip Cheetah;
• Nell’ambito più generale della realizzazione del simulatore di APEmille, sviluppo e test del modulo relativo al chip Cheetah, anche ai fini del suo impiego per verificare le parti più critiche del sistema di auto-diagnosi.

 L’algoritmo di auto-diagnosi scelto è stato sviluppato dall’Università di Pisa in collaborazione con l’istituto IEI del CNR di Pisa. Tale algoritmo è applicabile a sistemi con struttura di interconnessione a maglia toroidale a tre dimensioni, ed è stato dimostrato che esso permette di individuare correttamente lo stato (guasto o funzionante) di quasi tutti i processori nell’ipotesi che la percentuale di unità guaste non superi una soglia dichiarata dall’algoritmo medesimo in funzione della sindrome corrente. È stato anche dimostrato che tale soglia non è mai inferiore ad un valore dell’ordine di N^2/3 dove N è il numero delle unità del sistema. Per i valori di interesse pratico tale percentuale è inferiore al 10%. Inoltre si è verificato che, se non si supera quest’ultima soglia, le unità del sistema non diagnosticate (ovvero di quelle per le quali non si riesce ad individuare il loro stato) è mediamente non superiore a due.

Dal punto di vista della strategia di diagnosi il sistema APEmille può essere visto come l’insieme di tre differenti sottosistemi: quello delle unità Tarzan, quello delle unità Cheetah e quello delle unità Jane. Ogni sottosistema ha una struttura di interconnessione regolare a maglia tridimensionale e pertanto l’algoritmo di diagnosi è applicabile indipendentemente, almeno in prima approssimazione, a ciascun sottosistema. In ogni sottosistema i test sono realizzati mediante l’utilizzo di appositi comparatori, fisicamente integrati nel chip Cheetah. L’uscita di ogni comparatore e quindi memorizzata in un registro di stato. I test tra le unità del sottosistema Tarzan e del sottosistema Cheetah sono effettuati concorrentemente all’esecuzione di un qualsiasi job, mentre quello del sottosistema Jane richiede l’utilizzo di una speciale sessione di test durante la quale tutte i Jane eseguono lo stesso programma di test operando su uno stesso insieme di dati. Nella sessione di test per effettuare i test dei Jane viene utilizzato un apposito dispositivo hardware, chiamato Equal, in grado di realizzare sia il test dei Jane di una medesima board che quello tra board adiacenti

Nel corso del primo anno la mia attività ha riguardato oltre che la definizione della strategia di auto-diagnosi e dei relativi supporti hardware anche e soprattutto lo sviluppo del modulo di simulazione del chip Cheetah della macchina APEmille a livello di linguaggio C, nel quale sono state ovviamente integrate le funzionalità introdotte espressamente per l’auto-diagnosi. Tale modulo ha consentito di confrontare il modello VHDL con quello C, ovvero con un modello di descrizione più astratto e quindi più facile da predire e comprenderne il funzionamento. Inoltre e’ stato utilizzato per confrontare le uscite prodotte dal simulatore VHDL con quelle prodotte dal simulatore C in corrispondenza dei vettori di test dati in input. Per verificare la correttezza funzionale di ogni operazione supportata dal chip Cheetah ho inoltre contribuito a sviluppare un apposito set di vettori di test. Tali vettori sono stati elaborati dai tool di simulazione, messi a disposizione dagli ambienti di sviluppo di Synopsys e Cadence. Ad esempio, alcuni vettori di test sviluppati sono stati utilizzati per verificare il funzionamento delle seguenti funzionalità:

• Le operazioni di canale che si possono effettuare in system mode come le operazioni necessarie per il set-up della macchina;
• Il funzionamento delle primitive di comunicazioni che i processing node possono effettuare;
• Il funzionamento del modulo Equal per effettuare il test dei Jane in una sessione di diagnosi;
• Il funzionamento dei meccanismi di EDAC di rilevazione e correzione degli errori che possono verificarsi nella trasmissione dei dati su un bus che connette un chip ad un altro.

 Questi vettori sono stati utilizzati per verificare la correttezza del progetto confrontando le uscite del modello VHDL con quelle del C, e saranno utilizzati, nel prossimo futuro, sia per il test del chip nel processo di produzione e nei test utilizzati dal sistema di auto-diagnosi.

 L’attività futura sarà principalmente focalizzata sull’implementazione del sistema di auto-diagnosi per APEmille. È necessario studiare delle opportune system service per consentire all’host di interagire con APEmille per avviare i programmi di test, controllare l’esecuzione e per prelevare la sindrome. In particolare è necessario che l’host abbia la possibilità di scrivere opportuni valori nei registri di stato della macchina, ad esempio disabilitare tutte le interruzioni in modo da poter accumulare il maggior numero possibile di errori. Inoltre, l’host ha anche l’esigenza di leggere il contenuto dei registri di stato in modo da estrarre la sindrome.

Sulla base dei vettori di test già sviluppati occorre scrivere i programmi di test, ad esempio in linguaggio TAO. Tali programmi saranno eseguiti dopo aver configurato la macchina in modalità di diagnosi e consentiranno di rilevare un errore in presenza di guasti.

Infine, occorre implementare sull’host di APEmille l’algoritmo di diagnosi che avrà il compito di decodificare la sindrome ed individuare le schede che contengano almeno una unità guasta.

In tal modo, non appena saranno disponibili i primi prototipi di APEmille si potrà eseguire la sperimentazione delle procedure di test e di auto-diagnosi sul sistema reale, ed anche per la verifica dei prototipi stessi.

  La parallelizzazione degli Algoritmi Genetici é stata oggetto di numerosi studi ed i vantaggi rispetto ad una implementazione sequenziale sono stati dimostrati in numerosi casi. L'approccio di parallelizzazione piú semplice é chiamato globale: la valutazione della fitness degli individui e l'applicazione degli operatori vengono parallelizzati. In questo caso uno speed up proporzionale al numero di processori é da aspettarsi. Gli altri algoritmi fondamentalmente si dividono in due categorie: il modello a grana-fine (AGgf) ed il modello ad Isole (AGIs).

• Il modello AGgf consiste nel far evolvere una popolazione, dedicando ciascun processore ad un singolo individuo ed alla valutazione della sua fitness; gli operatori genetici vengono applicati ad individui vicini, mediante accessi remoti tra processori, connessi secondo una predefinita struttura di vicinanza, piana o tridimensionale. Questo modello è indicato per macchine parallele con architettura SIMD.
• Il modello AGIs consiste nel far evolvere diverse popolazioni indipendentemente, ciascuna su un processore. Un operatore non tradizionale, di migrazione, periodicamente scambia gli individui più rappresentativi delle popolazioni più vicine. Tale modello è particolarmente adatto per architetture parallele MIMD.

Verrá illustrata l'implementazione su APE100 di algoritmi genetici del tipo AGIs, con applicazione all'apprendimento off-line di controllori fuzzy e all'apprendimento off-line di Reti Neurali feed-forward. Si è deciso di adottare il modello AGIs per diversi motivi:

• Sviluppare del software predisposto alla successiva evoluzione dell'APE100, mediante integrazione con componenti MIMD.
• Limitare gli scambi di dati tra processori che, rispetto alle operazioni di calcolo, in APE100 incidono maggiormente sul tempo complessivo d'elaborazione: mentre il modello AGIs effettua accessi remoti in memoria solo per la migrazione, il modello AGgf ne avrebbe bisogno anche per la selezione e l'accoppiamento.
• Poter far evolvere popolazioni con dimensioni non vincolate dal numero di processori della macchina, vincolo implicito nell'utilizzo del modello AGfg.
• Ma soprattutto, far evolvere diverse popolazioni contemporaneamente, per cercare una soluzione affidabile: l'impiego degli AG sequenziali all'apprendimento off-line di controllori fuzzy, in esperimenti precedenti, hanno mostrato una certa variabilità nelle soluzioni ottenute, dati i loro valori di fitness di ordini di grandezza diversi quasi ad ogni esecuzione. E questa instabilità si è rilevata anche operando un'inizializzazione non casuale della prima generazione.

La struttura adottata nell'implementazione é stata quella elitaria e la migrazione degli individui migliori é stata limitata a sottopopolazioni "vicine" (secondo la topologia della macchina).

In particolare, gli AGIs sono stati impiegati nell'apprendimento off-line di un controllore fuzzy per la navigazione di un veicolo costeggiando qualunque ostacolo esso incontri sulla propria destra. Tale comportamento (seguire il muro) scelto come banco di prova per l'approccio scelto, è un importante tassello del progetto per la navigazione autonoma di un robot in ambienti chiusi (quali uffici, industrie, scuole o ospedali). Esso è stato già utilizzato per sperimentare l'approccio degli AG sequenziali, costituendo cosi' materiale per un confronto. L'output atteso dal processo di apprendimento è un'associazione ottimale tra dati sensoriali (rilevati da un anello di sensori) e la velocità angolare del veicolo. Sia i dati di input che di output sono rappresentati da variabili linguistiche e i rispettivi insiemi fuzzy, e l'associazione input-output è formalizzata da un insieme di regole fuzzy. Il codice genetico di ciascun individuo rappresenta sia gli insiemi fuzzy delle variabili linguistiche, sia la base di regole fuzzy, con la disponibilità di operatori genetici che agiscano solo sulla parte del cromosoma delle funzioni di appartenenza, o solo su quella della base di regole, oppure contemporaneamente su entrambe. I tradizionali operatori sono stati adattati alla particolare struttura degli individui. Inoltre per ottenere delle soluzioni efficienti e prive di ridondanza sono state apportate ulteriori modifiche: dalle basi di regole fuzzy vengono cancellate sia regole non significative (con antecedenti o conseguenti nulli) e le copie di regole già presenti. La funzione di fitness di ciascun individuo (controllore) valuta l'errore quadratico medio tra la sua risposta e quella attesa in riferimento ad insieme di esempi.

Verrá anche discussa l'applicazione del GAIn all'ottimizzazione di pesi e topologia dei Reti Neurali feed-forward: tale approccio utilizza una opportuna codifica in un cromosoma dei pesi e della topologia della rete.

Gli effetti delle variazioni del bilanciamento tra il raffinamento e l'esplorazione saranno mostrati e analizzati.

 Il problema della determinazione delle configurazioni di equilibrio stabile di molecole complesse può essere ricondotto alla ricerca dei punti dello spazio delle configurazioni corrispondenti a valori di minimo assoluto per l'energia libera del sistema. Tale problema richiede dunque l’uso di

1. un opportuno algoritmo di ottimizzazione che permetta di esplorare uno spazio molto vasto caratterizzato da notevoli irregolarità morfologiche,
2. una modellizzazione su scala atomica del sistema che consenta la valutazione dell'energia potenziale (coincidente con l'energia libera a temperatura nulla) delle strutture in esame.

 L'algoritmo di ottimizzazione scelto e' una combinazione tra un algoritmo genetico ed il "simulated annealing". Tale algoritmo ha mostrato buoni risultati se applicato a clusters atomici. Il calcolo dell'energia potenziale delle configurazioni è stato effettuato utilizzando il codice GROMOS (Dinamica Molecolare classica basata su potenziali empirici).

Questo algoritmo si adatta perfettamento ad una implementazione su una piattaforma ad architettura parallela ibrida SIMD-MIMD, come quella prevista nella prima fase del progetto PQE2000.

Verranno presentati il layout generale dell’algoritmo, gli specifici accorgimenti tecnici utilizzati per la sua implementazione sulla macchina ad architettura ibrida, i primi risultati ottenuti su un sistema molecolare semplice costituito da 12 residui di lisina. Verrà, inoltre, data una prima valutazione dell’efficacia del metodo su sistemi molecolari complessi e presentato lo sviluppo dell’applicazione su un caso di test più impegnativo.

Lo scopo principale del nostro lavoro è la simulazione al calcolatore di reazioni chimiche elementari in fase gassosa. Queste simulazioni sono importanti per una modellazione realistica di sistemi chimici complessi come quelli coinvolti nei processi atmosferici nonché per la modellazione di alcune moderne tecnologie come i laser chimici ogniqualvolta la simulazione sperimentale presenti difficoltà tali da rendere non fattibile o non "conveniente" l'esperimento stesso. Un approccio consolidato al problema consiste nel risolvere la equazione di Schroedinger per il moto dei nuclei atomici sotto l'effetto di un campo generato dal moto degli elettroni. Il lavoro può essere schematizzato quindi nei seguenti passi:

1. soluzione della equazione di Schroedinger elettronica tramite tecniche ab initio.
2. Ricerca di una forma funzionale e quindi costruzione della superficie di energia potenziale elettronica.
3. Risoluzione dell'equazione di Schroedinger nucleare.

Scopo del mio intervento sarà mostrare quali sono le tecniche teoriche adottate principalmente per affrontare l'ultimo punto e come l'uso di calcolatori ad architettura massicciamente parallela possa contribuire, da un lato, a ridurre sensibilmente i tempi di esecuzione delle applicazioni e, dall'altro, a sviluppare nuove metodologie e algoritmi progettati specificatamente per calcolatori paralleli. Due sono i possibili approcci per affrontare dal punto di vista quantistico il problema: un approccio time indipendent [1] in cui la dipendenza della funzione d'onda dal tempo è fattorizzata e quindi il problema si trasforma nella soluzione della equazione di Schroedinger stazionaria; ed un approccio time dipendent [2] in cui la variabile tempo è usata come variabile di continuità per integrare la equazione di Schroedinger. Quest'ultimo metodo presenta alcuni vantaggi rispetto all'approccio time indipendent. La sua implementazione è relativamente semplice e la possibilità di visualizzare la funzione d'onda graficando la densità di probabilità all'evolversi temporale del sistema fornisce ulteriori dettagli sulla dinamica dell'evento reattivo. Ciononostante, la sua implementazione su macchine parallele è particolarmente laboriosa e solo un modello di parallelismo a grana molto fine sembra essere adottabile. Al contrario l'approccio time indipendent, pur presentando maggiori difficoltà sia dal punto di vista formale che di implementazione, offre la possibilità di suddividere il lavoro computazionale in task indipendenti. Ciò ha fatto sì che i codici basati su questi metodi presentino caratteristiche computazionali più adatte all'uso di macchine parallele e che quindi noi concentrassimo in questi i nostri sforzi.

 Per un sistema atomo-diatomo la equazione di Schroedinger nucleare è una equazione differenziale a sei dimensioni nei vettori di Jacobi Rl e rl dove l indica uno dei tre possibili canali di arrangiamento:

 Se questa equazione è formulata utilizzando un sistema di riferimento fisso nello spazio, la parte angolare dell'hamiltoniano può essere espressa in termini degli operatori ll ² e jl ², rispettivamente operatori del momento angolare orbitale e del momento angolare rotazionale. Le già citate difficoltà nella trattazione a dimensionalità piena, sinora solo pochi sistemi sono stati studiati ed anche in questi casi a costo di un enorme sforzo computazionale, hanno fatto sí che si sviluppassero approcci a dimensionalità ridotta. Particolarmente adatto si è rivelato l'approccio RIOS (Reactive Infinite Order Sudden) [3] in cui la riduzione è ottenuta disaccoppiando i moti orbitali e rotazionali, e quindi sostituendo gli operatori ll ² e jl ² con i corrispondenti autovalori l(l+1) e j(j+1) rispettivamente.

Il calcolo si riduce così all'integrazione di un insieme di equazioni differenziali ordinarie del primo ordine a valori fissi dell'angolo Q l (l'angolo formato dai vettori di Jacobi) per il canale dei reagenti (l =a ) e dei prodotti (l =b ). Il calcolo va ripetuto per tutti quei valori di Q l per cui, ad una data energia, i due canali sono aperti.

 La parallelizzazione del codice è stata effettuata adottando il paradigma di parallelismo Message Passing distribuendo su differenti processori il compito di calcolare la funzione d'onda ad angolo ed energia costanti per un determinato valore del numero quantico di momento angolare orbitale l. La distribuzione del lavoro è stata organizzata usando un modello task farm. Questo modello assegna ad un nodo (master) il compito di organizzare la distribuzione del lavoro agli slave nonché quello di raccogliere ed ulteriormente elaborare i risultati provenienti a loro volta dagli slave. Le prestazioni ottenute adottando questo modello sono stati soddisfacenti. Esse sono state ulteriormente migliorate

adottando un modello task farm a più livelli. Nel modello task farm a due livelli al livello più basso avviene la distribuzione del calcolo ad angolo, energia ed l fissati mentre al livello superiore avviene la assegnazione degli angoli da calcolare.

 Parallelamente a questo lavoro, che consiste essenzialmente nell'adattamento di codici scritti e soprattutto pensati per macchine sequenziali, stiamo affrontando il problema, in un certo senso più fondamentale, di cercare algoritmi e procedure più intrinsecamente paralleli. Algoritmi, ovvero, pensati sin dall'inizio tenendo in considerazione le caratteristiche della piattaforma su cui poi girerà l'applicazione. In tal senso stiamo sperimentando un approccio non più propagativo ma variazionale

applicato al problema della integrazione della equazione di Schroedinger in una o più dimensioni. Nel seminario verranno presentati i risultati preliminari in questo senso. 

Bibliografia

 [1] R.T Pack and G.A. Parker, J. Chem. Phys. 87, 3888 (1987).

 [2] Gabriel G. Balint-Kurti, Richard N. Dixon and C. Clay Marston, International Reviews in Physical Chemistry, 11, (2), 317-344 (1992).

 [3] A. Laganà, E. Garcia, E. Gervasi, in Supercomputer Algoritms for Reactivity, Dynamics and Kinetics of Small Molecules, A. Laganà Ed. (Kluwer, Derdrecht, 1989) p.271.

 L'obiettivo primario di questa ricerca è quello di sviluppare uno strumento numerico duttile ed affidabile per lo studio dell'efficacia di alcuni farmaci anti-ipertensivi. Il sistema modello preso in considerazione e' costituito da un doppio strato di molecole di dimirilstoilfosfatidilcolina (DMPC) in interazione con molecole di diidropiridina (DHP). La prospettiva di uno studio sistematico di sistemi così complessi su piattaforme parallele, è richiesto preventivamente lo sviluppo di codici per la simulazione di sistemi diffusivi (liquidi).

E' stato quindi prodotto e testato con successo in ambiente APE un codice di Dinamica Molecolare (MD) scritto per un sistema diffusivo, liquido, a connessione totale, cioè per un sistema in cui il numero di termini del potenziale intermolecolare cresce come N2, essendo N il numero di componenti elementari (atomi) del sistema. Questo risultato, che sviluppa quanto già fatto per sistemi cristallini, rappresenta un passo in avanti decisivo nel contesto delle simulazioni di tipo MD, in quanto apre la strada alla possibilità di sfruttare le risorse di calcolo offerte dalle piattaforme della famiglia APE per lo studio di sistemi più complicati, quali le membrane cellulari o altri sistemi di interesse biologico. Il grosso del codice è stato scritto in linguaggio TAO. Tuttavia alcune routines (quelle nelle quali il programma spende la maggior parte del tempo di calcolo) sono state direttamente scritte in APE assembler sulla base della mappa di indirizzamenti generata dalla macchina. Per i tests di fattibilità abbiamo usato il butano (C4H10) che a temperatura ambiente è un liquido. Il potenziale usato per descrivere le interazioni fra i componenti "elementari" del butano (cioè fra i gruppi CH3 e CH2, C4H10=CH3-CH2-CH2-CH3) è una somma di termini armonici che descrivono i legami chimici intramolecolari, più una somma di potenziali di tipo Lennard-Jones che tengono conto delle interazioni di van der Waals fra molecole distinte e all'interno di una stessa molecola. Nel programma è stato implementato il metodo più moderno e più flessibile di integrazione delle equazioni di Hamilton attualmente disponibile, cioè il cosiddetto metodo dei "tempi multipli" [1] [2] [3] [4]. Il parallelismo di APE è stato sfruttato nell'organizzare il calcolo del potenziale intermolecolare in maniera "sistolica"[5]. Questo accorgimento riduce il tempo di calcolo, rispetto a quello richiesto in una macchina non parallela, da O(N2) a O(N2/p), ove p è il numero dei nodi della macchina. Sulla Torre è stato simulato un sistema di 512 molecole (= 2048 atomi effettivi) di butano liquido per un totale di circa 10 nanosecondi, con una "velocità" di produzione di 1 nanosecondo ogni 48 ore di CPU. Scrivendo in assembler la routine in cui viene calcolato il potenziale intermolecolare, il guadagno rispetto a questi tempi di simulazione è di circa un fattore 3. Il codice così ottimizzato raggiunge sulla Torre una velocità di produzione che è 15-20 volte più alta di quella ottenibile, a parità di strategia di integrazione, su una stazione a. I risultati ottenuti con APE, confrontati con i dati sperimentali esistenti, con quelli di vecchie simulazioni fatte su un campione di 64 molecole e con simulazioni da noi effettuate in doppia precisione su una stazione a, confermano la efficienza del codice e la affidabilità numerica della Torre, nonostante le limitazioni imposte dalla attuale architettura della macchina (assenza di indirizzamento locale e singola precisione). 

A causa delle difficoltà poste dalla mancanza di indirizzamento locale, non è possibile su APE la creazione della "lista", cioè di una tabella, periodicamente aggiornata durante la simulazione, nella quale sia riportato per ogni atomo del sistema l'insieme di atomi con i quali esso ha un'interazione non trascurabilmente piccola. L'uso della "lista" nelle simulazioni di Dinamica Molecolare è decisivo per lo studio di sistemi complessi, in quanto consente di ridurre l'esponente con cui cresce il tempo di calcolo, TCPU, con il numero di particelle da ~2 a ~1 (TCPU N2 TCPU N). Su APE abbiamo potuto ottenere un risultato parimenti soddisfacente, ricorrendo al metodo della "decomposizione in domini" [6], per il quale la mancanza di indirizzamento locale non rappresenta un ostacolo. Il metodo consiste nel suddividere lo spazio fisico, in cui è contenuto il sistema, in ncell = k3 p >>p cellette (k è un opportuno intero maggiore di 1), ciascuna di dimensioni tali che molecole appartenenti a cellette non spazialmente contigue abbiano fra loro un'interazione trascurabile. Ad ogni nodo saranno assegnate k3 cellette, nonchè copie delle cellette prime vicine che risiedono in altri nodi. In questo modo in ogni processore saranno presenti tutte le molecole fra le quali le interazioni intermolecolari devono essere calcolate. Ciò significa che, tenendo fissa la densità del sistema, il numero di operazioni per il calcolo del poteziale intermolecolare crescerà solo linearmente con N. A questo tempo di calcolo dovrà essere aggiunto il tempo necessario per riassegnare periodicamente le molecole del sistema alle cellette cui, durante l'evoluzione temporale, sono spazialmente venute ad appartenere. Attualmente è in fase avanzata di sviluppo e di test sia su stazioni a che sulla Torre un software che utilizza il metodo della "decomposizione in domini". Dalle prime prove da noi effettuate, i tempi di calcolo sono ridotti di ben un fattore 5 rispetto a quelli ottenibili senza la "decomposizione in domini". I risultati estremamente incoraggianti ottenuti fin'ora hanno permesso di passare alla simulazione di una membrana biologica, schematizzata come un doppio strato lipidico, ciascuno, per il momento, costituito da 32 molecole di fosfolipide sulla stazione a e 256 molecole di fosfolipide sulla Torre. Un fosfolipide è una grossa molecola con una testa polare idrofilica e una coda idrofobica, che viene schematizzata come un insieme di ~40 atomi effettivi (i gruppi CH, CH2 e CH3 sono, anche in questo caso, considerati singole entità atomiche), soggetti a forze elastiche (che simulano i forti legami covalenti), forze di van der Waals e forze elettrostatiche.

In presenza di forze a lungo range, quali sono le forze Coulombiane, il tempo di calcolo delle forze scala di nuovo proporzionalmente al quadrato del numero di "particelle" elettricamente cariche del sistema (TCoul Nc2). Inoltre in un sistema periodico (come quelli di solito usati in Dinamica Molecolare per minimizzare gli effetti di volume finito) la somma dei termini Coulombiani dovuti alla cariche reali e alle cariche immagine dà luogo ad una serie solo condizionalmente convergente.

La soluzione più comunemente usata in letteratura al problema della convergenza è quella di utilizzare il metodo di sommazione di Ewald sono però stati sviluppati anche metodi alternativi che sfruttano l'espansione in multipoli del potenziale nel calcolo dell'interazione Coulombiana. E' nostra intenzione implementare su APE sia il metodo delle somme di Ewald, utilizzando il software da noi sviluppato per il calcolo della FFT, sia la tecnica dello sviluppo in multipoli, che meglio sembra si adatti a sistemi con una simmetria planare, quali le membrane. Il confronto diretto fra le due strategie ci consentirà di scegliere quella che meglio risponde alle necessità di calcolo poste dal problema in studio.  

Bibliografia

 [1] M.Tuckerman, G.J.Martyna and B.J.Berne J.Chem.Phys. 97 (1992) 1990.

[2] D.D.Humphreys, R.A.Friesner and B.J.Berne, J.Phys.Chem. 98 (1994) 6885.

[3] M.Watanabe and M.Karplus, J.Chem.Phys. 99 (1993) 8063; J.Phys.Chem. 99 (1995) 5680.

[4] P.Procacci and B.J.Berne, J.Chem.Phys. 101 (1994) 2421.

[5] N.Petkov, "Systolic Parallel Processing" Elsevier Science-Amsterdam (1993)

[6] M.T.Nelson, W.Humphrey, A.Gursoy, A.Dalke, L.V.Kale', R.D. Skeel, K.Schulten, The International Journal of Supercomputing applications and High Performance Computing 10 (1996) 251

Oggetto della mia attività dell'anno di borsa INFN che sta per concludersi è stato lo sviluppo di codici Monte Carlo per la simulazione di sistemi di particelle con gradi di libertà traslazionali sia su macchine ad architettuttura MIMD (cluster di workstation e IBM-SP2) che ad architettura SIMD (Quadrics).

Su piattaforma MIMD abbiamo implementato un codice Monte Carlo per lo studio di sistemi di cristalli liquidi con interazioni di tipo Gay-Berne [1,2] e dipolo-dipolo. In particolare, scopo del mio lavoro è stato comprendere come l'applicazione di un campo elettrico su sistemi di molecole discotiche con dipolo trasverso possa modificare l'organizzazione macroscopica molecolare e le proprietà termodinamiche soprattutto nelle fasi colonnari.

Abbiamo considerato sistemi di particelle ellissoidali oblate con un dipolo elettrico centrato nella molecola e diretto lungo l'asse x molecolare. L'energia totale è data da U_ij =U_GB +U_dd + U_l. Il termine Gay-Berne U_GB è una generalizzione anisotropa del potenziale Lennard Jones per particelle di forma ellissoidale, che ha una dipendenza 12-6 dall'inverso dalla distanza, U_dd è il termine dipolo-dipolo e U_l è il termine di accoppiamento con un campo elettrico E applicato trasversalmente rispetto alle colonne. Abbiamo quindi fatto delle simulazioni Monte Carlo nell'ensemble isobarico-isotermico NPT (numero di molecole N, pressione p e temperatura T costanti) di sistemi di N=1000 particelle racchiuse in una scatola con condizioni al contorno periodiche investigando diverse temperature corrispondenti a fase liquido-cristalline nematiche e colonnari.

Sono stati implementati due modelli di parallelismo usando PVM: a) master--slave per piccoli cluster di Workstations (fino a 5) e SP2 ( fino a 13 nodi) b) data replicated per un numero grande di processori (fino a 128 PE).

Le simulazioni preliminari indicano che si viene a formare una fase colonnare biassiale e che la biassialità aumenta con l'intensità del campo.

L'implementazione di un codice per la simulazione di sistemi con gradi di libertà traslazionali su Quadrics (piattaforma SIMD) è risultata particolarmente impegnativa; il motivo alla base è che la macchina possiede un unico processore adibito all'elaborazione degli interi e le medesime operazioni vengono eseguite sui dati che risiedono nelle stesse locazioni di memoria sui vari processori. Questo aspetto non rappresenta un limite per potenziali su reticolo [3], in quanto le particelle interagenti sono identificate interamente dalla geometria della macchina, ma crea delle notevoli complicazioni non appena si considerano potenziali con gradi di libertà traslazionali. Anche con gli opportuni accorgimenti il codice risulta tanto più efficente quanto più il potenziale è a corto raggio; pertanto abbiamo deciso di implementare, almeno inizialmente, un codice per lo studio di sistemi di particelle con potenziale di interazione più a corto raggio dei potenziali usualmente studiati sulle macchine MIMD (potenziale dipolo-dipolo e potenziale Gay-Berne).

Attualmente lo studio del diagramma di fase di fluidi interagenti con potenziale attrattivi a corto raggio desta molto interesse, ad esempio riguardo alla possibilità che un sistema diquesto tipo non formi una fase liquida stabile, passando direttamente dalla fase solida a quella gassosa per sublimazione. Ci sono indicazioni che suggeriscono che una transizione di questo genere avviene in alcune miscele colloidali [4], per le quali il potenziale di interazione è a corto raggio. Di recente è stata anche investigata l'esistenza di una fase liquida stabile per il C60 [5,6,7], come già per il caso dei colloidi; é stato provato che ad alte temperature l'interazione tra due molecole di fullerene può essere modellata con un potenziale effettivo, proposto da Girifalco [8], che presenta una profonda buca attrattiva a corto raggio e che va a zero molto rapidamente:

dove s=r/(2a) e 2a è il diametro della molecola di C60. Tale potenziale di coppia differisce in modo della buca significativo dal più usuale potenziale Lennard-Jones 6-12; in particolare il rapporto tra la larghezza attrattiva e il diametro del core repulsivo è molto minore nel C60 che non in un gas nobile. Il fatto che il potenziale proposto sia a corto raggio e che quindi le interazioni tra secondi vicini siano molto piccole e quelle a terzi vicini addirittura trascurabili lo rende particolarmente adatto per l'implementazione su Quadrics. Attualmente disponiamo di un codice Monte Carlo funzionante, sia pure non ottimizzato, per la simulazione di sistemi massivi di fullereni.

Tre sono essenzialmente gli accorgimenti implementati rispetto a un comune codice seriale: a) introduzione di un flag di esistenza per ogni molecola per ovviare al fatto che, in virtù della possibilità di mosse traslazionali, il numero delle particelle per nodo non costante; b) suddivisione geometrica del campione in porzioni e sottoporzioni sulle memorie dei processori. Il campione di forma cubica viene suddiviso sulle memorie dei singoli processori, per cui ad ogni nodo è associato un array che contiene la porzione locale del campione. La porzione locale viene suddivisa in sottoporzioni di dimensione L maggiore del raggio di cutoff del potenziale. Questo accorgimento è estremamente utile in quanto ci consente di evitare il calcolo delle interazioni di tutte le coppie memorizzate su ogni singolo nodo, c) metodo delle cornici che consiste nelle replica sulla memoria locale di ciascun nodo di una cornice di sottoporzioni di spessore L trasferita dai nodi circostanti. In questo modo su ogni processore sono disponibili anche le informazioni relative alle particelle frontiera delle sottoporzioni prime vicine e si evita di effettuare comunicazioni internodo per calcolare interazioni tra le particelle di una porzione con le particelle delle sottoporzioni adiacenti.

Nel seminario verranno esposti i risultati preliminari delle simulazioni.

Bibliografia

Il problema della ricostruzione di immagini richiede sistemi estremamente potenti, sia in termini di memoria disponibile che di potenza di calcolo: da tempo tali problemi vengono risolti attraverso l’uso di architetture non seriali e di sistemi MPP. Nel campo dell’imaging medico l’uso di sempre più potenti architetture parallele stimola l’evolversi di nuove tecniche, consentendo inoltre di ottenere immagini sempre meglio definite, che, in questo campo, significano la possibilità di poter effettuare diagnosi precoci e più precise. Ciò che continua ad ostacolare la diffusione dell’utilizzo dei sistemi MPP in questo campo è il loro costo: quando possono, le strutture mediche ricorrono all’uso di centri di calcolo esterni, la cui disponibilità viene però condivisa con un ampia utenza. La realizzazione di sistemi embedded, basati su scheda Ape1000, dal costo relativamente contenuto, consente di superare questo ostacolo, ma contemporaneamente richiede lo studio di tecniche che permettano di sfruttare appieno questa architettura.

Il lavoro presentato esplora la possibilità di applicare le Reti Neurali Artificiali (ANN) alla ricostruzione di immagini PET (Positron Emission Tomography). Vi sono due ragioni per le quali viene ritenuta interessante l’applicazione delle ANN in questo campo. La prima è strettamente collegata alla modalità di azione delle stesse che, a fronte di un lento e delicato training, consentono di risolvere la classe di problemi per cui sono state addestrate in modo molto più veloce rispetto agli algoritmi tradizionali. La seconda consiste nel fatto che le ANN si prestano, a causa della loro stessa struttura, ad essere "naturalmente" realizzate su architetture massivamente parallele.

La PET è un metodo tomografico che si basa sul conteggio dei fotoni emessi da un corpo che ha assorbito un radiofarmaco: i fotoni emessi vengono raccolti da coppie di rivelatori disposti ad anello attorno al corpo stesso. In base al conteggio effettuato dalle diverse coppie si riesce a determinare, utilizzando tecniche di ricostruzione, la distribuzione originale del radiofarmaco. La PET viene usata per lo studio delle neoplasie e delle funzionalità fisiologiche del cervello: in questo studio si rende necessario l’impiego di particolari radiofarmaci per cui le altre tecniche non possono essere applicate. In questo lavoro l’apparato PET è stato simulato attraverso il metodo Montecarlo e si lavora su immagini test bidimensionali. Il problema non perde comunque generalità, in quanto i dati provenienti dalla simulazione sono, secondo studi fatti, congruenti a quelli di un nuovo apparato sperimentale in uso presso la Sezione INFN di Ferrara; inoltre, un’immagine tridimensionale può essere vista come la sovrapposizione di più immagini a due dimensioni.

Le ANN sono rappresentate da un modello costituito su "imitazione" di quelle naturali, da cui appunto deriva il nome: sono formate da neuroni (o nodi, semplici elementi di elaborazione), i quali ricevono e trasmettono impulsi attraverso le connessioni (sinapsi) che li uniscono. Qui si è utilizzato un percettrone semplice, costituito da due soli livelli di nodi, per l’input e l’output, completamente connessi, con il flusso in un’unica direzione, che utilizza il metodo dell’errorback propagation per l’apprendimento (learning). Ai nodi di input sono associate le coppie dei rivelatori, a quelli di output i pixel dell’immagine. L’applicazione di questa semplice rete consiste in due passi. Durante una prima fase, molto lenta, essa viene addestrata, utilizzando un set di esempi, ad associare a date distribuzioni dei conteggi nelle coppie di rivelatori le corrispondenti zone dell’immagine che l’hanno generata. Il secondo passo esegue la ricostruzione vera e propria: a questo punto la rete, se ben addestrata, è in grado di ricostruire in modo molto veloce l’immagine di un corpo in base alla distribuzione dei conteggi; inoltre, poiché l’addestramento dipende dalle dimensioni, piuttosto che dal contenuto, dell’immagine e dall’apparato specifico, una volta compiuto, la rete è in grado di ricostruire immagini di oggetti le cui dimensioni siano incluse, o uguali, a quelle usate per l’addestramento.

Il vantaggio derivante dall’applicazione della ANN consiste proprio nella rapidità con cui essa è in grado di ricostruire l’immagine; lo svantaggio sta invece nella lentezza, ma soprattutto nella complessità, anche computazionale, dell’addestramento. Se è vero che in teoria esso è necessario una sola volta, si devono in pratica eseguire diverse prove per la messa a punto del metodo di apprendimento. Inoltre, la complessità dell’algoritmo è proporzionale a N³, dove N è il quadrato delle dimensioni dell’immagine, e su una veloce architettura seriale, per una piccola immagine di 3,2 cm di lato, il learning dura circa una settimana; la trasposizione dell’algoritmo su architettura MPP si rende quindi indispensabile.

L’alto parallelismo intrinseco di questo problema offre due possibilità per la parallelizzazione dell’algoritmo. La prima prevede la riproduzione della rete completa su ciascun processore e la parallelizzazione della presentazione degli esempi; la seconda, all’opposto, implica la distribuzione della rete, in particolare dei suoi neuroni di output, su ciascun nodo fisico dell’architettura. Poiché nel primo caso la scalabilità dell’algoritmo è vincolata dalla capacità di memoria sui singoli nodi, è stata implementata la seconda possibilità.

L’algoritmo, sviluppato inizialmente su di una macchina con processore Alpha, è stato realizzato nella sua versione parallela sulle architetture Quadrics a 128 e 512 processori. L’elevata località dei dati, anche se non completa, ottenuta nella versione parallela, su queste architetture produce un overhead dovuto alle comunicazioni che risulta irrilevante nel computo totale dei tempi di elaborazione. Pur se l’applicazione, per la mole di dati trattata, risulta poco adatta ai Quadrics attualmente disponibili, i risultati ottenuti confermano la bontà della architettura SIMD, e sono incoraggianti se si pensa alla futura disponibilità di APE1000.

Il mio lavoro si inserisce nell’ambito del progetto PQE2000 e riguarda lo sviluppo di algoritmi per il CAD mammografico su architetture massivamente parallele (in particolare su calcolatori del tipo APE).

La ricerca e’ iniziata nel gruppo di Fisica Medica del Dipartimento di Fisica dell’Università di Pisa diretto dal Prof. A. Stefanini e prosegue ora all’interno della collaborazione CALMA (Computer Aided Library for Mammography).

CALMA è una collaborazione quadriennale tra le sezioni INFN di Bologna, Pisa, Torino e Udine che ha lo scopo di produrre un sistema CAD mammografico.

Un sistema CAD consiste (nel caso di analisi di immagini mediche) di una serie di filtri grafici che permettano l’individuazione, la selezione e la classificazione di zone "interessanti" dell’immagine. Nel caso delle mammografie tali zone corrispondono a tumori o lesioni con sospetto di tumore.

Data la grande varietà di lesioni si hanno diverse tipologie di immagini che si distinguono per densità, forma, dimensioni ecc.

L’interpretazione di una mammografia è dunque, come ogni procedura diagnostica in medicina, un lavoro di classificazione piuttosto complicato, effettuato usando un grande insieme di dati. In particolare la procedura di formazione della decisione clinica è molto difficile da tradurre come algoritmo. Per questi motivo riteniamo che il CAD mammografico sia un tipico campo di applicazione delle Reti Neurali Artificiali (ANN).

Un CAD basato sulle ANN deve prevedere una serie di algoritmi di preprocessing che consentano di estrarre una serie di informazioni dall’immagine riducendo di conseguenza la dimensione dei dati. È infatti impensabile, sia per questioni di tempo di calcolo che di limiti propri del metodo neurale (overtraining) costruire una rete neurale con un numero di ingressi pari al numero di pixel (tipicamente 2000x2000).

Un passo indispensabile per la costruzione del CAD è la produzione di un archivio di mammografie digitalizzate con le quali addestrare le reti neurali e validare gli algoritmi e l’intero sistema: ogni immagine, presente nell’archivio, deve essere accompagnata da una diagnosi (presenza o meno di lesioni, tipo e posizione della lesione, eventuali e utili informazioni sulla paziente ecc.).

Stimiamo che per poter affrontare il problema globalmente (cioè per tenere conto dei possibili tipi di lesione) siano necessarie più di 50000 immagini mammografiche.

Non è pubblicamente disponibile un archivio con tali caratteristiche. In particolare i database che è possibile trovare presso istituzioni estere che si occupano di CAD sono composti da poche immagini.

Quindi la prima parte del nostro lavoro e’ proprio la costruzione del database.

A tal fine abbiamo raggiunto un accordo con vari centri di screening mammografico (Bari, Bologna, Livorno, Torino, Udine) che ci forniranno le mammografie da digitalizzare, contemporaneamente e' stato stabilito un protocollo sul tipo di informazioni da accludere a ogni tipo di immagine.

Attualmente possediamo circa 600 mammografie digitalizzate sulle quali stiamo sperimentando gli algoritmi di preprocessing. Secondo le nostre informazioni si tratta del più grande database di mammografie digitali esistente in Europa.

 Per quanto riguarda il software in questo momento ci occupiamo dello sviluppo di algoritmi per l’individuazione di lesioni cosiddette stellate. Il nostro approccio prevede lo studio locale dell’immagine con un algoritmo basato sull’analisi della forma. Abbiamo raggiunto l’apprezzabile risultato di una sensibilità (numero di lesioni individuate su lesioni vere) del 100% con un numero di falsi negativi ancora troppo alto.

 Contemporaneamente stiamo sviluppando le reti neurali più adatte al nostro scopo. In particolare sperimentiamo reti di tipo feed-forward con apprendimento supervisionato tramite back-propagation e reti di tipo SOM (Self Organizing Maps) con autoapprendimento di tipo Kohonen.

L’implementazione di queste reti è fatta sia su normali workstations che su un computer dotato di una scheda CNAPS (128 processori). Visti i risultati ottenuti con tale dispositivo, pensiamo che l’uso di un calcolatore parallelo di alte prestazioni (tipo APE) sia indispensabile per eseguire sia gli algoritmi di preprocessing (che sono in gran parte parallelizzabili) che per le reti neurali. Il consumo di tempo di calcolo è infatti una caratteristica propria delle reti neurali che oltretutto sono naturalmente implementabili su architetture parallele.

Riteniamo che la costruzione del database e la sperimentazione di algoritmi e reti siano una premessa indispensabile alla parallelizzazione del software. Intendiamo comunque trasferire al più presto su APE sia l’algoritmo di preprocessing per lesioni stellate che le due architetture neurali suddette.