Optimización de Multiplicación de Matrices en Paralelo

   Si bien es cierto la multiplicacion de matrices tiene muchas aplicaciones sobre todo en investicaciones cientìficas es por ello que se han desarrollado distintos algoritmos como el algoritmo de Cannon, el algoritmo de Fox, el algoritmo DNS ( Deckel, Nassimi, Sahni ).  Resulta interesante ver que estos algoritmos están totalmente generalizados lo que hace que uno en comparativa con el otro no sea del todo superior pues depende parámetros como la comunicación entre procesos, la cantidad de memoria que utiliza que son propios de una implementación en paralelo.

Algoritmo Simple:
    Se basa en la formula simple de multiplicación de matrices en donde se descompone la matriz A en grupos de filas y cada grupo se le va asignando a cada procesador , claro que ese paso exige que cada procesador tenga la matriz B completa. Luego de ello se procede hacer la multiplicación de matrices que cada procesador tiene a disposición.

Implementación en MPI:

#include<stdio.h>
#include<mpi.h>
#define M 150
#define N 160
#define P 165
/**  MASTER WORKER  */
int main(int argc,char*argv[]){
 int rank,size;
 MPI_Status status;
 MPI_Init(&argc,&argv);
 MPI_Comm_size(MPI_COMM_WORLD,&size);
 MPI_Comm_rank(MPI_COMM_WORLD,&rank);
 int A[M][N],B[N][P],C[M][P];
 int i,j,k;
 if(rank == 0){
 /** LEEMOS LA MATRIZ A Y B EN EL PROCESO 0*/
 }
 MPI_Barrier(MPI_COMM_WORLD);
 double t0 = MPI_Wtime();
 int n_Columns[size],n_Rows[size],colums,rows,indices[size];
 /** MANDAMOS LA MATRIZ B A TODOS LOS PROCESOS*/
 MPI_Bcast(B,N*P,MPI_INT,0,MPI_COMM_WORLD);
 
 /** DESCOMPOSICION DE LA MATRIZ  A */
 rows = ( rank < M%size )?(M/size+1)*N:(M/size)*N;
 indices[0] = 0 ;
 n_Columns[0] = ( 0<M%size )?(M/size+1)*N:(M/size)*N;
 for(i=1;i<size;i++){
  n_Columns[i] = (i < M%size ) ? (M/size+1)*N:(M/size)*N;
  indices[i] = n_Columns[i-1]+indices[i-1];
 }
 MPI_Barrier(MPI_COMM_WORLD);
 MPI_Scatterv(A,n_Columns,indices,MPI_INT,A,rows,MPI_INT,0,MPI_COMM_WORLD);
 MPI_Barrier(MPI_COMM_WORLD);
 /** MULTIPLICACIÓN DE LA MATRIZ B con Bloques de A */
 for(i=0;i<rows/N;i++)
  for(j=0;j<P;j++){
   C[i][j] = 0;
   for(k=0;k<N;k++)
    C[i][j] += A[i][k]*B[k][j];
  }


 /** AGRUPAMOS LOS RESULTADOS OBTENIDOS EN C */
 colums = ( rank < M%size )?(M/size+1)*P : M/size*P;
 n_Rows[0] = ( 0 < M%size )?(M/size+1)*P : M/size*P;
 indices[0] = 0;
 for(i=1;i<size;i++){
  n_Rows[i] = (i < M%size )?(M/size+1)*P:(M/size)*P;
  indices[i] = n_Rows[i-1]+indices[i-1];
 }

 MPI_Barrier(MPI_COMM_WORLD);
 MPI_Gatherv(C,colums,MPI_INT,C,n_Rows,indices,MPI_INT,0,MPI_COMM_WORLD);
 MPI_Barrier(MPI_COMM_WORLD);
 double t1 = MPI_Wtime();
 
 /** FIN DEL ALGORITMO SIMPLON */
 if( rank == 0 ){
  printf(" MATRIX A[%d][%d]XB[%d][%d]=C[%d][%d]\n",M,N,N,P,M,P);
  /*for(i=0;i<M;i++){
   for(j=0;j<P;j++)
    printf(" %d ",C[i][j]);
   printf("\n");
  }*/
  printf("time %f!\n",t1-t0);
 }
 MPI_Barrier(MPI_COMM_WORLD);
 MPI_Finalize();
 return 0;
}

    Este Algoritmo es facil de implementar, pero requiere comunicacion de toda la matriz B a todos; la memoria ocupada es O(p*n2)  y la complejidad del agoritmo es O(n3/p).
   

Algoritmo de Cannon:
    El algorimo hace una version de multiplición de matrices tal modo que cada proceso tiene a disposicion de un ploque de tamaño sqrt(n)*sqrt(n).para simplicidad se requiere que el tamaño de la matriz n sea cuadrado perfecto y multiplo de sqrt(p) esto.

Algoritmo:

Algoritmo de FOX:

Similar al algoritmo de Cannon cada procesador pij tiene los bloques Aij y Bij; uego se repiten sqrt(p) los siguientes pasos:

1) La fila i-ésima de la malla de procesadores recibe el bloque A(i,(i+j)mod √p) en la j-ésima iteración.

2) Multiplicar el bloque recibido de A por el bloque residente de B.

3) Enviar el bloque de B al procesador directamente precedente en la fila del procesador, y recibir un bloque de B desde el procesador de la fila posterior.

 Obteniendo una complejidad de:

Algoritmo DNS:

Básicamente lo que hace el algoritmo DNS:

Supongamos que tenemos n3 procesos para multiplicar dos matrices n*n,, estos procesos son distribuidos en un Hipercubo , de tal forma que cada proceso calcule uno de las n3 multiplicaciones que hay en el algortimo de multiplición de matrices; luego se suma el valor obtenido por los procesos Pij0 Pij1 Pij2 Pij3 Pij4 Pij5 ... Pijn-1 son sumados para obtener Cij, la suma puede ser obtenida simultaneamente en logn pasos. Con lo que la complejidad del algoritmo es O(logn).

Conclusion:

Todos los algoritmos paralelos presentados comparten características comunes:

*) Adoptan el modelo de procesamiento SPMD.

*) Asumen que los nodos de procesamiento son homogéneos y aprovechan esta homogeneidad para obtener balance de carga.