Gli autovalori
Definizione 5 Si chiama autovalore di A uno scalare λ ∈ R per
5.1 Gli strumenti
Lo sviluppo di tecnologie sempre pi`u miniaturizzate e potenti
ha reso possibile la disponibilit`a sul mercato di strumenti che
integrano varie unit`a di calcolo . Si sta parlando di calcolatori
paralleli ovvero quei calcolatori formati da diverse unit`a di
in-put/ouput(I/O) ma soprattutto dotati di pi`u di un processore.
L’osservatorio radioastronomico del C.N.R di Medicina, nel gen-naio 2001 ha acquistato uno strumento per il calcolo parallelo
come si pu`o vedere dalla figura 5.1. Questo super-computer,
Figura 5.1. Elaboratore parallelo
costruito dalla azienda americana Mercury, `e uno strumento
mo-dulare poich`e ha la possibilit`a di alloggiare al suo interno fino a
5.2 Il sistema
Il sistema utilizzato per lo sviluppo della KLT `e composto da
un bus VME e da un insieme di 9 slot per l’alloggiamento dei vari sottosistemi di calcolo. Nell’ordine, partendo dal lato sinis-tro del modulo parallelo(vedi fig. 5.1), sono presenti le seguenti componenti:
1. Il processore che gestisce tutto il sistema modulare(Host), quindi anche il sistema operativo.
2. Il convertitore analogico-digitale PENTEK.
3. La scheda MCJ6 su cui alloggiano due processori(CE=computer element) di tipo Risc.
4. La scheda di controllo del bus del sistema.
5.3 PENTEK
Il convertitore analogico/digitale riceve i dati attraverso il
ca-vo che `e connesso agli apparati di ricezione come la parabola
o la “Croce del Nord”. Questa scheda ADC converte i segnali di tipo analogico in dati digitali che sono trattabili
numerica-mente tramite software. Questo componente pu`o campionare i
segnali ad una frequenza compresa fra 0 e 20Mhz e poich`e la
banda da analizzare `e di pochi 6MHz si `e settato la frequenza
di campionamento a 13.3Mhz coerentemente con il teorema di campionamento.
5.4 MCJ6
La MCJ6 denominata anche PPC7400 `e composta da due CE
ad architettura RISC con un unit`a vettoriale di tipo ALTIVEC (denominata anche Velocity Engine). Queste schede possono es-sere aggiunte facilmente al un sistema in modo da formare cluster
di elaboratori anche dell’ordine di centinaia di nodi. Come si pu`o
Figura 5.2. Struttura della scheda
vedere dalla fig. 5.2 ciascun CE MPC7400 ha a sua disposizione una memoria RAM, da 64MB, una cache di primo livello da 32kb
e una cache L2 da 2MB. Nella figura l’unit`a denominata ASIC
`
e un chip che gestisce in modo ottimale il transito dei dati fra varie schede di questo tipo attraverso il bus VME. Chiaramente in ambito parallelo diversi processi possono comunicare con al-tri processi in esecuzione su diversi processori di diverso tipo.
La gestione di una tal tipologia di programmazione `e basata su
ICS(Interprocessor Comunication System). ICS fornisce un’in-terfaccia standard per la comunicazione di processi che eseguono su processori diversi in cluster di computer eterogenei. In effetti gli oggetti interessati da ICS sono
1. CE: unit`a logica capace di eseguire processi, ciascuno di
questi elementi `e identificato da un numero univoco(CEID1).
2. HOST: `e l’unico componente a poter caricare il sistema ope-rativo in modo autonomo, esso gestisce servizi di input e output standard, servizi per dischi, servizi d’errore. L’HOST `
e l’unico ad avere un filesystem e quindi `e indispensabile, `e
inoltre compito di questo componente inizializzare il primo CE.
3. Clusters: Un cluster `e un gruppo di CE che condivide un
database. Questo database, residente su un CE, contiene le traccie per permettere ad un qualsiasi CE di comunicare con un altro per mezzo di ICS.
4. Processi: sono programmi indipendenti che possono compe-tere per l’utilizzo di risorse di sistema come CPU, memoria, controllori DMA e cosi via. ICS supporta la creazione e il lancio di processi in modo remoto.
5. SMB: `e l’oggetto primario di utilizzo basato su ICS. Un
SMB2 `e un buffer di memoria che pu`o essere acceduto da
pi`u di un processo attraverso diversi CE. Queste particolari
locazioni di memoria sono gestite attraverso puntatori, detti anche SMB handler.
Per capire meglio come funziona un ambiente parallelo di questo tipo si elencano qui di seguito i passi occorrenti per rendere attivo il cluster:
1. l’accensione della macchina, vedi fig. 5.1, comporta l’avvio
dell’HOST che, nella nostra configurazione, `e caratterizzata
da una macchina SPARC sistema operativo UNIX;
2. dalla linea di comando del sistema operativo UNIX si lan-ciano i comandi di inizializzazione: initmcs e sysmc;
3. il comando sysmc serve per inizializzare i CE e per
descri-vere la topologia del cluster che sar`a poi memorizzata in un
database adeguato;
4. il comando runmc serve per eseguire i processi sui CE, in particolare runmc carica l’imagine del file oggetto relativo al
processo su un particolare CE. Il file oggetto `e generato da
un apposito programma di compilazione chiamato ccmc. La fig. 5.3 mostra in maniera schematica, ma molto chiara, quali
Figura 5.3. Comunicazioni fra HOST e CE
sono i componenti lanciati durante l’inizializzazione di ogni CE
e quali sono quelli lanciati durante il ciclo di attivit`a di un CE.
i processi devono sfruttare l’HOST poich`e `e l’unico ad avere un
filesystem. Questo tipo di accesso `e ottenuto tramite l’utilizzo di
due tipo di processi: il console server e l’OSM server. La console
server fornisce al CE una console attraverso la quale i messaggi
del CE-kernel3 raggiungono lo sviluppatore, si noti che esiste un
unico processo di questo tipo. L’OMS server fornisce ai proces-si, in esecuzione su un CE, servizi di standard input/output e accesso ai dischi, in questo caso ad ogni processo su CE viene associato un OSM sull’HOST. Ad esempio quando funzioni come
printf,fread e write vengono richiamate su un CE di tipo
Mercu-ry, il kernel richiede all’OSM relativo di completare la richiesta sull’HOST.
5.5 Scheda di controllo
Questa scheda mostra sulla facciata una serie di led che specifi-cano lo stato del bus in tempo reale. In particolare sono presenti led relativi al bus dati e al bus indirizzi. Questi insieme ad altri led servono per monitorare l’utilizzo del bus VME.
5.6 Il Software
Il software sviluppato per il problema del rilevamento di segnali tramite KLT trae vantaggio dalla potente macchina parallela che,
nell’osservatorio di radioastronomia, `e battezzata MEDALT1. Il
progetto `e stato sviluppato in ambiente UNIX per quanto
ri-guarda il lato server mentre il lato client `e stato sviluppato in
ambiente Windows, va precisato l’implementazione del client `e
stata effettuata avendo cura di non vincolarsi a tale sistema
ope-rativo, infatti `e possibile eseguire la ricompilazione con modifiche
Figura 5.4. Moduli software implementati
minime al sorgente. Non si pu`o dire altrettanto del lato server
poich`e un uso appropriato della potenza di calcolo dell’ALTIVEC
costringe ad utilizzare funzioni proprietarie basate sulla libreria
SAL4. Per avere una visione generale del progetto si osservi la
fig. 5.4. I moduli presenti in figura sono:
1. Client: `e l’interfaccia grafica che visualizza i dati analizzati.
2. Server1: `e il server con il quale si stabilisce le connessioni per il lancio dei task KLT.
3. Server2: `e il processo che modifica i flag per la terminazione
dei task KLT.
4. Server PPC: `e il modulo che distribuisce i dati campionati
ai task KLT.
5. KLT: sono i processi che indefinitamente eseguono la tras-formata KLT.
5.6.1 Il client
Questo modulo costituisce il front-end grafico per l’utilizzo del-la KLT. Non ci sono molti parametri da settare infatti gli unici bottoni presenti sul pannello sono quelli relativi al numero di punti del frame-dati che si vuole analizzare, il numero di auto-valori/autovettori che si vuole calcolare e il numero di processori che si vuole adoperare. C’e inoltre un ulteriore checkbox che permette, in modo automatico quando si ferma l’analisi, di me-morizzare il frame-dati in un file con indice progressivo e con estensione ON oppure OFF. Il formato di memorizzazione di
questi file `e quello ASCII. Quando si `e lanciata l’elaborazione
nel area grande dello schermo compare il grafico dei risultati in
tempo reale, proprio per questo motivo ci si `e appoggiati su una
libreria grafica come OpenGL per la sua efficienza.
5.6.2 Server1
Una volta premuto il tasto di avvio(start ) nell’interfaccia client, i parametri settati vengono trasferiti via TCP/IP al processo server1 che esegue i seguenti passi:
Figura 5.5. Interfaccia grafica OPENGL del client
1. Passa i parametri al modulo PPC che avvia il campionamen-to dei dati.
2. Entra in ciclo infinito e aspetta i risultati delle KLT. 3. Se ci sono risultati dai task KLT li spedisce al client.
5.6.3 PPC
Questo modulo come gi`a detto assolve il compito di campionare
i dati e metterli a disposizione per la elaborazione KLT vera e
propria. Prima per`o di fare questo lancia i processi KLT i quali
restano in attesa di dati da elaborare. Il ciclo principale del
modulo PPC `e composto dai seguenti passi:
i parametri dal server GCC;
2. RIOJ-Init: inizializza il chip RINOJ presente sulla MCJ6 per il trasferimento dei dati dal convertitore al buffer;
3. CreateTransfer: prepara le strutture dati per inizializzare il DMA;
4. BootKLT: lancia i task KLT;
5. Acquisition: ciclo infinito di acquisizione tramite DMA; 6. DownKLT: distrugge tutte le strutture dati precedentemente
inizializzate per il DMA e per il chip RINOJ
. Poich´e il calcolo della trasformata KLT richiede un tempo di
calcolo che `e maggiore di quello necessario per il campionamento
da un frame all’altro, non `e stato necessario fare uso del
double-buffering.
5.6.4 KLT
Questi sono i processi che eseguono letteralmente il calcolo del-la KLT applicando il metodo di Lanczos. Il numero di processi
KLT che si pu`o lanciare dipende strettamente dal numero di
pro-cessori a disposizione. Il sistema implementato `e stato pensato
in maniera da rilevare eventuali nuovi processori per permettere
una certa scalabilit`a del software. In modo totalmente
automa-tico il task una volta processato il frame-dati pone il risultato in un buffer condiviso, setta un flag ricomincia con un nuovo ciclo di elaborazione. A questo punto si attiva il processo server1 che, rilevando il flag appena attivato dal task KLT, estrae il risultato e lo spedisce attraverso il TCP/IP al client.
5.6.5 Server2
Quest’ultimo modulo serve per interrompere l’intera sessione di calcoli in atto. Anche questo modulo accetta connessione via TCP/IP con il lato client, mentre dialoga con i restanti moduli attraverso flag,semafori e segnali.
5.7 I tempi
Come detto in precedenza l’analisi dei dati provenienti da stru-menti radioastronomici dovrebbe essere fatta in real-time. Per quanto riguarda la serie di Fourier esistono metodi veloci come la FFT e hardware realizzati specificamente allo scopo di calcolare questa trasformata che eseguono milioni di operazioni al
secon-do. Per quanto riguarda la KLT, purtroppo, fin ora non `e stato
inventato nessun algoritmo veloce ne tanto meno hardware di
calcolo dedicato. Ci si `e quindi concentrati sull’ottimizzazione
del codice, sfruttando la particolare struttura della matrice di
Toeplitz, la cache, la contiguit`dei dati in memoria(striding). La
matrice di Toeplitz `e stata sfruttata osservando che il prodotto
della matrice A per il vettore generico x pu`o essere ottimizzato
notando che questo corrisponde ad una convoluzione del vettore di correlazione con il vettore x. Inoltre la convoluzione
corris-ponde ad una moltiplicazione nel dominio di Fourier, quindi si `e
utilizzata tale trasformata per abbattere i calcoli. Un ulteriore
ottimizzazione la si `e ottenuta posizionando il codice in sequenze
pi`u idonee dal punto di vista dello sfruttamento della cache. In
ultima analisi si `e cercato il pi`u possibile di memorizzare
vet-tori in aree di memoria contigue poich`e in tal modo l’utilizzo
dell’unit`a ALTIVEC risulta pi`u efficiente.La tab. 5.6 mette in
evidenza il tempo impiegato per calcolare gli autovalori di un frame-dati con N=1024 a seconda del metodo utilizzato. La tab.
Metodo 3 Autovalori 10 Autovalori 80 Autovalori
µsec µsec µsec
Jacobi 216947 4158856 172sec.
Lanczos Classico 50766 67506 235590
Figura 5.6. Tabella dei tempi in microsecondi (µsec)
Nr.Punti Autocorrelazione IRL Totale Tempi
µsec µsec µsec µsec
1024 2860 3301 6022
2048 11085 7312 21899
4096 43009 18077 68156
8192 177032 51531 245021
Figura 5.7. Tabella dei tempi in microsecondi (µsec)
il metodo ottimizzato di Lanczos(IRL), si tenga presente che per N=4096 si ha una matrice di autocorrelazione di ben 16 milioni di punti. Nella tabella la quarta colonna riportante il “Totale
Tempi” `e comprensiva dei calcoli della correlazione, di
fatto-rizzazione di Lanczos, di estrazione autovalori e di un ulteriore modulo di integrazione degli autovettori.