1 El Algoritmo de Floyd Capítulo 6
2 Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un grafo dirigido con pesos. El largo de una trayectoria de un vértice u a otro vértice v es la suma de los pesos de las aristas que componen la trayectoria.
3 El Problema de Todos Pares Distancias mas CortasDado un grafo dirigido con pesos, ¿cuales son las trayectorias de largos mínimos (es decir “distancias mas cortas”) entre todos los pares de vértices?
4 La Matríz de AdyacenciasRepresentar un grafo dirigido con pesos G con n vértices por una matríz MG como sigue: Si 1,2, … ,n son los vértices, entonces el elemento en la fila #i y la columna #j es 0 si i=j, es ∞ (un número mas grande que cualquier peso) si no hay arista de I a j, y es el peso de la arista de i a j si tal arista existe. Lamemos MG la matríz de adyacencias.
5 Ejemplo 6 3 ∞ 4 1 5 2 A B C D E 4 A B 3 6 1 3 C 5 1 D 2 E Matríz de Adyacencias
6 El Algoritmo de Floyd for k 0 to n-1 for i 0 to n-1for j 0 to n-1 a[i,j] min (a[i,j], a[i,k] + a[k,j]) endfor
7 La Solución al Ejemplo Anterior6 3 4 7 1 10 9 5 12 2 A B C D E 8 11 4 A B 3 6 1 3 C 5 1 D 2 E Matríz de Distancias
8 La Idea del Algoritmo La trayectoria mas corta de i a kque pasa por 0, 1, …, k-1 i Computed in previous iterations k La trayectoria mas corta de i a j que pasa por 0, 1, …, k-1 La trayectoria mas corta de k a j que pasa por 0, 1, …, k-1 j
9 El Diseño del Algoritmo ParaleloParticionar Patronos de Comunicaciones Aglomeración y Asignación
10 Particionar En el seudo código la misma asignación se ejecuta n3 veces. No hay paralelismo funcional. Usemos descomposición de dominio: particionar la matriz A en sus n2 elementos.
11 Comunicaciones Para todo valor de k, a[k,m] se necesita por toda tarea asociada con elementos en la columna m y a[m,k] se necesita por toda tarea asociada con elements de la fila m. Durante de la iteración k, todo element en la fila k se emit a las tareas de la misma columna y todo elemento de la columna a se emite a la tarea en la misma fila
12 Comunicaciones Poner al dia a[3,4] Primitive tasks Cuando k=1Iteración k: Toda tarea en la fila k emite su valor a los procesos en la misma columna Iteración k: Toda tarea en la columna k emite su valor a los procesos en la misma fila
13 Aglomeración y AsignaciónEl número de taréas es estático Las comunicaciones entre las tareas son regulares El tiempo de computación por tarea es constante Un buena estrategia en este caso es Aglomerar tareas pare minimizar las comunicaciones Crear una tarea por proceso MPI
14 Dos Descomposiciones Rowwise block striped Columnwise block striped
15 Comparación de DescomposicionesColumnwise block striped Se eliminan las emisiones dentro de las columnas Rowwise block striped Escribir la salida es mas simple Escoja rowwise
16 La Entrada de la Matríz de AdyacenciasLa matríz se guarda en el orden “row major” en un archivo”. Si hay p procesos, entonces para cada i=0,1,…,p-2, el proceso p-1 lee la fila in/p hasta la fila (i+1)n/p -1 y las envia al proceso i. Después, lee las últimas filas para le mismo. La razón por la cual p-1 hace este trabajo es que no hay ningun proceso que va a ser responsible por mas filas que el p-1 (Ejercicio 6.1)
17 Comunicación Punto-PuntoEnvolve dos procesos Un proceso envia un mensaje El otro proceso receive el mensaje
18 Enviar int MPI_Send ( void *mensage, int cantidad, MPI_Datatype tipo,int dest, int etiqueta, MPI_Comm comunicador )
19 Recibir int MPI_Recv ( void *mensage, int cantidad, MPI_Datatype tipo,int fuente, int etiqueta, MPI_Comm comunicador, MPI_Status *estatus//un apuntador a un //record de tipo MPI_Status ) “fuente” puede ser MPI_ANY_SOURCE
20 El Argumento estatus de MPI_RecvAntes de usar MPI_Recv, hay que declarar un record de tipo MPI_Status Este record contiene tres campos: - MPI_source: el rango del proceso que envió el mensaje - MPI_tag: la etiqueta del mensaje - MPI_ERROR: la condición de error
21 El Código para Eniviar/Recibirif (ID == j) { … Receive from i } if (ID == i) { Send to j
22 MPI_Send La función bloquea hasta que el buffer este libreTipicamente el mensaje se envia a un buffer de mensaje que permite la devolución de control al proceso que llamó
23 MPI_Recv La función bloquea hasta que el mensaje se haya recibido o hasta que un error se haya detectado Cuando occure un error, el record dado como el último argumentocontiene información acerca del proceso que envió el mensaje, el valor de la etiqueta, y la condición de error.
24 Punto Muerto (“Deadlock”)Ocurre cuando un proceso espera una condición que nunca occura. Ejemplos en los cuales punto muerto ocurre: Dos procesos reciben antes de enviar. La etiqueta de enviar no es la misma como la etiqueta de recibir. Un proceso envia un mensaje a una destinación incorrecta.
25 Ejemplo Float a,b,c; Int id; MPI_Status estatus; … If(id==0){MPI_Recv(&b,1,MPI_FLOAT,1,0,MPI_COMM_WORLD,&estatus); MPI_Send (&a,1,MPI_FLOAT,1,0,MPI_COMM_WORLD); C=(a+b)/2.0; } else if (id==1){ MPI_Recv(&a,1,MPI_FLOAT,0,0,MPI_COMM_WORLD,&estatus); MPI_Send (&b,1,MPI_FLOAT,0,0,MPI_COMM_WORLD); C=(a+b)/2.0 } //El proceso #0 se queda esperando un mensaje del proceso #1 mientras que el proceso #1 se queda esperando un mensaje del proceso #0.
26 Otro Ejemplo Float a,b,c; Int id; MPI_Status estatus; … If(id==0) {MPI_Send (&a,1,MPI_FLOAT,1,1,MPI_COMM_WORLD); MPI_Recv(&b,1,MPI_FLOAT,1,1,MPI_COMM_WORLD,&estatus); C=(a+b)/2.0; }else if (id==1){ MPI_Send (&b,1,MPI_FLOAT,0,0,MPI_COMM_WORLD); MPI_Recv(&a,1,MPI_FLOAT,0,0,MPI_COMM_WORLD,&estatus); C=(a+b)/2.0 } /*El proceso #0 envia un mensaje con etiqueta 1 al proceso #1 y el proceso #1 envia un mensaje con etiqueta 0 al proceso #0. Pero el proceso #0 esta esperando un mensaje con etiqueta 1 y el proceso #1 está esperando un mensaje con etiqueta 0.*/
27 Una Versión Paralela en MPI del Algoritmo de FloydLa entrada consiste de un archivo que contiene una matríz n X n de enteros. Esta matriz se puede leer haciendo uso de una función read_row_striped_matrix
28 read_row_striped_matrixEsta función pone las filas de la matríz de entrada en los p procesadores de acuerdo con el Método 2, es decir que el procesador i, i=0,1,…,p-1, irecibirá las filas i n/p hasta la (i + 1) n/p -1 Dado el nombre del archivo de entrada, el tipo de dato de los elementos de la matriz, y un comunicador, (1) devuelve un apuntador a un arreglo de apuntadores y (2) un apuntador a la localización que contiene la matrix, y (3) las dimensiones de la matriz
29 Funciones Disponiblesread_row_striped_matrix además de otras funciones útiles se encuentran en el archivo MyMPI.h Este archivo además del código de fuente de los otros programas del texto se encuentran en la página de Michael J. Quinn:
30 Declaraciones y Inicializaciones#include
31 main /*Leer archivo que contiene la matríz de distancias*//*Imprimir la matríz de distancias*/ /*Llamar la función compute_shortest_paths*/ /*Computar tiempo total*/ /*Imprimir la nueva matríz de distancias
32 main read_row_striped_matrix (argv[1], (void *) &a,(void *) &storage, MPI_TYPE, &m, &n, MPI_COMM_WORLD); if (m != n) //terminate(id,”Matrix must be square\n”) print_row_striped_matrix ((void **) a, MPI_TYPE, m, n, MPI_COMM_WORLD); MPI_Barrier (MPI_COMM_WORLD); time = -MPI_Wtime(); compute_shortest_paths (id, p, (dtype **) a, n); time += MPI_Wtime(); MPI_Reduce (&time, &max_time, 1, MPI_DOUBLE, MPI_MAX, 0, MPI_COMM_WORLD); if (!id) printf ("Floyd, matrix size %4d, %3d processes: %10.6f seconds\n", n, p, max_time); print_row_striped_matrix ((void **) a, MPI_TYPE, m, n, MPI_Finalize(); }
33 compute_shortest_pathsvoid compute_shortest_paths (int id, int p, dtype **a, int n) { int i, j, k; int offset; /* Local index of broadcast row */ int root; /* Process controlling row to be bcast */ int *tmp; /* Holds the broadcast row */ tmp = (dtype *) malloc (n * sizeof(dtype)); for (k = 0; k < n; k++) { root = BLOCK_OWNER(k, p, n); if (root == id) { offset = k - BLOCK_LOW(id, p, n); for (j = 0; j < n; j++) tmp[j] = a[offset][j]; } MPI_Bcast (tmp, n, MPI_TYPE, root, MPI_COMM_WORLD); for (i = 0; i < BLOCK_SIZE(id, p, n); i++) a[i][j] = MIN(a[i][j], a[i][k] + tmp[j]); free (tmp);
34 Un Program para Generar una Matríz de Distancias AleatoriasgenMat4floyd escrito por Andrea di Blas Hay 4 entradas en la linea de comando: n (el número de vértices) r (la “densidad”, es decir el porciento de números no cero en la matríz de distancias) salida (el nombre del archivo de salida) seed (la “semilla” del generador de números aleatorios.
35 Un Programa para Crear un Archivo con una Matríz de Distancias Dada* #include
36 Programa generar(cont)n=atoi(argv[1]); //Abrir archivo para escribir if((fp = fopen(argv[2], "w")) == NULL) { printf("\n*** no se puede escribir en archivo %s ***\n", argv[2]); exit(1); } /* escribir las dimensiones n y n en el archivo */ fwrite(&n, sizeof(int), 1, fp); // Asignar memoria para almacenar el arreglo if((Astorage = (int *)malloc(n * n * sizeof(int))) == NULL) { printf( "\n*** no hay memoria ***\n"); exit(2); //Asignar memoria para los apuntadores a las filas if((A = (int **)malloc(n * sizeof(int *))) == NULL) { printf("\n*** no hay memoria ***\n");
37 Program generar (cont)/* inicializar arreglo de apuntadores */ for(i = 0; i < n; ++i) A[i] = &Astorage[i * n]; /* Entrar la matriz de distancias desde el teclado*/ /* set all values */ for(j = 0; j < n; ++j) { printf("A[%d][%d]=",i,j); scanf("%d",&A[i][j]); } /* escribir el arreglo en el archivo */ fwrite(Astorage, sizeof(int), n * n, fp); fclose(fp); return(0);
38 Función para Leer Matríz de Distancias/** Process p-1 opens a file and inputs a two-dimensional matrix, reading and distributing blocks of rows to the other processes.*/ void read_row_striped_matrix ( char *s, /* IN - File name */ void ***subs, /* OUT - 2D submatrix indices */ void **storage, /* OUT - Submatrix stored here */ MPI_Datatype dtype, /* IN - Matrix element type */ int *m, /* OUT - Matrix rows */ int *n, /* OUT - Matrix cols */ MPI_Comm comm) /* IN - Communicator */ { int datum_size; /* Size of matrix element */ int i; int id; /* Process rank */ FILE *infileptr; /* Input file pointer */ int local_rows; /* Rows on this proc */ void **lptr; /* Pointer into 'subs' */ int p; /* Number of processes */ void *rptr; /* Pointer into 'storage' */ MPI_Status status; /* Result of receive */ int x; /* Result of read */
39 read_row_striped_matrix (cont)MPI_Comm_size (comm, &p); MPI_Comm_rank (comm, &id); datum_size = get_size (dtype); /* Process p-1 opens file, reads size of matrix, and broadcasts matrix dimensions to other procs */ if (id == (p-1)) { infileptr = fopen (s, "r"); if (infileptr == NULL) *m = 0; else { fread (m, sizeof(int), 1, infileptr); fread (n, sizeof(int), 1, infileptr); } MPI_Bcast (m, 1, MPI_INT, p-1, comm); if (!(*m)) MPI_Abort (MPI_COMM_WORLD, OPEN_FILE_ERROR); MPI_Bcast (n, 1, MPI_INT, p-1, comm);
40 read_row_striped_matrix (cont)local_rows = BLOCK_SIZE(id,p,*m); /* Dynamically allocate matrix. Allow double subscripting through 'a'. */ *storage = (void *) my_malloc (id, local_rows * *n * datum_size); *subs = (void **) my_malloc (id, local_rows * PTR_SIZE); lptr = (void *) &(*subs[0]); rptr = (void *) *storage; for (i = 0; i < local_rows; i++) { *(lptr++)= (void *) rptr; rptr += *n * datum_size; }
41 read_row_striped_matrix (cont)/* Process p-1 reads blocks of rows from file and sends each block to the correct destination process. The last block it keeps. */ if (id == (p-1)) { for (i = 0; i < p-1; i++) { x = fread (*storage, datum_size, BLOCK_SIZE(i,p,*m) * *n, infileptr); MPI_Send (*storage, BLOCK_SIZE(i,p,*m) * *n, dtype, i, DATA_MSG, comm); } x = fread (*storage, datum_size, local_rows * *n, infileptr); fclose (infileptr); } else MPI_Recv (*storage, local_rows * *n, dtype, p-1, DATA_MSG, comm, &status);
42 Como Usar el Programa Paralelo de FloydCrear un archivo que contiene la matríz de distancias utilizando o generar.c (para un grafo especifico) o genMat4floyd.c (para un grafo a la azar) Si el archivo de objeto está en generar o genMat4floyd, respectivamente, entonces se ejecutan por ./generar n archivo o ./genMat4floyd n r archivo semilla
43 Compilar y Ejecutar Compilar MyMPI.c y floyd.c separadamente para crear archivos o mpicc –c MyMPI.c mpicc –c floyd.c Link: mpicc MyMPI.o floyd.o -o floyd Ejecutar: ./floyd archivo