Demostración programación paralela III Multiplicación de matrices



Demostración programación paralela Multiplicación de matrices


En anteriores tutoriales hemos visto cómo funcionan MPI y OpenMP y dos demostraciones de MPI, una con el algoritmo hill climbing y otra en la que cálculábamos el número π mediante el método de Montecarlo. En este tutorial vemos cómo usar MPI y OpenMP para multiplicar matrices y la inmensa mejoría en tiempo que ello supone cuando se trata de matrices grandes.

Nota

Todos los algoritmos generan matrices aleatorias para ser multiplicadas. El tiempo empleado en esta labor no se tiene en cuenta.

Algoritmo secuencial

Un único proceso multiplica las dos matrices. Este proceso es rápido cuando se trata de matrices pequeñas, pero muestra sus carencias con matrices de grandes dimensiones.

En la siguiente tabla podemos ver el tiempo que se tarda en multiplicar dos matrices cuadradas de diferentes dimensiones en Magerit empleando la arquitectura Power7 y la Intel. [Puede ser buena idea subir el código a github y enlazarlo aquí, ya que es largo].

Dimensión matricesArquitectura Power7Arquitectura Intel Xeon
100,000094 s0,00006 s
1000,0177 s0,0672 s
5002,057 s0,095 s
100018,094 s5,668 s
50001 h 0 min 3 s22 min 2 s
100009 h 59 min 27 s2 h 57 min 34 s

Algoritmo MPI

Ahora tenemos el número de procesos MPI especificado en la directiva #@ total_tasks del jobfile. El proceso padre se encarga de generar las matrices de manera aleatoria, enviárselas a los hijos para que operen y recibir los resultados. Cada proceso hijo se encarga de obtener un determinado número de filas de la matriz resultado. El nivel de paralelismo puede llegar a ser mayor que en el caso anterior, pues el número de procesos MPI no está limitado a 16.

En la siguiente tabla vemos los tiempos de ejecución en Power e Intel.

Dimensión matricesProcesos MPIArquitectura Power7Arquitectura Intel Xeon
1040,049 s0,061 s
5040,060 s0,062 s
10040,062 s0,061 s
50040,208 s0,084 s
100041,303 s0,219 s
8n sn s
500048 min 22 s34,5 s
8n s14,69 ss
16n s12,11 s
1000042 h 7 s3 min 58 s
8n s1 min 57 s
16n s1 min 38 s
32n s48,29 s
150004n s23 min 10 s
8n s13 min 16 s
16n s6 min 32 s
32n s3 min 9 s
64n s1 min 15 s

Conclusiones

Podemos observar cómo en matrices grandes el paralelismo es completamente necesario. Vemos también cómo en matrices pequeñas el algoritmo que mejor se comporta, aunque las diferencias son mínimas, es el secuencial. Esto se debe al tiempo que se tarda en desplegar los procesos MPI y/o los hilos OpenMP, tiempo que resulta despreciable al operar con matrices de grandes dimensiones.

Por otra parte, en la comparativa Power7 vs Intel Xeon podemos ver cómo el segundo es el claro ganador, a pesar de que cada core tiene una frecuencia de reloj menor.