Falso compartir y pthreads

Question

tengo la siguiente tarea de demostrar la falsa compartición y escribió un programa simple:

#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; 
} 

que estaba muy sorprendido cuando vi los resultados (I ejecutarlo en mi procesador i5-430M).

• Con el intercambio falso, fue 1020 ms.
• Sin compartir falsamente, fue 710 ms, solo 30% más rápido en lugar de 300% (se escribió en algunos sitios que sería más rápido que 300-400%).
• Sin usar pthreads, era 580 ms.

Por favor muéstrame mi error o explica por qué sucede.

Answer 1

El intercambio falso es el resultado de varios núcleos con memorias caché separadas que acceden a la misma región de memoria física (aunque no esa misma dirección, eso sería compartir de verdad).

Para comprender el uso compartido falso, debe comprender los cachés. En la mayoría de los procesadores, cada núcleo tendrá su propio caché L1, que contiene los datos accedidos recientemente. Los cachés están organizados en "líneas", que son segmentos de datos alineados, generalmente de 32 o 64 bytes de longitud (dependiendo de su procesador). Cuando lee desde una dirección que no está en la memoria caché, toda la línea se lee desde la memoria principal (o una memoria caché L2) en L1. Cuando escribe en una dirección en el caché, la línea que contiene esa dirección está marcada como "sucia".

Aquí es donde entra el aspecto de compartir. Si varios núcleos están leyendo desde la misma línea, cada uno puede tener una copia de la línea en L1. Sin embargo, si una copia está marcada como sucia, invalida la línea en las otras cachés. Si esto no sucediera, las escrituras hechas en un núcleo podrían no ser visibles para otros núcleos hasta mucho más tarde. Así que la próxima vez que el otro núcleo vaya a leer desde esa línea, el caché omite y tiene que buscar la línea nuevamente.

False se produce cuando los núcleos están leyendo y escribiendo en diferentes direcciones en la misma línea. A pesar de que no están compartiendo datos, las memorias caché actúan como son, ya que están muy cerca.

Este efecto depende en gran medida de la arquitectura de su procesador. Si tuviera un solo procesador central, no vería el efecto en absoluto, ya que no habría intercambio. Si sus líneas de caché fueran más largas, vería el efecto tanto en los casos "malo" como "bueno", ya que todavía están muy juntos. Si sus núcleos no compartieron un caché L2 (que supongo que lo hacen), es posible que vea una diferencia de 300-400% como dijo, ya que tendrían que recorrer todo el camino hasta la memoria principal en una falla de caché.

También es posible que desee saber que es importante que cada hilo sea tanto de lectura como de escritura (+ = en lugar de =). Algunos procesadores tienen cachés de escritura cachés, lo que significa que si un núcleo escribe en una dirección que no está en la memoria caché, no falla y busca la línea desde la memoria. Contraste esto con caché de escritura cachés, que se pierden en las escrituras.

Answer 2

Busqué en google la función clock() en C. Le da el número de relojes de la CPU transcurridos desde el inicio hasta el final. Ahora cuando ejecuta dos hilos paralelos, el número de ciclos de la CPU será (ciclos de reloj de CPU1 + reloj ciclos de cpu2). Creo que lo que quieres es un reloj con temporizador real. Para esto, usa clock_gettime() y obtendrás el resultado esperado.

Ejecuté su código con clock_gettime().Tengo esto:

con el intercambio de falsa 874.587381 ms

sin distribución de falsa 331.844278 ms

cálculo secuencial 604.160276 ms