Introduzione | Cap.1 | Cap.2 | Cap.3 | Cap.4 | Cap.5 | Appendice | Bibliografia
L' idea base dei computer paralleli e' che diversi processori cooperano nella soluzione di un singolo problema. Il motivo che spinge ad occuparsi di calcolo parallelo e' proprio il tentativo di velocizzare il calcolo della soluzione dei problemi computazionali. Intuitivamente si potrebbe pensare che, se un processore impiega un tempo t per eseguire un compito, allora p processori possono ultimare lo stesso in un tempo t/p.
In realta' soltanto in casi molto particolari questo ' incremento
di velocita' ' puo' essere raggiunto, e comunque e' compito del
programmatore progettare l' algoritmo in modo da ottenere il massimo
beneficio da architetture multi processore.
La piu' importante classificazione delle macchine parallele e' stata proposta da Flynn. Secondo questa classificazione tutte le architetture parallele rientrano nelle due grandi classi SIMD e MIMD.
In un sistema SIMD (Single-Instruction-Multiple-Data), tutti i processori sono sotto il controllo di un processore 'master' , detto controllore ,e sono vincolati ad eseguire, in un dato istante, la stessa istruzione (o nessuna).
C' e', quindi, un singolo flusso di istruzioni che opera su piu' flussi di dati, uno per ciascun processore.L' ILLIAC IV, il primo sistema parallelo (completato nel 1970), era una macchina SIMD.I calcolatori vettoriali possono essere inclusi nella categoria di macchine SIMD.
La grande maggioranza di computer paralleli costruiti dopo l' ILLIAC IV sono sistemi MIMD (Multiple-Instructions-Multiple-Data). In questi il singolo processore gira sotto il controllo di un proprio programma. Cio' permette una grande flessibilita' nei compiti che un processore puo' eseguire, ma introduce il problema della sincronizzazione. In un sistema SIMD la sincronizzazione dei processori e' svolta dal controllore, mentre in sistemi MIMD devono essere usati altri metodi in modo da assicurare che i processori svolgano i propri compiti nell' ordine corretto e con i dati corretti. Alcuni sistemi di questo tipo sono CRAY X-MP, IBM 3090, INTEL IPCS.
In molti problemi, il programma che i processori di una macchina
MIMD eseguono puo' essere lo stesso. Quindi, tutti i programmi
compiono le stesse operazioni su differenti insieme
di dati, proprio come farebbe una macchina SIMD.Questo modello
di calcolo e' detto SPMD ( Simple-Program Multiple-Data ).
Un' altra importante differenza nei computer paralleli riguarda
il modello di memoria utilizzato. Esso puo' essere di tipo condiviso
(shared memory) o distribuito (distributed memory). Un sistema
a memoria condivisa e' mostrato in Fig 4.1. Qui, tutti i processori
hanno accesso ad una memoria comune. Ciascun processore puo' anche
avere una propria memoria locale per il codice del programma e
dati temporanei, mentre la memoria comune e' utilizzata per dati
e risultati necessari a piu' di un processore. Tutte le comunicazioni
tra i processori sono compiute attraverso la memoria comune. Il
piu' grande vantaggio dei sistemi a memoria condivisa e' l' alta
velocita delle comunicazione tra processori, mentre il grande
svantaggio e' che processori diversi possono desiderare di utilizzare
la memoria comune nello stesso istante. In tal caso uno dei processori
deve attendere che sia liberata la memoria al fine di evitare
conflitti ( un processore potrebbe alterare i dato proprio mentre
l'altro li sta leggendo ). Questo ritardo puo' crescere al crescere
del numero di processori. In genere la memoria condivisa viene
usata su sistemi con un numero di processori basso ( tipicamente
16 processori ).
Un alternativa ai sistemi a memoria comune sono i sistemi a memoria
distribuita, in cui ciascun processore puo' riferirsi soltanto
alla propria memoria locale. Le comunicazioni tra processori avvengono
mediante lo scambio di messaggi (message passing).
Negli elaboratori a memoria distribuita e' importante il modo
in cui avvengono le comunicazioni tra processori, e piu' precisamente
il modo in cui ciascun processore e collegato agli altri (interconnection
network). La scelta di un tipo di network influenza la costruzione
e l' efficienza degli algoritmi. Vediamo brevemente alcuni dei
piu' comuni schemi di interconnessione.
In un sistema di questo tipo ciascun processore ha un collegamento
diretto con tutti gli altri.Chiaramente e' soltanto uno schema
teorico in quanto improponibile per un alto numero di processori.
Infatti, se p e' il numero di processori nel sistema, esso
richiede che si diramino p-1 collegamenti da ciascun processore.
Un altro approccio ai sistemi completamente connessi e' rappresentato da un crossbar switch in cui ciascun processore puo' essere collegato a ciascuna memoria attraverso l'uso di interruttori (switch). Questo presenta il vantaggio di permettere a ciascun processore l' accesso ad ogni memoria con un piu' basso numero di linee di connessione (Fig.4.2).
Uno svantaggio e' che un crossbar switch richiede p2 interruttori
per collegare p processori a p memorie. Questo e'
impraticabile per valori di p grandi a meno di usare uno switching
network. In Fig.4.3 e' rappresentato un semplice esempio
di switching network. Sul lato sinistro ci sono otto processori
e sul destro altrettante memorie. Ogni rettangolo rappresenta
un interruttore a due vie e le linee i canali di trasmissione
(links). In questo modo ciascun processore puo' riferirsi ad ogni
memoria. Infatti supponiamo, per esempio che il processore P1
voglia riferirsi alla memoria M8 .L' interruttore [1,1] viene
settato in modo da instaurare il collegamento tra il processore
e lo switch [2,2] e quindi si setta lo switch [3,4] per collegare
il processore alla memoria M8. La Fig.4.3 rappresenta un sistema
shared memory ma le memorie a destra potrebbero essere esse stesse
processori in tal caso la figura rappresenterebbe un sistema a
memoria distribuita.
FIG.4.3-UNO SWITCHING NETWORK CHE CONSENTE I COLLEGAMENTI TRA
8 PROCESSORI E 8 MEMORIE.
Quando ciascun processore e' collegato soltanto con alcuni processori confinanti si ottiene uno dei piu' comuni schemi di interconnessione. Il tipo piu' semplice e' il linear array ( array lineare) visibile in fig.4.4 .In esso ciascun processore e' collegato ai due piu' vicini. I processori esterni possono essere collegati ad un solo processore o tra loro;in tal caso si parla di ring array ( array ad anello ).
Il linear array e' simile al bus network. Nel bus network ciascun processore ottiene le informazione da un bus ad alta velocita'. Uno dei problemi dei bus network e' che ogni processore deve attendere che il bus sia libero prima di spedire informazioni.
Un linear array e' differente da un bus per il fatto che processori
distanti comunicano attraverso i processori intermedi. Per esempio,
se il processore P1 desidera spedire dati al processore Pp ,i
dati devono essere spediti al processore P2 , quindi a P3 ,e così
via. Il numero massimo di trasmissioni necessarie a collegare
due processori qualsiasi del sistema prende il nome di lunghezza
di comunicazione o diametro del sistema.
La maggior parte dei sistemi mesh-connected che sono stati costruiti usano schemi di connessione bidimensionali. Uno degli schemi piu' semplici di questo tipo e' visibile in Fig.4.7. In esso i processori si trovano ai nodi di una griglia a due dimensioni ed ogni processore e' collegato ai quattro piu' vicini.
La lunghezza di comunicazione per p processori posti ai
nodi di una griglia quadrata e' pari a p½ .
Un' interessante variante delle mesh-connection si ottiene considerando la stessa su piu' dimensioni. Fissiamo prima l' attenzione su un cubo a tre dimensioni e immaginiamo che i processori si trovino ai vertici del cubo. I lati rappresentano le linee di comunicazione tra i processori, cosi' che ogni processore e' collegato ai tre che stanno sui vertici piu' vicini. Consideriamo adesso uno schema analogo che usa un cubo a k dimensioni. Come prima i processori si troveranno sui 2k vertici del cubo k-dimensionale, ed ogni processore sara' collegato con i k nei vertici adiacenti.
Per un cubo in quattro dimensioni ci sono 16 processori ed ognuno
e' collegato con altri quattro.
Gli array di processori connessi con topologia mesh sono particolarmente adatti alla risoluzione di problemi in cui la parte predominante di calcolo e' l'elaborazione su una struttura dati ad elevata regolarita', tipicamente un vettore o una matrice. Nel campo dell' algebra lineare vi sono numerosi problemi che danno origine a computazioni di questo tipo.
Consideriamo il problema di sommare due n-vettori a e b. Le addizioni
sono tutte indipendenti e quindi possono essere eseguite in parallelo.Questo
problema ha quindi un parallellismo matematico perfetto. D' altra
parte esso non ha un parallellismo perfetto su un computer parallelo
a causa del difficile bilanciamento del carico di lavoro.
Per bilanciamento del carico intendiamo l' assegnamento dei compiti
ai processori del sistema in modo che ogni processore compie lavoro
utile per piu' tempo possibile. Supponiamo, per esempio, che ci
sono p=32 processori nel nostro sistema e n=100.
In questo caso i processori possono lavorare perfettamente in
parallelo per 96 addizioni mentre soltanto 4 processori rimarranno
attivi per le quattro addizioni rimanenti. Non c'e' quindi un
grado di parallelismo tale da riflettere il perfetto parallelismo
matematico.
Idealmente, potremmo risolvere un problema p volte piu' veloce su p processori che su un singolo processore. Questa condizione ideale e' raggiunta soltanto in casi molto particolari e questo sopratutto per due motivi:
- presenza nell' algoritmo di parti chee devono essere eseguite sequenzialmente;
- per la presenza di una parte supplemeentare di codice (overhead) il cui compito e' di assegnare i processi ai processori;
Cio' che si ottiene invece e' detto speed-up dell' algoritmo parallelo ed e' definito da:
dove Ts e' il tempo di esecuzione su singolo processore e Tp il tempo usando p processori.
Strettamente legata allo speed-up e' l' efficienza ( efficiency ) definita da:
Essa indica la frazione di tempo impiegata in maniera utile. Dal
momento che Sp£p, risulta Ep£1
e quindi Ep=1 corrisponde ad uno speed-up perfetto Sp=p.
La realizzazione di architetture di tipo transputer risale al 1984. Essi rientrano tra le architetture di tipo MIMD ed interagiscono mediante lo scambio di messaggi.
L' elaboratore su cui e' stata sviluppata la presente tesi e'
dotato di 3 schede, di cui una e' formata da un solo transputer
(monoputer) e le altre sono schede di tipo quadputer, cioe' conteneti
quattro processori.
Express supporta due modelli di programmazione l' Host-Node ed il Cubix.
L' Host-Node prevede la scrittura di due programmi, uno girante
sull' Host e l' altro sui nodi. Questo modello di programmazione
e' del tipo Master-Slave (Fig. 4.9), in cui il master coordina
l' operato degli slave. Nel nostro caso la parte del master e'
svolta dall' Host, il quale si occupa anche di gestire le operazioni
di I/O.
Nel modello Cubix, invece, e' necessaria la scrittura di un solo programma girante su tutti i nodi, che comunicano con l' ambiente esterno attraverso le facilities del sistema operativo del computer ospitante.
I parametri da considerare per effettuare la scelta del modello da utilizzare sono: la quantita' di memoria utilizzata, la quantita' di I/O e non ultima la complessita' del codice.
Il modello di programmazione Cubix offre alcuni vantaggi dal punto di vista del programmatore, tra cui:
- la facilita' di sviluppare programmi,, poiche' non necessita la scrittura di programmi separati;
- la possibilita' di eseguire un programma anche su macchine sequenziali apportando poche modifiche.
Introduzione | Cap.1 | Cap.2 | Cap.3 | Cap.4 | Cap.5 | Appendice | Bibliografia