Tópicos Avançados de Informática

Programação Paralela

Ano Lectivo de 2003/2004


Trabalho Prático

O principal objectivo do trabalho é permitir que os alunos adquiram uma maior sensibilidade e conhecimento prático do funcionamento de um ambiente de programação distribuído. Em particular, pretende-se que os alunos utilizem a ferramenta de programação LAM/MPI para resolver um problema concreto.

O trabalho deve ser entregue pessoalmente ou por email até 9 de Novembro de 2003, sendo a sua demonstração feita posteriormente em horário a marcar (de 10 a 14 de Novembro).


Descrição do Problema

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.

Em traços gerais, o problema que se pretende resolver consiste em encontrar o conjunto de todos os caminhos mais curtos entre pares de nós de um determinado grafo (este problema é conhecido na literatura por all-pairs shortest paths).

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 bibliografia e/ou a internet.


Input e Output

A aplicação a desenvolver deverá aceitar como entrada de dados um ficheiro com a descrição do grafo a considerar. Essa descrição deverá seguir o seguinte padrão: a primeira linha indica o inteiro N que representa o número de nós do grafo, enquanto que as seguintes N linhas indicam a matriz que representa as ligações entre todos os pares de nós do grafo. Segue-se o ficheiro que descreve o grafo do exemplo apresentado:
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 0
No 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 0
O 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).