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

Pamdahl's Law and Gustafson's Law

Pamdahl's Law states that every algorithm consists of two parts: one that can be parallelized and one that cannot be, due to data dependencies. The formula for speedup (S) is given by S = P / (1+(P-1) f), where P is the proportion of the algorithm that can be parallelized and f is the fraction of the algorithm that cannot be parallelized. This law highlights the strong dependency on the non-parallelizable part of the algorithm in calculating the final speedup. For example, if a program is 95% parallelizable, the speedup will never be more than 20 times. It is important to note that Amdahl's Law applies only when the problem size is fixed.

Gustafson's Law, on the other hand, defines the scaled speedup by keeping the parallel execution time constant and adjusting P as the problem size N increases. The formula for speedup (S) is given by S = P + (1-P) * alpha(N), where alpha(N) is the non-parallelizable fraction. This law tells us that if N increases, then S is almost P, meaning that the speedup will be proportionate to the processing core counts.

The goals of parallelization are to achieve faster performance with the same workload (Amdahl's Law) and to handle more data in the same amount of time (Gustafson's Law).

There are several sources of performance loss in parallelization, including overhead from communication, synchronization, and computation.

memory- Non-parallelisable code section f (needs to be reduced as much as possible) - Contention units that compete for common resources - Idle time - Span longest series of operations that have to be performed sequentially due to data dependency. The lower lo span, the higher the parallelization of the algorithm. 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, data access, 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: - workers threads/processors, l'obiettivo è bilanciare i workers e ridurre la comunicazione. Può essere statica o dinamica, ed è onere o del programmatore o del framework/libreria. Orchestrazione: strutture comunicative, mantenimento delle dependencies.

schedulare i task,→organizzare le data structure (semafori, etc). Goals ridurre i costi di comunicazioneo 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, inmodo da far si che egli abbia la memoria già pronta. E’ possibile anche fare la stessacosa sui core della GPU. Quest’operazione è eseguita a livello di OS di solito, maavviene anche a livello di compiler.

CPUs moderne

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

Memorie:

Le ram sono lente, hanno latenza. Ridurre il più possibile il numero di accessi allamemorie. Hanno una banda specifica, che è la velocità alla quale esse possonofornire 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 si 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 si che le CPU non riordino determinate istruzioni. Per esempio: Thread 1 Thread 2 x=1 if ready == 1 write fence read fence ready = 1 R=x In Java le shared variable si chiamano volatile. In C++, atomics. Questi tipi di variabili dicono al compilatore di risolvere problemi di accessi di memoria tra thread con la tecnica delle fences. 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 modelsDesign 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

cambiare spesso la loro assegnazione durante l'esecuzione del programma. Per ottenere una assegnazione statica dei task, è necessario conoscere la suddivisione dei task all'inizio della computazione e questa suddivisione non cambierà durante l'esecuzione del programma. Questo approccio è utilizzabile quando il numero di iterazioni del ciclo for è noto in anticipo. Per ottenere una assegnazione dinamica dei task, si assegna un task a un thread non appena il thread diventa disponibile. Questo approccio richiede l'identificazione dei thread e può essere consigliabile quando il numero di task è molto maggiore del numero di thread disponibili. Di base, è più facile partire con tanti task piccoli anziché con pochi task grandi e poi cercare di dividerli. È consigliabile avere almeno tanti task quanti il numero di thread o core disponibili. In questo modo si evita di aumentare troppo i costi di overhead utilizzando troppi thread. Gli obiettivi della suddivisione dei task sono la flessibilità (non specifica per una specifica architettura) e l'efficienza (i task dovrebbero essere in grado di far lavorare i thread o core per un tempo più alto rispetto al tempo/costo necessario per gestire la parallelizzazione, come la creazione e lo swapping dei thread). Inoltre, i task dovrebbero essere abbastanza indipendenti tra loro in modo da non dover cambiare frequentemente la loro assegnazione.

dipenderetroppo gli uni dagli altri),- semplicità (il codice dovrebbe rimanere facile da leggere e debuggare)- Data decomposition: l’applicazione può computare diverse porzioni deldataset indipendentemente. Se i dati sono indipendenti tra loro, possiamodividerli in chunks per assegnare le diverse porzioni a diversi thread/core.→Come dividere i dati in chunks? forma e granularità, tipicamentemassimizzare il rapporto volume/superficie.Possiamo avere anche qui come nella task d. associazione statica o dinamicadei task. Buona norma da adottare quando una gran parte del computationtime è dominato dalla manipolazione di grandi strutture dati (calcolomatriciale, etc.) e/o quando sui differenti chunks devono essere eseguiteoperazioni simili.Data layout: AoS vs SoAArray of Structures: versione OOP di una struttura contenente vari array ognunocontenente 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. Latenza = 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 thread richiede la risorsa che è al momento utilizzata da thread ,2 1ma 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 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 un 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 assegna i task ai worker. →Task pool è un insieme di task che viene riempito tipicamente da un processo master e poi estratti dai worker che le eseguiranno. Necessita di accesso concorrente → evitare race conditions. Piccola variante: produttore-consumatore, in cui possonoe. In questo caso, i thread possono scambiarsi informazioni scrivendo e leggendo direttamente dalla memoria condivisa. - memoria distribuita: in questo caso, i thread comunicano tra loro attraverso messaggi inviati tramite canali di comunicazione. Ogni thread ha la propria memoria e invia messaggi agli altri thread per scambiare informazioni. Per implementare la comunicazione tra thread, è possibile utilizzare vari meccanismi come le code di messaggi, i semafori, i mutex e le variabili di condizione. Questi strumenti consentono di sincronizzare l'accesso alla memoria condivisa e di gestire la comunicazione tra i thread in modo sicuro e efficiente. È importante considerare che la scelta dell'implementazione della comunicazione tra thread dipende dalle specifiche esigenze dell'applicazione e dalle caratteristiche del sistema in cui viene eseguita.