Riassunto esame Parallel computing, Prof. Marco Bertini, libro consigliato Parallel Programming for Multicore and Cluster Systems, Thomas Dauber and Gudula Rünger, Springer

Parallelism vs concurrency

Introduzione al parallelismo e concorrenza

Il parallelismo a livello hardware, diversi ambienti e paradigmi di programmazione parallela, analisi di performance.

Esame: elaborato di programmazione, relazione e presentazione (40%) + elaborato di programmazione finale, elaborato, relazione e presentazione (60%).

Definizioni e differenze

Parallelism vs concurrency:

• Concurrent: supporta due o più azioni in corso allo stesso tempo alternate, computazione indipendente di processi in esecuzione.
• Parallel: supporta l’esecuzione simultanea di due o più azioni, possibile solo quando sono disponibili più core. Esecuzione simultanea delle computazioni.

La concorrenza riguarda la struttura, mentre il parallelismo riguarda l’esecuzione. Un programma concorrente ha più thread logici di controllo, mentre un programma parallelo può o meno avere più di uno di essi.

Un algoritmo concorrente necessita di controllare l’esecuzione dei thread.

Benefici: più veloce (stesso lavoro in meno tempo) e/o più grande (più lavoro nello stesso tempo).

Vantaggi e svantaggi del parallelismo

Parallel (fornisce performance) vs Distributed (fornisce convenienza). Il parallelismo serve anche a conservare energia, poiché l’energia cresce con il quadrato della frequenza della CPU. Abbassare la frequenza e aumentare le unità di elaborazione in realtà risparmia sia tempo che energia.

Casi in cui il parallelismo è inefficace: rallentamenti dovuti a overhead di comunicazione, problemi di scalabilità (più veloce solo quando la dimensione del problema è effettivamente grande).

Tipi di parallelismo

• Bit-level parallelism: aumento della dimensione della parola del processore, più dati vengono elaborati contemporaneamente.
• Instruction-level parallelism: pipeline di istruzioni, esecuzione fuori ordine, esecuzione speculativa (prevenzione dei salti).
• Data-level parallelism: stessa operazione su una grande quantità di dati.
• Task-level parallelism: memoria condivisa (multiprocessore, ogni CPU ha una memoria comune) vs memoria distribuita (ogni CPU ha la propria memoria).

Concetti fondamentali

Per scrivere algoritmi paralleli, bisogna assumere che non ci siano dipendenze tra le istruzioni I₁ e I₂, in altre parole dobbiamo programmare con il concetto che non abbiamo conoscenza sull’ordine in cui le istruzioni saranno eseguite.

SPMD = programma parallelo su computer MIMD.

Architetture parallele

RAM = Random Access Machine con variante parallela (PRAM). CTA = Candidate Type Architecture separa due tipi di riferimenti di memoria: riferimenti locali a basso costo e riferimenti non locali ad alto costo. I riferimenti ad alto costo hanno una latenza, chiamata Memory Latency, che può essere 2-5 ordini di grandezza superiore a quella locale.

Metriche di performance

• Service time: opposto alla larghezza di banda del processamento (throughput medio).
• Completion time: tempo medio necessario per completare la computazione.
• Latency: tempo medio per processare un elemento del flusso.

Modulo sequenziale e parallelo

• Modulo sequenziale:
  • Tempo di servizio t = somma p * t_i
  • Tempo di completamento t = m * t_c
  • Larghezza di banda B = 1/t
  • Latenza = tempo di servizio
• Modulo parallelo:
  • Grado di parallelismo sigma è nncn
  • Tempo di completamento t = m * t (dove m è molto più grande di n, segnalando che la mole di dati è molto più grande del grado di parallelismo)

Nel parallelismo, il tempo di servizio e la latenza differiscono: il tempo di servizio misura l’intervallo medio dopo il quale sigma può accettare nuovo flusso di ingresso senza aspettare il risultato di uscita. A seconda del paradigma di parallelismo utilizzato, la latenza può aumentare (pipelining), ma ci interessa il tempo di servizio (che definisce il tempo di completamento), quindi va bene.

Scalabilità e Speedup

• Scalabilità: misura della velocità relativa della computazione n-parallela rispetto alla stessa computazione con parallelismo pari a 1: S = B_n / B₁ = t₁ / t_n.
• Speedup: metrica da utilizzare: S = t_s / t_p dove t_s = tempo di completamento del programma in forma sequenziale, t_p = tempo di completamento del programma in forma parallela. Superlinear speedup dipende dagli effetti della cache, aumenta la latenza.
• Efficienza E = S_P / P, stima quanto sono utilizzati i processori, analizza quanto tempo viene speso dai CPU in idle/non-idle. L'ideale è il 100%. Poiché dividiamo per P, dobbiamo trovare il punto ottimale per aumentare E_P.

Leggi di Amdahl e Gustafson

Legge di Amdahl: ogni algoritmo consiste di due parti: una che può essere parallelizzata e una che non può esserlo, a causa delle dipendenze dai dati. S = P / (1+(P-1)f). Abbiamo una forte dipendenza dalla parte non parallelizzabile del nostro algoritmo nel calcolare il S finale. Ad esempio, se un programma è parallelizzabile al 95%, l'accelerazione non sarà mai superiore a 20 volte. La legge di Amdahl si applica solo quando la dimensione del problema è fissa.

Legge di Gustafson: definisce l'accelerazione scalata mantenendo il tempo di esecuzione parallelo costante e regolando P man mano che la dimensione del problema N aumenta. S_P,N = P + (1-P) * alpha(N) dove alpha(N) è la frazione non parallelizzabile, questo indica che se N aumenta, allora S_P,N è quasi P, e ciò significa che la velocità sarà proporzionata al numero di core di elaborazione.

Obiettivi della parallelizzazione

• Più veloce con lo stesso carico di lavoro (Amdahl).
• Più dati nello stesso tempo (Gustafson).

Fonti di perdita di performance

• Overhead di comunicazione, sincronizzazione, computazione, memoria.
• Sezione di codice non parallelizzabile f (deve essere ridotta il più possibile).
• Contesa tra unità che competono per risorse comuni.
• Tempo di inattività.

26/09/2019 Task e modern cpu

Parallelizzare un programma

• Identificare la porzione di lavoro che può essere parallelizzata.
• Spartizione del carico di lavoro.
• Orchestrare i workers, accesso ai dati, comunicazione tra i thread, sincronizzazione.

Decomposizione del problema

Identificare le dipendenze tra i dati, scomporre il problema in sotto-parti che possono essere parallele.

Assegnamento dei task

• Thread/processori workers: l'obiettivo è bilanciare i workers e ridurre la comunicazione. Può essere statico o dinamico, ed è onere del programmatore o del framework/libreria.

Orchestrazione

Strutture comunicative, mantenimento delle dipendenze, schedulazione dei task, organizzazione delle strutture dati (semafori, ecc.). Obiettivi: ridurre i costi di comunicazione o sincronizzazione, ridurre l'overhead, preservare la località dei dati il più possibile.

Mappamento sull’hardware

È possibile per esempio assegnare uno specifico thread ad uno specifico core, in modo da far sì che egli abbia la memoria già pronta. È possibile anche fare la stessa cosa sui core della GPU. Quest’operazione è eseguita a livello di OS di solito, ma avviene anche a livello di compiler.

CPUs moderne

Il numero di transistor aumenta nella forma dell’aumento di core fisici. Aumenta anche il numero di ALU all’interno di ogni core.

Memorie

Le ram sono lente, hanno latenza. Ridurre il più possibile il numero di accessi alla memoria. Hanno una banda specifica, che è la velocità alla quale esse possono fornire dati ai processori.

Possibile soluzione: prefetch data, ovvero un caricamento anticipato della risorsa.

Esecuzione out-of-order

Eseguire due o più istruzioni in ordine diverso da quello previsto in parallelo, però facendo sì che alla fine le due istruzioni risultino eseguite comunque nell’ordine corretto, conservando sempre le dipendenze.

Memory/Concurrency

Per una singola CPU, più istruzioni store non sono riordinate con altre istruzioni store, e in ogni caso mai riordinate prima di load precedenti. Il riordino delle istruzioni può causare il non-funzionamento delle sezioni critiche e portare a deadlock. Ci sono metodi per far sì che le CPU non riordinino determinate istruzioni.

Locking

Nelle moderne CPU x86 il cpu lock è più economico delle barriere di memoria (fences).

I sistemi a memoria condivisa (SMA) sono divisi in due categorie: uniformi (UMA) e non-uniformi (NUMA), la seconda va per la maggiore. Vi sono sezioni della memoria più vicine ad ogni CPU e altre più lontane. Quelle più vicine costano di meno per essere accedute e vice-versa, è fatto per prevenire che CPU accedano senza un buon motivo a memorie lontane e magari destinate ad altre CPU. È buona norma localizzare thread che condividono memoria sullo stesso socket, che quindi ha accesso ad aree precise di memoria.

La coerenza della cache è gestita direttamente dalla CPU. È possibile utilizzare delle funzioni SIMD direttamente in C/C++.

30/09/2019 PC design models

Design models for parallel programs

Task decomposition

Creo un set di task il più indipendenti tra loro (eseguibili in qualsiasi ordine). Anche chiamata functional decomposition. Diversi task sono assegnati a diversi thread e questa assegnazione non cambia (assegnazione statica, devo conoscere la spartizione dei task all'inizio della computazione e non cambia durante la computazione stessa, se utilizzabile con un ciclo for richiede che il numero di iterazioni sia noto; o dinamica, assegno un task non appena un thread è disponibile, richiede identificazione dei thread consigliabile se n >> n_task / n_thread).

Di base è più facile partire con tanti task piccoli che con pochi grandi e poi tentare di dividerli. Avere almeno tanti task quanto il numero di thread (/core). Evitare di aumentare troppo i costi di overhead utilizzando troppi thread.

Goals della task decomposition

• Flessibilità (non specifico sulla specifica architettura).
• Efficienza (i task dovrebbero essere in grado di far lavorare i thread/core per un tempo più alto in proporzione al tempo/costo di gestire la parallelizzazione (creazione, swapping di thread), i task dovrebbero essere abbastanza indipendenti da non dover dipendere troppo gli uni dagli altri).
• Semplicità (il codice dovrebbe rimanere facile da leggere e debuggare).

Data decomposition

L’applicazione può computare diverse porzioni del dataset indipendentemente. Se i dati sono indipendenti tra loro, possiamo dividerli in chunks per assegnare le diverse porzioni a diversi thread/core. Come dividere i dati in chunks? Forma e granularità, tipicamente massimizzare il rapporto volume/superficie.

Possiamo avere anche qui come nella task decomposition associazione statica o dinamica dei task. Buona norma da adottare quando una gran parte del computation time è dominato dalla manipolazione di grandi strutture dati (calcolo matriciale, ecc.) e/o quando sui differenti chunks devono essere eseguite operazioni simili.

Data layout: AoS vs SoA

• Array of Structures: versione OOP di una struttura contenente vari array ognuno contenente elementi simili di ogni oggetto.
• Structure of Arrays: versione OOP di un array di oggetti crea problemi di cache.

Comunicazione

(Dipende dal problema) Se non ci sono problemi di sincronia o memoria in comune, in questi casi la comunicazione tra thread non è necessaria. Nella maggior parte dei casi le applicazioni parallele richiedono qualche forma di comunicazione/sincronia tra thread genera overhead, ridurle.

Latentza = tempo necessario per mandare un messaggio da punto A a B. Banda = quantità di messaggi che posso mandare per unità di tempo. Posso includere vari messaggi in un unico pacchetto per risparmiare latenza.

Comunicazione sincrona vs asincrona

• Sincrona: prevede qualche sorta di handshake, implica intrinsecamente un qualche sorta di blocco per l’attesa della risposta.
• Asincrona: tipicamente non bloccante, preferita.

Safety e liveness

Dobbiamo avere:

• Mutua esclusione (= una risorsa è utilizzata in un dato momento da un unico thread).
• No deadlock (= il programma deve terminare, il che significa che se due thread vogliono la stessa risorsa, uno delle due la ottiene).
• Starvation freedom (= se due thread vogliono una stessa risorsa, è importante che almeno una delle due la ottiene prima o poi).
• Waiting (= se un thread richiede la risorsa che è al momento utilizzata da un altro thread, ma il rilascio di questa risorsa fallisce).

Mutua esclusione implementata tramite comunicazione persistente

Design patterns for parallel programming: di base ordino i task seguendo le dipendenze tra i dati e le eseguo non appena l’input è disponibile.

Loop-level parallelism

Assegno diverse iterazioni di un loop a diversi thread/core. La durata del ciclo deve essere nota all’avvio e non devono esistere dipendenze tra i dati all’interno del ciclo, ovvero l’iterazione I_k non deve essere richiesta come dipendenza da I_k+1.

Task-level parallelism

Distribuzione di diversi task su diverse unità di computazione. Necessita di comunicazione. Non abbiamo alcuna assunzione su cosa venga eseguito prima e dopo. I task possono anche essere diversi. La comunicazione di solito avviene per fornire dati a task successivi nelle dipendenze.

Fork/join parallelism

Esiste un thread parent che genera sotto-thread di parallelismo per eseguire computazione parallela e poi ri-joina (senza uno specifico ordine) i thread per continuare con la porzione sequenziale. Durante il join i figli devono scrivere o su memoria condivisa o su memoria propria il risultato della computazione.

SPMD: Single Program Multiple Data

Le varie unità di computazione eseguono lo stesso programma su diversi dati o diverse porzioni dello stesso dataset.

Master-worker

Un processo master crea un pool di processi worker e un pool di task e a... [testo troncato]