Programmazione concorrete e parallela su cloud (PCPC)

2018/2019

PROGRAMMAZIONE CONCORRENTE E

PARALLELA SUL CLOUD – APPUNTI

CORSO LAUREA MAGISTRALE – CLOUD COMPUTING 1

Sommario

1. ARCHITETTURA MULTI-CORE ............................................................................................................... 3

2. PARALLELIZZAZIONE ............................................................................................................................ 6

3. MUTUA ESCLUSIONE ........................................................................................................................... 7

4. CONCURRENT OBJECTS.......................................................................................................................15

5. SPINLOCKS (come si realizza un lock in maniera efficiente?)................................................................22

6. MONITOR ...........................................................................................................................................29

7. LISTE ...................................................................................................................................................36

8. CODE ..................................................................................................................................................47

9. SCHEDULING .......................................................................................................................................56

2

PROGRAMMAZIONE CONCORRENTE E PARALLELA SU CLOUD

INTRODUZIONE

Il rapidissimo sviluppo delle tecnologie hardware mette a dura prova le tecniche di progettazione di

software esistenti. Una delle leggi più citate dell'informatica è la legge di Moore ossia che il numero di

transistor per chip raddoppia ogni due anni, il che rende i computer molto più potenti . Questa

progressione è esponenziale. Però è vero che la velocità dei transistor aumenta ma rallenta la velocità di

clock e la potenza di calcolo, il problema è il thermal noise.

Thermal noise: effetto della termodinamica che disturba la crescita secondo la legge di Moore nel numero

di transistor, perché i processori devono essere alimentati a basso voltaggio cioè devono dissipare il meno

possibile l'energia e quindi limitare i problemi di raffreddamento. In pratica questo problema è che

tecnologicamente non è possibile avere tanti transistor che siano facili a raffreddare, che non dissipano

molta energia e che abbiano un clock molto alto. Thermal noises ci dice che non possiamo avere tutte

queste caratteristiche e si rinuncia alla velocità di clock ma non si rinuncia al numero di transistor.

La soluzione è il multiprocessor, cioè aumentare i core del processore ognuno con la propria cache e

tramite un bus ognuno acceda alla memoria condivisa.

Problemi di accesso alla memoria con multi core (“free lunch is over”)

- problemi di asincronia (Cache miss, Page Faults, context-switch dallo scheduler);

- Problemi di sincronizzazione (inconsistenza della memoria, interfoglamento, race condition).

1. ARCHITETTURA MULTI-CORE

I processori moderni combinano sia multi-core che multi-thread: ogni core è in grado di eseguire più

thread, usando parallelismo interno. Il multi-thread su core nasconde la latenza dell'accesso alla memoria:

un thread in attesa della memoria viene sostituito con un altro thread pronto.

Processori (o core) sono hardware che serve per eseguire thread e c’è un interconnessione a bus che

collega i processori tra loro e processori alla memoria.

Memoria è una gerarchia di componenti che memorizzano dati, da un livello (o più) di cache fino alla

(lenta) memoria principale.

Ciclo di un processore è il tempo per prelevare ed eseguire una sola istruzione. Mentre i tempi di un ciclo

macchina (ciclo di clock) sono cambiati nel tempo, ma il costo di accesso alla memoria non è cambiato nel

tempo se espresso in termini di cicli di macchina.

Interconessioni

- SMP (Symmetric Multiprocessing): i processori sono collegati da un bus, consente di fare bus

controllers sia sui processori che sulla memoria, ossia snooping bus (quello che viene scritto sul bus

viene inviato potenzialmente a tutti in quanto è possibile reperire questi valori restando in ascolto

sul bus). Il bus è poco scalabile in quanto alla crescita di n processori cresce anche il bus (sarei

costretto ad abbassare il clock per consentire la comunicazione tra processori e memoria). Infine

per simmetria intendiamo che il costo in termini di clock per un processore per accedere alla

memoria è uguale per tutti.

- NUMA (Non-Uniform Memory Access): l'idea è che ciascuno dei processori mantiene un pezzettino

della memoria e sono interconnessi in una rete punto-punto. Ciò significa che ogni nodo ha la

propria memoria locale, ma può accedere alla memoria degli altri processori. Il tempo di accesso la

memoria non è uniforme, in quanto un processore per accedere a una risorsa che si trova su un

altro processore deve mandare un messaggio all’interno della rete, passando attraverso diversi

processori fino alla destinazione, il tempo, quindi, per l’accesso alla memoria locale è più veloce per

alcuni e meno per altri, non uniforme.

Sia per SMP che per NUMA, la interconnessione tra core (processori) è una risorsa finita, da usare con

accuratezza.

Memoria

La memoria può essere vista come un array di word indicizzata da un indirizzo e la lettura della stessa è un

messaggio inviato dal processore alla memoria, a cui la memoria risponde inviando il valore. Mentre la 3

scrittura è un messaggio inviato dal processore alla memoria con indirizzo/nuovo valore, a cui la memoria

risponde con un ACK (ci possono volere anche centinaia di cicli macchina per un accesso alla memoria).

Cache

Memoria di piccola dimensione, situate vicino ai processori e più veloci. Il processore prova ad accedere

prima alla cache, se ha successo legge con velocità (hit) dalla cache, altrimenti deve leggere dalla memoria

principale. Centrale il concetto di hit ratio: rapporto tra hit e numero totale di richieste.

Le cache sono efficaci se:

- Il programma ha la locality: una locazione acceduta nel passato ha buone probabilità di essere

acceduta di nuovo;

- Per questi motivi, si accede alla memoria con una granularità più ampia della word in un insieme di

word vicine e dette cache lines;

Ci sono due tipi di cache: L1 cache situate sullo stesso chip del processore (1-2 cicli per l’accesso) e L2 cache

on oppure off-chip ma richiede decine di cicli per l’accesso. In generale le cache sono costose da costruire.

Nelle cache è necessario un algoritmo di replacement per aggiornare le linee memorizzate nella cache, è

cruciale anticipare le richieste dell’algoritmo senza conoscerle, in modo da non pagare penalty per cache

miss, se manca una locazione nella cache viene caricata l’intera cache lines in modo da avere tutte le

locazioni vicini che potrebbero essere richieste sfruttando il principio di località.

Ci sono diverse politiche di rimpiazzo di una cache lines:

- fully associative: qualsiasi linea è candidata all’eviction (più efficiente, meno cache miss);

- directed mapped: solo una linea può essere evicted (essenzialmente una funzione hash prende

l’indirizzo e lo spedisce in una certa direzione, directed mapped è meno costoso in termini di

hardware).

Mantenere le cache coerenti

Quando un processore legge o scrive un indirizzo che è in cache anche da un altro processore si ha la

memory contention. In caso di scrittura, la copia in cache dell’altro processore va invalidata. Ci sono diversi

protocolli per assicurare la coerenza delle cache.

Protocollo MESI (Intel): il nome deriva dai quattro stati in cui si può trovare una cache lines.

- Modified: la linea è stata modificata in cache, essa deve essere scritta, prima o poi, in memoria

principale, quindi manda in broadcast a tutti i processori una notifica che ha modificato quel valore,

in modo che se gli altri processori hanno quell’indirizzo in cache devono passare a invalid;

- Exclusive: Linea di cache non viene modificata, ma nessun altro processore la ha in cache;

- Shared: La linea di cache non è stata modificata, ma altri processori l'hanno in cache, potenziale

incoerenza. Grazie al bus snooping si riconosce che c'è un conflitto, poiché più processori hanno

quella linea di codice in cache (e i processori passano in questo stato);

- Invalid: la linea di cache non contiene dati validi, viene mandato un messaggio in broadcast di

richiesta del valore corretto, grazie al bus snooping il processore che ha modificato l’indirizzo (e

reso invalido il valore del processore corrente) si accorge che qualcuno vuole il valore corretto e a

questo punto risponde inviando i valori al processore che lo ha richiesto e scrivendolo in memoria

(passando poi di nuovo allo stato shared).

Spinning: un processore fa spinning se controlla ripetutamente una word in memoria, in attesa che qualche

altro processore cambi il valore, questa operazione è molto costosa in quanto uso sempre la CPU.

Su architettura SMP senza cache, spinning è molto inefficiente, consuma bus senza realizzare alcun lavoro

utile, compromettendo il lavoro dei processori che potrebbero usare il bus per cose utili.

Su architettura NUMA senza cache, lo spinning può essere accettabile se la variabile è nella memoria locale.

Però su un architettura SMP/NUMA con cache, spinning diventa molto efficiente: alla prima lettura, ha una

cache miss e carica in cache la variabile, se la variabile non è modificata, allora continua a leggere dalla

cache senza usare risorse, siano essi il bus condiviso oppure la comunicazione con un altro processore.

Appena la variabile risulta modificata, ha un cache miss e carica il valore e ferma lo spinning.

TASLock e TTASLock 4

Due thread che condividono una stessa risorsa devono usarla in mutua esclusione, ogni thread deve fare

lock della risorsa prima di usarla e unlock dopo averla usata.

Dati due algoritmi equivalenti chiamati TASlock (Test and set lock) e TTasLock (test and test and set lock)

che sono logicamente equivalenti, risulta:

- TASLock sembra essere il più semplice, ripetutamente cerca di accedere a effettuare il lock e ritorna

solo quando lo ha fatto;

- TTasLock sembra fare operazioni “inutili”, cioè prova a leggere quando il lock è disponibile (false) e

solo in quel caso, prova a fare il lock, con una operazione atomica. Se riesce, prova di nuovo a

leggere (solamente) ripetutamente, fino a quando non è di nuovo disponibile.

Anderson fece un esperimento, cioè l’accesso ad una piccola sezione critica per un milione di volte, il

risultato fu che TASLock funzionò peggio di TTASLock.

Bisogna tener conto del giusto trade-off tra efficienza e velocità.

Ad ogni getAndSet(true) di TASLock viene generato traffico sulla interconnessione (riscrivendo in memoria il

valore booleano) fino ad arrivare a saturare il bus condiviso, ritardando gli altri thread. Mentre lo spinning

di TTASLock legge da una copia in cache e non produce carico sulla interconnessione, rimanendo in loop

(sulla cache) senza fare nulla di costoso, niente abuso di risorse condivise. TTASLock non è scalabile perché

quando il lock viene rilasciato e la variabile viene messa false (viene modificata), tutte le copie in cache

sono invalidate e quindi tutti i processori in attesa (si rendono conto, grazie allo spinning che hanno un

valore invalido) leggono da memoria il nuovo valore, chiamano tutti getAndSet(true) causando un certo

traffico.

False Sharing

Quando processori dovrebbero accedere dati logicamente distinti, ma che generano un conflitto perché le

locazioni giacciono sulla stessa cache line (generando traffico aggiuntivo, sostituendo quei valori che non

sto usando ma che si trovano nella stessa cache line del valore che sto riscrivendo).

Trade off: cache line ampie aumentano possibilità di sfruttare località, ma aumentano anche la possibilità di

fare false sharing. Si dovrebbe fare un controllo a grana fine sui dati, però non sempre è possibile, dipende

dal compilatore (possibile in C/C++, poco in Java) in generale cercare di separare i dati che hanno

comportamenti diversi.

Relaxed Consistency (Consistenza rilassata)

Quando un valore è scritto in memoria, il valore mantenuto in cache e segnato come dirty: esso deve

essere ancora scritto in memoria (per quanto possibile) in modo da riuscire a risolvere più problemi

insieme. Le richieste di scrittura in memoria non vengono eseguite subito ma messe in un write buffer.

Vantaggi:

- Batching delle richieste: con una solo tempo di latenza vengono effettuate più scritture in memoria.

- Write absorption: se un valore in cache viene modificato e sta nel write buffer, se arriva una

successiva write dello stesso valore, la precedente non deve essere fatta (evito una scrittura in

memoria che poteva essere evitata).

Conseguenza: l'ordine in cui vengono richieste read/write in memoria non e l'ordine con cui avvengono. I

compilatori complicano le cose, per ottimizzare l'accesso alla memoria (fare batch) effettuano reordering

delle read/write in memoria, però questo può creare problemi se altri thread accedono a quei valori. 5

Esistono alcune tecniche ad alto livello (happens before) per il programmatore utili a gestire queste

problematiche.

Tecniche per il controllo del caching

Memory barriers: effettuano il flush dei buffer, inserite automaticamente per operazioni atomiche o

critiche, costose in termini di tempo ma necessarie per liberarsi di bug.

In Java quindi istruzioni di read/write fuori da un blocco synchronized possono essere riordinate, mentre le

read/write ad una variabile volatile non sono riordinate.

2. PARALLELIZZAZIONE

La legge di Amdahl

lo Speedup S di un programma X è il rapporto tra il tempo impiegato da un processore per eseguire X

rispetto al tempo impiegato da n processori per eseguire X.

Sia p la parte del programma X che è possibile parallelizzare: con n processori la parte parallela prende

tempo p/n mentre la parte sequenziale prende tempo (1-p).

La legge di Amdahl ci dice che la parte sequenziale del programma rallenta significativamente qualsiasi

speedup che possiamo pensare di ottenere. Quindi per velocizzare un programma non basta investire

sull’hardware, ma è assolutamente necessario e molto più cost-effective impegnarsi a rendere la parte

parallela predominante rispetto la parte sequenziale, anche solo il 5% di sequenziale rallenta in modo

significativo il programma.

Difficoltà della programmazione parallela

Problematiche inerenti alla complessità di utilizzare più strumenti di computazione in maniera coordinata,

problematiche di tipo tecnologico cioè come valutare le prestazioni, infine approccio culturale diverso viene

reso necessario (anche gli algoritmi sono profondamente diversi, si dovrebbe imparare prima a

programmare in maniera parallela perché è il modo in cui programmare).

Alcuni problemi sono “embarassungly parallel”, altri hanno solo una parte parallelizzabile con facilità (la

parte sequenziale è difficile da parallelizzare). Però non essendo sempre possibile parallelizzare tutto il

codice, grazie ad alcune architetture asimmetriche con core di grandi dimensioni ed altri più piccoli, quello

che si può fare è utilizzare il core grande per il codice sequenziale, mentre la parte parallelizzabile affidata

ai core piccoli.

Problematiche di tipo tecnologico: le prestazioni

E’ complesso valutare le prestazioni in ambito parallelo e concorrente.

Possiamo valutarle in metriche diverse ognuna valida in diversi scenari:

- Tempo di esecuzione; massa, è un altro collo di bottiglia, quindi

- scalabilità; limitare il data rate verso l’esterno);

- efficienza parallela (all’aumentare del - Network throughput (quantità di dati che

numero di processori ho un il network riesce a trasmettere, cosa che

miglioramento visibile delle prestazioni?); ha a che fare con la banda di

- requisiti di memoria; trasmissione);

- Throughput (quanti job per secondo - costi (di progettazione, implementazione,

riesce a misurare/realizzare il nostro verifica, ma soprattutto manutenzione

sistema, indicatore spesso collegato alla per cambiare ad esempio architettura);

scalabilità); - potenziale per riutilizzo e portabilità

- latenza (aspetto importante perché in (riutilizzo su diverse architetture e diversi

maniera trasversale ritarda tutte le linguaggi, come MPI, nel calcolo parallelo

attività); è più critico portare software da un

- I/O data rate (quando si parla di GPU o ambiente ad un altro rispetto al

dati di grandi dimensioni, quindi devono sequenziale, potremmo essere costretti a

necessariamente messi su memoria di riscrivere il programma da capo);

- requisiti hardware. 6

Problematiche di tipo “culturale”: approccio “ragionato” alle applicazioni

Per calcolo parallelo e concorrente, in particolare, i risultati vanno valutati con cura. E’ necessario

comprendere esattamente cosa viene nascosto dai modelli e dalle valutazioni algoritmiche. Quindi la

notazione “O grande” va usata con cura.

Secondo la legge di Amdhal a seconda della porzione parallela i codice la sfida ha come obiettivo qualcosa

16

di estremamente limitato, cioè posso impiegare 2 processori per arrivare ad uno speedup di qualche

decina ad algoritmi i cui la parte parallela è preponderante. Quindi la sfida è quanto riusciamo a rendere

parallelo il nostro codice.

Java e la Concorrenza

I thread in Java sono oggetti, istanze quindi di una classe Thread. Uso dell’interfaccia Runnable, si esegue il

metodo start().

Sei un trade acquisisce il lock di un oggetto A, nessun altro thread può acquisirlo fino a quando non è stato

rilasciato. In Java per acquisire il lock basta dichiarare un metodo synchronized ed in questo modo nessun

altro metodo dell'oggetto può essere invoca