mejorar la localidad y disminuir la contaminación de la caché en una implementación de reconstrucción de imágenes médicas

Question

Estoy haciendo una investigación para mi Universidad relacionada con un algoritmo de reconstrucción de imágenes para uso médico.

estoy atascado en algo hasta 3 semanas, tengo que mejorar el rendimiento del siguiente código:

for (lor=lor0[mypid]; lor <= lor1[mypid]; lor++) 
{ 
    LOR_X = P.symmLOR[lor].x; 
    LOR_Y = P.symmLOR[lor].y; 
    LOR_XY = P.symmLOR[lor].xy; 
    lor_z = P.symmLOR[lor].z; 
    LOR_Z_X = P.symmLOR[lor_z].x; 
    LOR_Z_Y = P.symmLOR[lor_z].y; 
    LOR_Z_XY = P.symmLOR[lor_z].xy; 

    s0 = P.a2r[lor]; 
    s1 = P.a2r[lor+1]; 

    for (s=s0; s < s1; s++) 
    { 
    pixel  = P.a2b[s]; 
    v   = P.a2p[s]; 

    b[lor] += v * x[pixel]; 

    p   = P.symm_Xpixel[pixel]; 
    b[LOR_X] += v * x[p]; 

    p   = P.symm_Ypixel[pixel]; 
    b[LOR_Y] += v * x[p]; 

    p   = P.symm_XYpixel[pixel]; 
    b[LOR_XY] += v * x[p]; 


    // do Z symmetry. 
    pixel_z = P.symm_Zpixel[pixel]; 
    b[lor_z] += v * x[pixel_z]; 


    p   = P.symm_Xpixel[pixel_z]; 
    b[LOR_Z_X] += v * x[p]; 


    p   = P.symm_Ypixel[pixel_z]; 
    b[LOR_Z_Y] += v * x[p]; 

    p   = P.symm_XYpixel[pixel_z]; 
    b[LOR_Z_XY] += v * x[p]; 

    } 

} 

para cualquier persona que quiera saber, el código implementa la función de avance MLEM y todos las variables son FLOAT.

Después de varias pruebas, me di cuenta de que la gran demora estaba en esta parte del código. (ya sabes, la regla 90 - 10).

Más tarde, utilicé Papi (http://cl.cs.utk.edu/papi/) para medir errores de caché de L1D. Como pensé, Papi confirmó que el rendimiento disminuye debido a una mayor cantidad de errores, particularmente para el acceso aleatorio al vector b (de gran tamaño).

Leyendo información en Internet Solo conozco dos opciones para mejorar el rendimiento hasta el momento: mejorar la ubicación de los datos o disminuir la contaminación de los datos.

Para hacer la primera mejora, voy a tratar de cambiar el código de caché de ser conscientes, al igual que se nos propuso por Ulrich Drepper en Lo que todo programador debe saber sobre la memoria (www.akkadia.org/drepper/ cpumemory.pdf) A.1. Multiplicación de matrices.

Creo que bloqueando el SpMV (Multiplicación escasa matriz-vector) mejorará el rendimiento.

Por otro lado, cada vez que el programa intentaba acceder al vector b, teníamos lo que se conoce como contaminación del caché.

¿Hay alguna manera de cargar el valor del vector b con la instrucción SIMD sin usar el caché?

Además, es posible usar una función como void _mm_stream_ps (float * p, __m128 a) para almacenar UN valor de flotación en el vector b sin contaminar el Cache?

No puedo usar _mm_stream_ps porque siempre almacena 4 flotantes pero el acceso al vector b es claramente aleatorio.

Espero ser claro en mi dilema.

Más información: v es el valor de columna de una tienda de matriz dispersa con formato CRS. Me di cuenta de que se podía hacer otra optimización si intentaba cambiar el formato CRS a otro, sin embargo, como dije antes, hice varias pruebas durante meses y sé que la disminución del rendimiento está relacionada con el acceso aleatorio en el vector b. de 400.000.000 L1D Faltas Puedo ir a 100 ~ Faltas cuando no almaceno en el vector b.

Gracias.

Answer 1

Yo diría que, al principio, intente ayudar un poco a su compilador.

• declaran los límites para el bucle externo como const antes del bucle.
• declarar todas las variables que pueden (todo el LOR_..) como variables locales, algo como: float LOR_X = P.symmLOR[lor].x; o size_t s0 = P.a2r[lor];
• Esto también, en particular para el bucle las variables si le sucede que tiene moderna, C99 compatible, compilador: for (size_t s=s0; s < s1; s++)
• Separar la carga y almacenar para su b vector. Las ubicaciones de los artículos a los que acceda, no dependen de en s.Por lo tanto crear una variable local para mantener el valor real de todos los casos distintos que usted maneja antes del bucle interno, actualizar estas variables locales dentro de la bucle interno, y almacenar los resultados después del bucle interno .
• Quizás separe su lazo interno en varios. Los cálculos de índice son relativamente baratos, y luego su sistema podría reconocer mejor el acceso de transmisión a algunos de sus vectores .
• Mire el ensamblador que produce su compilador e identifique el código para el lazo interno. Experimente un bit para mover la mayor cantidad de carga "distante" y almacene fuera de ese bucle.

Editar: después de volver a leer la respuesta de Gravitron y su comentario, lo importante aquí es realmente para declarar las variables locales como sea posible y para comprobar el ensamblador que el compilador consigue que las cargas de caché-desaparecidos y almacena fuera del bucle interno.

Answer 2

Una optimización simple para reducir el acceso aleatorio en el vector b sería nunca escribir en el vector b dentro del ciclo for interno.

En lugar de eso, cargue todos los valores necesarios del vector B en variables temporales, haga todo el ciclo interno durante la actualización de estas variables temporales, luego vuelva a escribir las variables temporales en el vector B.

Las variables temporales se encontrarán en el peor de los casos en las mismas líneas de caché, dependiendo de su compilador y entorno también puede indicar que el compilador use registros para estas variables.

Answer 3

Ni siquiera voy a fingir que sé lo que está haciendo el código :) Pero una posible causa de algún tipo de acceso de memoria adicional es Aliasing: si el compilador no puede estar seguro de que b, x, y las diversas matrices P.symm no se superponga, luego escribe en b y afectará cómo se pueden programar las lecturas de x y P.symm. Si el compilador es particularmente pesimista, incluso podría forzar la recuperación de los campos de P de la memoria. Todo esto contribuirá a las fallas de caché que está viendo. Dos formas sencillas de mejorar esto son:

1. Uso __restrict en b. Esto garantiza que b no se superpone con las otras matrices, por lo que las escrituras no afectarán las lecturas (o escrituras) de otras matrices.

2. Reordenar las cosas para que todo el lee de P.symm 's son primero, y luego la lee de x, y finalmente todas las escrituras en b. Esto debería romper algunas de las dependencias en las lecturas y el compilador programa las lecturas de P.symm en paralelo, luego las lecturas de x en paralelo, y con suerte las escribe en b con sensatez.

Otra cosa estilística (lo que ayudará con el punto # 2) es no volver a utilizar variables para p tanto. No hay ninguna razón por la que no pueda tener, p. p_x, p_y, p_xy, etc., y facilitará la reordenación del código.

Una vez que todo está en su lugar, puede comenzar a rociar las instrucciones de captación previa (es decir, __builtin_prefetch en gcc) antes de las fallas de caché conocidas.

Espero que ayude.

Answer 4

Estas son buenas respuestas, y preguntaría ¿por qué tanta indexación? por valores de índice que no cambian mucho a nivel local?

Además, no te mataría hacer algunas pausas aleatorias para ver dónde está normalmente.