Laboratório 4 - 4/4/2001

Na aula de 2/4, discutimos alguns algoritmos que usam paralelismo de dados e que fazem uso do mecanismo de barreira. No laboratório de hoje, vocês implementarão um algoritmo desse tipo, usando a função barreira implementada na semana passada.

1. O problema de encontrar o caminho mais curto entre todos os pares em um grafo G é o de encontrar o caminho mais curto entre cada par de nós (diferentes) desse grafo. Dado um grafo com n nós, a saída de uma algoritmo de caminho mais curto entre todos os paresé uma matriz D de tamanho n*n, onde cada elemento (i,j) é o custo do caminho mais curto entre os nós i e j.

   Um algoritmo simples de caminho mais curto entre todos os pares é o algoritmo baseado em multiplicação de matrizes. Em cada iteração desse algoritmo, ocorre uma "multiplicação" de 2 matrizes n*n (na realidade a operação de produto interno entre uma linha e coluna é substituída pela operação que procura o mínimo da soma dos pares).

   Escreva uma versão paralela desse algoritmo, onde n threads são criadas, e a cada iteração uma delas fica responsável pelo cálculo de uma linha da nova matriz. Ao final de cada iteração, as threads devem se sincronizar utilizando a barreira que você desenvolveu anteriormente.

   sugestão...: Para não ficar brigando com entrada e saída no seu tempo de lab, atribua estaticamente os valores da matriz de custos. Por exemplo, utilize a matriz abaixo, com 5 threads:

     0    3  inf    1  inf
     3    0  inf    1    4
   inf  inf    0    5    1
     1    1    5    0    2
   inf    4    1    2    0
   

   Execute primeiro seu programa sem chamadas à barreira. Force seu programa a ter comportamento inconsistente, se necessário, com a introdução de loops de espera. Em seguida insira as chamadas à função de barreira.

2. Caso você termine cedo :-) implemente o seguinte algoritmo de ordenação de n inteiros em paralelo. Utilize n processos p[1:n], supondo que n é par. Cada processo corresponde a um índice do array de inteiros. O algoritmo procede em n fases, alternando entre fases pares e fases ímpares. Em cada fase ímpar, cada processo de índice ímpar compara, e troca, se for o caso, o valor de seu índice com o valor seguinte. Em cada fase par, cada processo de índice par compara, e troca, se for o caso, o valor de seu índice com o valor seguinte.