Problema de velocidad con la gran matriz C utilizando Visual C de 64 bits

Question

Necesito leer una gran cantidad de datos en un búfer (aproximadamente 20 gig). Tengo 192 gb de DDram muy rápido disponible, así que no hay problema con el tamaño de la memoria. Sin embargo, estoy descubriendo que el siguiente código se ejecuta más lento y más lento cuanto más se acerca al búfer. El generador de perfiles de Visual C me dice que el 68% del tiempo de ejecución de 12 minutos está en las 2 instrucciones dentro del ciclo en myFunc(). Estoy ejecutando win7, 64 bits en un dell muy rápido con 2 CPU, 6 núcleos físicos cada uno (24 núcleos lógicos), y los 24 núcleos están completamente al máximo mientras se ejecuta esto.

#define TREAM_COUNT 9000 
#define ARRAY_SIZE ONE_BILLION 

#define offSet(a,b,c,d) (((size_t) ARRAY_SIZE * (a)) + ((size_t) TREAM_COUNT * 800 * (b)) + ((size_t) 800 * (c)) + (d)) 

void myFunc(int dogex, int ptxIndex, int xtreamIndex, int carIndex) 
{ 
    short *ptx = (short *) calloc(ARRAY_SIZE * 20, sizeof(short)); 

    #pragma omp parallel for 
    for (int bIndex = 0; bIndex < 800; ++bIndex) 
      doWork(dogex, ptxIndex, carIndex); 
} 

void doWork(int dogex, int ptxIndex, int carIndex) 
{ 

    for (int treamIndex = 0; treamIndex < ONE_BILLION; ++treamIndex) 
    { 
     short ptxValue  = ptx[ offSet(dogex, ptxIndex, treamIndex, carIndex) ]; 
     short lastPtxValue = ptx[ offSet(dogex, ptxIndex-1, treamIndex, carIndex) ]; 

     // .... 
    } 

} 

Answer 1

El código asignó 20 bloques de mil millones de entradas cortas. En un cuadro de Windows de 64 bits, un int corto tiene 2 bytes. Entonces la asignación es ~ 40 gigabytes.

Dice que hay 24 núcleos y están al máximo. El código tal como está no parece mostrar ningún paralelismo. La forma en que el código se paraleliza podría tener un profundo efecto en el rendimiento. Es posible que deba proporcionar más información.

-

Su problema básico, sospecho, gira en torno a los límites de comportamiento y de acceso a memoria caché.

En primer lugar, con dos CPU físicas de seis núcleos cada una, saturará por completo su bus de memoria. Probablemente usted tenga una arquitectura NUMA de todos modos, pero no hay control en el código sobre dónde se asigna su calloc() (por ejemplo, podría tener una gran cantidad de código almacenado en la memoria que requiere múltiples saltos para llegar).

Hyperthreading está activado. Esto reduce a la mitad los tamaños de caché. Dado que el código está ligado al bus de memoria, en lugar de computar vinculado, el hyperthreading es dañino. (Dicho esto, si la computación está constantemente fuera de los límites del caché, esto no cambiará mucho).

No está claro (¿se acabó/algo?) El código, cómo se accede a la matriz y el patrón de acceso y la optimización de ese patrón para honrar la optimización de la caché es la clave del rendimiento.

Lo que veo en cómo se calcula el offset() es que el código requiere constantemente la generación de nuevas búsquedas de direcciones virtuales a físicas, cada una de las cuales requiere algo así como cuatro o cinco accesos de memoria. Este es el rendimiento kiling, por sí mismo.

Mi consejo básico sería dividir la matriz en bloques de caché del nivel 2, dar un bloque a cada CPU y dejar que procese ese bloque. Puedes hacer eso en paralelo. En realidad, es posible que pueda usar hyperthreading para precargar la memoria caché, pero esa es una técnica más avanzada.

Answer 2

Esta optimización se librará de las lentas multiplicaciones:

... 
    int idx1 = offSet(dogex, ptxIndex, 0, carIndex); 
    int idx2 = offSet(dogex, ptxIndex-1, 0, carIndex); 

    for (int treamIndex = 0; treamIndex < ONE_BILLION; ++treamIndex) 
    {    
     short ptxValue  = ptx[ idx1 ]; 
     short lastPtxValue = ptx[ idx2 ]; 
     idx1+=800; 
     idx2+=800;    ... 

Answer 3

Debe intentar acceder a la matriz de una manera más lineal si es posible. Esto probablemente causa una cantidad excesiva de errores de caché.

Answer 4

Creo que el problema de este código es su patrón de acceso a la memoria. El hecho de que cada hilo de acceso a memoria en grandes (2 x 800 bytes) incrementos tiene 2 consecuencias negativas:

1. Al principio todos los subprocesos tienen acceso a la misma pieza de memoria, que está precargado en la memoria caché L2/L3 y es eficiente utilizado por cada hilo. Más adelante, los subprocesos avanzan con una velocidad ligeramente diferente y acceden a diferentes fragmentos de memoria, lo que provoca la eliminación de la caché (un subproceso carga datos en la memoria caché y desaloja los datos de allí, que aún no han sido leídos por otros subprocesos que lo necesitan).Como resultado, la misma pieza de memoria se lee en la memoria caché varias veces (en el peor de los casos, 12 veces, por el número de subprocesos en una CPU). Como el bus de memoria es relativamente lento, esto ralentiza todo el programa.
2. La memoria caché L1 también se utiliza de forma no eficiente: solo una pequeña parte de los datos en cada línea de caché es utilizada por núcleos de CPU.

La solución es permitir que cada hilo para acceder secuencialmente memoria (como el intercambio de c y d argumentos de la offSet(a,b,c,d) macro).