False condivisione e pthreads

Question

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

#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 (ho eseguito sul mio processore i5-430M).

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

Vi prego di mostrare il mio errore o spiegare perché succede.

Answer 1

Brief sulla funzione orologio () in C - Ti dà il numero di clock della CPU trascorsi dall'inizio fino alla fine. Così, quando si esegue due fili paralleli, il numero di cicli di CPU sarà cicli di clock di CPU1 + orologio cicli di CPU2. Penso che quello che vuoi è un vero e proprio orologio timer. Per questo uso clock_gettime () e si dovrebbe ottenere i risultati attesi.

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

con falsa condivisione 874.587381 ms

senza falsa condivisione 331.844278 ms

calcolo sequenziale 604.160276 ms

Answer 2

False condivisione è il risultato di più core con cache separate di accesso a stessa regione di memoria fisica (anche se non lo stesso indirizzo - che sarebbe vera condivisione).

Per capire falsa condivisione, è necessario capire le cache. Nella maggior parte dei processori, ciascun core avrà la propria cache L1, che detiene i dati di recente. Cache vengono organizzate in "linee", che sono allineati blocchi di dati, di solito 32 o 64 byte di lunghezza (a seconda del processore). Quando si legge da un indirizzo che non è nella cache, l'intera linea viene letta dalla memoria principale (o un cache L2) in L1. Quando si scrive a un indirizzo nella cache, la riga contenente l'indirizzo è marcato "sporco".

Ecco dove l'aspetto di condivisione entra in gioco. Se più core sono la lettura della stessa linea, ognuno di essi può avere una copia della linea in L1. Tuttavia, se una copia è contrassegnato sporco, si invalida la linea nelle altre cache. Se questo non è accaduto, poi scrive fatta su un core potrebbe non essere visibile agli altri nuclei solo molto più tardi. Così la prossima volta l'altro core va a leggere da quella linea, le cache miss, e deve prendere di nuovo la linea.

false di condivisione si verifica quando i nuclei sono la lettura e la scrittura di diversi indirizzi sulla stessa linea. Anche se non sono la condivisione dei dati, le cache si comportano come sono dal momento che sono così vicini.

Questo effetto è fortemente dipendente l'architettura del processore. Se si ha un processore single core, non sarebbe vedere l'effetto a tutti, dal momento che non ci sarebbe condivisione. Se le linee di cache erano più lunghe, si dovrebbe vedere l'effetto in entrambi i casi "cattivo" e "buono", dal momento che sono ancora vicini. Se i nuclei non condividevano una cache L2 (che sto cercando di indovinare che fanno), si potrebbe vedere la differenza 300-400% come hai detto, dal momento che avrebbero dovuto andare fino in fondo alla memoria principale su una cache miss.

Ti potrebbe piacere anche sapere che è importante che ogni thread è sia la lettura e la scrittura (+ = invece di =). Alcuni processori hanno write-through cache che significa che se un nucleo scritture ad un indirizzo non nella cache, non manca e recuperano la linea dalla memoria. Questo contrasto con write-back di cache, che fanno perdere lo scritture.