O trabalho consiste no desenvolvimento de uma aplicação passível de ser executada em arquitecturas distribuídas com suporte para o modelo MPI. A aplicação deve ser estruturada tendo em conta esse facto e desenhada por forma a tirar o máximo partido das várias unidades de processamento disponíveis para assim acelerar a resolução do problema.
A ideia é a seguinte: dado um grafo dirigido G = (V,E) em que V é o conjunto de nós e E é o conjunto de ligações entre os nós, pretende-se determinar para todos os pares de nós (vi,vj) o tamanho do menor caminho que começa em vi e termina em vj. Um caminho não é nada mais do que uma sequência de ligações, em que o nó de destino e o nó de origem de duas ligações consecutivas da sequência são o mesmo. Uma ligação pode ser vista como um tuplo da forma < vi, vj, t > em que vi é o nó de origem, vj é o nó de destino e t é o tamanho da ligação entre os nós. A soma dos tamanhos das ligações de um caminho definem o tamanho do caminho.
Um grafo dirigido com V nós pode ser representado por uma matriz D1 de dimensão NxN (N = 6 no exemplo que se segue) em que cada elemento (i,j) da matriz corresponde ao tamanho da ligação que liga o nó vi ao nó vj. A não existência de qualquer ligação entre um determinado par de nós pode ser representado pelo valor zero.
A solução do problema pode ser igualmente representada por uma matriz Df de dimensão NxN em que cada elemento (i,j) da matriz corresponde ao menor tamanho dos caminhos que começam em vi e terminam em vj.
O algoritmo de Floyd-Warshall permite obter a matriz Df a partir da matriz D1 utilizando uma forma adaptada de multiplicação de matrizes, em que as operações de multiplicação e soma são substituídas pelas operações de soma e mínimo, respectivamente. Utilizando essa forma adaptada de multiplicação podemos obter a matriz Df construindo sucessivamente matrizes D2 = D1xD1, D4 = D2xD2, D8 = D4xD4, ..., Df = DgxDg em que f >= N e g < N.
A multiplicação de matrizes com a mesma dimensão pode ser eficientemente implementada em ambientes distribuídos utilizando o algoritmo de Fox. No entanto, a aplicação do algoritmo de Fox nem sempre é possível pois depende da dimensão das matrizes a multiplicar e do número de processos disponíveis. Para matrizes de dimensão NxN e P processos disponíveis no sistema, deve existir um inteiro Q tal que P = Q * Q e N mod Q = 0. O algoritmo de Fox divide as matrizes de dimensão NxN em P sub-matrizes de dimensão (N/Q)x(N/Q) e atribui cada uma delas aos P processos disponíveis no sistema.
Para calcular o resultado da multiplicação da sua sub-matriz, cada processo, apenas necessita de trocar informação com os processos da mesma linha e da mesma coluna de sub-matrizes que a sua, o que permite reduzir o tamanho e número de mensagens a trocar entre os processos envolvidos. A aplicação sucessiva do algoritmo de Fox permite calcular as matrizes D2, D4, ..., Df do algoritmo de Floyd-Warshall e obter assim a matriz que soluciona o nosso problema.
Para obter mais informações acerca dos detalhes de implementação dos algoritmos de Fox e de Floyd-Warshall deverá consultar a biblioteca e/ou a internet.
6 0 2 0 5 0 0 0 0 0 0 0 0 0 2 0 0 0 5 0 0 0 0 1 0 3 9 3 0 0 0 0 0 0 0 1 0No caso da dimensão da matriz e do número de processos disponíveis não serem compatíveis com os requisitos do algoritmo de Fox, deverá ser apresentada uma mensagem de erro e a execução deve ser cancelada.
Como resultado a aplicação deverá escrever as N linhas da matriz que representa o menor tamanho dos caminhos entre todos os pares de nós do grafo. Para o grafo do exemplo, o resultado a obter seria o seguinte:
0 2 9 5 6 14 0 0 0 0 0 0 9 2 0 14 6 5 4 6 4 0 1 9 3 5 3 8 0 8 4 6 4 9 1 0O ficheiro de entrada de dados deverá ser lido do standard input e o resultado deverá ser escrito para o standard output (carregue aqui para obter um conjunto de exemplos de teste).