False condivisione e pthreads

Question

Ho il seguente compito di dimostrare falsa condivisione e scritto un semplice programma:

#include <sys/times.h> 
#include <time.h> 
#include <stdio.h> 
#include <pthread.h> 

long long int tmsBegin1,tmsEnd1,tmsBegin2,tmsEnd2,tmsBegin3,tmsEnd3; 

int array[100]; 

void *heavy_loop(void *param) { 
    int index = *((int*)param); 
    int i; 
    for (i = 0; i < 100000000; i++) 
    array[index]+=3; 
} 

int main(int argc, char *argv[]) { 
    int  first_elem = 0; 
    int  bad_elem = 1; 
    int  good_elem = 32; 
    long long time1; 
    long long time2; 
    long long time3; 
    pthread_t  thread_1; 
    pthread_t  thread_2; 

    tmsBegin3 = clock(); 
    heavy_loop((void*)&first_elem); 
    heavy_loop((void*)&bad_elem); 
    tmsEnd3 = clock(); 

    tmsBegin1 = clock(); 
    pthread_create(&thread_1, NULL, heavy_loop, (void*)&first_elem); 
    pthread_create(&thread_2, NULL, heavy_loop, (void*)&bad_elem); 
    pthread_join(thread_1, NULL); 
    pthread_join(thread_2, NULL); 
    tmsEnd1 = clock(); 

    tmsBegin2 = clock(); 
    pthread_create(&thread_1, NULL, heavy_loop, (void*)&first_elem); 
    pthread_create(&thread_2, NULL, heavy_loop, (void*)&good_elem); 
    pthread_join(thread_1, NULL); 
    pthread_join(thread_2, NULL); 
    tmsEnd2 = clock(); 

    printf("%d %d %d\n", array[first_elem],array[bad_elem],array[good_elem]); 
    time1 = (tmsEnd1-tmsBegin1)*1000/CLOCKS_PER_SEC; 
    time2 = (tmsEnd2-tmsBegin2)*1000/CLOCKS_PER_SEC; 
    time3 = (tmsEnd3-tmsBegin3)*1000/CLOCKS_PER_SEC; 
    printf("%lld ms\n", time1); 
    printf("%lld ms\n", time2); 
    printf("%lld ms\n", time3); 

    return 0; 
} 

sono rimasto molto sorpreso quando ho visto i risultati (lo faccio funzionare sul mio processore i5-430M).

• Con condivisione errata, era 1020 ms.
• Senza condivisione errata, era 710 ms, solo il 30% più veloce invece del 300% (è stato scritto su alcuni siti che sarebbe più veloce del 300-400%).
• Senza usare pthreads, era 580 ms.

Per favore mostrami il mio errore o spiegami perché succede.

Answer 1

La condivisione errata è il risultato di più core con cache separate che accedono alla stessa regione della memoria fisica (sebbene non quello stesso indirizzo - che sarebbe vera condivisione).

Per comprendere la condivisione errata, è necessario comprendere le cache. Nella maggior parte dei processori, ogni core avrà la propria cache L1, che contiene i dati recentemente consultati. Le cache sono organizzate in "linee", che sono blocchi di dati allineati, in genere 32 o 64 byte di lunghezza (a seconda del processore). Quando si legge da un indirizzo che non è nella cache, l'intera riga viene letta dalla memoria principale (o una cache L2) in L1. Quando scrivi su un indirizzo nella cache, la riga contenente quell'indirizzo è contrassegnata come "dirty".

Ecco da dove viene l'aspetto della condivisione. Se più core leggono dalla stessa riga, ognuno di essi può avere una copia della linea in L1. Tuttavia, se una copia è contrassegnata come dirty, invalida la riga nelle altre cache. Se ciò non accadesse, le scritture fatte su un core potrebbero non essere visibili agli altri core fino a molto tempo dopo. Quindi la prossima volta che l'altro core andrà a leggere da quella linea, mancherà la cache e dovrà recuperare di nuovo la linea.

False condivisione si verifica quando i nuclei stanno leggendo e scrivendo a indirizzi diversi sulla stessa linea. Anche se non condividono i dati, le cache funzionano come se fossero così vicine.

Questo effetto dipende in gran parte dall'architettura del processore. Se avessi un processore single core, non vedresti l'effetto, poiché non ci sarebbe condivisione. Se le linee della cache fossero più lunghe, vedresti l'effetto in entrambi i casi "cattivo" e "buono", poiché sono ancora vicini. Se i tuoi core non condividono una cache L2 (che suppongo facciano), potresti vedere una differenza del 300-400% come hai detto, dato che dovevano andare fino alla memoria principale in una miss cache.

Potrebbe anche piacere sapere che è importante che ogni thread sia sia in lettura che in scrittura (+ = anziché =). Alcuni processori dispongono di write-through cache che significa che se un core scrive su un indirizzo non presente nella cache, non perde e recupera la linea dalla memoria. Contrastare questo con write-back cache, che mancano sulle scritture.

Answer 2

Ho cercato su google la funzione clock() in C.Esso il numero di clock della CPU trascorsi dall'inizio alla fine.Ora quando si eseguono due thread paralleli, il numero di cicli della CPU sarà (cicli di clock della CPU1 + clock cicli di cpu2). Penso che quello che vuoi sia un vero timer. Per questo usi clock_gettime() e otterrai l'output atteso.

Ho eseguito il codice con clock_gettime().Ho ottenuto questo:

con falsa condivisione 874.587381 ms

senza falsa condivisione 331.844278 ms

calcolo sequenziale 604.160276 ms