Introduzione “CALCOLO AD ALTE PRESTAZIONI”

“CALCOLO AD ALTE PRESTAZIONI”
Introduzione
Salvatore Orlando
CALCOLO ALTE PRESTAZIONI- S. Orlando
1
Notizie generali sul corso
• 
Sito Web:
–  http://www.dsi.unive.it/~calpar/
–  Iscriversi alla lista di discussione
• 
Esame suddiviso in due parti:
–  Lettura di articoli scientifici o capitoli di libro, con piccolo orale sugli
argomenti del corso
–  Progetto di Laboratorio
Il voto per i due esami di Calcolo Parallelo e Laboratorio come media dei due voti
• 
• 
Materiale didattico
–  Slides
–  A. Grama, A. Gupta, G. Karypis, V. Kumar. Introduction to Parallel
Computing, 2° Ed., Addison-Wesley, 2003.
–  B. Wilkinson, M. Allen. Parallel Programming: Techniques and Applications
Using Networked Workstation and Parallel Computers. 2° Ed., Prentice-Hall,
2003.
–  The Sourcebook of Parallel Computing. J. Dongarra, I. Foster, G. Fox, et al.
Morgan Kaufmann, 2002.
–  I. Foster. Designing and Building Parallel Programs. Addison-Wesley, 1995,
Versione online disponibile presso http://www-unix.mcs.anl.gov/dbpp.
CALCOLO ALTE PRESTAZIONI- S. Orlando
2
Calcolo parallelo
•  Calcolo sequenziale:
–  risolve un problema tramite un algoritmo le cui istruzioni sono
eseguite in sequenza
–  modello computazionale caratterizzato da un singolo
processore
•  Calcolo parallelo:
–  risolve un problema tramite un algoritmo le cui istruzioni sono
eseguite in parallelo
–  modello computazionale che prevede processori multipli e
relativi meccanismi di cooperazione
–  l’algoritmo deve sfruttare in maniera efficiente il parallelismo
esplicitabile nel problema, per rendere più veloce l’esecuzione
CALCOLO ALTE PRESTAZIONI- S. Orlando
3
Processo di parallelizzazione ottimale
•  Metodologia generale:
–  dividere il problema tra processori (decomposizione)
–  i vari processori lavorano sui propri pezzi del problema, e
comunicano per cooperare
–  con l’obiettivo di bilanciare il carico e ridurre le comunicazioni/
sincronizzazioni allo stretto necessario
CALCOLO ALTE PRESTAZIONI- S. Orlando
4
Trend nello sviluppo di hw/sw ad alte prestazione
•  Ultime decadi: migliorano le prestazioni dei microprocessori
–  Legge di Moore (2x transistor/chip ogni anno e mezzo)
–  Parallelismo/Pipeline nell’esecuzione delle istruzioni
• 
• 
• 
• 
• 
ILP (Instruction Level Parallelism)
Parallelismo implicito a grana finissima
CPI medio ridotto di un ordine di grandezza (in una decade)
Ciclo di clock ridottissimo (frequenza nell’ordine dei GHz)
Incremento FLOPS di picco
•  Ultimi anni
–  Il bottleneck del collegamento con la memoria, la cui tecnologia non è migliorata
dal punto di vista delle latenze, diventa più evidente
•  si pone rimedio con la memoria cache, ma anche questo ha un limite
tecnologico e di costo
–  Limiti oggettivi nell’estrarre ulteriore parallelismo ILP da un singolo programma
sequenziale
CALCOLO ALTE PRESTAZIONI- S. Orlando
5
Trend nello sviluppo di hw/sw ad alte prestazione
•  Ultimi anni
–  La curva delle prestazioni segna il passo per i processori più recenti
•  curva misurata rispetto al benchmark SPEC, ovvero insiemi standard e
rappresentativi di programmi sequenziali
CALCOLO ALTE PRESTAZIONI- S. Orlando
6
Trend nello sviluppo di hw/sw ad alte prestazione
•  Esistono quindi limiti nell’approccio basato su hw/sw
sequenziale, anche se con parallelismo implicito a grana
fine di tipo ILP
–  i trend non fanno prevedere ulteriori incrementi di velocità
•  HW
–  I costruttori di CPU corrono ai ripari, sfruttando l’area dei chip e
i grande numero di transistor per produrre CPU con processori
multipli
•  Si prevede che il numero di processori (“core”) per chip dovrebbe
raddoppiare ogni 2 anni
•  SW
–  Parallelismo, anche esplicito, ovvero specificato direttamente
dal programmatore tramite opportuni linguaggi, librerie,
ambienti di programmazione parallela
CALCOLO ALTE PRESTAZIONI- S. Orlando
7
Trend nello sviluppo di hw/sw ad alte prestazione
• 
I bassi costi oggi permettono la larga diffusione di server/workstation con
2/4/8 processori (anche sullo stesso chip) interconnessi in cluster
–  usando reti veloci
• 
• 
Non solo calcolo scientifico, ma anche applicazioni di tipo business
Ad esempio, per piattaforme parallele data intensive come web server, data
base, motori di ricerca, data mining
–  maggiore banda aggregata di accesso alla memoria
–  maggiore dimensione aggregata della memoria CALCOLO ALTE PRESTAZIONI- S. Orlando
8
Trend nello sviluppo di hw/sw ad alte prestazione
• 
• 
• 
• 
Applicazioni di visualizzazione e
grafica computazionale usano
pipe multiple per il rendering
(rendering farm)
–  Uso massiccio di farm
parallele da parte di recenti
produzioni cinematografiche
Piattaforme parallele usate anche per garantire high availability (ridondanza)
Applicazioni scientifiche e di ingegneria richiedono l’accesso a piattaforme
più complesse, con centinaia di processori (MPP – Massively Parallel
Processor)
Visto il campo applicativo in rapida espansione, è quindi estremamente
importante capire dal punto di vista dei costi e delle prestazioni, e dei
requisiti applicativi:
–  Principi, strumenti e tecniche per programmare le piattaforme parallele
oggi disponibili
CALCOLO ALTE PRESTAZIONI- S. Orlando
9
Motivazioni contro il parallelismo
•  Contro
–  Lo sviluppo di software parallelo è considerato molto
difficile
•  Complessità inerente nello specificare e coordinare task
concorrenti
•  Algoritmi e software non portabili tra piattaforme differenti
•  Ambienti di programmazione non standardizzati
–  Miglioramento continuo delle prestazioni dei
microprocessori
•  “Ha senso dedicarsi sviluppare sw parallelo con costi elevati di
sviluppo, visto gli incrementi di prestazioni dei microprocessori?”
•  In certe casi ha comunque senso per scalare con la dimensioni dei
problemi da risolvere
CALCOLO ALTE PRESTAZIONI- S. Orlando
10
Argomenti a favore del parallelismo
•  A favore
–  Standardizzazione hw
•  uso dei microprocessori off-the-shelf per realizzare piattaforme
parallele
–  ambienti di programmazione paralleli più standard che
migliorano la portabilità del sw
•  MPI, Open-MP, PVM
–  parallelismo implicito a grana fine non sufficiente in futuro
•  limiti sulla quantità di parallelismo esplicitabile
CALCOLO ALTE PRESTAZIONI- S. Orlando
11
Altri argomenti a favore del parallelismo
•  Bassa velocità della memoria e dei dischi
–  Prestazioni non dipendono solo dalla velocità del calcolo, ma
anche dalla capacità della memoria di fornire i dati sui cui
computare alla velocità richiesta
–  Von Neumann bottleneck
•  L’uso delle gerarchie di memoria (cache) ha diminuito in parte le
conseguenze sulle prestazioni del bottleneck
–  le cache diminuiscono le latenze di accesso alla memoria
•  Il problema comunque rimane, in quanto le prestazioni della
memoria sono limitate della frazione di richieste alla memoria che
riescono ad essere soddisfatte dalla cache
–  Le piattaforme parallele diminuiscono le conseguenze del
bottleneck
•  Perché forniscono cache aggregate più grandi
•  Banda aggregata di accesso alla memoria (anche dischi) più grande
•  Necessario comunque sviluppare algoritmi paralleli in grado di
sfruttare il principio della località
CALCOLO ALTE PRESTAZIONI- S. Orlando
12
Altri argomenti a favore del parallelismo
•  Le infrastrutture di rete
–  Oggi è possibile usare Internet e i computer ad essa interconnessi
come una piattaforma a larga scala, ma eterogenea, per il calcolo
parallelo/distribuito
–  Spesso l’esigenza nasce anche da vincoli sul movimento dei dati, che
impediscono la centralizzazione degli stessi su una piattaforma
standard parallela
–  Però non tutte le applicazioni sono adatte per poter essere eseguite su
tali piattaforme …
–  Esempi:
•  SETI@home (Search for Extra Terrestrial Intelligence) utilizza la potenza dei
desktop computer per analizzare i segnali elettromagnetici provenienti dallo
spazio
•  Fattorizzazione di interi estremamente grandi, con applicazioni in crittografia
e problemi di ottimizzazione
CALCOLO ALTE PRESTAZIONI- S. Orlando
13
Programmare in parallelo
•  Un programma sequenziale può essere suddiviso in due tipi di
sezioni:
–  non parallelizzabili, ovvero inerentemente sequenziali
–  potenzialmente parallelizzabili
•  I metodi di suddivisione delle sezioni parallelizzabili sono critici per
il raggiungimento di elevate prestazioni
•  Scopo di una buona parallelizzazione:
– 
– 
– 
– 
– 
ottenere piccole sezioni sequenziali
mantenere tutti i processori (equamente) occupati (load balancing)
minimizzare le comunicazioni inter-processor (grana grossa)
limitare la replicazione del calcolo allo stretto necessario
evitare che i processori rimangano idle nell’attesa di
sincronizzazioni o latenze di I/O
•  eliminare/spostare le sincronizzazioni
•  associare ad ogni processore task multipli indipendenti (eccesso di
parallelismo) per nascondere idle times
CALCOLO ALTE PRESTAZIONI- S. Orlando
14
A che serve il parallelismo?
•  Esistono applicazioni che storicamente richiedono maggiore
capacità di quanto i computer sequenziali possano attualmente
fornire
•  e-Science
•  Esempi di problemi scientifici Grand Challenge, ovvero problemi
che non possono essere oggi risolti in tempi ragionevoli:
–  Modellare grandi strutture di DNA
–  Modellare e previsione dei fenomeni meteorologici globali, e di
quelli correlati (es. inquinamento, maree, ecc.)
–  Modellare il movimento di corpi celesti
•  Le esigenze applicative sono duplici
1.  ottenere computazioni che terminano in un tempo ragionevole
2.  eseguire nello stesso tempo e con lo stesso algoritmo problemi
più complessi (es. simulazione su dati più grandi, o con timestep più piccolo)
CALCOLO ALTE PRESTAZIONI- S. Orlando
15
E-Science
• 
• 
• 
Modellazione del Clima e Previsioni
atmosferiche
Ricerca di riserve energetiche
Problemi di cosmologia, con
grandissime scale spaziali e temporali
CALCOLO ALTE PRESTAZIONI- S. Orlando
16
e-Science & HPC Computational Science
•  HPC (High Performance Computing) offre un nuovo modo di fare
scienza:
–  Sperimentare, Teorizzare/Modellare, Computare
•  Il modello computazione è principalmente usato per approssimare
sistemi chimico/fisici
•  Tra i vantaggi
–  Giocare con i parametri della simulazione per studiare nuove
soluzioni, o eventi su cui non abbiamo raccolto dati sperimentali
•  es. simulare eventi catastrofici
–  La possibilità di ripetere particolari eventi simulati
–  Studiare sistemi quando non esistono teorie esatte
CALCOLO ALTE PRESTAZIONI- S. Orlando
17
Esempio di applicazione: Industria delle automobili
•  Grandi utilizzatori di tecnologia HPC
•  Principali usi della simulazione:
–  Aerodynamics (in modo simile all’industria aerospaziale)
–  Crash simulation
–  Metal sheet formation
–  Noise/vibration optimization
•  Principali benefici:
–  Riduzione del time-to-market di nuove automobili
–  Aumento della qualità dei prodotti
–  Riduzione della necessità di costruire prototipi
–  Più integrazione ed efficienza nell’intero processo
manufatturiero
CALCOLO ALTE PRESTAZIONI- S. Orlando
18
Previsioni del tempo
• 
• 
• 
• 
• 
• 
L’intera atmosfera è modellata dividendola in regioni o celle tridimensionali
Il calcolo su ogni cella è ripetuto diverse volte per modellare il trascorrere
del tempo
Esempio:
–  atmosfera suddivisa in celle di dimensioni 1 miglio × 1 miglio × 1 miglio,
per un’altezza di 10 miglia (per un’altezza di 10 celle)
–  per un totale di circa 5 × 108 celle
Supponiamo che il calcolo associato a ciascuna cella richiede 200 FP ops,
in un passo sono necessari 1011 FP ops
Per una previsione meteo su 10 giorni, usando intervalli di tempo di
simulazione di 10 minuti, sono necessari 6 passi per simulare un’ora, per
un totale di 1440 passi (circa 1,4 × 1014 FP ops)
–  Un computer che operasse a 100 Mflops (108 FP ops/sec)
impiegherebbe più di 106 secs (circa 16 giorni !!!!)
–  Per eseguire lo stesso calcolo in 10 minuti ci vorrebbe un computer in
grado di eseguire 0,2 Tflops (0,2 × 1012 FP ops/sec)
Cosa succede se aumentassimo i passi o rimpicciolissimo le celle?
CALCOLO ALTE PRESTAZIONI- S. Orlando
19
Simulazione movimento corpi celesti (N-bodies)
• 
• 
• 
• 
Ogni corpo celeste è attratto dagli altri dalla forza gravitazionale.
Il loro movimento può essere predetto calcolando la forza che incide su ogni
corpo
Se ci sono N corpi, dobbiamo calcolare N - 1 forze per corpo, o
approssimativamente N2 calcoli in totale
Esistono algoritmi approssimati che richiedono N × log2 N calcoli
–  sono basati sulla suddivisione dei corpi in agglomerati di elementi vicini
(galassie, sistemi solari)
–  interazioni tra agglomerati, invece che tra singoli corpi (es. Sistema
solare approssimato con il centro di massa per calcolare l’interazione
con la stella Proxima Centaury)
CALCOLO ALTE PRESTAZIONI- S. Orlando
20
Simulazione movimento corpi celesti (N-bodies)
–  Gli algoritmi approssimati (come ad es. quello di Barnes-Hut) usano
strutture dati irregolari organizzate ad albero (oct-tree)
•  tali alberi mantengono informazioni sui corpi presenti nello spazio, che viene
suddiviso in sottoblocchi
•  su quali agglomerati di corpi ricadono nello stesso box
•  sui centri e i valori di massa degli agglomerati di corpi
CALCOLO ALTE PRESTAZIONI- S. Orlando
21
Simulazione movimento corpi celesti (N-bodies)
• 
• 
• 
Gli algoritmi di simulazione degli N corpi si iterano per più passi:
–  ad ogni passo si determina la nuova posizione dei corpi
–  il calcolo deve essere quindi ripetuto
Supponiamo di avere una galassia con 1011 stelle.
Anche se ogni calcolo potesse essere ottimisticamente fatto in 1 µs (10-6 s),
sarebbero necessari
–  circa 109 anni per un’iterazione, usando l’algoritmo di complessità N2
–  quasi un anno per un’iterazione usando l’algoritmo approssimato (di
complessità N × log2 N)
CALCOLO ALTE PRESTAZIONI- S. Orlando
22
Web Search Engines
Page Repository
Collection
Indexer
Analysis
Queries
Results
Query Engine
Ranking
Crawlers
Text
Crawl Control
Structure
Utility
Indexes
CALCOLO ALTE PRESTAZIONI- S. Orlando
23
Data Mining (DM)
• 
• 
• 
• 
Applicazioni tipicamente commerciali/business
Esplorazione & Analisi, in modo automatico o semi automatico, di
grandissime quantità di dati per scoprire e estrarre Pattern Significativi &
Regole
–  Pattern & Regole devono essere innovative, valide, potenzialmente utili,
comprensibili
Algoritmi di DM su grandi quantità di dati costosi dal punto di vista
computazionale e di Input/Output
DM è un passo del processo di KDD ….
CALCOLO ALTE PRESTAZIONI- S. Orlando
24
DM
• 
• 
Disciplina che trae origine da vari campi: machine learning/AI, pattern
recognition, statistica, database, e visualizzazione di dati scientifici
Alcuni dei più importanti Data Mining Tasks:
•  Classification [Predittiva, Supervised]
•  Clustering [Descrittiva, Unsupervised]
•  Association Rule Discovery [Descrittiva, Unsupervised]
• 
Le tecniche tradizionali (sequenziali) possono non essere adatte a causa di
–  dati enormi e con alta dimensionalità
–  natura eterogenea e distribuita dei dati
CALCOLO ALTE PRESTAZIONI- S. Orlando
25
DM: Association rules
• 
• 
Uno degli algoritmi di DM più impiegati e più studiati dal punto di vista della
parallelizzazione
Identifica regole associative all’interno di insiemi di transazioni, dato un certo
supporto e una data confidenza
TID
1
2
3
4
5
Esempio:
Items
Pane, Latte
Birra, Pane, Pannolini, Uova
Birra, Coca, Pannolini, Latte
Birra, Pane, Pannolini, Latte
Coca, Pane, Pannolini, Latte
Association rule: X⇒s,c y
Support: s =σ(X∪y) / |T|
Confidence:
c = σ(X∪y) / σ(X)
{Pannolini,Latte} ⇒s,c Birra
Il supporto è la probabilità che un certo
itemset appaia nelle transazioni del dataset.
s=P({Pannolini,Latte, Birra})
La confidenza è una probabilità condizionata
c=P({Birra} | {Pannolini,Latte})
s = σ({Pannolini,Latte, Birra}) / Tot_trans =
= 2/5 = 0.4 = 40%
c = σ({Pannolini,Latte, Birra}) /
σ({Pannolini,Latte}) =
= 2/3 = 0.66
CALCOLO ALTE PRESTAZIONI- S. Orlando
26
DM: Association rules
• 
• 
• 
Per identificare tutte regole associative dato un certo supporto s
–  si trovano prima tutti gli itemset frequenti, ovvero almeno con
supporto σ(Itemset) = s
–  è il passo più costoso dell’algoritmo
–  l’algoritmo più noto è Apriori [Agarwal, Srikant]
Apriori visita il dataset più volte, e identifica, ad ogni iterazione k, i
k-itemset più frequenti
–  l’algoritmo termina quando troviamo che, per un certo valore k, non
esistono k-itemset frequenti caratterizzati da quel certo valore di s
Per supporti piccoli (es. 0.5 %) e dataset relativamente piccoli (es. 128 MB),
Apriori può impiegare anche diversi minuti per completare in sequenziale
–  il tempo impiegato dipende
•  dalle caratteristiche del dataset, dal numero di item presenti nella transazioni,
dalla dimensione del dataset, oltre che
•  dalla potenza del calcolatore, dalla memoria disponibile e dal I/O
–  per provare più istanze dell’algoritmo, per scalare con la dimensione del
dataset, per rendere il processo di mining interattivo è necessario
distribuire/parallelizzare l’algoritmo
CALCOLO ALTE PRESTAZIONI- S. Orlando
27
Computer paralleli e loro programmazione
• 
• 
• 
Negli scorsi anni abbiamo assistito al proliferare di architetture parallele
diverse, associate con paradigmi di programmazione differenti e specializzati
A causa di ciò, programmare in parallelo è stata considerata un’attività
complessa, che richiede l’uso di strumenti di programmazione a basso livello,
e un’elevata attività di tuning dei programmi per ottenere alte prestazioni
Flynn [1972] ha introdotto la seguente tassonomia dei computer, dove le
classi interessanti di computer paralleli sono MIMD (Multiple Instruction
stream- Multiple Data stream) e SIMD (Single Instruction stream - Multiple
Data stream)
CALCOLO ALTE PRESTAZIONI- S. Orlando
28
Potenzialità dei 4 modelli di computer
CALCOLO ALTE PRESTAZIONI- S. Orlando
29
SIMD
• 
• 
L’array di processori opera in modo
sincrono, ovvero a ogni passo (global
clock tick) tutti i processori eseguono la
stessa istruzione su dati differenti
–  Array processors : Connection
Machine, ICL DAP (Distributed Array
Processor), MasPar MP
–  Pipelined vector computer : CRAY 1 &
2 e CYBER 205
–  Co-processori SIMD per multimedia
–  GPUs (Graphics Proc. Units)
Macchine SIMD adatte per risolvere
problemi data parallel regolari, dove la
stessa istruzione può essere applicata a
(partizioni di) dati distinti
–  es.: Somma di 2 matrici: A + B = C.
–  Se A[2][2] e B[2][2] distribuite su 4
processori, in parallelo:
A11 + B11 = C11
A12 + B12 = C12
A21 + B21 = C21
A22 + B22 = C22
CALCOLO ALTE PRESTAZIONI- S. Orlando
30
MIMD (Multiprocessor / Multicomputer)
• 
• 
• 
• 
Ogni processore opera in modo
asincrono sotto il controllo di un
proprio programma e su dati diversi
Come nel caso SIMD, la comunicazione
dei dati e dei risultati può avvenire
attraverso memoria condivisa o rete
Computer MIMD con memoria
condivisa sono conosciuti come
multiprocessors o tightly coupled
machines. I multi-core attuali rientrano
in questa classe.
Computer MIMD dove i processi
comunicano tramite messaggi sono
conosciuti come multicomputers o
loosely coupled machines. Esempi
sono le vecchie reti di Transputer, IBM
SP, Intel Paragon, TM CM5, Cray T3E,
Meiko CS-2, i moderni cluster di WS.
CALCOLO ALTE PRESTAZIONI- S. Orlando
31
Shared memory vs message passing
• 
Sia nel caso SIMD e sia nel caso MIMD per cooperare è necessario scambiare
dati tra processori. Questo può essere fatto in due modi
–  Usando SHARED MEMORY (SM) e SHARED VARIABLES
–  Usando DISTRIBUTED MEMORY (DM) e MESSAGE PASSING
• 
Alcune architetture moderne:
Shared Memory
Message Passing
CALCOLO ALTE PRESTAZIONI- S. Orlando
32
Shared memory vs message passing
• 
Nel caso SM abbiamo un unico spazio di indirizzamento fisico a cui i vari
processori possono accedere
–  problemi legati alla scalabilità, parzialmente risolvibile tramite cache
–  modalità di cooperazione adatta per piccoli numeri di processori
(multiprocessor MIMD a 2-32 vie)
–  message-passing emulato a software tramite astrazioni di canali di
comunicazione realizzati in SM
• 
Nel caso DM abbiamo uno spazio di indirizzamento privato a ciascun
processore, per cui per comunicare i processori devono scambiarsi
messaggi via rete
–  modalità tipica di molti MPP di tipo MIMD e dei cluster di WS con rete
veloce
–  un unico spazio di indirizzamento (shared address space) può essere
emulato a software - Virtual Shared Memory (VSM)
CALCOLO ALTE PRESTAZIONI- S. Orlando
33
Il processo di parallelizzazione
•  Una buona metodologia di progetto richiede di progettare in
maniera indipendente dall’architettura target
•  Individuiamo prima cosa può essere eseguito
concorrentemente (data/task parallelism)
•  Ritardiamo quanto più possibile tutti gli aspetti di progetto
machine-specific
CALCOLO ALTE PRESTAZIONI- S. Orlando
34
Il processo di parallelizzazione
•  Esempio di ciclo di progetto
–  Partizionamento. Decomponiamo la computazione in task, a cui
assegniamo i dati su cui operare, e senza preoccuparci delle risorse
fisiche disponibili (processori/memoria).
–  Comunicazione/Sincronizazione. Determiniamo la struttura di
comunicazione/sincronizzazione per coordinare i task.
•  Accesso ai dati, comunicazione e sincronizzazione tra i processi
•  Compito diverso se prevediamo una SM o una DM
–  Agglomerazione. Valutiamo le strutture di comunicazione /
sincronizzazione, e cerchiamo di limitarle assegnando task piccoli (di
minima granularità) a processi (thread) sequenziali più grossi.
Necessario modello dei costi.
–  Mapping e Scheduling. I processi (thread) sono mappati sui processori
per massimizzare l’utilizzo del processore e minimizzare le
comunicazioni. Può essere effettuato staticamente o a runtime per
bilanciare il carico. Scheduling locale dei processi assegnati allo stesso
nodo.
CALCOLO ALTE PRESTAZIONI- S. Orlando
35
Il processo di parallelizzazione (Foster)
CALCOLO ALTE PRESTAZIONI- S. Orlando
36
Partizionamento / Decomposizione
• 
• 
• 
• 
Algoritmo sequenziale:
–  funzione F applicata su un dato I
per produrre un dato O: O =
F(I)
Data Parallelism o Domain
Decomposition
–  Partizioniamo i dati
–  I = {I1,…,In}
O = {O1,…,On}, dove
Oj=F(Ij)
Task Parallelism o Functional
Parallelism
–  Partizioniamo il controllo
–  Pipeline (vantaggioso solo se
c’è uno stream di dati in input):
•  O= F(I) = Fm( Fm-1( … F1(I)))
–  Task graph (esempio)
•  O = F(I) = F3( F1(I), F2(I) )
Combinazioni di Task & Data
Parallelism
I1
I2
F
F
F
O2
O1
I
In
F1
On
F2
Fm
I
I
F1
F2
O
F3
O
CALCOLO ALTE PRESTAZIONI- S. Orlando
37
Partizionamento / Decomposizione
• 
E’ buona norma provare strategie di partizionamento diverse, per poi
valutarle durante le fasi successive
• 
Es. di programma sequenziale da parallelizzare
–  l’analisi Data Flow a livello delle singole operazioni (minima granularità)
mette in evidenza tutto il parallelismo esplicitabile nel programma
L
M
N
O
J1
J2
K
=
=
=
=
=
=
=
I1
I3
I5
I7
L
N
J1
*
*
*
*
*
*
*
I2
I4
I6
I8
M
O
J2
I1
I2
I3
*
L
I4
I5
*
M
I6
*
N
*
I7
I8
*
O
*
J1
*
J2
K
–  Per eseguire il programma, bisogna assegnare le operazioni ai processi
(processori virtuali) da mappare poi sui processori reali
CALCOLO ALTE PRESTAZIONI- S. Orlando
38
Comunicazione e Agglomerazione
• 
Il grafo data flow definisce un partizionamento funzionale
–  I nodi rappresentano task (di grana minima) eseguibili in parallelo
–  Gli archi sono dipendenze sui dati (relazioni prod/cons), da trasformare
in comunicazioni esplicite o in sincronizzazioni
•  dipende dal modello di programmazione (DM o SM)
–  Al massimo 4 task sono eseguibili in parallelo su processori diversi
–  Se ogni task venisse eseguito in uno step da processori diversi:
•  Tseq=7 step
• 
Tpar=3 step
Speedupmax= 7/3 = 2,3 su 4 proc
Il processo di agglomerazione tende a porre task dipendenti all’interno di
uno stesso processo (da assegnare ad un processore) riducendo il grado
di parallelismo massimo esplicitabile
–  incrementare la granularità dei processi (da fine a medio/grossa)
•  riduce il rapporto tra numero di sincronizzazioni/comunicazioni e
numero di passi computazionali elementari eseguiti da ciascun processo
–  ridurre il numero di sincronizzazioni/comunicazioni è di solito
vantaggioso perché si riducono i ritardi ad esse associate
•  soprattutto nel modello DM, dove gli archi corrispondono a comunicazioni
per spostare dati tra le memorie private associate ai processori
CALCOLO ALTE PRESTAZIONI- S. Orlando
39
Mapping e scheduling
•  Mapping
–  Assegnamento dei processi sui processori fisici
•  Mapping Tradeoff:
–  Processi mappati su nodi diversi, per migliorare la concorrenza e il
bilanciamento del carico
–  Processi (che comunicano frequentemente) mappati sullo stesso nodo,
per rendere locali le comunicazioni e
• 
Una volta co-allocati i processi (cooperanti) ai nodi (singolo- o multiprocessori), essi dovrebbero essere schedulati simultaneamente per
evitare ritardi
–  Su MPP, scheduling di tipo space-sharing, senza time-sharing
–  Sui cluster, dove i nodi sono dotati di SO general-purpose timesharing, i processi vanno solitamente in esecuzione secondo la politica
di scheduling locale
•  Non abbiamo il co-scheduling di processi cooperanti su nodi distinti
CALCOLO ALTE PRESTAZIONI- S. Orlando
40
Agglomerazione: aumentiamo la granularità
I1 I2
I1
I2
I3
I4
I5
I6
I7
I8
*
Task a grana minima
1
comp.
+
1
output
comm.
*
*
*
*
*
*
*
Task di grana media
I1 I2 I3 I4
L = I1 * I2;
M = I3 * I4;
J = L * M;
3
comp.
+
1
output
comm.
CALCOLO ALTE PRESTAZIONI- S. Orlando
41
Granularità, mapping e performance
6
6
6
*: 5
6
6
*: 5
6
6
*: 5
6
*: 5
6
6
P1 P2 P3 P4
Time
6
+: 5
6
*: 5
Aumento
granularità
6
*: 5
6
P1 P2
Time
5
6
33
32
CALCOLO ALTE PRESTAZIONI- S. Orlando
42
Replicazione
• 
• 
Spesso, oltre a partizionare, è utile replicare la computazione per
–  Ridurre/evitare le comunicazioni e bilanciare il carico
Rispetto al modello DM, può essere necessario replicare anche i dati
associati ai task da replicare
CALCOLO ALTE PRESTAZIONI- S. Orlando
43
Modello di programmazione
• 
• 
• 
• 
Controllo
–  Come il parallelismo viene creato
–  Qual è e come viene garantito l’ordine corretto tra le operazioni
–  Come thread di controllo differenti si sincronizzano
Naming
–  Quali dati sono private e quali shared
–  Come i dati shared sono acceduti/comunicati dal punto di vista logico
–  Nominandoli direttamente oppure inviando messaggi ai loro gestori (naming dei
processi/canali di comunicazione)
Insieme di operazioni e costi
–  Quali sono le operazioni di base
–  Qual è il loro costo
Storicamente
–  Ciascuna macchina parallela era unica, e caratterizzata da una specifico modello
architetturale
–  Aveva il proprio modello di programmazione e un linguaggio associato
–  Discutiamo con un semplice esempio
CALCOLO ALTE PRESTAZIONI- S. Orlando
44
Un semplice esempio
• 
Decomposizione/Agglomerazione:
–  Ciascuna valutazione / somma parziale diventa un task
–  Assegniamo n/p numeri/subtask a ciascuno dei p processori virtuali
•  Ciascuno computa in maniera indipendente risultati “privati” e somme
parziali
•  Uno (o tutti) colleziona le somme parziali e computa la somma globale
=> Classi di Dati
–  Logicamente condivisi
•  Lo sono gli n numeri originali, e la somma globale
–  Logicamente privati
•  Lo sono le variabili usate per memorizzare le funzioni di valutazione
individuali e le somme parziali
CALCOLO ALTE PRESTAZIONI- S. Orlando
45
Modelli di programmazione 1 (SM)
• 
• 
• 
• 
• 
Shared Memory (SM). Nel modello shared-memory i processi (thread)
condividono uno spazio di memoria comune, sul quale leggono/scrivono in
maniera asincrona. Meccanismi vari come lock e semafori possono essere
usati per controllare gli accessi alla SM.
Un vantaggio dal punto di vista del programmatore è che non esiste la
nozione di “ownership” dei dati, e quindi non c’è bisogno di comunicare
dati. Comunque, dal punto di vista della programmazione efficiente, gestire
la località può diventare complesso.
Il modello shared memory è in un certo senso primitivo su macchine SM
MIMD, ma uno spazio di indirizzamento comune può essere realizzato
(efficientemente !?) anche su un DM MIMD (Virtual SM).
Il modello non mette vincoli alla fantasia del programmatore (unrestricted
model) ed è di basso livello. Un ambiente di programmazione tipico sono le
librerie portabili per la programmazione multi-threading (es.: pthread) da
linkare con codice sequenziale.
Parallelismo di tipo esplicito: il programmatore è responsabile delle
suddivisione del programma in task, e della cooperazione tra i task via SM
CALCOLO ALTE PRESTAZIONI- S. Orlando
46
Modello di programmazione 1 (SM)
• 
Shared Address Space
–  Il programma consiste di una collezione di thread di controllo
–  Ciascuno con un set di variabili private,
•  es. variabili locali sullo stack
–  Collettivamente hanno accesso a variabili condivise
•  Es. variabili statiche, heap globale
–  I thread comunicano implicitamente leggendo/scrivendo variabili
condivise
–  I thread si coordinano attraverso operazioni di sincronizzazione su
variabili condivise
•  Leggi/scrivi flag
•  Usa locks, semafori
• 
Come la programmazione
concorrente sugli
uniprocessori
CALCOLO ALTE PRESTAZIONI- S. Orlando
47
Modello architetturale 1 (SM)
• 
• 
• 
Una macchina SM (UMA)
–  Processori connessi ad una singola SM
–  Non abbiamo memoria “locale” del nodo, ma abbiamo una cache
Sun, DEC, Intel “SMPs” (Symmetric multiprocessors)
Costo: molto più performante accedere alla cache rispetto alla memoria
principale
CALCOLO ALTE PRESTAZIONI- S. Orlando
48
Codice SM per calcolare la somma
•  Variabili condivise
–  Array A[N], in sola lettura
–  Variabile s, che alla fine deve contenere la somma degli N numeri
Cosa potrebbe andare storto?
CALCOLO ALTE PRESTAZIONI- S. Orlando
49
Problemi e soluzioni
• 
Come avviene la somma globale (s = local_s1 + local_s2)?
• 
• 
• 
Istruzioni di thread differenti possono mescolarsi arbitrariamente
Quale potrebbe essere il risultato finale in memoria?
–  Race Condition
Soluzione possibile: Mutua Esclusione con Lock (semafori binari)
• 
I lock devono essere atomici (senza interruzione)
CALCOLO ALTE PRESTAZIONI- S. Orlando
50
Modello di programmazione 2 (MP)
• 
• 
• 
• 
• 
• 
• 
• 
Message passing (MP). Il modello message-passing è basato sull’astrazione
di processi multipli, creati staticamente o dinamicamente.
Ogni processo è caratterizzato da uno specifico codice e incapsula dati
privati.
Le primitive send/receive nominano direttamente i processi (tramite degli
identificatori/nomi unici) o delle astrazioni di canali di comunicazione che
collegano i processi
–  Esistono primitive collettive (gather/scatter/reduce) e di multicast.
Modello di basso livello, che permette qualsiasi tipo (unrestricted approach)
di decomposizione e struttura di comunicazione
Il modello message passing è in un certo senso primitivo su macchine DM
MIMD, ma può essere realizzato efficientemente anche su un SM MIMD.
Esistono linguaggi message passing, anche se oggi l’ambiente di
programmazione tipico fa uso di librerie portabili, facili da usare, e efficienti
da linkare con codice sequenziale (MPI, PVM)
Parallelismo di tipo esplicito: il programmatore è responsabile delle
suddivisione del programma in processi, e della cooperazione tra i processi
via MP
Paradigma naturale su DM-MIMD:
–  MPMD - Multiple Programs Multiple Data – ovvero processi che eseguono
ALTE PRESTAZIONIprogrammi diversi su dati diversi e che cooperanoCALCOLO
tramite
MP S. Orlando 51
Modello di programmazione 2 (MP)
• 
Message Passing
–  I programmi consistono in una collezione di processi con nome
•  Thread di controllo con in più uno spazio di indirizzamento privato
–  Variabili locali, variabili statiche, heap
• 
• 
• 
–  I dati logicamente condivisi devono essere partizionati tra gli spazi di
memoria locali dei vari processi
Processi comunicano con data transfer espliciti
–  Coppie di send & receive (matching) tra una sorgente e una dest.
La sincronizzazione è implicita in ogni evento di comunicazione
Simile alla computazione
distribuita su rete
CALCOLO ALTE PRESTAZIONI- S. Orlando
52
Modello architetturale 2 (DM)
Processori connessi direttamente solo alla propria memoria privata & cache
–  Non possono accedere direttamente alla memoria di altri processori
–  Memoria distribuita (DM)
•  Ciascun “nodo” ha una sua interfaccia di rete (NI)
–  Tutte le comunicazioni/sincronizzazioni passano attraverso questa NI
•  Macchine a memoria distribuita
–  IBM SP, Cluster di Workstations
CALCOLO ALTE PRESTAZIONI- S. Orlando
53
Calcolare S = X(1) + X(2) su ciascun processore
• 
Prima soluzione per realizzare S = X(1)+X(2)
(con possibili problemi.. deadlock)
• 
Seconda soluzione
CALCOLO ALTE PRESTAZIONI- S. Orlando
54
Modello di programmazione 3 (DP)
• 
Data Parallel (DP)
–  Un unico thread di controllo che consiste di
•  operazioni parallele applicate a tutti i (o un ben definito sottoinsieme dei)
dati elementari che costituiscono una struttura dati
–  La comunicazione è implicita negli operatori paralleli e nelle operazioni
di “shift” delle strutture dati (array)
–  Elegante e facile da capire
–  Non tutte le parallelizzazioni possono essere espresse naturalmente
con questo modello (solo data paralellism)
• 
Vector Computing
–  Una istruzione eseguita su tutti i dati di una struttura dati in modo
pipeline
CALCOLO ALTE PRESTAZIONI- S. Orlando
–  Sfrutta ancora il data parallelism
55
Modello architetturale 3 (DP)
• 
• 
• 
Macchina SIMD (Single Instruction Multiple Data)
Un gran numero di processori piccoli ed elementari
Un singolo “controllo” invia le istruzioni per tutti i processori
–  Ciascun processore esegue la stessa istruzione
–  Alcuni processori possono essere “spenti” sull’esecuzione di
specifiche istruzioni
• 
Le macchine SIMD a larghissima scala non sono più molto popolari (es.
Connection Machne), ma lo è il modello di programmazione
–  Implementato allocando il parallelismo originale ad n-vie (a grana
finissima) su un numero ridotto p di processori
–  Supportato da compilatori (e.s., HPF = High Performance Fortran), che
producono codice SPMD (vedi prossima slide)
CALCOLO ALTE PRESTAZIONI- S. Orlando
56
Modelli di programmazione (SPMD)
• 
• 
• 
• 
• 
SPMD - Single Program Multiple Data - è un paradigma software
(tipicamente di tipo MP) usato su computer DM-MIMD per implementare il
data parallelism
Il modello di calcolatore SIMD permette di implementare il parallelismo di
tipo data parallel in modo sincrono: ogni processore opera in lockstep
Il modello SPMD è la versione software e asincrona del modello SIMD?
–  medesimo programma eseguito da ciascun processore di una
macchina MIMD: ma ogni processore ha un proprio controllo e un
proprio clock
Poiché i programmi sono eseguiti su dati separati, è possibile che i flussi
di controllo, a causa dei salti condizionali, siano differenti.
–  I processori non eseguono le stesse istruzioni in lockstep, ma solo
processi caratterizzati dallo stesso codice
–  Comportamento del codice differenziato in base al PID del processo
–  Processi scambiano dati ancora tramite message passing
Considera il seguente programma:
IF X = 0 THEN S1 ELSE S2
–  Se X=0 su P1 e X != 0 su P2, P1 esegue S1 mentre P2 esegue S2
–  Questo non potrebbe accadere sulla macchina SIMD (MIMD più potente
che SIMD)
CALCOLO ALTE PRESTAZIONI- S. Orlando
57
Modelli di programmazione (sommario)
• 
• 
• 
Storicamente, tutte le architetture parallele
avevano caratteristiche uniche
–  Ciascuna con il proprio modello di
programmazione e linguaggio associato
Necessario riprogettare il sw parallelo per
ogni macchina …
Attualmente
–  Distinguiamo il modello di programmazione dall’architettura sottostante
•  Il modello di programmazione visto come una concettualizzazione della
macchina parallela che il programmatore usa per le sue applicazioni
• 
• 
–  Possiamo scrivere codice corretto e portabile, che esegue su più
macchine
MPI (modello MP) è oggi l’opzione più portabile
–  Ma cosa possiamo dire per le prestazioni?
–  Purtroppo scrivere codice portabile ma veloce richiede ancora il tuning
per ogni specifica architettura
La sfida è rendere semplice questo processo di programmazione parallela
portabile ed efficiente
–  Campo di ricerca per algoritmi, linguaggi e strumenti di compilazione
CALCOLO ALTE PRESTAZIONI- S. Orlando
58
Valutazione delle prestazioni: Speedup
• 
Speedup su n processori:
• 
• 
Massimo speedup Sp(n)=n con n processori: speedup lineare
Speedup superlineare se Sp(n) > n
–  può essere dovuto all’uso di un algoritmo sequenziale sub-ottimo
–  può essere dovuto a caratteristiche dell’architettura che favoriscono la
versione parallela.
Una ragione comune dello speedup superlineare è la maggiore quantità di
memoria disponibile sulle architetture parallele, che permette di mantenere
in memoria più dati del problema rispetto al caso sequenziale (senza quindi
coinvolgere il disco … swapping).
• 
CALCOLO ALTE PRESTAZIONI- S. Orlando
59
Legge di Amdahl
• 
Massimo speedup ottenibile nel parallelizzare un algoritmo
CALCOLO ALTE PRESTAZIONI- S. Orlando
60
Legge di Amdahl
• 
Lo Speedup Factor è dato da
• 
Se la frazione non parallelizzabile del codice sequenziale è f = 1/k, la legge
di Amdahl stabilisce che il massimo speedup ottenibile per n → ∞ è:
Sp(n) = 1/f = k
CALCOLO ALTE PRESTAZIONI- S. Orlando
61
Valutazione delle prestazioni: Efficienza
• 
Efficienza:
• 
L’efficienza dà una misura della frazione del tempo totale durante il quale i
vari processori sono efficacemente usati per effettuare la computazione.
• 
Un’efficienza uguale a 1 (Sp(n)=n) significa che tutti i processori
partecipano in maniera proficua all’esecuzione dell’algoritmo
Un’efficienza molto minore di 1 testimonia il fatto che
–  carico sbilanciato
–  processori idle
–  lavoro extra nella versione parallela dell’algoritmo
–  overhead legati alle comunicazioni/sincronizzazioni
• 
CALCOLO ALTE PRESTAZIONI- S. Orlando
62
Valutazione delle prestazioni: Costo
• 
Il prodotto processor-time o Costo (o Work) di una computazione è definita
come
Costo= (no. Totale di processori usati) ⋅ (tempo di esecuzione)
•  Il Costo di una computazione sequenziale è semplicemente ts
• 
Il Costo di una computazione parallela è n ⋅ tp
• 
Poiché tp = ts / Sp(n) il Costo può essere formulato come
Costo = n ⋅ tp = n ⋅ ts / Sp(n) = ts / E(n)
• 
Un algoritmo parallelo è Cost-Optimal se il costo per risolverlo in parallelo
è simile al costo per risolverlo in sequenziale
–  Efficienza ottima = 1
CALCOLO ALTE PRESTAZIONI- S. Orlando
63
Valutazione delle prestazioni: Scalabilità
• 
Il termine scalabilità si usa per indicare un progetto hardware che può
essere espanso (aggiungendo processori, memoria, rete, I/O) per
aumentare la banda totale di comunicazione/calcolo:
–  In questo caso parliamo di scalabilità dell’architettura o dell’hardware
–  Es.: il bus è una struttura di interconnessione facilmente ed
economicamente espandibile, ma non scalabile
• 
• 
Esiste anche il concetto di scalabilità algoritmica
Un algoritmo parallelo è scalabile se è possibile
–  a causa di un incremento della dimensione dei dati
–  incrementare il livello di parallelismo (usare più processori)
con un basso o limitato incremento del tempo di esecuzione
Problema
–  Come aumenta il lavoro da compiere all’aumentare della dimensione
dei dati ?
–  Questo aumento è in relazione con la quantità di processori che
dobbiamo aggiungere per garantire che i tempi di esecuzione non
CALCOLO ALTE PRESTAZIONI- S. Orlando
cambino
• 
64
Dimensione del problema e Scalabilità
•  Poniamo
–  numero di dati da processare = dimensione del problema
•  Raddoppiare la dimensione del problema non necessariamente
implica il raddoppio del numero di passi computazionali
–  dipende dal problema
–  è vero per la somma di 2 matrici bidimensionali di N elementi, e
di lato n (n = N1/2)
•  N = n2 passi, uguali al numero di elementi di ogni matrice
•  se raddoppio la dimensione: 2 N = (21/2 n)2 il numero di passi
diventa: (21/2 n)2 = 2 n2
–  non è vero per il prodotto di 2 matrici
•  N3/2 = n3 passi, dove N = n2 è il numero di elementi di ogni matrice
•  se raddoppio la dimensione: 2 N = 2 n2 = (21/2 n)2 il numero di passi
diventa: (21/2 n)3 = 23/2 n3
•  La definizione di scalabilità algoritmica dipende anche da
–  come aumentiamo la dimensione del problema
CALCOLO ALTE PRESTAZIONI- S. Orlando
65
Legge di Gustafson
• 
• 
• 
Si assume che, all’aumentare del grado di parallelismo
–  viene incrementato la dimensione del problema
–  in modo da mantenere costante il lavoro eseguito da ogni processore
in parallelo (tempo Tp costante)
Inoltre, all’aumentare della dimensione del problema la computazione
inerentemente sequenziale si suppone fissa, e prende sempre un tempo Ts
–  il razionale della legge di Gustafson sta nell’uso attuale delle macchine
MPP, usate per eseguire problemi più grossi rispetto al caso seriale
–  in questo caso la legge di Amdahl è pessimistica, perché non tiene
conto che, all’aumentare della dimensione del problema, la frazione f
del tempo inerentemente seriale solitamente diminuisce
Lo Scaled Speedup Factor, ovvero lo speedup quando il problema è
scalato con il numero di processori, è dato dalla seguente formula, dove
s = Ts/(Ts+Tp),
p = Tp/(Ts+Tp),
s+p = 1
CALCOLO ALTE PRESTAZIONI- S. Orlando
66
Legge di Gustafson: scaled speedup
• 
• 
• 
• 
• 
• 
Lo scaled speedup della legge di Gustafson si riferisce a problemi dove,
all’aumentare della dimensione, Ts rimane costante
Se su 20 processori abbiamo una parte seriale del 5% (Ts=0,05 T), allora
s = (0,05 T) / (0,05 T + 0,95 T / 20) = 0,51
e
p = 1-s = 0,49
Lo scaled speedup su 20 processori è quindi:
–  Spscaled(20) = s+np=0.51 + 20 * 0,49 = 10.3
Lo scaled speedup su 40 processori è invece:
–  Spscaled(40) = s+np=0.51 + 40 * 0,49 = 20,1
Se il problema non fosse stato “scalato in dimensioni” su 40 processori, lo
speedup sarebbe stato:
–  Sp(40) = T / (0.05 T + 0.95 T / 40) = 13,6
Nota che per applicare Gustafson, la dimensione del problema su 40
processori deve essere accresciuta (scalata), ovvero scelta in modo che il
tempo totale T’ risulti uguale a
T’ = Ts + 40 * Tp = 0,05 T + 40 * 0,95 T / 20 = 0,05 T + 2 * 0,95 T = 1,95 T
dove T era il tempo totale del problema (più piccolo) eseguito su 20
processori
CALCOLO ALTE PRESTAZIONI- S. Orlando
67
Scaling del problema e Isoefficienza
• 
Funzione di isoefficienza (Kumar)
–  la funzione stabilisce come deve essere aumentata la dimensione del
problema per mantenere costante l’efficienza
–  la funzione è descritta in termini di
• 
• 
• 
• 
W: tempo sequenziale rispetto ad un certo size del problema
Tp: tempo in parallelo
p: numero di processori
To(W, p): overhead globale (comms+waiting+replica+sbilanciamento) in
funzione di W e del grado di parallelismo
•  E: efficienza da mantenere costante
–  To(W,p) = p Tp - W
–  E = S/p = W / (p Tp) = W / (W + To(W,p)) = 1 / ((W + To(W,p)) / W)
–  Derivando W dall’equazione dell’efficienza, si ottiene la funzione di
isoefficienza, ovvero di quanto deve aumentare W (ovvero il size del
problema) all’aumentare di p per mantenere costante E:
CALCOLO ALTE PRESTAZIONI- S. Orlando
68