Algoritmo de Floy Paralelizado.

   El Algoritmo de Floyd resuelve el problema de encontrar la ruta más corta en todos los pares de nodos o vértices de un grafo, sin necesidad de definir un nodo o vértice inicial. Además de ello nos indica la distancia, y el recorrido a seguir. En esta oprtunidad  presentamos el algorimo de Floyd paralelizado.

   Antes de comenzar vamos hacer unas cuantas definiciones:

   Sea G = (V,E,w) un grafo con pesos, donde V = {v1, v2, v3, ..., vn } es el conjunto de vértices de G donde E es el conjunto de pares (vi,vj) cuyo peso viene dado por wij. Consideremos un conjunto de vértices { v1, v2, v3, ..., vk } , para cualquier para de vertices vi, vj considerar todos los caminos, tales que los vetices pertenecientes al camino pertenezcan a dicho conjunto para algún k <=n. Sea pk_ij el camino de peso minimo entre ellos y sea dk_ij el peso de dicho camino:

            * Si vk no pertenece al camino minimo entonces pk_ij = pk-1_ij.

           * Si vk pertenece al camino minimo entonces tenemos un camino minimo 
            de vi a vk y otro de vk a vj cada uno de esos caminos usa los vertices de 
            { v1,...,vk}.

Nota:
   siendo más exigentes el camino de vk a vj excluye al vertice vi el camino de vi a vk excluye al vertice vj siendo aún más exigentes el camino vi a vk se intersectan con el camino de de vk a vj en un solo vertice.

Con ello podemos plantear la siguiente ecuación:

How to replicate more than 300TB across regions including snapshots in each DataCenter.

   En primer lugar tenemos que tener ciertas consideraciones la necesidad del negocio y la capacidad de la infraestructura tecnológica que disponemos, por ejemplo cuantos datacenters debemos disponemos. Para ir directo al punto podemos plantear varias arquitecturas como ejemplos:

1.- Arquitectura de replicación dos sitios.

2.- Arquitectura de replicación tres sitios.

3.- Arquitectura de replicación de cuatro sitios.

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).