Otimização do Algoritmo de caminho mínimo entre grafos de Floyd-Warshall, transformando de serial para paralelo.
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.
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).
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.
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.
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.
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.
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.
$ 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.