Un po’ di coerenza

Nello scorso post ho presentato OpenMP, un’estensione del C per scrivere programmi paralleli in maniera semplice. Poi ho fatto un esempio, che purtroppo non funziona: il programma parallelo va alla stessa velocità di quello sequenziale. Come mai?

Per capire come mai, bisogna andare a guardare un po’ meglio cosa ci sta sotto, ovvero l’architettura dei moderni processori, e la gerarchia della memoria. Nella seguente figura sono schematizzati i diversi tipi di memoria presenti un un moderno calcolatore (cliccare per ingrandire).

Gerarchia di memoria

La gerarchia della memoria

In alto abbiamo memoria veloce, ma costosa. Man mano che scendiamo in basso, abbiamo memoria più lenta ma meno costosa.

La memoria RAM che sta sui vostri PC, basata su tecnologia DRAM, è memoria veloce, ma non abbastanza per stare al passo con la velocità del processore. Un processore moderno lavora a cicli di clock intorno ai 2 Ghz. Purtroppo, il sistema di comunicazione tra processore e memoria – il bus - che sta sulla scheda madre e quindi al di fuori del chip,  non riesce a stare al passo, deve lavorare a una frequenza notevolmente inferiore. Questo vuol dire che per leggere un dato dalla memoria servono parecchi cicli di clock del processore, durante i quali lo stesso rimane bloccato in attesa che il dato venga caricato. Per come sono fatti i processori, questo è un grosso problema: il programma stesso si trova in memoria, insieme a tutte le variabili! Il processore ha bisogno di accedere alla memoria praticamente ad ogni istruzione.

Perché non utilizzare memoria più veloce e sullo stesso chip, così che possa funzionare alla stessa frequenza di clock del processore? Sarebbe in effetti possibile: la tecnologia SRAM, per esempio, permette di realizzare memoria molto veloce. Purtroppo, questa tecnologia è molto più costosa della tecnologia DRAM. Inoltre, 2 Gb di SRAM prenderebbero troppo spazio sul chip, e consumerebbero troppa energia.

Per cui, si utilizzano le cache: una quantità limitata di SRAM sul chip (o appena fuori) agisce come buffer temporaneo (o cache) verso una quantità molto più grande di DRAM lenta fuori dal chip.  Ogni volta che il processore legge un dato (o un’istruzione da eseguire) dalla memoria principale, tale dato viene memorizzato anche nella cache. La prossima volta che il dato verrà acceduto, il processore lo troverà direttamente in cache. Quindi il ritardo si ha solo sul primo accesso in lettura. Naturalmente, se la cache è già piena bisogna prima cancellare qualche altro dato già esistente. Di solito si cancella quello che non si accede da più tempo (Least Recently Used). La cache funziona benissimo per il principio di località dei programmi. Ad esempio, considerate il seguente pezzo di codice:

int sum = 0;
int a[10];
int i;
for (i=0; i<10; i++)
    sum+=a[i];

Quando il processore comincia ad eseguire il ciclo for, per dieci volte accederà alle variabili   i   e   sum   ed eseguirà sempre la stessa istruzione di somma. Mantenendo queste variabili in cache, si accellera il programma di molto rispetto allo stesso programma che esegua su un processore senza cache.

Tutto bene allora? Beh, su un sistema con un singolo processore in effetti va tutto bene. Prima di passare al caso multiprocessore, però, guardiamo cosa succede quando il processore deve scrivere una variabile (per esempio, la variabile sum dell’esempio precedente). Ci sono due possibilità: la tecnica write-through, e  la tecnica copy-back. Nel primo caso, ogni volta che si scrive un dato la modifica viene riportata immediatamente in memoria principale, e nel frattempo il processore può passare avanti a fare qualcos’altro (sempre che non sia necessario accedere alla memoria). La seconda tecnica, invece, tiene il dato in cache senza accedere alla memoria fino a che questo non è assolutamente necessario (ad esempio subito prima che il dato venga cancellato dalla cache). Ah, dimenticavo: ci possono essere più livelli di cache, da L1 (che è più piccola e più veloce) fino a L3 (chè è più grande e un po’ più lenta).

Ok, passiamo al caso multicore. Ogni core ha la sua cache di livello L1 (quella più veloce) privata, mentre le cache di livello L2 o L3 può essere condivisa. Il problema si ha sulla cache L1, quella privata.

Supponiamo che su ogni core esegua un thread diverso in parallelo, ma che entrambi i thread utilizzino la stessa variabile. Nell’esempio dello scorso post, si aveva il seguente codice:

#pragma omp parallel for
    for (int i=0; i<DIM; i++)
        for (int j=0; j<DIM; j++)
            if (array[i][j]) count++;

La variabile count è condivisa fra i vari thread. La prima volta che un thread legge il valore di count, tale valore viene memorizzato nella cache L1 del processore su cui esegue il thread. Se i thread eseguono in parallelo, ogni processore avrà una copia della variabile count sulla propria cache L1.

Il problema è che tali copie di count devono sempre avere tutte lo stesso valore, altrimenti l’algoritmo non funziona! Tecnicamente parlando, devono essere coerenti. Per cui, ogni volta che un thread ne modifica il valore (count++), il contenuto delle cache sugli altri processori deve essere aggiornato. Ci sono vari modi per fare questa cosa, si chiamano protocolli di coerenza, ma tutti richiedono di passare dalla cache condivisa di livello superiore, o dalla memoria centrale. Questo causa un notevole rallentamento del codice dei thread: in pratica, dato che tutti devono leggere e aggiornare un unico dato (count), è come se l’accesso a tale dato fosse sequenziale.

Quindi, siamo arrivati alla fine: è per questo specifico motivo che il programma precedente ha performance pari a quelle di un programma sequenziale. Per risolvere il problema, dobbiamo riscrivere il programma in modo che ogni thread faccia le somme parziali in una variabile diversa, in modo da evitare il problema della coerenza.  Tali somme parziali vanno poi integrate in un’unico risultato finale. Per far questo in maniera semplice e pulita ci serve qualche altra informazione su OpenMP. Alla prossima!

About these ads
Post a comment or leave a trackback: Trackback URL.

Commenti

  • juhan  On 17 luglio 2010 at 11:44

    Non me me vado di qui finché non vedo la soluzione ;-)
    È un po’ come una volta quando c’erano gli sceneggiati sulla RAI (c’era solo quella) e uno doveva aspettare tutta la settimana per vedere la prossima puntata.

  • laperfidanera  On 17 luglio 2010 at 17:45

    @ juhan
    Scusa, ti scrivo qui direttamente, ho letto il tuo stupendissssimo post da Popinga, grazie, grazie, grazie!

  • juhan  On 17 luglio 2010 at 20:15

    Grazie & Pasta a te.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

Iscriviti

Ricevi al tuo indirizzo email tutti i nuovi post del sito.

Unisciti agli altri 82 follower

%d blogger cliccano Mi Piace per questo: