Falso compartido y pthreads

Question

Tengo la siguiente tarea para demostrar el intercambio falso y escribí 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; 
} 

Me sorprendió mucho cuando vi los resultados (lo ejecuto en mi procesador de i5-430m).

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

Por favor, muéstreme mi error o explique por qué sucede.

Answer 1

Función breve sobre reloj () en C: le brinda la cantidad de relojes CPU transcurridos desde el inicio hasta el final. Entonces, cuando ejecuta dos hilos paralelos, el número de ciclos de CPU serán los ciclos de reloj de los ciclos de reloj CPU1 + de CPU2. Creo que lo que quieres es un reloj de temporizador real. Para esto, use clock_gettime () y debe obtener la salida esperada.

Ejecuté tu código con el clock_gettime (). Obtuve esto:

con falso compartido 874.587381 ms

sin falsas compartir 331.844278 ms

Computación secuencial 604.160276 ms

Answer 2

El intercambio falso es el resultado de múltiples núcleos con cachés separados que acceden a la misma región de la memoria física (aunque no es esa misma dirección, eso sería un verdadero intercambio).

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

Aquí es donde entra el aspecto de intercambio. 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 sucia, invalida la línea en los otros cachés. Si esto no sucedió, entonces las escrituras hechas en un núcleo podrían no ser visibles para otros núcleos hasta mucho más tarde. Entonces, la próxima vez que el otro núcleo se lea desde esa línea, el caché pierde, y tiene que volver a buscar la línea.

Falso Compartir ocurre cuando los núcleos están leyendo y escribiendo a diferentes direcciones en la misma línea. Aunque no comparten datos, los cachés actúan como lo son, ya que están muy cerca.

Este efecto depende en gran medida de la arquitectura de su procesador. Si tuviera un procesador de un solo núcleo, no verá el efecto en absoluto, ya que no habría compartir. Si sus líneas de caché fueran más largas, vería el efecto en los casos "malos" y "buenos", ya que todavía están muy juntos. Si sus núcleos no compartían un caché L2 (lo que supongo que hacen), es posible que veas la diferencia del 300-400% como dijiste, ya que tendrían que ir hasta la memoria principal en una falla de caché.

También le gustaría saber que es importante que cada hilo esté leyendo y escribiendo (+= en lugar de OF =). Algunos procesadores tienen escriba por medio de Caches, lo que significa que si un núcleo se escribe en una dirección que no está en el caché, no se pierde y obtiene la línea de la memoria. Contrastar esto con respóndeme Caches, que se pierden en las escrituras.