A p p u n ti d i C alcolatori E lettron ici -...

AAAppppppuuunnntttiii dddiii CCCaaalllcccooolllaaatttooorrriii EEEllleeettttttrrrooonnniiiccciii CCCaaapppiiitttooolllooo 111000 ––– PPPaaarrraaalllllleeellliiisssmmmooo nnneeeiii cccaaalllcccooolllaaatttooorrriii

DIREZIONI FUTURE ............................................................................................................. 2

Introduzione .................................................................................................................. 2

Tassonomia dei calcolatori secondo Flynn ....................................................................... 2

Calcolatori SIMD........................................................................................................... 3

Calcolatori MISD........................................................................................................... 5

Calcolatori MIMD.......................................................................................................... 5

Terminologia per le macchine MIMD ........................................................................... 6

Architettura MIMD a scambio di messaggi.................................................................... 7

Architettura MIMD a memoria condivisa ...................................................................... 8

Problema della coerenza delle cache.......................................................................... 9

Prestazioni e problemi delle macchine MIMD ............................................................. 10

Processori per applicazioni speciali: DSP...................................................................... 12

APPUNTI VARI SUI SISTEMI PARALLELI ............................................................................... 13

Limiti della classificazione di Flynn e nuova classificazione............................................ 13

Architetture sincrone ................................................................................................. 13

Architetture MIMD ................................................................................................... 14

Paradigmi MIMD ...................................................................................................... 15

Confronto tre architetture seriali, pipelined e parallele .................................................. 15

Pipelining................................................................................................................. 16

Parallelismi .............................................................................................................. 18

Valutazione delle prestazioni ........................................................................................ 19

Strutture di interconnessione......................................................................................... 20

Banda passante di un sistema di calcolo ........................................................................ 20

Legge di Amdahl applicata ad una macchina con N processori ........................................ 21

Legge di Braunl per architetture SIMD .......................................................................... 23

Tempo di comunicazione inter-processor........................................................................ 25

Legge di Amdahl modificata .......................................................................................... 25

Appunti di “Calcolatori Elettronici” – Capitolo 10

Autore: Sandro Petrizzelli aggiornamento: 15 luglio 2001 2

DDDiii rrreeezzziiiooonnniii fffuuutttuuurrreee

IntroduzioneIntroduzione In questo capitolo vogliamo abbandonare la prospettiva sostanzialmente

“conservativa” seguita nei precedenti capitoli, dando invece dei cenni al futuro dell’architettura dei calcolatori. In generale, possiamo allora subito dire che gli obbiettivi dei progetti innovativi sono essenzialmente due, alternativi tra loro:

• riduzione del rapporto costo/prestazioni;

• raggiungimento di un’alta scalabilità (1) affiancata da un soddisfacente rapporto costo/prestazioni.

Abbiamo ampiamente visto che le CPU con parallelismo a livello di istruzioni

sfruttano il parallelismo intrinseco di un programma, ossia quello esistente tra le singole istruzioni. Si può però facilmente verificare che il parallelismo di tale tipo è relativamente limitato, salvo applicazioni molto particolari: risulta infatti difficile raggiungere una buona efficienza di uso al di sopra di 8 unità funzionali parallele all’interno della singola CPU. A questo, si aggiunge il fatto che esistono applicazioni nelle quali è molto difficile, se non impossibile, individuare parallelismo a livello di istruzione: i sistemi operativi sono un classico esempio a questo proposito.

L’alternativa emersa da alcuni decenni è quella dei cosiddetti sistemi paralleli, nei quali cioè il parallelismo sfruttato è quello a livello di sequenza di istruzioni o di processo: l’architettura, in questi sistemi, è costituita da un certo numero di unità di elaborazione, dotate ognuna di proprie risorse e che interagiscono l'una con l’altra in modo opportuno. Il concetto alla base dei sistemi paralleli è quello per cui, eseguendo simultaneamente più passi di uno stesso problema, si può completare il lavoro molto più velocemente.

Tassonomia dei calcolatori secondo FlynnTassonomia dei calcolatori secondo Flynn Diversi anni fa, Flynn propose un semplice metodo di classificazione dei

calcolatori, basato sul parallelismo del flusso di istruzioni e del flusso di dati ad esso connesso:

• con flusso di istruzioni intendiamo la sequenza di istruzione eseguite da

una unità di elaborazione (un processore);

• con flusso di dati intendiamo invece la sequenza di operandi manipolato dalla suddetta unità di elaborazione.

Flynn propose le seguenti 4 categorie (classificazione di Flynn):

1 La scalabilità è sostanzialmente la possibilità di ripartire lo svolgimento di un dato compito tra più unità funzionali, al fine di sveltire lo svolgimento stesso.

Parallelismo nei sistemi di calcolo

aggiornamento: 15 luglio 2001 Autore: Sandro Petrizzelli 3

• macchine SISD (Single Instruction Single Data): flusso di istruzioni unico e flusso di dati unico; sono le classiche macchine monoprocessore di tipo sequenziale;

• macchine SIMD (Single Instruction Multiple Data): esiste un unico flusso di istruzioni, che però viene applicato a più flussi di dati; risono dunque più processori che eseguono simultaneamente la stessa istruzione su dati diversi (2);

• macchine MISD (Multiple Instruction Singole Data): esiste un unico flusso di dati, cui però vengono applicati diversi flussi di istruzioni; in pratica, più processori eseguono in maniera autonoma istruzioni diverse sullo stesso flusso di dati;

• macchine MIMD (Multiple Instruction Multiple Data): in quest’ultimo caso, più processori eseguono in maniera autonomia istruzioni diverse su dati diversi.

Nonostante questa classificazione appaia un po’ grossolana (molte macchine

sono infatti un ibrido tra varie categorie) e ormai decisamente superata, essa è indubbiamente semplice e facile da comprendere e, in ogni caso, fornisce una prima approssimazione accettabile della realtà attuale.

La macchina tradizionale di Von Neumann è ovviamente di tipo SISD: essa ha un unico flusso di istruzioni (cioè un unico programma) eseguito da una sola CPU ed ha poi un’unica memoria che contiene i dati su cui opera il flusso di istruzioni; la prima istruzione viene presa dalla memoria e poi eseguita, dopodiché si passa al prelievo ed alla esecuzione dell’istruzione successiva e così via fino al termine del programma. Le altre tre tipologie, invece, fanno tutte riferimento a macchine che si definiscono parallele, dove il parallelismo riguarda appunto il flusso di istruzioni o il flusso di dati o entrambi. Nelle classi SIMD e MIMD ricade la quasi totalità di macchine parallele realmente costruite. Le macchine MISD, invece, sono sostanzialmente un caso particolare della classe MIMD.

Calcolatori SIMDCalcolatori SIMD Come anticipato nel precedente paragrafo, una macchina SIMD è caratterizzata

dal fatto che il flusso di istruzioni è singolo, ma opera su più flussi di dati. In questo caso, si può pensare ad una sola unità di controllo che acceda ad una sola memoria istruzioni ed invii, ciclo per ciclo, la stessa istruzione da eseguire a un insieme di unità di esecuzione, che accedono invece ognuna a una propria area della memoria dati (o, alternativamente, che sono dotate ognuna di una propria memoria dati opportunamente precaricata) (3).

Architetture di questo tipo possono essere ricondotte nello schema più semplice alla struttura seguente:

2 Vedremo più avanti che macchine di questo tipo sono anche dette calcolatori matriciali o array computers. 3 I processori vettoriali che abbiamo esaminato nel capitolo 7 potrebbero sembrare delle macchine SIMD, ma in realtà non lo sono: infatti, abbiamo visto che le istruzioni vettoriali operano su più dati, usando una sola unità funzionale con un parallelismo di tipo pipeline; quindi, al contrario di quanto avviene nelle macchine SIMD, una singola istruzione vettoriale non attiva molte unità funzionali; invece, una macchina SIMD effettiva potrebbe ad esempio avere 64 dati che vanno simultaneamente a 64 unità ALU per formare 64 somme nello stesso ciclo di clock.



Memoria istruzionie

unità di controllo

Memoria Dati

Unitàdi

elaborazione

Unitàdi

elaborazione

Unitàdi

elaborazione......

Le varie unità di elaborazione possono naturalmente essere organizzate secondo

schemi più complessi ed eventualmente scambiarsi informazioni. In ogni caso, in una struttura di questo tipo, i singoli processori possono anche

essere dispositivi molto semplici (al limite, unità aritmetiche dotate di registri di ingresso e di uscita) come anche architetture dedicate a particolari computazioni. La sincronizzazione fra i diversi nodi è rigida, dato che tutti, almeno in linea di principio, devono eseguire l'identica istruzione, con la stessa latenza, sui propri dati.

Il vantaggio principale delle macchine SIMD è dunque quello per cui tutte le unità funzionali per l’esecuzione parallela sono sincronizzate e rispondono ad una sola istruzione, proveniente da un unico registro PC (4). Ci sono poi altri vantaggi:

• in primo luogo, si può ridurre il costo dell’unità di controllo affiancandola a

decine di unità di esecuzione;

• in secondo luogo, di recente ci si è resi conto che si può anche adottare una dimensione ridotta della memoria di programma: infatti, le macchine SIMD necessitano di una sola copia del programma da eseguire, al contrario per esempio delle macchine MIMD che richiedono una copia per ogni processore. In questo modo, anche in presenza di un elevato numero di unità funzionali, il costo della memoria di programma risulta minore per le architetture della classe SIMD rispetto alle altre.

I calcolatori SIMD, al pari delle macchine vettoriali, presentano istruzioni

“compatibili” sia con la classe SIMD (ovviamente) sia anche con la classe SISD: per esempio, operazioni come il calcolo di diramazioni o di indirizzi non richiedono alcun parallelismo e sono quindi eseguite da un host computer di tipo SISD. Le istruzioni SIMD sono invece trasmesse a tutte le unità di esecuzione, ognuna delle quali è provvista del suo insieme di registri.

Come le macchine vettoriali, anche le macchine SIMD hanno istruzioni che disabilitano le singole unità di esecuzione.

Al contrario delle macchine vettoriali, invece, l’elevato parallelismo delle macchine SIMD dipende strettamente dalle reti di interconnessione, ossia da tutto quanto (hardware e software) viene usato per lo scambio di dati tra i vari elementi processanti.

4 In questo senso, dal punto di vista del programmatore, il comportamento della macchina è molto simile a quello di una classica macchina SISD (monoprocessore).



Le architetture SIMD raggiungono le loro massime prestazioni quando le istruzioni vettoriali vengono utilizzate in pieno, ad esempio quando gli array vengono scanditi all’interno di cicli FOR. Questo per dire che, per ottenere il massimo parallelismo, occorre una “grande quantità di dati”, intesa naturalmente come “parallelismo dei dati”. Il limite principale di una macchina SIMD emerge invece quando essa deve eseguire comandi in cui ogni singola unità di esecuzione deve svolgere operazioni diverse su dati diversi.

Il progetto di una macchina SIMD richiede di porre attenzione a due importanti fattori ed al loro rapporto: l’efficienza di utilizzo del singolo processore ed il numero di processori. La tendenza attuale delle macchine SIMD sembra privilegiare un elevato grado di parallelismo rispetto all’elevato rendimento del singolo processore.

Architetture di tipo SIMD sono state ampiamente studiate, in particolare per l'elaborazione di segnale e per quella delle immagini: per esempio, è interessante ricordare che l'estensione MMX dell'architettura Pentium, progettata esplicitamente per elaborazione di immagine, è riconducibile a uno schema SIMD.

Calcolatori MISDCalcolatori MISD Non è del tutto intuitivo immaginare una macchina MISD, in cui cioè più flussi di

istruzioni operano contemporaneamente su un unico flusso di dati, in quanto risulta molto più semplice pensare a flussi multipli ognuno associato ad un proprio flusso di dati (che poi è la definizione di macchine MIMD). Ad ogni modo, due esempi di macchine MISD potrebbero in qualche modo essere le macchine superscalari e le architetture VLIW descritte nel paragrafo 6, che però presentano una differenza non irrilevante con le macchine MISD propriamente dette: hanno un unico registro PC, mentre invece le macchine MISD prevedono un registro PC per ciascun flusso.

Calcolatori MIMDCalcolatori MIMD Potremmo affermare che le macchine MIMD sono le macchine parallele per

eccellenza, dato che presuppongono il parallelismo sia a livello di flusso di istruzioni sia a livello di flusso di dati. In effetti, fin dalle prime realizzazioni di calcolatori, i progettisti si sono sempre sforzati di ottenere macchine di questo tipo, in cui cioè la “potenza” in generale fosse ottenuta semplicemente connettendo molti calcolatori più piccoli. Con una simile architettura, l’utente dispone, in modo ordinato, di tante CPU quante se ne può permettere ed ottiene un rendimento di quantità proporzionata (5).

Le architetture MIMD hanno almeno altri due vantaggi, oltre le prestazioni particolarmente elevate: un rendimento assoluto più alto rispetto al più potente monoprocessore ed anche un più alto rapporto affidabilità/disponibilità, ottenuto proprio sfruttando la ridondanza di processori (se un processore si guasta, ce ne sarà un altro pronto a lavorare per lui).

5 Vedremo comunque tra poco che l’aumento di prestazioni non è lineare come l’aumento delle CPU utilizzate.



TTTeeerrrmmmiiinnnooolllooogggiiiaaa pppeeerrr llleee mmmaaacccccchhhiiinnneee MMMIIIMMMDDD Prima di fornire qualche dettaglio maggiore sulle macchine MIMD, risulta

opportuno introdurre un po’ di terminologia relativa a questo tipo di macchine. Una importante suddivisione delle macchine MIMD è relativa alle modalità con cui

viene ripartita l’ “informazione”:

• nei processori a memoria condivisa, esiste una zona di memoria cui possono accedere tutti i processori (6); i processori comunicano attraverso variabili allocate in tale zona di memoria condivisa. Per coordinare i vari processi, sono disponibili delle primitive di sincronizzazione;

• in alternativa, per la condivisione dei dati si può pensare di mettere in comunicazione i vari processi tramite uno scambio di messaggi.

Sulla base di questa suddivisione, Bell ha suggerito l’uso delle seguente

terminologia:

• multiprocessore è una macchina MIMD in cui la comunicazione avviene tramite memoria condivisa;

• multicalcolatore è invece una macchina MIMD in cui la comunicazione avviene solo tramite il passaggio di messaggi espliciti.

In effetti, ci sarebbe da precisare una cosa: in presenza di memoria condivisa, la si

potrebbe comunque usare per lo scambio di messaggi, per cui un multiprocessore potrebbe essere in grado di eseguire programmi basati invece sullo scambio di messaggi (e quindi destinati ai multicalcolatori); dualmente, un multicalcolatore potrebbe simulare, proprio tramite i messaggi, la presenza di una memoria condivisa, in modo da eseguire programmi che richiedono l’uso della memoria condivisa. Ecco allora che la distinzione proposta da Bell è specificamente basata sull’hardware a disposizione della macchina e sul modello di esecuzione del programma e non sul software che dovrebbe essere eseguito.

Ci sono sostenitori sia del multiprocessore sia del multicalcolatore: i primi mettono in discussione la programmabilità dei multicalcolatori (data la necessità e la difficoltà di progettare le primitive per lo scambio dei messaggi), mentre invece i secondi mettono in discussione la scalabilità dei multiprocessori (data appunto la presenza di un’unica memoria condivisa, che potrebbe essere limitante delle prestazioni).

Ad ogni modo, analizziamo con maggiore dettaglio le due soluzioni: • architetture a scambio di messaggi:

o il parallelismo è fra processi: tipicamente, si alloca un processo su ogni nodo, dove per nodo intendiamo un singolo processore e la sua memoria;

o i processi comunicano solo scambiandosi messaggi, mediante primitive send (accompagnate dall’identificatore del destinatario, da un'etichetta e dal messaggio vero e proprio) e receive (accompagnata da etichetta e messaggio);

o i processi si sincronizzano “bloccandosi” sui messaggi: il processo che ha inviato il messaggio si blocca in attesa della risposta. Inoltre, essi si

6 I multiprocessori dotati di cache coerenti sono tipiche macchine a memoria condivisa.



bloccano ponendo delle “barriere” che non possono essere superate fino a quando lo scambio non è andato a buon fine.

• architetture a memoria condivisa:

o sono i cosiddetti threads (cioè sottoprocessi che condividono lo stesso spazio di indirizzamento) ad essere allocati sui diversi nodi (CPU);

o i threads comunicano attraverso uno spazio di memoria condiviso (mediante normali istruzioni load e store del tipo visto per il DLX);

o i threads si sincronizzano tra loro, mediante operazioni "atomiche" (non divisibili) sulla memoria o mediante barriere.

In una macchina MIMD, in generale, l’applicazione da eseguire deve essere

innanzitutto partizionata (in processi o in threads), in modo da essere allocata sui diversi nodi, e le diverse unità di programma devono poi essere ordinate nel tempo (schedulazione) in modo da garantire che le dipendenze di dati e di controllo vengano rispettate.

AAArrrccchhhiiittteeettttttuuurrraaa MMMIIIMMMDDD aaa ssscccaaammmbbbiiiooo dddiii mmmeeessssssaaaggggggiii Lo schema generale di una simile architettura (detta anche a memoria distribuita)

è il seguente:

Rete di Interconnessione

...................

CPU

Memoria

CPU

Memoria

CPU

Memoria

nodo

I vari calcolatori (nodi) sono collegati tramite una rete di interconnessione; ogni

nodo viene dotato di una interfaccia veloce alla suddetta rete, in modo da implementare in modo efficiente le primitive di send e di riceive, nonché le barriere di cui si è parlato. A parte questo, sotto ogni altro aspetto il sistema è indistinguibile da un normale sistema monoprocessore.

In queste architetture, i collegamenti tra le unità di elaborazione sono tali che ognuna di essere abbia il controllo esclusivo di una certa porzione di memoria. Ci sono in proposito vari schemi di connessione: ad anello, a maglia, ad albero binario. Una soluzione particolare è quella che prevede una topologia ad ipercubo: le unità di elaborazione sono collegate tra loro come se si trovassero ai vertici di un cubo multidimensionale. Il vantaggio è che, pur senza realizzare un numero elevato di collegamenti, ogni unità di elaborazione può inviare messaggi ad una qualsiasi altra tramite un percorso comunque breve.



AAArrrccchhhiiittteeettttttuuurrraaa MMMIIIMMMDDD aaa mmmeeemmmooorrriiiaaa cccooonnndddiiivvviiisssaaa Lo schema generale di una simile architettura è il seguente:

CPU CPU CPU

Memoria Condivisa

.........................


I vari processori condividono in questo caso un unico spazio di

indirizzamento; le comunicazioni sono implicite, in quanto avvengono mediante letture e scritture in posizioni di memoria condivise. La sincronizzazione avviene ancora mediante la condivisione della memoria e mediante le barriere.

All’aumentare del numero di processori, la memoria condivisa diviene il collo di bottiglia di tutto il sistema; al contrario, nel caso delle architetture con scambio di messaggi, questo problema non si poneva, ma il collo di bottiglia era comunque nella struttura di interconnessione.

Per aggirare il problema del collo di bottiglia sulla memoria, in molti casi questa architettura concettuale viene in realtà implementata con un multiprocessore in cui lo spazio di indirizzamento viene distribuito sulle memorie locali dei vari nodi o in cui comunque ogni nodo è dotato di una cache locale mentre è la RAM ad essere condivisa. Si realizza perciò una architettura del tipo seguente:


...................

CPU

Cache

CPU

Cache

CPU

Cache

nodo

Memoria Condivisa



Uno svantaggio di questo sistema si ha quando si decide che ogni unità di elaborazione può accedere a tutte le unità di memoria globali e comuni: servono infatti molti collegamenti (si parla di schema a connessione diretta).

Una alternativa sarebbe l’uso di un bus lungo il quale le unità di elaborazione inviano richieste ai banchi di memoria, i quali in risposta inviano i dati: tuttavia, sarebbe nuovamente il bus ad essere troppo affollato.

Una ulteriore possibilità è la cosiddetta rete a OMEGA: le unità di elaborazione sono connesse ai banchi di memoria tramite una serie di commutatori, ognuno dei quali ha due linee di ingresso e due di uscita; in tal modo, ogni unità di elaborazione può accedere a tutti i banchi di memoria, ma non è necessario avere tante linee di comunicazione come nello schema a connessione diretta, in quanto ci pensano i commutatori ad instaurare il “percorso” richiesto dal collegamento. E’ chiaro che il vantaggio è tanto maggiore quanto maggiore è il numero di unità di elaborazione e di banchi di memoria. Al contrario, c’è lo svantaggio per cui ogni messaggio deve passare attraverso molti commutatori prima di giungere a destinazione.

Problema della coerenza delle cache Una soluzione in cui i nodi sono dotati ciascuna di una propria cache fa nascere

un problema particolare: è il cosiddetto problema della coerenza della cache. Ad esempio, un processore potrebbe leggere dati “vecchi” nella propria cache, mentre quelli nella memoria condivisa sono stati aggiornati da un altro processore; oppure, un processore può leggere dati vecchi nella memoria condivisa invece di quelli aggiornati nella cache di un altro professore.

Si può pensare a varie soluzioni per questo problema:

• la soluzione più banale consiste nell'evitare di portare in cache i dati condivisi;

• una soluzione più efficiente richiede invece l'introduzione di un protocollo per la coerenza delle cache: tale protocollo deve tener traccia delle varie copie dei dati condivisi e deve informare i nodi (con un aggiornamento o semplicemente “invalidando” i dati vecchi) quando un nodo compie un’operazione di scrittura.

A proposito di questa seconda soluzione, si può pensare a due diverse

implementazioni effettive:

• la prima è quella di un protocollo snoopy (cioè “curioso”): in pratica, una scrittura viene inviata in broadcast a tutti i nodi, il che presuppone ovviamente che ogni nodo “resti in ascolto” delle eventuali scritture e stabilisca se deve aggiornare o meno la propria cache;

• la seconda implementazione è quella dei cosiddetti protocolli directory-based, nei quali una transazione di scrittura viene inviata solamente a quei nodi di cui è noto che possiedono una copia del dato da aggiornare. In questo caso, deve esserci da qualche parte una specie di tabella consultabile da ciascun nodo, in cui siano registrati i nodi che possiedono una copia del dato che si sta per scrivere; così facendo, il nodo che vuole effettuare la scrittura può informare solo i nodi interessati e inviare solo a loro i nuovi dati.



E evidente che la prima soluzione è più semplice, ma comporta un traffico molto più elevato sul bus, data la necessità del broadcast; essa si adatta perciò soprattutto a quelle architetture in cui il collegamento tra i nodi viene effettuato mediante un bus condiviso.

Ad ogni modo, ad prescindere dalla soluzione scelta, il nodo può poi decidere se aggiornare la copia invalidata oppure no: ad esempio, se i dati coinvolti non sono più necessari, non è necessario perdere tempo ad aggiornarli.

Resta poi insoluta un’ultima questione: se aggiornare anche la memoria primaria quando si aggiornano le cache, oppure considerare corretti solo i dati contenuti in queste ultime.

PPPrrreeessstttaaazzziiiooonnniii eee ppprrrooobbbllleeemmmiii dddeeelllllleee mmmaaacccccchhhiiinnneee MMMIIIMMMDDD Rispetto ad una tradizionale macchina SISD, le macchine MIMD offrono

prestazioni decisamente migliori per l’implementazione di sistemi time sharing (cioè a condivisione di tempo): a parità di carico di lavoro, in una macchina MIMD si possono infatti eseguire in parallelo più compiti tra loro indipendenti, nonostante il tempo di CPU di ciascun compito rimanga invariato rispetto alle macchine SISD. Il risultato è dunque un maggiore throughput, mentre la latenza dei singoli programmi rimane invariata (7). Proprio per questo motivo, attualmente le macchine MIMD rappresentano una fetta di mercato significativa, che si aggiudica la maggior parte del settore dei mainframe e in pratica tutto il settore dei supercalcolatori.

Ad ogni modo, non bisogna pensare, relativamente alle macchine MIMD, che sia tutto “rose e fiori”. Infatti, uno dei principali punti deboli per queste macchine è il numero ancora troppo esiguo di applicazioni destinate specificamente a questo tipo di macchine e quindi in grado di sfruttarne le potenzialità: la maggior parte delle applicazioni non sono state scritte o adattate (rispetto alle versioni originali per le macchine SISD) per sfruttare tutti i processori presenti e ridurre così il throughput, il che inficia l’opportunità di acquistare questo tipo di macchine. Viene ovviamente da chiedersi il perché di questa carenza di applicazioni: la risposta sta proprio nella difficoltà di scrivere simili applicazioni. Per comprendere a pieno il concetto, facciamo una analogia, confrontando il tempo necessario affinché un dato lavoro venga svolto da un’unica persona o da un gruppo di persone: almeno a livello teorico, se il gruppo è formato da N persone, il lavoro dovrebbe essere completato in un tempo N volte inferiore rispetto a quello impiegato da un singolo individuo (per cui si avrebbe una accelerazione pari idealmente ad N); in realtà, non sarà mai così , in quanto è necessario quanto meno che le varie persone del gruppo comunichino tra loro man mano che svolgono i propri compiti; la difficoltà di tale comunicazione è minima se le persone sono 2 o 3, ma se diventano 1000 o 10000, allora è evidentemente che le cose si complicano non poco. Più avanti nel capitolo faremo una analisi più quantitativa di questo discorso.

Un’altra difficoltà per la scrittura di applicazioni per macchine MIMD è il grado di conoscenza dell’hardware richiesta al programmatore: se quest’ultimo deve scrivere una applicazione (in un linguaggio ad alto livello) per una macchina SISD, può tranquillamente disinteressarsi dell’hardware della macchina, in quanto sarà poi compito del compilatore ottimizzare il codice macchina in funzione di tale hardware; al contrario, per una macchina multiprocessore, il programmatore scriverà

7 Accade cioè una cosa analoga a quella che riguarda il singolo programma eseguito su una macchina SISD dotata di pipeline: la latenza delle singole istruzioni rimane invariata, ma il CPI viene molto ridotto e quindi l throughput finale è maggiore.



programmi tanto più efficienti e scalabili quanto maggiore è la sua conoscenza sia dell’hardware sia dell’organizzazione della macchina. Tra l’altro, quest’ultima considerazione rende i programmi paralleli poco portabili, proprio perché nascono specificamente per una macchina e difficilmente si adeguano ad un’altra macchina (o quanto meno non riescono a sfruttarne a pieno le potenzialità).

L’ultima limitazione per la scrittura di applicazioni parallele proviene direttamente dalla legge di Amdahl: infatti, questa legge evidenzia che anche le parti meno importanti di un programma devono essere parallelizzate se si vuole raggiungere il pieno potenziale, in quanto tutte le eventuali migliorie apportate alla macchine e/o al programma forniscono incrementi di prestazioni tanto più pronunciati quanto maggiore è la frazione di tempo in cui possono essere impiegati.

Per comprendere bene questo aspetto, possiamo fare un esempio molto semplice: supponiamo di voler eseguire un programma su un macchina dotata di 100 processori e di voler ottenere un incremento di prestazioni equivalente rispetto ad una macchina SISD; ci chiediamo quale porzione della computazione originale può rimanere sequenziale e quale invece debba essere parallelizzata. Ci basta applicare la legge di Amdahl, che riportiamo qui di seguito nella sua espressione riassuntiva:

( )migliorata

miglioratamigliorata oneAccelerazi

FrazioneFrazione-1

1oneAccelerazi

+=

In questa espressione, il termine “ migliorataFrazione ” indica la frazione di

computazione che deve risultare migliorata (ossia, nel nostro caso, la frazione di codice che deve essere parallelizzata), mentre invece il termine “ migliorataoneAccelerazi ” è

il miglioramento di prestazioni ottenibile nel caso ideale in cui tutta la computazione venisse ottimizzata. Nel nostro caso, quest’ultima quantità vale 100, dato che usiamo 100 processori al posto di uno solo, per cui cominciamo a scrivere che

( )100

FrazioneFrazione-1

1oneAccelerazi

miglioratamigliorata +

=

Dobbiamo ora inserire l’obbiettivo che ci siamo preposti, ossia un miglioramento

complessivo delle prestazioni pari a 100:

( )100

FrazioneFrazione-1

1001

miglioratamigliorata +

=

Questa equazione va risolta nell’unica incognita rimasta ed è intuitivo il risultato

finale: 1Frazionemigliorata = , il che significa che, per ottenere un incremento lineare con

100 processori, TUTTA la computazione originale deve essere parallelizzata. Se per esempio avessimo voluto una accelerazione complessiva pari a 99, sarebbe risultato

99999.0Frazionemigliorata = , ossia solo una parte pari a 0.0001 di computazione originale

sarebbe potuta rimanere sequenziale. Visto in un’altra prospettiva, quest’ultimo calcolo mostra che anche una piccolissima porzione di codice non parallelizzato (0.0001, cioè lo 0.01%) può determinare una riduzione dell’accelerazione



complessiva rispetto a quella ideale desiderata. Anche di questo aspetto ci occuperemo comunque in seguito nel capitolo.

ProcessorProcessori per applicazioni speciali: DSPi per applicazioni speciali: DSP Quanto detto nei paragrafi precedenti illustra dunque la grande attenzione che i

progettisti devono rivolgere e rivolgono effettivamente al parallelismo ottenibile nei calcolatori. Un'altra questione ampiamente approfondita da progettisti è quella dei calcolatori per applicazioni speciali: grazie all’ausilio di sempre più sofisticati programmi di CAD (Computer Aided Design) e all’incremento della capacità dei singoli chip, si è infatti presentata l’opportunità di produrre, rapidamente ed a prezzi ridotti, circuiti volti a risolvere in maniera efficiente compiti particolari. Esempi classici sono riscontrabili nei dispositivi per il riconoscimento vocale in tempo reale e per l’elaborazione di immagini.

I dispositivi per uso speciale (detti spesso coprocessori) agiscono generalmente in collaborazione con la CPU. Uno dei filoni attualmente più diffusi è quello dei dispositivi per l’elaborazione dei segnali digitali (DSP, Digital Signal Processing): questi dispositivi non rispondono ai modelli di calcolo tradizionali, ma sembrano piuttosto macchine microprogrammate orizzontali (8) o al più macchine VLIW (9). Essi tendono a risolvere problemi in tempo reale partendo essenzialmente da un flusso di dati (in questo caso bit) di tipo continuo.

8 Ne abbiamo parlato nel capitolo 5: sono macchine in cui si predilige l’uso di poche microistruzioni ma di grande lunghezza al posto di molte microistruzioni di piccola lunghezza. 9 Ne abbiamo parlato nel capitolo 6: sono macchine in cui una singola istruzione corrisponde all’esecuzione di più operazioni.



AAAppppppuuunnnttt iii vvvaaarrr iii sssuuuiii sssiiisssttteeemmmiii pppaaarrraaalll llleeelll iii

Limiti della classificazione di Flynn e nuova Limiti della classificazione di Flynn e nuova classificazioneclassificazione

La classificazione di Flynn (che suddivide le architetture dei calcolatori in SISD, SIMD, MISD e MIMD), per quanto molto semplice, appare oggi insufficiente per classificare i calcolatori presenti sul mercato. Ad esempio, i cosiddetti processori vettoriali in pipeline possono essere considerati come macchine parallele, ma difficilmente li si può classificare secondo Flynn: infatti, non sono macchine di tipo SIMD in quanto non hanno più processori che eseguono la stessa istruzione, né possono essere viste come macchine MIMD in quanto non sono asincrone.

Una classificazione senz’altro più attuabile, al giorno d’oggi, è quella che individua le seguenti categorie:

• architetture sincrone:

o processori vettoriali in pipeline;

o processori SIMD del tipo processor array;

o processori SIMD del tipo associative memory;

o processori sistolici;

• architetture MIMD:

o architetture a memoria distribuita;

o architetture a memoria condivisa;

• paradigmi MIMD:

o calcolatori ibridi MIMD/SIMD;

o calcolatori data flow;

o calcolatori di riduzione;

o calcolatori wave front.

AAArrrccchhhiiittteeettttttuuurrreee sssiiinnncccrrrooonnneee I processori vettoriali in pipeline (come il DLXV) sono caratterizzati dall’avere

più unità funzionali in pipeline, che effettuano in parallelo operazioni aritmetiche e logiche sia su vettori sia su scalari. Il parallelismo si manifesta nella sovrapposizione di fasi diverse di una stessa istruzione su dati diversi, come in una catena di montaggio in cui vengono lavorati simultaneamente più pezzi. In strutture di questo tipo, il tempo di latenza è definito come il tempo che intercorre tra l’inizio dell’elaborazione e l’apparire del primo risultato. Una struttura con elevato tempo di latenza può risultare comunque efficiente solo quando vi è un gran numero di calcoli identici da eseguire, in quanto in questo modo nessuna unità funzionale risulta inattiva.



I processori SIMD di tipo processor array (detti anche processori matriciali) forniscono invece ottime prestazioni solo per quei programmi che contengono una alta percentuale di istruzioni vettoriali. Tipiche applicazioni per queste macchine sono quelle per l’elaborazione delle immagini: la singola immagine è organizzata in forma matriciale e può essere sia sistemata in una memoria comune sia partizionato su più memorie locali, a seconda del tipo di elaborazione da compiere.

Da notare che una differenza fondamentale tra i processori vettoriali e i processori matriciali è che questi ultimi sono dotati di un dispositivo di comunicazione dei dati che invece i processori vettoriali non hanno.

Una variante dei processori matriciali consiste nell’usare un gran numero di processori single-bit.

I processori SIMD di tipo associative memory (detti anche semplicemente processori associativi) sono caratterizzati dal fatto che l’insieme delle memorie dati è realizzato tramite una memoria associativa: ogni parola di tale memoria è associata a speciali registri ed alla logica di confronto che compone un processore:

Memoria di programma Controllore di Programma Array Controller

ALU e registri speciali

Memoria associativa

Infine, i sistemi di tipo sistolico sono stati pensati per sfruttare la tecnologia

VLSI ed il fatto che le interconnessioni semplici sono quelle che consentono implementazioni più economiche, alta densità di integrazione ed alte prestazioni; tali sistemi inglobano contemporaneamente i concetti di pipeline, parallelismo e regolarità nelle interconnessioni.

In generale, un sistema sistolico è una rete di processori, collegati tramite interconnessioni dedicate, secondo topologie regolari. Ciascun processore autonomamente calcola dati e li trasmette attraverso le proprie interconnessioni. Il “pulsare” regolare dei processori conduce ad un flusso di dati regolare e continuo attraverso l’intero sistema. Questo tipo di architetture sono molto usate nell’elaborazione dei segnali, dove infatti l’uscita deve essere cadenzata così come è cadenzato l’ingresso dei dati.

AAArrrccchhhiiittteeettttttuuurrreee MMMIIIMMMDDD Come più volte detto in precedenza, in questo caso il programmatore può

controllare più flussi di istruzioni e più flussi di dati. Le due alternative sono tra architetture a memoria condivisa ed architetture a

memoria distribuita e sono state già esaminate in precedenza.



PPPaaarrraaadddiiigggmmmiii MMMIIIMMMDDD Le macchine appartenenti a questa classe sono tutte basate sui principi MIMD di

operazioni asincrone e manipolazione concorrente di più istruzioni e più flussi di dati. Si tratta in genere di macchine ancora sperimentali.

I processori ibridi MIMD/SIMD sono architetture che consentono a parti selezionate di una architettura MIMD di essere controllate in maniera SIMD. In queste macchine, è fondamentale avere dei collegamenti a larghissima banda, in modo che dati ed istruzioni possano “spostarsi” rapidamente tra le unità di elaborazione, rendendo minimi i temi morti: in genere, le unità di elaborazione sono poche e molto veloci e sono collegate da fibre ottiche.

Un processore ibrido a flussi di dati (o data flow) prende le basi da una rappresentazione grafica particolare, introdotta da Dennis: in pratica, si utilizza un grafo in cui i nodi corrispondono a operatori e gli archi corrispondono a canali di comunicazione per trasmettere valori da un operatore all’altro; la particolarità è che le operazioni non vengono eseguite dai nodi secondo una sequenza definita dal programma: ogni nodo esegue la propria operazione solo nel momento in cui possiede tutti i dati necessari, dopodiché trasmette il risultato al nodo successivo. Questo schema computazionale è molto simile ad una corsa a staffetta: ogni atleta (nodo) parte non appena ha ricevuto il testimone (dato) dall’atleta che ha percorso il tratto precedente di gara. Naturalmente, proprio per il fatto che ogni nodo esegue il compito assegnatogli solo quando possiede tutti i dati necessari, non c’è il pericolo di eseguire operazioni prematuramente, così come, ad esempio, non ci può essere il tentativo di molte unità di elaborazione di leggere simultaneamente una stessa locazione di memoria. Il vantaggio finale delle architetture a flusso di dati è che si evitano i casi di strozzatura delle architetture parallele e, allo stesso tempo, si offre un nuovo modo per sfruttare il parallelismo implicito nei programmi.

Per concludere con questa panoramica, nei primi anni ’80 Kung sviluppò i concetti del wave front array: il principio di fondo è che, quando un processore ha eseguito i suoi calcoli ed è pronto a passare i dati al successore, lo informa di ciò ed aspetta che questi gli dia il via per il trasferimento.

Confronto tre architetture seriali, pipelined e paralleleConfronto tre architetture seriali, pipelined e parallele Consideriamo l’esecuzione di tre processi (A, B e C) su un calcolatore; supponiamo

che ogni processo richieda un certo numero di variabili di ingresso (ad esempio due, denominate x ed y) e produca un certo numero di variabili in uscita (ad esempio una sola, denominata z). Supponiamo inoltre di poter dividere ogni singolo processo in 4 sottoprocessi (S1, S2, S3 e S4). Nella prossima figura vengono confrontate le modalità di esecuzione dei vari sottoprocessi in tre architetture:

• architettura seriale classica (SISD);

• architettura seriale con pipeline (MISD);

• architettura parallela con tre processori (MIMD).



S1 S2 S3 S4xA

yAzA

S1 S2 S3 S4xB

yBzB

S1 S2 S3 S4xC

yCzC

Esecuzione seriale

S1 S2 S3 S4xA

yAzA

S1 S2 S3 S4xB

yBzB

S1 S2 S3 S4xC

yCzC

Esecuzione pipelined

S1 S2 S3 S4xA

yAzA

S1 S2 S3 S4xB

yBzB

S1 S2 S3 S4xC

yCzC

Esecuzione parallela

E’ ovvio che, nell’esecuzione pipelined, si suppone che non ci siano ostacoli (quelli che nel capitolo 6 abbiamo chiamato conflitti) all’esecuzione contemporanea di più sottoprocessi. Analogamente, nell’esecuzione parallela, si suppone che siano disponibili almeno tre processori, uno per ciascun processo, e che i tre processi siano del tutto indipendenti tra loro, proprio per consentire la contemporaneità della loro esecuzione.

Sull’esecuzione seriale dei programmi, abbiamo ben poco da dire. Al contrario, i prossimi due paragrafi forniscono qualche dettaglio in più circa il pipelining e l’esecuzione parallela.

PPPiiipppeeellliiinnniiinnnggg Il concetto di pipelining può essere applicato fondamentalmente a tre “livelli”

distinti:

• pipeline a livello di processore (processor pipeline);

• pipeline a livello di istruzioni (instruction pipeline);

• pipeline a livello di operazioni aritmetiche (arithmetic pipeline).



La seconda e la terza tipologia di pipelining sono quelle presenti nei processori vettoriali (specialmente il pipeline aritmetico). Il pipeline a livello di processori corrisponde invece ad usare una catena di processori funzionanti in pipeline.

In ogni caso, il pipelining è un esempio di “sistema MISD”, in cui cioè un insieme multiplo di istruzioni opera contemporaneamente sullo stesso insieme di dati.

Le figure seguenti schematizzano le tre possibilità:

CPU MEM CPU MEM CPU MEM

Processors Pipeline. Si suppone che ciascuna memoria abbia una doppia porta di accesso. Si suppone inoltre che il funzionamento sia sincrono, perché solo in questo caso si parla

rigorosamente di pipeline. Potrebbe capitare che un processore sia più veloce di altri: si potrebbe allora pensare di farlo lavorare su quantità di dati maggiori rispetto agli altri, ad

esempio operando procedure di sovracampionamento dei dati in ingresso

MEMFETCH

istr iDECODistr i-1

FETCHistr i-2

EXEistr i-3

ALU MEM

Instructions Pipeline

MEMALU

1R1

ALU2

R2

ALUn

Rn

MEM

Arithmetic Pipeline

Soffermiamoci sull’ultima figura, in cui abbiamo schematizzato il pipelining a livello di operazioni in virgola mobile (ossia quindi il pipelining dello stadio EX, con riferimento alla terminologia usata nel capitolo 6): con R1, R1,…,Rn-1 abbiamo indicato i risultati parziali delle operazioni in virgola mobile, mentre ovviamente Rn è il risultato finale.

Nel caso di pipeline vettoriale, quando il primo scalare esce da R1, entra lo scalare successivo, in modo che, in condizioni di regime si abbia uno nuovo scalare per ogni ciclo di clock.

Segnaliamo infine che il concetto di pipelining, almeno in generale, è applicabile a qualsiasi livello: intero sistema, singolo processo, singola istruzione, singola operazione, singolo stadio di esecuzione di una operazione (livello più basso). A prescindere dal livello cui venga applicato, il pipelining è tale per cui, all’aumentare del numero di stadi della pipeline, aumentino anche le probabilità di conflitti: abbiamo ad esempio visto, nel capitolo 6, che quanto maggiore è il numero di stadi della pipeline di esecuzione delle istruzioni nel DLX, tanto maggiore è la probabilità di avere conflitti di dati.



PPPaaarrraaalllllleeellliiisssmmmiii In un calcolatore, il parallelismo si può ottenere in vari modi:

• parallelismo temporale→pipeline (vector processor): abbiamo una rete di unità di esecuzione, con una sola unità di controllo;

• parallelismo spaziale sincrono→ array processor: abbiamo tanti processori (omogenei tra loro) che scambiano dati in modo sincrono, nonostante eseguano istruzioni diverse; i processori sono disposti secondo una matrice, in modo che ciascuno possa comunicare con quelli che ha attorno (che generalmente sono 4 se la matrice è quadrata, ma possono anche essere di più o di meno). Proprio per questa particolare disposizione si parla di parallelismo “spaziale”;

• parallelismo spaziale asincrono→multiprocessori: abbiamo una rete di processori autonomi ed eterogenei; essi si scambiano informazioni secondo protocolli del tipo domanda→risposta. Rispetto al caso precedente, la disposizione può anche essere la stessa, ma in generale manca la sincronizzazione tra i processori. Ci sono del resto casi in cui i processori sono comunque sincronizzati, come avviene ad esempio nelle macchine SIMD.

Possiamo inoltre fare la seguente classificazione:

• elaborazione concorrente (concurrent processing): si ha quando un sistema di calcolo esegue il suo carico elaborativo costituito da più processi indipendenti (ed eventualmente eterogenei tra di loro), eseguibili in tempi successivi ed eventualmente sotto il controllo di un’unica unità di controllo. In questo caso, dunque, i vari task (o compiti o processi) “concorrono” per la produzione del risultato finale nonché per l’uso dell’unica unità di controllo;

• elaborazione distribuita: si ha quando un sistema di calcolo esegue il suo carico elaborativo costituito da un insieme di processi (concorrenti nell’esecuzione del codice) eseguibili contemporaneamente su diverse unità di elaborazione (PU, Processing Unit); esiste ovviamente una unità di elaborazione che potremmo definire master e che ha il compito di ripartire il carico di lavoro tra i vari nodi del sistema;

• elaborazione parallela: si ha quando il carico elaborativo del sistema di calcolo è costituito da più “parti” (dette unità atomiche (10) o moduli) eseguibili nello stesso tempo su differenti unità di calcolo (fondamentalmente delle ALU), che sono in grado di scambiarsi dati d’utente e dati di controllo. Questo tipo di elaborazione presuppone dunque che una applicazione venga decomposta in più moduli, omogenei tra loro, che interagiscano tra loro mediante opportuni meccanismi di comunicazione e sincronizzazione e che possano essere eseguiti in concorrenza come processi paralleli: si parla in questo caso di programmazione concorrente (più processi su più processori) da non confondere con la multiprogrammazione (più processi contemporanei su un solo processore).

10 Cioè non ulteriormente divisibili



I processori con pipeline (MISD) e gli array processor (SIMD) effettuano l’elaborazione parallela, mentre invece i multiprocessori (MIMD) eseguono l’elaborazione concorrente (11).

Per poter effettuare il calcolo parallelo, è necessario che l’insieme dei processi locali che operano concorrentemente possano scambiarsi tra loro dei dati medianti appositi canali di comunicazione logici; questi ultimi non devono necessariamente essere fisici. Lo scopo del calcolo parallelo è quello di migliorare le prestazioni semplicemente ripartendo le attività su un numero crescente di nodi della rete (definizione di scalabilità). Occorre dunque avere una architettura che consenta lo svolgimento in parallelo del maggior numero di operazioni, allo scopo di ridurre il tempo totale di elaborazione.

Il parallelismo può essere di quattro tipi:

1. parallelismo a livello di fasi di esecuzione di singole istruzioni (pipeline);

2. parallelismo a livello di accessi gerarchici alla memoria (shared memory);

3. parallelismo nell’esecuzione di una singola istruzione su strutture dati (processori vettoriali);

4. istruzioni multiple interagenti (ci sono cioè più istruzioni eseguite contemporaneamente ed in grado anche di interagire tra loro).

Le prime due tipologie di parallelismo non alterano la struttura dei programmi,

mentre invece le altre due richiedono espressamente che vengano isolate le operazioni da eseguire in parallelo.

Valutazione delle prestazioniValutazione delle prestazioni Possiamo subito distinguere due casi:

• componenti di calcolo: in questo caso, dobbiamo valutare le prestazioni di picco di uno specifico componente, fornendo le sue caratteristiche di targa (12), ossia caratteristiche che non siano degradate dall’uso di periferiche o di memorie o di altro;

• sistema di calcolo: in questo caso, dobbiamo valutare la risposta di un software complesso (inteso come composizione di software applicativo e software di configurazione) eseguito su un determinato hardware.

Fondamentalmente, l’analisi ed il progetto di un sistema di calcolo dotato di più

processori presuppongono che si valuti l’aumento della capacità di calcolo ottenibile aumentando il numero di processori e lasciando invariata la tecnologia adottata. I parametri di prestazione cui prestare attenzione sono i seguenti:

11 In quest’ultima affermazione si tenga conto che ciascun processore di una macchina MIMD può anche eseguire più processi: di conseguenza, l’eventuale elaborazione concorrente avviene quando, sul sistema MIMD nel suo complesso, ci sono più processori che lavorano per arrivare ad un risultato unico, anche se ciò non esclude che gli stessi processori si stiano dedicando anche ad altro. Del resto, se non fosse così, se cioè o gni processore si potesse dedicare solo ad un processo, una macchina MIMD con N processori potrebbe eseguire solo N processi. 12 Le attuali architetture di microprocessori tendono a fornire elevate prestazioni su piccoli programmi “benchmark”, facendo uso di registri, memorie cache, ecc.



• tempi di elaborazione, sia assoluti sia relativi (cioè confrontati rispetto al clock oppure rispetto ad altre macchine);

• efficienza computazionale (riferita cioè all’impiego delle risorse di calcolo);

• accelerazione, ossia guadagno di velocità rispetto al sistema monoprocessore (con uguale tecnologia): per esempio, se la scalabilità è massima, l’uso di N processori dovrebbe idealmente garantire una accelerazione pari proprio ad N;

• quantità di memoria locale necessaria (ad esempio, deve essere sufficiente per non dover spezzare in più parti un unico codice sequenziale);

• rapporto costo/prestazioni. Gli obbiettivi cui bisogna mirare sono i seguenti:

• massimo parallelismo del codice eseguibile;

• massimo bilanciamento, tra le varie unità di elaborazione, del carico computazionale;

• minima attività di comunicazione tra i vari nodi (unità di elaborazione) del sistema di calcolo;

• ottimizzazione della quantità di memoria a disposizione del singolo nodo;

• ottimizzazione della potenza di calcolo di ciascun nodo.

Strutture di interconnessioneStrutture di interconnessione Si è detto più volte che, in un sistema dotato di più unità di elaborazione

(sistema parallelo), devono essere presenti delle adeguate strutture di interconnessione per lo scambio di informazioni. Si è verificato che proprio tali strutture sono spesso i veri colli di bottiglia per un sistema parallelo (13), in quanto introducono delle forti limitazioni sul numero di processori collegabili e possono essere oggetto di contesa da parte di più processori.

Un concetto fondamentale, per le strutture di interconnessione, è la cosiddetta banda passante: è la portata (espressa in bit per secondo, bps) della rete di interconnessione tra i vari processori nonché tra i processori ed il mondo esterno.

Banda passante di un sistema di calcoloBanda passante di un sistema di calcolo Consideriamo il caso semplice di un sistema monoprocessore con h processi da

eseguire: indicando con b la banda passante del processore, la banda passante del sistema (cioè il numero di eventi o processi da eseguire) risulta pari a

( ) K)h(rT1b)1(Bh −−⋅=

In questa espressione, rT(h) è la frazione di carico computazionale spesa per

l’attività di routing, ossia per l’instradamento dei dati nel rispetto della topologia

13 Qualcosa di analogo avviene per il bus nei sistemi a singolo processore del tipo Von Neumann



adottata nel sistema. La costante K, invece, è una costante correttiva e tiene conto di altri eventi paralleli accessori: ad esempio, tiene conto delle routine eseguite dal sistema operativo.

Per estendere quella formula al caso di N processori, ci basta sostituire il termine additivo 1 proprio con N ed eliminare K:

( ))h(rTNb)N(Bh −⋅=

Questa quantità raggiunge evidentemente il suo limite superiore (=b×N) quando

non c’è carico dovuto al routing, per cui rT(h) diventa pari ad 0.

Legge di Amdahl applicata ad una macchina con N Legge di Amdahl applicata ad una macchina con N processoriprocessori

Quando abbiamo studiato la legge di Amdahl, ne abbiamo dato la seguente rappresentazione analitica:

( )migliorata

miglioratamigliorata oneAccelerazi

FrazioneFrazione-1

1oneAccelerazi

+=

Essa afferma sostanzialmente che l’accelerazione ottenibile introducendo una

qualche miglioria su una macchina è legata strettamente alla frazione di computazione che risente positivamente delle migliorie, frazione che deve essere quanto più grande possibile.

Se partiamo da una classica macchina sequenziale monoprocessore (SISD), una possibile miglioria consiste nell’aggiungere un certo numero di processori (passando dunque ad una macchina parallela) in grado di operare in parallelo. Il nostro obbiettivo è dunque quello di verificare se e quale accelerazione è ottenibile con l’introduzione di tali processori.

Cominciamo ad elencare i termini che utilizzeremo:

• indichiamo con h il grado di parallelismo del carico elaborativo che intendiamo eseguire, ossia il numero di processi che possono essere eseguiti in parallelo;

• indichiamo con Th(1) il tempo che sarebbe richiesto da un sistema monoprocessore per completare il carico computazionale dovuto agli h processi e con Th(N) il tempo che sarebbe invece richiesto, per lo stesso carico computazionale, da un generico sistema ad N processori;

• infine, indichiamo con f la porzione non parallelizzabile del codice, ossia quella che deve essere necessariamente eseguita in modo sequenziale (tramite quindi un unico processore).

Si può vedere facilmente che la quantità Th(N) è calcolabile nel modo seguente:

( )N

)1(Tf1)1(Tf)N(T h

hh ⋅−+⋅=



Il senso della formula è abbastanza evidente: il tempo totale richiesto dal sistema multiprocessore è la somma del tempo richiesto dal sistema monoprocessore, pesato per la frazione di codice non parallelizzabile, e di un contributo che sfrutta i vantaggi all’elaborazione parallela; quest’ultimo contributo, pesato per la frazione di codice parallelizzabile, è infatti dato dal tempo richiesto dal monoprocessore diviso per il numero di processori disponibili.

Il caso ideale sarebbe ovviamente quello in cui f=0, in quanto avremmo

banalmente N

)1(T)N(T h

h = , ossia una riduzione del tempo di elaborazione di un

fattore pari al numero di processori a disposizione. Al contrario, per f≠0, si ha una penalizzazione dovuta alla frazione di codice che non è parallelizzabile e quindi non può usufruire della presenza dei vari processori, ma ne utilizzerà uno solo.

A questo punto, diventa immediato calcolare l’accelerazione ottenuta col sistema ad N processori, confrontando i tempi totali tra il suddetto sistema e quello a singolo processore:

( ) ( ) ( )1Nf1

N

f1Nf

N

N

1f1f

1

)N(T

)1(ToneAccelerazi

h

h

−⋅+=

−+⋅=

⋅−+==

Da notare che abbiamo qui calcolato il rapporto tra Th(1) e Th(N) e non viceversa,

per il semplice motivo che Th(1) è il tempo più lungo, per cui la frazione così calcolata risulta maggiore di 1 e quindi effettivamente indicativa di una accelerazione.

E’ importante chiarire che l’accelerazione così calcolata è relativa ad N processori e h processi, per cui spesso si trova quella formula scritta nel modo seguente:

( )1Nf1

N

)N(T

)1(T)N(S

h

hh −⋅+

==

dove S sta per “speed up”, ossia appunto “accelerazione”.

Facciamo un rapido esempio numerico: supponiamo che i processori a disposizione siano 1000 e che anche i processi da eseguire siano 1000; supponendo che la frazione di codice non parallelizzabile sia pari all’ 1% (quindi f=0.01), otteniamo una accelerazione pari a

( ) 911100001.01

1000)1000(S1000 =

−⋅+=

Risulta evidente, da questo calcolo, che l’incremento di prestazione ottenuto

(quantificato appunto dall’accelerazione) è decisamente non proporzionato al numero di processori: in particolare, una accelerazione pari a 91, rapportata a 1000 processori, dice sostanzialmente che il sistema viene impegnato per meno del 10% delle sue prestazioni di picco e questo a causa di una piccola porzione sequenziale (1%). Solo nel caso ideale in cui fosse f=0, otterremo una accelerazione perfettamente commisurata all’incremento del numero di processori (14).

14 Ci sono alcune ragioni per cui non potrà mai essere f=0: ad esempio, l’inizializzazione dei parametri è un tipico processo non parallelizzabile, come anche la raccolta dei risultato. Tanto per fare un esempio, consideriamo l’elaborazione di una immagine: essa dovrà essere acquisita da un solo processori e solo dopo potrà essere elaborata da più processori (ad



Un modo abbastanza intuitivo per sintetizzare quest’ultimo concetto consiste nel calcolare l’accelerazione per N che tende ad infinito (cioè l’accelerazione asintotica):

( ) f

1

N

11f

N

11

lim1Nf1

Nlim)N(Slim

NNhN=

−⋅+

=−⋅+

=∞→∞→∞→

Questo risultato dice che, a prescindere da quanti processori utilizziamo

(purché ovviamente in numero elevato), l’accelerazione ottenibile è comunque superiormente limitata da 1/f; al crescere di f, il limite scende in maniera inversamente proporzionale. Ad esempio, se abbiamo un programma costituito per il 10% da calcoli puramente sequenziali, non potremo mai ottenere una accelerazione superiore a 1/0.1=10, anche se usassimo infiniti processori.

Questa forte limitazione di prestazioni è dovuta essenzialmente al fatto che, nonostante la presenza di molti processori, alcuni di essi non vengono comunque usati per tutto il tempo di esecuzione, data la presenza del codice non parallelizzabile: l’accelerazione è tanto minore quanto maggiore è il numero di processori effettivamente impegnati. Una misura quantitativa di quest’ultimo concetto si ottiene facendo il rapporto tra l’accelerazione ed il numero N di processori, in modo da ottenere l’efficienza di utilizzo dei processori stessi:

( )1Nf1

1

N

)N(Sh

−⋅+==η

Bisogna a questo punto precisare una cosa: questo modo di studiare una

macchina dotata di più processori potrebbe risultare troppo pessimistico nel caso di alcuni tipi di architetture; in particolare, esso risulta applicabile solo per macchine di tipo MIMD (in cui ci sia parallelismo asincrono dei dati, cioè più processi operanti in modo indipendente su più dati), mentre per altre architetture (ad esempio le SIMD) bisogna fare altre considerazioni, cui sono destinati i prossimi paragrafi.

Legge di Braunl per architetture SIMDLegge di Braunl per architetture SIMD In questo paragrafo ci concentriamo specificamente su una macchina SIMD (cioè

con flusso singolo di istruzioni e flussi multipli di dati): a tal proposito, ricordiamo che una simile macchina può essere pensata come costituita da una sola unità di controllo che acceda ad una sola memoria istruzioni ed invii, ciclo per ciclo, la stessa istruzione da eseguire a un insieme di unità di esecuzione.

Un programma SIMD contiene comandi sia scalari sia vettoriali e la sua esecuzione è simile a quella di un programma eseguito in modo sequenziale sulla macchina di Von Neumann: infatti, un singolo comando vettoriale di un sistema SIMD con N processori può essere implementato su un sistema monoprocessore tramite N comandi eseguiti in sequenza.

La terminologia che useremo in questo paragrafo è solo leggermente diversa rispetto al paragrafo precedente:

esempio suddividendola in tante righe quanti sono i processori); al termine dell’elaborazione, essa dovrà essere ricostruita nuovamente da un solo processore.



• indichiamo con N il numero di componenti di un singolo comando vettoriale SIMD;

• indichiamo con TN(1) il tempo necessario per elaborare un comando vettoriale ad N componenti tramite un unico processore (15); indichiamo invece con TN(N) il tempo richiesto per eseguire lo stesso comando tramite N processori (16);

• infine, indichiamo con f la porzione non parallelizzabile del codice, ossia quella che deve essere necessariamente eseguita in modo sequenziale.

Possiamo subito calcolare la quantità TN(1): se il codice fosse interamente

parallelizzabile (f=0), il tempo di esecuzione richiesto al sistema monoprocessore sarebbe banalmente pari ad N volte il tempo richiesto dal sistema con N processori; al contrario, in presenza di una frazione f non nulla di codice non parallelizzabile, bisogna tener conto della relativa penalizzazione, per cui risulta

( ) )N(TNf1)N(Tf)1(T NNN ⋅⋅−+⋅=

Abbiamo qui calcolato quanto tempo è necessario per elaborare un comando

vettoriale ad N componenti su un unico processore sapendo quanto tempo impiegano N processori e sapendo che esiste una frazione f≠0 di codice non parallelizzabile. Questa è la legge di Braunl.

Usandola per calcolare l’accelerazione del sistema SIMD rispetto ad un classico sistema monoprocessore, otteniamo evidentemente che

( ) Nf1f)N(T

)1(T)N(S

N

NN ⋅−+==

Se facciamo lo stesso esempio numerico fatto nel paragrafo precedente (cioè

N=1000 e f=0.01), otteniamo una accelerazione pari a 990, quindi molto prossima ad N (al contrario di quanto ci veniva indicato dalla legge di Amdahl, che forniva una accelerazione pari appena a 91) .

In generale, la formula ottenuta, confrontata con la legge di Amdahl applicata a macchine MIMD (e solo a quelle), ci dice che, mentre con le macchine MIMD l’accelerazione ottenuta è tanto maggiore quanto minore è f (cioè diminuisce linearmente con 1/f), con le macchine SIMD essa diminuisce al diminuire di f (in particolare, l’accelerazione diminuisce quasi linearmente con f).

In questi discorsi bisogna tener conto che la frazione di codice non parallelizzabile è data da

N

ff SIMD=

A parità di fSIMD, maggiore è il numero dei processori impegnati in un comando

SIMD e minore diventa la frazione f.

15 Come si è detto prima, questo equivale ad eseguire N comandi in sequenza equivalenti all’unico comando vettoriale in questione. 16 Un sistema che mette a disposizione tanti processori quanti sono i processi da eseguire prende il nome di paracomputer.



Tempo di comunicazione interTempo di comunicazione inter--processorprocessor Nei due precedenti paragrafi, abbiamo calcolato l’accelerazione di sistemi

multiprocessore (MIMD e SIMD) adottando una ipotesi di fondo: abbiamo trascurato il tempo che nel sistema viene “perso” per la comunicazione tra i vari processori costituenti il sistema. Al contrario, per valutare in modo compiuto le prestazioni di una macchina dotata di più processori, dobbiamo necessariamente includere tale tempo, che indichiamo con C (detto appunto tempo di comunicazione inter-processor).

Supponiamo allora che il codice da eseguire sia completamente parallelizzabile, per cui supponiamo f=0. In questo caso, seguendo i discorsi dei paragrafi precedenti, il tempo di elaborazione del sistema ad N processori risulterebbe idealmente pari al rapporto tra il tempo di elaborazione del sistema monoprocessore ed N stesso:

N

)1(T)N(T h

h =

In realtà, dobbiamo includere il tempo di comunicazione inter-processor, per cui

scriviamo più correttamente che

CN

)1(T)N(T h

h +=

Calcolando l’accelerazione (mantenendo l’ipotesi di f=0), otteniamo

N)1(T

C1

N

NC)1(T

)1(NT

CN

)1(T)1(T

)N(T

)1(T)N(S

h

h

h

h

h

h

hh

+=

+=

+==

La quantità )1(T

C

h

è chiaramente il tempo di comunicazione inter-processor

espresso in rapporto al tempo di elaborazione del single-processor: la si indica normalmente con c, per cui scriviamo che

Nc1

N)N(Sh ⋅+

=

Rispetto al valore ideale di accelerazione (=N) calcolato per f=0, abbiamo dunque

una penalizzazione di un fattore (1+c⋅N), che sarebbe evidentemente nulla se fosse c=0.

Legge di Amdahl modificataLegge di Amdahl modificata I discorsi dei paragrafi precedenti portano alla introduzione della cosiddetta

legge di Amdahl modificata. Useremo la seguente terminologia:

• εε è la possibilità che un dato programma non possa essere ripartito su N processori (coincide dunque con la frazione non parallelizzabile del codice, che in precedenza abbiamo indicato con f);



• δδ è il cosiddetto sbilanciamento relativo del carico tra gli N processori impiegati, di cui parleremo tra un attimo;

• infine, δ/N è il tempo eccedente il tempo di elaborazione ottimale (pari ad 1/N), dovuto appunto allo sbilanciamento.

Per quanto riguarda lo sbilanciamento del carico, esso è definito come la

differenza tra il tempo massimo ed il tempo minimo di elaborazione dei vari processori. Nel caso tale differenza venga normalizzata al tempo massimo, si parla di sbilanciamento relativo (simbolo δδ):

sbilanciamento = Tmax – Tmin

sbilanciamento relativo = max

minmax

T

TT −=δ

E’ evidente che lo sbilanciamento tiene conto delle perdita percentuale che si

subisce quando un processore termina prima di un altro il proprio carico di lavoro, divenendo così inattivo e quindi inefficiente. Il massimo valore dello sbilanciamento (δ=1, causato da Tmax>>Tmin) si ottiene evidentemente se uno qualsiasi dei processori rimane completamente inattivo.

Nel caso in cui ε→0 e non tenendo conto del tempo di comunicazione tra i vari processori, la legge di Amdahl modificata dice semplicemente che

δ+=

1

N)N(Sh

Questa espressione dice che l’accelerazione ottenuta con gli N processori,

supponendo il codice completamente parallelizzabile, è comunque penalizzata, rispetto al valore ideale N, dallo sbilanciamento: se lo sbilanciamento raggiungesse il suo massimo valore (δ=1), l’accelerazione risulterebbe addirittura dimezzata (=N/2), mentre invece, in assenza di sbilanciamento (δ=0), si raggiungerebbe il valore reale.

Nel caso più realistico in cui il codice presentasse una frazione non parallelizzabile non nulla (ε≠0), allora la legge di Amdahl modificata dice quanto segue:

NlogNc)1)(1(

N)N(S

2h ⋅ε+⋅+δ+ε−

=

In questa espressione (ottenuta mettendo insieme i vari contributi al tempo Th(N)

visti nei precedenti paragrafi), il termine c⋅N tiene conto della penalizzazione dovuta alla comunicazione tra i vari processori, mentre invece il termine ε⋅log2N è un termine correttivo sul quale non approfondiamo.

Autore: Sandro Petrizzelli e-mail: [email protected]

sito personale: http://users.iol.it/sandry

A p p u n ti d i C alcolatori E lettron ici -...

Documents

Transcript of A p p u n ti d i C alcolatori E lettron ici -...