Modelli
di macchine parallele
Dato l’argomento
abbastanza caotico dovuto a una grande varietà di algoritmi, software
e hardware, numerosi ricercatori hanno cercato di produrre schemi
di classificazione e tassonomie per l’elaborazione parallela. Uno schema
molto usato è quello di Flynn che risale al 1972 e comunque anche
questo risulta una pura approssimazione. La classificazione di Flynn è
basata su due concetti : i flussi di istruzioni e i flussi di dati. Un
flusso di istruzioni corrisponde ad un contatore di programma . Un sistema
con n CPU ha n contatori di programmi, quindi n flussi di istruzioni.
Un programma è costituito da un insieme di operandi. Un programma
che calcola la media di un elenco di temperature ha un flusso di dati.
Un programma che calcola la media delle temperature per ognuno di 100 termometri,
sparsi in tutto il mondo, ha 100 flussi di dati. Possiamo distinguere tra
quattro classi di calcolatori a seconda se esiste uno o più di questi
insiemi di dati e di istruzioni:
1) Singola Istruzione, Singolo
Dato (SISD)
2) Multiple Istruzioni, Singolo
Dato (MISD)
3) Singole Istruzioni, Multipli
Dati (SIMD)
4) Multiple Istruzioni, Multipli
Dati (MIMD)
Calcolatori SISD
Un calcolatore della classe SISD
è costituito da un’unica unità di calcolo che riceve una
singola istruzione che opera su un singolo dato.
Ad ogni passo durante il calcolo
l’unità di controllo emette una istruzione che opera su un dato
ottenuto dall’unità di memoria. Questa istruzione può dire
al calcolatore, per esempio, di eseguire una operazione logica o aritmetica
su di un dato e poi di ricaricarla nella memoria. La grande maggioranza
dei calcolatori oggi aderisce a questo modello inventato da John von Neumann
e dai suoi collaboratori nei tardi anni 1940.
Un algoritmo per calcolatore di
questa classe è detto sequenziale (o seriale).
Calcolatori MISD
Un calcolatore della classe MISD
è costituito da N processori, ciascuno dotato di una propria
unità di controllo e condividente la stessa unità di memoria
dove risiedono i dati. Su questo tipo di calcolatore abbiamo N istruzioni
e un unico dato. A ciascun passo, un dato ricevuto dalla memoria
viene utilizzato da tutti i processori simultaneamente, ciascuno
in accordo con l’istruzione che riceve dalla sua unità di controllo.
Dunque il parallelismo viene raggiunto permettendo ai processori
di fare cose diverse nello stesso tempo sullo stesso dato. Questo tipo
di calcolatori possono essere molto utili per una classe di problemi di
natura piuttosto specializzata. Per la maggior parte delle applicazioni
però questi calcolatori potrebbero essere molto difficili da usare.
I calcolatori paralleli che sono più flessibili e più adattabili
ad un vasto campo di problemi sono quelli descritti successivamente.
Calcolatori SIMD
La classe dei calcolatori
SIMD è costituita da N processori identici. Ogni processore ha la
sua memoria locale in cui può registrare programmi e dati. Tutti
i processori operano sotto il controllo di una singola istruzione che viene
fornita dall’unità di controllo centrale. Praticamente, in un calcolatore
di questa classe possono risiedere N processori che possiedono copie identiche
di un singolo programma in modo da elaborare N dati, uno per ogni processore.
Tali processori operano in modo sincrono cioè ad ogni passo tutti
eseguono la stessa istruzione ma ciascuno con un dato differente. Si possono
avere istruzioni semplici come la somma o il confronto fra due numeri oppure
di tipo complesso come la fusione fra due liste di numeri. Analogamente
per il dato che può essere semplicemente un numero o diversi numeri
nel caso più complesso. Qualche volta si ritiene necessario avere
solo un sotto insieme di processori che eseguono un’istruzione e in tal
caso è indispensabile che alcuni di questi siano attivi per eseguire
l’istruzione oppure inattivi per attendere poi l’istruzione successiva.
La disciplina di queste priorità viene affidata ad un meccanismo
a tempo, il clock globale. L’intervallo di tempo fra due successive istruzioni
può dipendere da queste oppure essere fissato a priori. Per poter
ottimizzare lo scambio di dati o di risultati intermedi risulta interessante
risolvere i problemi relativi alla comunicazione fra processori. Quest’ultimo
concetto può essere affrontato in due diversi modi dando origine
a due diverse sotto classi dei calcolatori SIMD in cui la comunicazione
avviene attraverso una memoria condivisa o per mezzo di una rete di interconnessione.
A loro volta queste sotto classi si suddividono in vari modelli.
1) I calcolatori SIMD
con Memoria Condivisa (Shared-Memory) sono noti anche come macchina parallela
con accesso casuale : Parallel Random Access Machine (PRAM). Gli N processori
condividono una memoria comune e quando due di essi si desidera farli comunicare
si sfrutta la condivisione di memoria. Si supponga che il processore i
voglia passare un numero al processore j. Inizialmente il processore i
scrive il numero nella memoria condivisa ad una data locazione accessibile
al processore j. Al passo successivo, quest’ultimo legge il numero da questa
locazione. Durante l’esecuzione di un algoritmo, gli N processori hanno
la possibilità di accedere alla memoria condivisa per leggere dati
in ingresso, per leggere o scrivere risultati intermedi e per scrivere
i risultati finali. Il modello base permette a tutti i processori di accedere
simultaneamente alla memoria condivisa se le locazioni di queste sono diverse.
Ovviamente possono crearsi problemi di conflittualità perciò
a seconda se due o più processori hanno la possibilità di
accedere alla stessa locazione di memoria troviamo una gestione distinta
dei modelli base. La necessità è quella di suddividere
il modello SM SIMD in quattro sotto classi .
i) I calcolatori SM SIMD a
esclusiva lettura, esclusiva scrittura : Exclusive-Read, Exclusive-Write
più brevemente EREW hanno, per i processori, un accesso esclusivo
alle locazioni di memoria. Praticamente, due processori non possono accedere
simultaneamente per leggere o scrivere alla stessa locazione di memoria.
ii) I calcolatori SM SIMD
a lettura concorrente, scrittura esclusiva : Concurrent-Read, Exclusive-Write
più brevemente CREW hanno, i processori, che possono leggere nella
stessa locazione di memoria ma il diritto di scrivere è ancora esclusivo.
iii) I calcolatori SM SIMD
a lettura esclusiva, scrittura concorrente : Exclusive-Read, Concurrent-Write
più brevemente ERCW hanno, i processori, che possono scrivere nella
stessa locazione di memoria ma l’accesso alla lettura resta esclusivo.
iv) I calcolatori SM SIMD
a lettura concorrente, scrittura concorrente : Concorrent-Read, Concorrent-Write
più brevemente CRCW hanno, i processori, che possono sia scrivere
che leggere la stessa locazione di memoria.
Concettualmente ciascuno dei diversi
processori che legge la stessa locazione di memoria fa una copia dei contenuti
di quella locazione e li immagazzina nella sua memoria locale. Dunque,
permettere l’accesso alla lettura contemporanea dello stesso indirizzo
di memoria potrebbe non creare grossi problemi. Per quanto riguarda il
multiplo accesso alla scrittura la situazione si complica. Si rabbrividisce
al pensiero che diversi processori possano registrare contemporaneamente
dati differenti in un specifico indirizzo di memoria. Per evitare questo
conflitto di scrittura si possono usare, naturalmente per i calcolatori
a scrittura concorrenziale di tipo ERCW e CRCW, varie alternative.
Una potrebbe essere quella di abilitare alla scrittura il processore con
il numero più basso negando l’accesso a tutti gli altri. Un’altra
alternativa potrebbe essere quella di abilitare alla scrittura quei
processori che hanno uguale la quantità che vogliono scrivere negando
l’accesso a tutti gli altri.
Il modello EREW SM SIMD di calcolatori
è indubbiamente il più debole degli altri poiché restringe
l’accesso in uno specifico indirizzo ad un processore per volta. Un algoritmo
per un modello di questo tipo deve essere progettato in modo da escludere
ogni tentativo da parte di più processori di leggere o di scrivere
simultaneamente la stessa locazione di memoria. Fortunatamente il modello
EREW è sufficientemente flessibile tale da permettere la simulazione
di accesso multiplo. Una simulazione di questo tipo è interessante
poiché l’unico calcolatore parallelo disponibile è di tipo
EREW e quindi l’unico modo per eseguire algoritmi di tipo CREW, ERCW o
CRCW è attraverso la simulazione su di esso. Da un punto di vista
tecnologico costruire calcolatori paralleli del tipo CREW, ERCW e CRCW
con un grande numero di processori risulta praticamente impossibile. La
difficoltà risiede sul numero di processori che può simultaneamente
connettere le locazioni di memoria. Tale numero è limitato sia dalla
dimensione che dalle proprietà fisiche del dispositivo.
Il calcolatore SM SIMD è
un modello di calcolo piuttosto veloce, anche nella sua manifestazione
più debole : la classe EREW.
I calcolatori paralleli basati su
questo modello non possono essere costruiti per l’alto costo e la proibitiva
grandezza che possono avere i circuiti di decodifica tra i processori e
la memoria. Infatti quando un processore ha la necessità di creare
un percorso con una locazione di memoria che contiene il dato si sviluppa
un costo dell’eventuale circuito espresso come numero di porte logiche
necessarie per codificare l’indirizzo fornito dal processore. In questo
caso se la memoria è costituita da M locazioni, il costo del circuito
si può pensare come f(M). Se N processori condividono la memoria
come nel modello SM SIMD, il costo del circuito di decodifica sale a
N x f(M) e quindi dipendenti da N e M. Per affrontare questo problema esistono
molti modi e tutti portano inevitabilmente a modelli di calcolatori più
deboli del SM SIMD. Naturalmente qualunque algoritmo può essere
simulato su un modello più debole pagando un prezzo in maggiore
spazio o in maggior numero di passi computazionali. Viceversa, qualunque
algoritmo per modelli più deboli gira su macchine del tipo SM SIMD
senza costi addizionali. Un modo per ridurre i costi di circuiti per decodifica
è usare blocchi di memoria condivisa. Se per esempio, si dispone
di R blocchi di locazioni ciascuno è indispensabile
la progettazione di M+R linee a doppio percorso che permettono a ciascun
processore di avere accesso a qualunque blocco di memoria in qualunque
momento. Tuttavia, non più di un processore può leggere o
scrivere in un blocco simultaneamente come mostrato in figura 6 nel caso
N=5 ed R=3. Quindi, il costo totale del circuito di decodifica è
x più il costo degli interruttori.
2) I calcolatori SIMD
a rete di interconnessione rappresentano l’estensione del modello SIMD
a memoria condivisa in blocchi. In questa classe di calcolatori le
M locazioni di memoria condivisa sono distribuite tra N processori in modo
che ciascuno riceva locazioni. Inoltre, ciascuna coppia
di processori è connessa da una linea bidirezionale per poter
ricevere e spedire un dato. Con queste considerazioni ciascun processore
deve contenere un circuito dal costo di capace di decodificare
un indirizzo per trasmettere agli altri processori e un altro circuito
dal costo di capace di decodificare un indirizzo fornito da un altro
processore. Che questo modello sia più potente rispetto a quello
di memoria condivisa a blocchi lo si vede dal fatto che in esso i processori
comunicano a coppie istantaneamente.
Per questo modello è
importante discutere il costo necessario per la connessione completa degli
N processori. Infatti, il collegamento di una quantità tale di processori
avviene ad un costo totale pari a un numero di combinazioni semplici
di N(N-1)/2 linee. Chiaramente, per un numero elevato di processori, il
costo risulta altissimo. Anche se si desiderasse affrontare un prezzo così
alto, il modello non sarebbe realizzabile in quanto la dimensione fisica
del processore impone un limite sul numero delle linee. Infine è
da notare come un calcolatore del modello appena introdotto sia più
debole rispetto ad uno SM SIMD poiché non più di un processore
può accedere simultaneamente ad un blocco associato ad un altro
processore. Permettere questa proprietà porterebbe ad un costo
di che è circa lo stesso costo che si ha per calcolatori
SM SIMD. Peraltro, a questo totale c’è da aggiungere il costo quadratico
delle linee a doppio percorso. Fortunatamente, nella maggior parte delle
applicazioni è sufficiente un piccolo sotto insieme delle connessioni
per ottenere buone prestazioni, è il caso delle Reti semplici per
calcolatori SIMD. Vediamo singolarmente le varie reti :
i) Vettore lineare. Il modo
più semplice per connettere N processori è nella forma di
un vettore monodimensionale. Il processore Pi è connesso con
i due vicini Pi-1 e Pi+1 per mezzo di una linea di comunicazione a due
sensi. Ovviamente, i processori estremi hanno un solo vicino.
ii) Matrice bidimensionale. Una
rete di questo tipo viene ottenuta connettendo N processori in una matrice
dove. Una siffatta rete è anche denominata maglia. Il processore
di riga j e colonna k definito connette con quattro suoi vicini
ad eccezione dei processori sulla frontiera.
iii) Connessione ad albero
(calcolatori connessi ad albero). In questa rete i processori formano un
albero binario completo. Tale albero ha d livelli numerati da 0 a d-1 e
N=2d-1 nodi che rappresentano ciascuno un processore. Ciascun processore
al livello i è connesso attraverso una linea a doppio senso con
il suo genitore a livello i+1 e con i suoi due figli a livello i-1.
Naturalmente il processore radice non ha genitori così come i processori
foglie non hanno figli. Comunque, oltre a quelle descritte, esistono diverse
altre reti di interconnessione. L’uso di queste dipende notevolmente dalle
applicazioni e in particolare da fattori quali i tipi di calcoli che devono
essere eseguiti, la velocità di esecuzione desiderata e il numero
dei processori disponibili. Per il modello SIMD, i primi strumenti di ricerca
che hanno influenzato in modo significativo le progettazioni successive
coinvolgono un’ampia gamma di applicazioni anche se in realtà hanno
avuto un’esigua risposta commerciale. Tra queste si ricorda la Illiac IV,
un sistema sviluppato all’Università dell’Illinois nel 1960. L’architettura
di questa macchina è di tipo SIMD multiplo con base di array. Essa
è divisa in 4 arrays di 64 processori ciascuno e controllati da
4 unità di controllo. Un’altra importante architettura di tipo SIMD
è la Massively Parallel Processor o più brevemente MPP che
è stata sviluppata nel 1980 dalla Goodyear Aerospazio per conto
della NASA. La sua prima applicazione è stata quella di elaborare
milioni di elementi di immagini satellitari. La caratteristica prorompente
di questa macchina è che elabora simultaneamente ogni elemento dell’immagine.
Fondamentalmente si basa su una unità di tipo array collegata in
ingresso e in uscita da due interfacce a 128 bits e con memoria distribuita.
Finora si è visto come i
calcolatori SIMD siano molto più versatili rispetto a quelli di
tipo MISD. Però l’inconveniente dei calcolatori SIMD è
che le applicazioni sono ristrette solo a quella classe di problemi che
possono essere suddivisi. Questo perché ogni sotto problema viene
risolto simultaneamente dallo stesso insieme di istruzioni. Ovviamente
esistono molti calcoli che non hanno questa caratteristica e quindi non
possono essere risolti dallo stesso insieme di istruzioni. Un modo per
affrontare questo inconveniente è l’introduzione di una quarta classe
di calcolatori che risulta essere decisamente la più potente fra
tutte quelle viste.
Calcolatori MIMD
La classe dei calcolatori MIMD la
possiamo pensare composta da N processori che eseguono N istruzioni su
N dati. Ogni processore opera sotto il controllo di un insieme di istruzioni
eseguite dalla propria unità di controllo. Quindi i processori possono
potenzialmente eseguire programmi diversi applicati a dati diversi. Questo
significa che i processori operano in modo asincrono. In modo del tutto
analogo ai calcolatori di tipo SIMD, i processori comunicano per mezzo
di una condivisione della memoria o per mezzo di una rete di interconnessione.
I calcolatori MIMD che condividono una memoria comune sono chiamati multiprocessori
o macchine altamente accoppiate. Quelli con una rete di interconnessione
sono chiamati multicalcolatori o macchine debolmente accoppiate. Per i
multiprocessori sorgono gli stessi problemi visti precedentemente nella
sezione delle SM SIMD e perciò anche in questo caso ha senso parlare
di modelli come EREW,CREW,ERCW e CRCW. Per quanto riguarda le macchine
debolmente accoppiate si deve distinguere tra multicalcolatori e sistemi
distribuiti. Nei primi i processori sono molto vicini gli uni dagli altri,
nei sistemi distribuiti non lo sono. In quest’ultimo caso l’esempio è
una rete costruita con processori che risiedono in diverse città.
Tale differenza è rilevante nel momento della valutazione degli
algoritmi paralleli.I calcolatori di questa classe vengono usati per risolvere
problemi che non hanno una struttura regolare come richiesto dai modelli
SIMD. Questa generalità non è gratuita; gli algoritmi asincroni
sono difficili da progettare e valutare. Per algoritmo asincrono s’intende
un insieme di processi o sezioni dell’algoritmo che vengono eseguiti simultaneamente
su tutti i processori disponibili. L’algoritmo parallelo viene avviato
su un numero di processori scelto arbitrariamente creando un insieme di
processi che devono essere eseguiti. Appena un processore si rende disponibile,
il processo viene assegnato al processore che esegue i calcoli specificati
dal processo. Se non ci sono processori disponibili, il processo viene
inserito in una coda di attesa. Analogamente, se un processore è
libero e non c’è nessun processo in attesa, allora il processore
viene inserito in un’apposita coda. L’ordine con cui i processi vengono
eseguiti può seguire una qualunque regola che assegni priorità
ai processi. Ad esempio attraverso una priorità del tipo fifo (first
input first output) cioè primo in ingresso e primo in uscita oppure
per mezzo di una lifo (last input first output) cioè ultimo in ingresso
e primo in uscita. Talvolta si ritiene utile assegnare un processo ad uno
specifico processore e quindi una gestione diversa rispetto alla sola disponibilità.
C’è quindi bisogno di una condizione addizionale che deve essere
soddisfatta. Questi problemi vengono chiamati scheduling (gestione delle
code) che sono una caratteristica della programmazione dei multiprocessori.
Trovare una soluzione efficiente per questi problemi è di grandissima
importanza per rendere utili i calcolatori di tipo MIMD. In teoria, qualunque
algoritmo parallelo può essere eseguito in modo efficiente su modelli
MIMD. Tuttavia questi possono essere usati per costruire calcolatori paralleli
adatti a molte applicazioni. In tal caso vengono definiti come architetture
per applicazioni generali (general-purpose).
Si è visto come un
algoritmo progettato su un modello possa essere simulato su un altro. Una
versatilità che induce a pensare come tutti i calcolatori paralleli
siano equivalenti rispetto ai problemi che si possono risolvere. Naturalmente,
la distinzione fra i vari modelli si evidenzia sulla facilità e
la velocità con cui risolvono un particolare problema. E’ importante
valutare l’insieme delle applicazioni per cui il calcolatore può
essere usato e l’urgenza con cui sono necessarie le risposte del problema.
Comunque, nella pratica, la scelta di un calcolatore parallelo è
in generale dettata da considerazioni economiche. |
| |
|
 |
Introduzione
/ Indice