Classificazione delle Architetture Parallele Architetture parallele

Università degli Studi di Roma “Tor Vergata”
Facoltà di Ingegneria
Classificazione delle
Architetture Parallele
Corso di Sistemi Distribuiti
Valeria Cardellini
Anno accademico 2009/10
Architetture parallele
•
Definizione (Almasi e Gottlieb, 1989): un’architettura
parallela è un insieme di elementi di elaborazione che
cooperano e comunicano per risolvere velocemente
problemi di dimensioni considerevoli, talvolta
intrattabili su macchine sequenziali
• Obiettivi:
1. Migliorare le prestazioni
–
E’ possibile utilizzare un’architettura parallela per risolvere
•
•
Un problema più grande nello stesso tempo (scale-up)
Lo stesso problema in minor tempo (speed-up)
2. Migliorare il rapporto costo/prestazioni
SD - Valeria Cardellini, A.A. 2009/10
1
Il parallelismo è ovunque!
SD - Valeria Cardellini, A.A. 2009/10
2
Architetture parallele (2)
• Opzioni di progettazione di un’architettura
parallela:
– Quanti processori?
– Quale è la capacità di elaborazione di ciascun
processore?
– Quale tecnologia utilizzano i processori?
– Quale organizzazione per l’elaborazione?
– Come è organizzata la memoria?
– In che modo sono interconnessi i processori?
– Come vengono scambiate le informazioni?
SD - Valeria Cardellini, A.A. 2009/10
3
Le sfide della programmazione parallela
• La programmazione parallela fino ad ora si è
sviluppato soprattutto in ambito accademico ed in
centri di ricerca: perché?
• Primo problema: parallelismo limitato nei programmi
• Secondo problema: elevata latenza degli accessi
remoti
• La vera difficoltà non è realizzare architetture parallele,
ma sviluppare applicazioni parallele!
– Le architetture parallele raggiungono buone prestazioni solo
se programmate in modo opportuno
– Servono algoritmi opportuni
– Gli ambienti di programmazione non sono molto sviluppati
• La programmazione parallela è più complessa
• Il debugging di programmi paralleli è complesso
• I compilatori autoparallelizzanti sono solo sperimentali
SD - Valeria Cardellini, A.A. 2009/10
4
Classificazione di Flynn
• E’ la classificazione tradizionale delle architetture
parallele
• Ad opera di Flynn (1966)
– Proposta quando non c’erano ancora vere architetture parallele
– Sebbene siano passati più di 40 anni, risulta ancora utile!
•
•
•
•
Single instruction stream, single data stream (SISD)
Single instruction stream, multiple data stream (SIMD)
Multiple instruction stream, single data stream (MISD)
Multiple instruction stream, multiple data stream (MIMD)
Dati singoli Dati multipli
Istruzioni singole
SISD
SIMD
Istruzioni multiple
MISD
MIMD
SD - Valeria Cardellini, A.A. 2009/10
5
SISD e SIMD
• Single instruction stream, single data stream (SISD)
– Flusso di istruzioni singolo, flusso di dati singolo
– Il sistema monoprocessore (architettura di Von Neumann)
• Single instruction stream, multiple data stream
(SIMD)
– Flusso di istruzioni singolo, flusso di dati multiplo
– Più processori eseguono la stessa istruzione su flussi di dati
diversi: si sfrutta il parallelismo a livello di dati
– Ogni processore ha la propria memoria dati; ci sono una
sola memoria istruzioni ed un solo processore di controllo
– I processori multimediali presentano una forma (limitata) di
parallelismo SIMD; le architetture vettoriali sono la classe più
ampia
– Negli ultimi anni: rinascita degli approcci SIMD grazie alla
crescente importanza delle prestazioni grafiche
SD - Valeria Cardellini, A.A. 2009/10
6
SISD e SIMD (2)
SISD
IS
Control Unit
IS
PE
DS
Memory
SIMD
Legenda:
IS: Instruction Stream
DS: Data Stream
PE: Processing Element
SD - Valeria Cardellini, A.A. 2009/10
7
MISD e MIMD
• Multiple instruction stream, single data stream (MISD)
– Flusso di istruzioni multiplo, flusso di dati singolo
– Non è stata ancora costruita un’architettura commerciale di
questo tipo
• Multiple instruction stream, multiple data stream (MIMD)
– Flusso di istruzioni multiplo, flusso di dati multiplo
– Ogni processore legge le proprie istruzioni ed opera sui propri
dati: parallelismo a livello di thread
– Il parallelismo a livello di thread è più flessibile del parallelismo
a livello di dati → ha un’applicabilità più diffusa
– I processori sono spesso commerciali standard (commodity)
SD - Valeria Cardellini, A.A. 2009/10
8
MIMD
• Il modello MIMD è emerso come l’architettura prescelta
di tipo generale perché:
– è flessibile
– si possono costruire architetture MIMD usando processori
commerciali
SD - Valeria Cardellini, A.A. 2009/10
9
Classificazione estesa
• Analizziamo un’estensione della classificazione di Flynn
per considerare diversi tipi di architetture MIMD
Classificazione
di Flynn
Anche
dette SMP
SD - Valeria Cardellini, A.A. 2009/10
10
Architetture MIMD
Shared memory
I/O1
Interconnection
network
Interconnection
network
I/On
PE1
PEn
Processors
PE1
PEn
M1
Mn
P1
Pn
Multiprocessori (memoria condivisa) Multicomputer (message passing)
SD - Valeria Cardellini, A.A. 2009/10
11
MIMD: multiprocessori
• Multiprocessori: architetture MIMD a memoria
condivisa (shared memory)
– La memoria ha un unico spazio di indirizzamento, condiviso tra
tutti i processori
– I processori comunicano tramite variabili condivise e ciascun
processore è in grado di accedere ad ogni locazione di memoria
tramite istruzioni load e store
– Occorre un meccanismo di sincronizzazione, per coordinare il
comportamento di processi che possono essere in esecuzione
su processori differenti
– I multiprocessori possono avere memoria condivisa e
centralizzata, ma possono anche avere memoria condivisa e
distribuita
• Memoria condivisa e distribuita: la memoria è fisicamente
distribuita ma è logicamente condivisa
SD - Valeria Cardellini, A.A. 2009/10
12
MIMD: multicomputer
• Multicomputer: architetture MIMD a scambio di
messaggi
– Non hanno una memoria condivisa a livello di architettura, ma le
memorie sono riservate per i singoli processori
• Lo spazio di indirizzamento è costituito da più spazi privati,
logicamente disgiunti e non indirizzabili da parte dei processori
remoti
– La comunicazione tra i processori avviene mediante scambio di
messaggi (message passing) esplicito
• Procedure per inviare e ricevere messaggi (send e receive)
SD - Valeria Cardellini, A.A. 2009/10
13
Classificazione estesa (2)
• Aggiungiamo un ulteriore livello nella classificazione
Classificazione
di Flynn
Anche dette
SMP
SD - Valeria Cardellini, A.A. 2009/10
14
Classificazione dei multiprocessori
• Classificazione basata sul modo in cui i
multiprocessori implementano la memoria
condivisa:
– UMA (Uniform Memory Access)
– NUMA (Non Uniform Memory Access)
– COMA (Cache Only Memory Access)
SD - Valeria Cardellini, A.A. 2009/10
15
Classificazione dei multiprocessori: UMA
• Multiprocessori con memoria ad accesso uniforme
• Anche detti SMP (Symmetric MultiProcessor):
multiprocessori simmetrici
• Ogni processore ha lo stesso tempo di accesso alla
memoria principale, indipendentemente dal processore
richiedente e dalla locazione della parola di memoria
richiesta
• Prestazioni eccellenti ma sono limitate per dimensioni
(numero di processori)
• Esempi: multi-core basati su ISA x86 (ad es. Intel Xeon,
AMD Opteron), IBM Power Express (con processore
IBM Power 6), NEC SX-8, …
SD - Valeria Cardellini, A.A. 2009/10
16
Classificazione dei multiprocessori: NUMA
• Multiprocessori con memoria ad accesso non uniforme
• Alcuni accessi in memoria sono più veloci di altri a
seconda del processore richiedente e dalla locazione
della parola di memoria richiesta; un processore può
accedere:
– rapidamente alla propria memoria locale
– più lentamente alle memorie degli altri processori o alla
memoria condivisa
– il caching permette di nascondere in una certa misura la
differenza nel tempo di accesso
• Raggiungono dimensioni maggiori dei multiprocessori
UMA
• Esempi: SIG Altix 330, Sun Fire X4600, Cray X1
(prodotto fino al 2003)
SD - Valeria Cardellini, A.A. 2009/10
17
Classificazione dei multiprocessori: COMA
• Architetture COMA (Cache Only Memory Access)
– Come NUMA anche questi multiprocessori non sono uniformi
nell’accesso alla memoria
• La memoria principale viene usata come se fosse una
cache
– Ogni pagina non ha un processore prefissato di appartenenza
– La memoria è detta di attrazione (attraction memory), in quanto
si limita ad attrarre le linee di cache quando sono richieste
• In contrapposizione a home memory nei multiprocessori NUMA
• Due nuovi problemi:
– Come localizzare le linee di cache
– Come evitare di cancellare dalla memoria l’ultima copia di una
linea di cache
SD - Valeria Cardellini, A.A. 2009/10
18
Classificazione dei multicomputer
• Architetture MPP (Massively Parallel Processor)
– Molti processori autonomi, interconnessi con reti proprietarie
a larga velocità
• Cluster
– Nodi totalmente separati, interconnessi con reti veloci e
tecnologia commerciale (tipicamente tecnologia off-the-shelf)
– Approccio molto efficiente in termini di costo
– In passato, anche indicati con i termini:
• NOW (Network of Workstations)
• COW (Cluster of Workstations)
SD - Valeria Cardellini, A.A. 2009/10
19
Classificazione estesa (3)
• Aggiungiamo un ulteriore livello nella classificazione dei
multiprocessori e dei multicomputer
Classificazione
di Flynn
Anche dette
SMP
SD - Valeria Cardellini, A.A. 2009/10
20
Classificazione dei multiprocessori (2)
• Abbiamo già visto il primo livello di
classificazione dei multiprocessori
– Multiprocessori UMA (o SMP)
– Multiprocessori NUMA
– Multiprocessori COMA
• La categoria dei multiprocessori NUMA
comprende:
– CC-NUMA: Cache Coherent NUMA
– NC-NUMA: Non Cache Coherent NUMA
SD - Valeria Cardellini, A.A. 2009/10
21
Diffusione delle varie architetture nei top 500
• Lista dei 500 top supercomputer:
– http://www.top500.org/
– Prestazioni misurate tramite il benchmark Linpack
(soluzione di un sistema denso di equazioni lineari Ax=b)
– Classifica aggiornata ogni 6 mesi
In un decennio:
• scomparsa di
uniprocessori, SMP e
SIMD dalla lista dei top 500
• crescita dei cluster
SD - Valeria Cardellini, A.A. 2009/10
22