/PCD_Trabalho4

Quarto trabalho da disciplina de Programação Concorrente e Distribuída da Universidade Federal de São Paulo.

Primary LanguageC

Otimização do Algoritmo de caminho mínimo entre grafos de Floyd-Warshall, transformando de serial para paralelo.


Descrição do algoritmo

O algoritmo de Floyd-Warshall foi desenvolvido por Bernard Roy, Stephen Warshall e Robert Floyd em 1962. Seu objetivo é encontrar o caminho mais curto entre todos os pares de vértices de um grafo direcionado e ponderado, gerando como saída uma matriz de distâncias que contém os valores do menor caminho entre cada par de vértices.


Complexidade

O código possui três laços aninhados que são executados n vezes, logo, a complexidade final é O(n^3), ou mais precisamente, Θ(n^3).


Paralelização

Como mencionado anteriormente, o código tem uma alta complexidade, logo o nosso trabalho visa melhorar o tempo de execução do algoritmo. Fizemos a paralelização em duas linguagens de programação diferentes, C e Python, nos baseando em códigos disponíveis aqui (em C) e aqui (em Python).

Em C optamos por utilizar a API para programação paralela OpenMP, enquanto que em Python utilizamos as bibliotecas multiprocessing e functools.


Resultados

Linguagem de programação C

Em C fizemos testes inserindo grafos de tamanho 5000 x 5000.
O código serial levou 82 segundos para executar, enquanto que o código com 8 threads demorou 21 segundos para ser executado.

Linguagem de programação Python

Em python fizemos testes inserindo grafos de tamanho 400 x 400.
O código serial levou 44,48 segundos para executar, enquanto que o código com 4 threads demorou 21,74 segundos para ser executado.

Gráficos

Além dos testes mencionados, foram feitos outros testes. Posteriormente montamos gráficos para melhor visualização dos resultados obtidos. Os mesmos estão disponíveis aqui.


Vale ressaltar que os testes em C foram realizados em uma máquina diferente da utilizada para testar o código em Python.


Conclusão

Os resultados obtidos foram extremamente satisfatórios, tendo em vista que em C foi possível obter uma execução quatro vezes mais rápida e em python conseguimos reduzir o tempo de execução pela metade.



Para compilar

Código em C que utiliza OpenMP:


$ gcc -O3 -fopenmp -o <executável> <nome do arquivo>.c
$ time ./<executável>

  • O parâmetro -O3 presente na primeira linha é uma das flags que o compilador GCC possui. Ela serve para deixar o executável mais rápido, fazendo com que seja possível ocupar melhor os recursos do processador (paralelismo no nível de instruções).

  • O time, presente na segunda linha, é opcional. Ele serve para mostrar mais detalhadamente o tempo de execução do programa.



Referências