el algoritmo de floyd capítulo 6. grafos con pesos un grafo dirigido en la cual hay asociado con...
TRANSCRIPT
![Page 1: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/1.jpg)
El Algoritmo de Floyd
Capítulo 6
![Page 2: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/2.jpg)
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.
![Page 3: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/3.jpg)
El Problema de Todos Pares Distancias mas Cortas
• Dado 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?
![Page 4: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/4.jpg)
La Matríz de Adyacencias
• Representar 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.
![Page 5: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/5.jpg)
Ejemplo
A
E
B
C
D
4
6
1 35
3
1
2
0 6 3 ∞
4 0 ∞ 1
∞ ∞ 0 5
∞ 3 ∞ 0
∞ ∞ ∞ 2
A
B
C
D
E
A B C D
∞
∞
1
∞
0
E
Matríz de Adyacencias
![Page 6: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/6.jpg)
El Algoritmo de Floyd
for k 0 to n-1
for i 0 to n-1
for j 0 to n-1
a[i,j] min (a[i,j], a[i,k] + a[k,j])
endfor
endfor
endfor
![Page 7: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/7.jpg)
La Solución al Ejemplo Anterior
A
E
B
C
D
4
6
1 35
3
1
2
0 6 3 6
4 0 7 1
10 6 0 3
7 3 10 0
9 5 12 2
A
B
C
D
E
A B C D
8
8
1
11
0
E
Matríz de Distancias
![Page 8: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/8.jpg)
La Idea del Algoritmo
i
k
j
La trayectoria mas corta de i a k que pasa por 0, 1, …, k-1
La trayectoria mas corta de k a j que pasa por 0, 1, …, k-1
La trayectoria mas cortade i a j que pasa por 0, 1, …, k-1
Computedin previousiterations
![Page 9: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/9.jpg)
El Diseño del Algoritmo Paralelo
• Particionar
• Patronos de Comunicaciones
• Aglomeración y Asignación
![Page 10: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/10.jpg)
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.
![Page 11: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/11.jpg)
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
![Page 12: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/12.jpg)
Comunicaciones
Primitive tasksPoner al diaa[3,4] Cuando k=1
Iteración k:Toda tareaen la fila kemite su valora los procesosen la misma columna
Iteración k:Toda tareaen la columna k emite su valora los procesosen la misma fila
![Page 13: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/13.jpg)
Aglomeración y Asignación
• El 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
![Page 14: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/14.jpg)
Dos Descomposiciones
Rowwise block striped Columnwise block striped
![Page 15: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/15.jpg)
Comparación de Descomposiciones
• Columnwise block striped– Se eliminan las emisiones dentro de las
columnas
• Rowwise block striped– Se eliminan las emisiones dentro de las
columnas– Escribir la salida es mas simple
• Escoja rowwise
![Page 16: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/16.jpg)
La Entrada de la Matríz de Adyacencias
• La 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)
![Page 17: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/17.jpg)
Comunicación Punto-Punto
• Envolve dos procesos
• Un proceso envia un mensaje
• El otro proceso receive el mensaje
![Page 18: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/18.jpg)
Enviar
int MPI_Send ( void *mensage, int cantidad, MPI_Datatype tipo, int dest, int etiqueta, MPI_Comm comunicador )
![Page 19: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/19.jpg)
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
![Page 20: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/20.jpg)
El Argumento estatus de MPI_Recv
• Antes 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
![Page 21: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/21.jpg)
El Código para Eniviar/Recibir
if (ID == j) { … Receive from i …}…if (ID == i) { … Send to j …}
![Page 22: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/22.jpg)
MPI_Send
• La función bloquea hasta que el buffer este libre
• Tipicamente el mensaje se envia a un buffer de mensaje que permite la devolución de control al proceso que llamó
![Page 23: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/23.jpg)
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.
![Page 24: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/24.jpg)
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.
![Page 25: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/25.jpg)
EjemploFloat 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.
![Page 26: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/26.jpg)
Otro EjemploFloat 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);MPI_Send (&b,1,MPI_FLOAT,0,0,MPI_COMM_WORLD);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.*/
![Page 27: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/27.jpg)
Una Versión Paralela en MPI del Algoritmo de Floyd
• La 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
![Page 28: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/28.jpg)
read_row_striped_matrix
• Esta 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
![Page 29: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/29.jpg)
Funciones Disponibles
• read_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:
http://ac-staff.seattleu.edu/quinnm/web./education/ParallelProgramming
![Page 30: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/30.jpg)
Declaraciones y Inicializaciones#include <stdio.h>#include <mpi.h>#include "MyMPI.h"typedef int dtype;#define MPI_TYPE MPI_INTint main (int argc, char *argv[]) { dtype **a; /* Doubly-subscripted array */ dtype *storage; /* Local portion of array elements */ int i, j, k; int id; /* Process rank */ int m; /* Rows in matrix */ int n; /* Columns in matrix */ int p; /* Number of processes
*/ double time, max_time; void compute_shortest_paths (int, int, int**, int); MPI_Init (&argc, &argv); MPI_Comm_rank (MPI_COMM_WORLD, &id); MPI_Comm_size (MPI_COMM_WORLD, &p);
![Page 31: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/31.jpg)
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
![Page 32: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/32.jpg)
mainread_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_COMM_WORLD);
MPI_Finalize();}
![Page 33: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/33.jpg)
compute_shortest_paths• void 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++)• for (j = 0; j < n; j++)• a[i][j] = MIN(a[i][j], a[i][k] + tmp[j]);• }• free (tmp);• }
![Page 34: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/34.jpg)
Un Program para Generar una Matríz de Distancias Aleatorias
• genMat4floyd 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.
![Page 35: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/35.jpg)
Un Programa para Crear un Archivo con una Matríz de
Distancias Dada• *
#include <stdio.h>#include <stdlib.h>/******************************************************************************/int main(int argc, char *argv[]){ int i, j;
int n;FILE *fp;int *Astorage;int **A;int x;if(argc != 3){ printf("\nDebe ser: generar <n> <archivo> ");
printf("\ndonde la matriz de distancias es nxn");printf("\n");exit(1);
}
![Page 36: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/36.jpg)
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);fwrite(&n, sizeof(int), 1, fp);
// Asignar memoria para almacenar el arregloif((Astorage = (int *)malloc(n * n * sizeof(int))) == NULL){ printf( "\n*** no hay memoria ***\n");
exit(2);}
//Asignar memoria para los apuntadores a las filasif((A = (int **)malloc(n * sizeof(int *))) == NULL){ printf("\n*** no hay memoria ***\n");
exit(2);}
•
![Page 37: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/37.jpg)
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(i = 0; i < n; ++i)
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);
}• }
![Page 38: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/38.jpg)
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 */
![Page 39: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/39.jpg)
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);
![Page 40: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/40.jpg)
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; }
![Page 41: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/41.jpg)
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);}
![Page 42: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/42.jpg)
Como Usar el Programa Paralelo de Floyd
• Crear 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
![Page 43: El Algoritmo de Floyd Capítulo 6. Grafos con Pesos Un grafo dirigido en la cual hay asociado con cada arista un número positivo (el “peso”) se llama un](https://reader035.vdocumento.com/reader035/viewer/2022062219/551cee05550346497a8b5231/html5/thumbnails/43.jpg)
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