Paralelizar lecturas aleatorias parece funcionar bien, ¿por qué?

18

Considere el siguiente programa de computadora muy simple:

for i = 1 to n:
    y[i] = x[p[i]]

Aquí e y son matrices de n elementos de bytes, y p es una matriz de palabras de n elementos. Aquí n es grande, por ejemplo, n = 2 31 (de modo que solo una fracción insignificante de los datos cabe en cualquier tipo de memoria caché).Xynortepagnortenortenorte=231

Suponga que consiste en números aleatorios , distribuidos uniformemente entre 1 y n .pag1norte

Desde la perspectiva del hardware moderno, esto debería significar lo siguiente:

  • leer es barato (lectura secuencial)pag[yo]
  • leer es muy costoso (lecturas aleatorias; casi todas las lecturas son errores de caché; tendremos que buscar cada byte individual de la memoria principal)X[pag[yo]]
  • escribir es barato (escritura secuencial).y[yo]

Y esto es de hecho lo que estoy observando. El programa es muy lento en comparación con un programa que solo realiza lecturas y escrituras secuenciales. Excelente.

Ahora viene la pregunta: ¿qué tan bien se paraleliza este programa en las plataformas modernas de múltiples núcleos?


Mi hipótesis era que este programa no se paraleliza bien. Después de todo, el cuello de botella es la memoria principal. Un solo núcleo ya está perdiendo la mayor parte de su tiempo solo esperando algunos datos de la memoria principal.

Sin embargo, esto no fue lo que observé cuando comencé a experimentar con algunos algoritmos donde el cuello de botella era este tipo de operación.

Simplemente reemplacé el bucle for ingenuo con un bucle for paralelo paralelo OpenMP (en esencia, dividirá el rango en partes más pequeñas y ejecutará estas partes en diferentes núcleos de CPU en paralelo).[1,norte]

En las computadoras de gama baja, las aceleraciones fueron menores. Pero en las plataformas de gama alta me sorprendió que estaba obteniendo excelentes aceleraciones casi lineales. Algunos ejemplos concretos (los tiempos exactos pueden estar un poco apagados, hay muchas variaciones aleatorias; estos fueron solo experimentos rápidos):

  • 2 x Xeon de 4 núcleos (en total 8 núcleos): factoriza 5-8 aceleraciones en comparación con la versión de un solo hilo.

  • 2 x Xeon de 6 núcleos (en total 12 núcleos): factoriza entre 8 y 14 aceleraciones en comparación con la versión de un solo hilo.

Ahora esto fue totalmente inesperado. Preguntas:

  1. Precisamente, ¿por qué este tipo de programa es tan paralelo ? ¿Qué pasa en el hardware? (Mi conjetura actual es algo así: las lecturas aleatorias de diferentes hilos están "canalizadas" y la tasa promedio de obtener respuestas a estas es mucho mayor que en el caso de un solo hilo).

  2. ¿Es necesario usar múltiples hilos y múltiples núcleos para obtener aceleraciones? Si realmente se lleva a cabo algún tipo de interconexión en la interfaz entre la memoria principal y la CPU, una aplicación de un solo subproceso no podría hacerle saber a la memoria principal que pronto necesitará , x [ p [ i + 1 ] ] , ... ¿y la computadora podría comenzar a buscar las líneas de caché relevantes de la memoria principal? Si esto es posible en principio, ¿cómo lo logro en la práctica?X[pag[yo]]X[pag[yo+1]]

  3. ¿Cuál es el modelo teórico correcto que podríamos usar para analizar este tipo de programas (y hacer predicciones correctas del rendimiento)?


Editar: ahora hay algunos códigos fuente y resultados de referencia disponibles aquí: https://github.com/suomela/parallel-random-read

Algunos ejemplos de figuras de estadio ( ):norte=232

  • aprox. 42 ns por iteración (lectura aleatoria) con un solo hilo
  • aprox. 5 ns por iteración (lectura aleatoria) con 12 núcleos.
Jukka Suomela
fuente

Respuestas:

9

Olvide por un momento todos los problemas relacionados con el acceso a la memoria principal y al caché de nivel 3. Desde una perspectiva paralela, ignorando estos problemas, el programa se paraleliza perfectamente cuando se usa pagnortepagnortepagpag

Ahora, tomemos en cuenta los problemas de memoria. La velocidad súper lineal que realmente observó en su nodo basado en Xeon de alta gama se justifica de la siguiente manera.

nortenorte/ /pagpag

norte=231

norte

Finalmente, además de QSM (Memoria compartida en cola) , no conozco ningún otro modelo teórico paralelo que tenga en cuenta al mismo nivel la contención para acceder a la memoria compartida (en su caso, cuando usa OpenMP, la memoria principal se comparte entre los núcleos , y el caché siempre se comparte también entre los núcleos). De todos modos, a pesar de que el modelo es interesante, no obtuvo un gran éxito.

Massimo Cafaro
fuente
1
También puede ser útil considerar esto ya que cada núcleo proporciona una cantidad más o menos fija de paralelismo de nivel de memoria, por ejemplo, 10 x [] cargas en proceso en un momento dado. Con una probabilidad de 0.5% de un golpe en L3 compartido, un solo subproceso tendría una probabilidad de 0.995 ** 10 (95 +%) de requerir que todas esas cargas esperen una respuesta de memoria principal. Con 6 núcleos que proporcionan un total de 60 x [] lecturas pendientes, hay casi un 26% de posibilidades de que al menos una lectura llegue a L3. Además, cuanto más MLP, más puede programar el controlador de memoria los accesos para aumentar el ancho de banda real.
Paul A. Clayton
5

Decidí probar __builtin_prefetch () yo mismo. Lo publico aquí como respuesta en caso de que otros quieran probarlo en sus máquinas. Los resultados están cerca de lo que describe Jukka: aproximadamente una disminución del 20% en el tiempo de ejecución cuando se recuperan 20 elementos por delante frente a 0 elementos por delante.

Resultados:

prefetch =   0, time = 1.58000
prefetch =   1, time = 1.47000
prefetch =   2, time = 1.39000
prefetch =   3, time = 1.34000
prefetch =   4, time = 1.31000
prefetch =   5, time = 1.30000
prefetch =   6, time = 1.27000
prefetch =   7, time = 1.28000
prefetch =   8, time = 1.26000
prefetch =   9, time = 1.27000
prefetch =  10, time = 1.27000
prefetch =  11, time = 1.27000
prefetch =  12, time = 1.30000
prefetch =  13, time = 1.29000
prefetch =  14, time = 1.30000
prefetch =  15, time = 1.28000
prefetch =  16, time = 1.24000
prefetch =  17, time = 1.28000
prefetch =  18, time = 1.29000
prefetch =  19, time = 1.25000
prefetch =  20, time = 1.24000
prefetch =  19, time = 1.26000
prefetch =  18, time = 1.27000
prefetch =  17, time = 1.26000
prefetch =  16, time = 1.27000
prefetch =  15, time = 1.28000
prefetch =  14, time = 1.29000
prefetch =  13, time = 1.26000
prefetch =  12, time = 1.28000
prefetch =  11, time = 1.30000
prefetch =  10, time = 1.31000
prefetch =   9, time = 1.27000
prefetch =   8, time = 1.32000
prefetch =   7, time = 1.31000
prefetch =   6, time = 1.30000
prefetch =   5, time = 1.27000
prefetch =   4, time = 1.33000
prefetch =   3, time = 1.38000
prefetch =   2, time = 1.41000
prefetch =   1, time = 1.41000
prefetch =   0, time = 1.59000

Código:

#include <stdlib.h>
#include <time.h>
#include <stdio.h>

void cracker(int *y, int *x, int *p, int n, int pf) {
    int i;
    int saved = pf;  /* let compiler optimize address computations */

    for (i = 0; i < n; i++) {
        __builtin_prefetch(&x[p[i+saved]]);
        y[i] += x[p[i]];
    }
}

int main(void) {
    int n = 50000000;
    int *x, *y, *p, i, pf, k;
    clock_t start, stop;
    double elapsed;

    /* set up arrays */
    x = malloc(sizeof(int)*n);
    y = malloc(sizeof(int)*n);
    p = malloc(sizeof(int)*n);
    for (i = 0; i < n; i++)
        p[i] = rand()%n;

    /* warm-up exercise */
    cracker(y, x, p, n, pf);

    k = 20;
    for (pf = 0; pf < k; pf++) {
        start = clock();
        cracker(y, x, p, n, pf);
        stop = clock();
        elapsed = ((double)(stop-start))/CLOCKS_PER_SEC;
        printf("prefetch = %3d, time = %.5lf\n", pf, elapsed);
    }
    for (pf = k; pf >= 0; pf--) {
        start = clock();
        cracker(y, x, p, n, pf);
        stop = clock();
        elapsed = ((double)(stop-start))/CLOCKS_PER_SEC;
        printf("prefetch = %3d, time = %.5lf\n", pf, elapsed);
    }

    return 0;
}
Pat Morin
fuente
4
  1. El acceso a DDR3 está canalizado. http://www.eng.utah.edu/~cs7810/pres/dram-cs7810-protocolx2.pdf diapositivas 20 y 24 de muestran lo que sucede en el bus de memoria durante las operaciones de lectura canalizadas.

  2. (parcialmente incorrecto, ver más abajo) No son necesarios varios subprocesos si la arquitectura de la CPU admite la captación previa de caché. Modern x86 y ARM, así como muchas otras arquitecturas, tienen una instrucción de captación previa explícita. Además, muchos intentan detectar patrones en los accesos a la memoria y realizan la captación previa automáticamente. El soporte de software es específico del compilador, por ejemplo, GCC y Clang tienen __builtin_prefech () intrínseco para la captación previa explícita.

El hyperthreading de estilo Intel parece funcionar muy bien para programas que pasan la mayor parte del tiempo esperando errores de caché. En mi experiencia, en la carga de trabajo intensiva de computación, la aceleración va muy poco por encima del número de núcleos físicos.

EDITAR: Me equivoqué en el punto 2. Parece que si bien la captación previa puede optimizar el acceso a la memoria para un solo núcleo, el ancho de banda de memoria combinado de múltiples núcleos es mayor que el ancho de banda de un solo núcleo. Cuánto mayor, depende de la CPU.

El prefetcher de hardware y otras optimizaciones juntas hacen que la evaluación comparativa sea muy complicada. Es posible construir casos en los que la captación previa explícita tenga un efecto muy visible o inexistente en el rendimiento, siendo este punto de referencia uno de los últimos.

Juhani Simola
fuente
__builtin_prefech suena muy prometedor. Desafortunadamente, en mis experimentos rápidos no pareció ayudar mucho con el rendimiento de un solo hilo (<10%). ¿Qué grandes mejoras de velocidad debo esperar en este tipo de aplicación?
Jukka Suomela
Esperaba más. Como sé que la captación previa tiene un efecto significativo en DSP y juegos, tuve que experimentar yo mismo. Resultó que la madriguera del conejo es más profunda ...
Juhani Simola
Mi primer intento fue crear un orden aleatorio fijo almacenado en una matriz, luego iterar en ese orden con y sin captación previa ( gist.github.com/osimola/7917602 ). Eso trajo una diferencia de alrededor del 2% en un Core i5. Parece que la captación previa no funciona en absoluto o que el predictor de hardware comprende la indirección.
Juhani Simola
1
Entonces, probando eso, el segundo intento ( gist.github.com/osimola/7917568 ) accede a la memoria en secuencia generada por una semilla aleatoria fija. Esta vez, la versión de captación previa fue aproximadamente 2 veces más rápida que la no captación previa y 3 veces más rápida que la captación previa 1 paso adelante. Tenga en cuenta que la versión de captación previa realiza más cálculos por acceso a la memoria que la versión sin captación previa.
Juhani Simola
Esto parece depender de la máquina. Intenté el código de Pat Morin a continuación (no puedo comentar esa publicación porque no tengo la reputación) y mi resultado está dentro del 1.3% para diferentes valores de captación previa.
Juhani Simola