Optimización de la función de transposición de arrays

Question

Estoy trabajando en una tarea y he estado atascado durante horas en mi solución. El problema que nos ha surgido es optimizar el siguiente código, para que funcione más rápido, independientemente de lo desordenado que se vuelva. Se supone que debemos usar cosas como explotar bloques de caché y desenrollar bucles.

Problema:

//transpose a dim x dim matrix into dist by swapping all i,j with j,i 
void transpose(int *dst, int *src, int dim) { 
    int i, j; 

    for(i = 0; i < dim; i++) { 
     for(j = 0; j < dim; j++) { 
       dst[j*dim + i] = src[i*dim + j]; 
     } 
    } 
} 

Lo que tengo hasta ahora:

//attempt 1 
void transpose(int *dst, int *src, int dim) { 
    int i, j, id, jd; 

    id = 0; 
    for(i = 0; i < dim; i++, id+=dim) { 
     jd = 0; 
     for(j = 0; j < dim; j++, jd+=dim) { 
       dst[jd + i] = src[id + j]; 
     } 
    } 
} 

//attempt 2 
void transpose(int *dst, int *src, int dim) { 
    int i, j, id; 
    int *pd, *ps; 
    id = 0; 
    for(i = 0; i < dim; i++, id+=dim) { 
     pd = dst + i; 
     ps = src + id; 
     for(j = 0; j < dim; j++) { 
       *pd = *ps++; 
       pd += dim; 
     } 
    } 
} 

Algunas ideas, por favor, corríjanme si me equivoco:

He pensado en bucle desenrollado pero No creo que eso ayude, porque no sabemos si la matriz NxN tiene dimensiones primarias o no. Si lo comprobé, incluiría cálculos en exceso que ralentizarían la función.

Los bloques de caché no serían muy útiles, porque no importa qué, vamos a acceder linealmente a una matriz (1,2,3,4) mientras que a la otra vamos a acceder en saltos de N. Si bien podemos obtener la función de abusar de la memoria caché y acceder al bloque src más rápido, todavía llevará mucho tiempo colocarlos en la matriz dst.

También he intentado usar punteros en lugar de accesadores de arreglo, pero no creo que realmente acelere el programa de ninguna manera.

Cualquier ayuda sería muy apreciada.

Gracias

Answer 1

El bloqueo de caché puede ser útil. Por ejemplo, digamos que tenemos un tamaño de línea de caché de 64 bytes (que es lo que x86 usa en estos días). Entonces, para una matriz lo suficientemente grande como para que sea más grande que el tamaño de caché, entonces si transponemos un bloque de 16x16 (desde sizeof (int) == 4, entonces 16 ints caben en una línea de caché, asumiendo que la matriz está alineada en un bounday) necesitamos cargar 32 (16 de la matriz de origen, 16 de la matriz de destino antes de que podamos ensuciarlos) guardar en caché las líneas de la memoria y almacenar otras 16 líneas (aunque las tiendas no sean secuenciales). Por el contrario, sin el bloqueo del caché, la transposición de los elementos 16 * 16 equivalentes requiere que carguemos 16 líneas de caché desde la matriz de origen, pero 16 * 16 = 256 líneas de caché que se cargarán y luego se almacenarán para la matriz de destino.

Answer 2

Unrolling es útil para matrices grandes.
Necesitará un código para manejar el exceso de elementos si el tamaño de la matriz no es un múltiplo de las veces que se desenrolla. Pero esto estará fuera del ciclo más crítico, por lo que para una matriz grande vale la pena.

En cuanto a la dirección de acceso, puede ser mejor leer linealmente y escribir en saltos de N, en lugar de viceversa. Esto se debe a que las operaciones de lectura bloquean la CPU, mientras que las operaciones de escritura no lo hacen (hasta un límite).

Otras sugerencias:
1. ¿Se puede usar la paralelización? OpenMP puede ayudar (aunque si se espera que entregues un solo rendimiento de CPU, no es bueno).
2. Desarme la función y léala, centrándose en el lazo más interno. Puede encontrar cosas que no notaría en el código C.
3. El uso de contadores decrecientes (deteniéndose en 0) podría ser un poco más eficiente que aumentar los contadores.
4. El compilador debe suponer que src y dst pueden alias (señalar a la misma memoria o superponerse), lo que limita sus opciones de optimización. Si de alguna manera puede decirle al compilador que no se pueden superponer, puede ser de gran ayuda. Sin embargo, no estoy seguro de cómo hacerlo (tal vez use el calificador restrict).

Answer 3

Sólo una idea de cómo implementar desenrollar:

void transpose(int *dst, int *src, int dim) { 
    int i, j; 
    const int dim1 = (dim/4) * 4; 

    for(i = 0; i < dim; i++) { 
     for(j = 0; j < dim1; j+=4) { 
       dst[j*dim + i]  = src[i*dim + j]; 
       dst[(j+1)*dim + i] = src[i*dim + (j+1)]; 
       dst[(j+2)*dim + i] = src[i*dim + (j+2)]; 
       dst[(j+3)*dim + i] = src[i*dim + (j+3)]; 
     } 
     for(; j < dim; j++) { 
       dst[j*dim + i] = src[i*dim + j]; 
     } 
     __builtin_prefetch (&src[(i+1)*dim], 0, 1); 
    } 
} 

De cource debe quitar el conteo (como i*dim) del bucle interno, como ya hizo en sus intentos.

La captación previa de caché se puede usar para la matriz de origen.

Answer 4

probablemente sepa esto pero register int (le dice al compilador que sería inteligente poner esto en el registro). Y hacer el int unsigned, puede hacer que las cosas vayan un poco más rápido.

Answer 5

Desorden no es un problema, entonces: Agregaría una bandera transposed a cada matriz. Este indicador indica si el conjunto de datos almacenados de una matriz debe interpretarse en orden normal o transpuesto.

Todas las operaciones de matriz deberían recibir estas nuevas marcas además de cada parámetro de matriz. Dentro de cada operación, implemente el código para todas las combinaciones posibles de banderas. Quizás las macros pueden guardar escritura redundante aquí.

En esta nueva implementación, la transposición de la matriz simplemente alterna el indicador: El espacio y el tiempo necesarios para la operación de transposición son constantes.