Salvadera

barbo gracioso 25 de julio de 2011 a las 00:59

Multiplicación de matrices paralelas o magia de caché. un poco de investigacion

Introducción

Este artículo trata sobre un pequeño estudio que se realizó por pura curiosidad. Pero como los resultados fueron interesantes, decidí publicarlos. Se discutieron los conceptos básicos de la computación paralela mediante una tarea simple y conveniente: la multiplicación de matrices.

¡Hay varias imágenes debajo del corte!

Formalmente, la tarea se plantea de la siguiente manera:
Dadas dos matrices A y B de dimensión NxN. Es necesario calcular su producto: matriz C.
C[i][j] = suma de k de 1 a N A[i][k]*B[k][j].

Solución sin computación paralela

El algoritmo más simple para resolver este problema con asintóticas es el siguiente:

para (int i = 0; i< n; ++i)
para (int j = 0; j< n; ++j){
c[i][j] = 0;
para (int k = 0; k< n; ++k)
c[i][j] = a[i][k]*b[k][j];
}

Existe un truco muy conocido que le permite acelerar el código anterior entre 4 y 5 veces. Esto reemplaza la matriz b con la matriz bt, que contiene la matriz B transpuesta:

para (int i = 0; i< n; ++i)
para (int j = 0; j< n; ++j)
bt[i][j] = b[j][i];
para (int i = 0; i< n; ++i)
para (int j = 0; j< n; ++j){
c[i][j] = 0;
para (int k = 0; k< n; ++k)
c[i][j] = a[i][k]*bt[j][k];
}

* Este código fuente fue resaltado con Resaltador de código fuente .

La aceleración en este caso está relacionada con el diseño de la caché del procesador. Al acceder a una celda de memoria, no solo ella, sino también varias celdas vecinas se escriben en la memoria caché. En el primer caso, los elementos del array b, al que accedemos en un bucle a través de k, están en filas diferentes, pero en la misma columna, y por tanto en RAM están ubicados a una distancia igual al tamaño de una fila de la matriz. En el segundo caso, accedemos secuencialmente a los elementos de una línea de la matriz bt, que se encuentran en la memoria en una fila.

Solución de computación paralela

Dado que cada elemento de la matriz C se calcula independientemente de los demás y las matrices A y B no cambian, para calcular el producto en paralelo basta simplemente con indicar qué elementos de C a qué hilo calcular.
Para ello se creó una función que recibe 2 números: lf y rg. La función calcula las filas de la matriz C desde lf hasta rg inclusive, utilizando la matriz B original:

#definir forn(i, n) para (int i = 0; i< int (n); ++i)

estructura matrizMulParam(
int lf, rg;
matrizMulParam(int cLf = 0, int cRg = 0): lf(cLf), rg(cRg)()
};

Matriz DWORDMulNoHack(LPVOID p)(
para (int i = ((matrixMulParam*)p)->lf; i<= ((matrixMulParam*)p)->rg; ++yo)
forma(j, n)(
c[i][j] = 0;
forma(k, n)
c[i][j] += a[i][k] * b[k][j];
}

Eliminar ((matrixMulParam*)p);
devolver 0;
}

* Este código fuente fue resaltado con Resaltador de código fuente .

De la misma forma, se escribió una función utilizando una matriz transpuesta.

Recopilación de datos de tiempo de funcionamiento

Los cálculos se realizaron el 4 diferentes computadoras con diferentes procesadores:

1. Intel átomo N550
   • Frecuencia del reloj: 1,5GHz
   • Número de núcleos: 2
   • Número de hilos: 4
     Esto no es un error tipográfico. Aquí hay un enlace al sitio web de Intel y aquí hay capturas de pantalla del Administrador de tareas y del Administrador de dispositivos de mi netbook.
   • Tamaño de caché L2: 1 MB
2. Intel Core2Duo P8600
   • Frecuencia de reloj: 2,4 GHz
   • Número de núcleos: 2
   • Número de hilos: 2
   • Tamaño de caché L2: 3 MB
3. Intel Core2Quad Q6600
   • Frecuencia de reloj: 2,4 GHz
   • Número de núcleos: 4
   • Número de hilos: 4
   • Tamaño de caché L2: 8 MB
4. Instancia extragrande con CPU alta de Amazon EC2,
   aproximadamente igual en potencia al segundo Intel Xeon E5410
   • Frecuencia de reloj: 2,33 GHz
   • Número de núcleos: 4 (8 en total)
   • Número de transmisiones: 4 (8 en total)
   • Tamaño de caché L2: 12 (24 en total) MB

Para obtener estadísticas se variaron los siguientes parámetros:

• Tamaño de matriz: 1000x1000 o 2000x2000.
  Las matrices se llenaron con números enteros pseudoaleatorios del 1 al 1000.
• Número de hilos de 1 a 16.
• Utilizando la matriz B original o una transpuesta.

Para cada combinación de los parámetros especificados, los cálculos se realizaron al menos 5 veces y como resultado se utilizó la media aritmética de los tiempos de ejecución del programa.

Resultados

Como estaba mirando diferentes procesadores con diferentes parámetros, entonces, a modo de comparación, no puede utilizar el tiempo de ejecución absoluto del programa en milisegundos. Para hacer esto, introducimos el tiempo de operación relativo: la relación, como porcentaje, entre el tiempo de calcular el producto de matrices con ciertos parámetros y el tiempo de calcular el producto de las mismas matrices con los mismos parámetros en un hilo.

Veamos los gráficos de la dependencia del tiempo de funcionamiento relativo del número de subprocesos para el algoritmo utilizando la matriz original:

Este gráfico cumple con todas las expectativas: el tiempo de ejecución disminuye a medida que aumenta el número de subprocesos hasta el número de núcleos, y luego permanece aproximadamente constante. Sin embargo, si los resultados de Core2Quad y Xeon difieren de los ideales en menos del 1%, entonces para Core2Duo y Atom los resultados son peores.

Cuando el tamaño de los datos aumenta 4 veces, el retraso se vuelve aún mayor. Especialmente en el Atom N550 (las netbooks claramente no están diseñadas para multiplicar matrices de 2000x2000 por ). Esto se explica de la misma manera que la reducción de tiempo al utilizar una matriz transpuesta. Cuando hay varios subprocesos que acceden a diferentes áreas de la memoria, cada subproceso individualmente funcionará más lento que un subproceso que atraviesa la memoria en orden. Pero a pesar de esto, varios hilos funcionarán más rápido que uno.

Los siguientes gráficos representan el tiempo de ejecución relativo frente al número de subprocesos del algoritmo utilizando una matriz transpuesta:


Dado que la aceleración cuando se utiliza una matriz transpuesta está asociada con más uso efectivo caché, luego comienza a funcionar peor si aumenta el número de subprocesos y se interrumpe la secuencia de acceso a la memoria. Atom y Core2Quad se comportan de manera interesante: el gráfico de Atom se mantuvo prácticamente sin cambios, mientras que el rendimiento de Core2Quad se deterioró drásticamente al pasar de 1000x1000 a 2000x2000.
Esto se explica de la siguiente manera: con un tamaño de matriz de 1000x1000, tenemos 2 arrays (ayb) con 1000*1000 elementos de 4 bytes (int). Eso son aproximadamente 8 megabytes. La caché de 1 MB del Atom N550 contiene sólo 1/8 de todos los datos, cuando la caché Core2Quad cabe en todos los datos. Cuando ampliamos las matrices a 2000x2000, aumentamos la cantidad de datos 4 veces. Por lo tanto, ahora solo 1/4 de los datos cabe en el caché Core2Quad y el truco de transposición se vuelve menos efectivo, no funcionó en el procesador Atom y continúa sin funcionar.
Para ilustrar el efecto descrito anteriormente, considere dos gráficos más.
Llamemos a la eficiencia del uso de una matriz transpuesta la relación entre el tiempo de ejecución del algoritmo que usa la matriz transpuesta bajo ciertos parámetros y el tiempo de ejecución del algoritmo que usa la matriz original bajo los mismos parámetros.


Este gráfico ilustra bien todo lo anterior. La eficiencia de Core2Quad y Xeon disminuye debido a la gran cantidad de subprocesos simultáneos que acceden a diferentes áreas de la memoria y destruyen el caché. La eficiencia del Core2Duo casi no cambia debido al hecho de que sólo tiene 2 subprocesos ejecutándose a la vez y porque el tamaño de la caché no es tan grande como el de los procesadores anteriores.
La siguiente figura contiene el mismo gráfico, solo que con la adición de indicadores Atom N550.


Nunca he podido entender este aumento en la eficiencia del caché y el truco de transposición. Espero que podamos llegar al fondo de la verdad en los comentarios.

Conclusión

En primer lugar, La memoria caché del procesador afecta significativamente a la velocidad de ejecución del programa, aunque en la mayoría de los casos ni siquiera pensamos en ello.
En segundo lugar, El código fuente y, en general, todo lo que utilicé en este artículo se pueden descargar desde el enlace en un archivo.
En tercer lugar, compilador usado g++ 4.5.2, línea de compilación g++ -Pared -O,
Windows 7 y Windows Server 2008 R2 en Amazon.
Gracias por su atención.
Saludos cordiales, Iván.

PD Así fue el proceso de recopilación de datos

Etiquetas: computación paralela, multiplicación, matriz, c más más

Este artículo no está sujeto a comentarios porque su autor aún no es miembro de pleno derecho de la comunidad. Sólo podrá ponerse en contacto con el autor después de que reciba una invitación de alguien de la comunidad. Hasta ese momento, su nombre de usuario estará oculto por un alias.

Este artículo discutirá Estándares POSIX Hilos y OpenMP. Es decir, la multiplicación paralela de matrices NxN utilizando estos estándares y su comparación.

1) Código de multiplicación de matrices usando OpenMP.

#incluir #incluir #incluir #incluir #incluir #incluir #incluir #incluir #incluir #incluir #incluir #incluir int *alloc_matrix(int ​​​​tamaño)( int *matrix = (int*)malloc(tamaño * tamaño * tamañode(int)); printf("matriz %dx%d asignada\n", tamaño, tamaño); devuelve matriz ) void del_matrix(int ​​*matrix)( free(matrix); ) double dtime())( struct timeval tv; struct timezone tz; double t; gettimeofday(&tv, &tz); t = (double)tv.tv_sec + (double)tv .tv_usec*1e-6; return(t); int main() ( int N = 50; int THR = 2; int i, j, k; printf("Ingrese el número de subprocesos\n" ); scanf("% i",&THR); omp_set_dynamic(0); omp_set_num_threads(THR); printf("Ingrese el tamaño de la matriz\n"); ); int *B = alloc_matrix(N); int *C = alloc_matrix(N); int rand_num(hora(NULL));

2) Código de multiplicación de matrices usando Pthread.

#incluir #incluir #incluir #incluir #incluir #incluir #incluir #incluir #include #include #define TAMAÑO 50 int *alloc_matrix(int ​​tamaño)( int *matrix = (int*)malloc(tamaño * tamaño * tamañode(int)); printf("matriz %dx%d asignada\n" , tamaño, tamaño de retorno matriz; ) void del_matrix(int ​​*matrix)( free(matrix); ) double dtime())( struct timeval tv; struct timezone tz; double t; gettimeofday(&tv, &tz); t = (doble) tv.tv_sec + (doble)tv.tv_usec*1e-6; return(t); struct Matrix_args( int *m1; int *m2; int *ans; int tamaño; int inicio; int fin; ) ARG; void *multiply_matrix(void *pargs)( struct Matrix_args *args = (struct Matrix_args *) pargs; int i, j, k, l, m, tmp = 0; double t0 = dtime(); int *m1 = args-> m1; int *m2 = argumentos->ans; int tamaño = argumentos->tamaño; int fin = argumentos->fin;< end; i++){ m = i * size; for(j = 0; j < size; j++){ l = 0; for(k = 0; k < size; k++){ tmp += m1 * m2; l += size; } ans = tmp; tmp = 0; } } printf("thread works %fs\n", dtime() - t0); pthread_exit(NULL); } main(int argc, char** argv){ int i, j, size, k, step, pos, res; int THR_NUM,THR,N; printf("Введите число потоков\n"); scanf("%i",&THR); printf("Введите размер матрици\n"); scanf("%i",&N); THR_NUM = THR; size = N; pthread_t threads; pthread_attr_t attr; printf("allocating\n"); int *m1 = alloc_matrix(size); int *m2 = alloc_matrix(size); int *ans = alloc_matrix(size); srand(time(NULL)); for(int i=0; i

3) Pruebas

Multiplicación de matrices de 1000x1000 elementos en un procesador Intel Atom

Según los datos obtenidos, está claro que se produce un ligero aumento en el rendimiento en 2 subprocesos debido a la tecnología Hyper Threading que admite el procesador. El posterior aumento en el número de subprocesos no provocó un aumento en el rendimiento, sino que lo ralentizó. También está claro que la paralelización manual usando Pthread es más efectiva que la paralelización automática usando OpenMP.

Multiplicación de matrices de 1000x1000 elementos en un procesador Intel Xeon

Según los datos obtenidos, está claro que el rendimiento aumenta en 2 y 4 subprocesos, ya que el procesador puede asignar un núcleo separado para cada subproceso. Pero el rendimiento empieza a bajar cuando intentamos ejecutar un programa con 10 hilos, esto también sucede por el tiempo dedicado a la cuantificación entre hilos. De esta tabla podemos suponer que es más eficiente ejecutar un subproceso por núcleo (la aplicación mostró el mejor rendimiento en 4 subprocesos). También está claro que la paralelización manual mediante Pthread resultó ser más eficaz que la paralelización automática mediante OpenMP.

Su problema se debe a una condición de carrera en la variable j del bucle interno. Debe hacerse privado.

En C89 haría algo como esto:

#pragma omp paralelo ( int i, j, k; #pragma omp for for(i=0; ...

Para C++ o C99, utilice declaraciones mixtas

#pragma omp paralelo para for(int i=0; ...

Al hacer esto, no es necesario declarar explícitamente nada público o privado.

Algunos comentarios adicionales a su código. Cuando usa B[k][j] su código de subproceso único no se almacena en caché. Esto lee el anacardo, luego pasa a la siguiente línea de caché, y así sucesivamente hasta que se ejecuta el producto escalar, momento en el cual los otros pines habrán sido desalojados. En cambio, la transposición primero debe transferirse y accederse como BT[j][k] . Además, ha asignado matrices de matrices, no una matriz 2D contigua. Corregí su código para usar transposición y una matriz 2D contigua.

Aquí está el tiempo que obtengo para la talla = 512.

Sin transposición, sin openmp 0.94s, sin transposición, openmp 0.23s, sin transposición, sin openmp 0.27s, openmp 0.08s #include #incluir #incluir transposición vacía (doble *A, doble *B, int n) ( int i,j; for(i=0; i