Este repositório é dedicado ao segundo trabalho da cadeira de Arquiteturas Avançadas (INF). É esperado que nós implementemos dois algoritmos de busca em grafos na linguage CUDA, para GPUs.
Da especificação do trabalho:
Implemente dois algoritmos de grafos: Floyd-Warshall e BFS para que utilizem uma GPU para realizar a computação. Realize testes com as diferentes entradas fornecidas e compare o desempenho da versão disponibilizada com sua implementação em GPU. Faça uma análise crítica dos resultados obtidos em relação ao desempenho obtido na GPU vs obtido na CPU. Era o que vocês esperavam? Houve diferença entre os dois algoritmos? Por quê? E entre os grafos? Detalhe as características do processador e da GPU utilizados para os testes.
Segue a estrutura do projeto, comentada:
. ├── bin ├── build ├── data ├── include │ ├── clipp │ └── fmt ├── lib └── src ├── fmt ├── methods │ └── helpers └── utils 12 directories
Utilizamos algumas ferramentas open-source no processo de desenvolvimento desse trabalho:
- {fmt} (GitHub page)
Para a formatação simples (estilo Python) de strings para as saídas padrão.
- clipp (GitHub page)
Para o parseamento de opções provenientes da linha de comando.
Para buildar, execute a seguinte linha no root do repositório:
make
Para usar todos as threads de execução da sua máquina, execute da seguinte maneira:
make -j<NUMBER_OF_CORES>
# ex:
make -j4
No processo de compilação, são gerados dois binários:
- cpu
- para a execução em CPU
- gpu
- para a execução em GPU
Verifique as opções de execução do binário conforme o seguinte comando:
./build/gsg help
Tal execução retornará as seguintes linhas:
DESCRIPTION finds an element in a graph using different methods these methods are intended as a way of comparing the different effectiveness in visiting a whole graph SYNOPSIS ./build/gsg help ./build/gsg [-v] cpu (bfs|floyd) [-s <VERTEX>] [-i <INITIAL>] <instance> ./build/gsg [-v] cuda [-b <BLOCKSIZE>] (bfs|floyd) [-s <VERTEX>] [-i <INITIAL>] <instance> OPTIONS -v, --verbose show detailed output possible implementations cpu use the implementation in CPU host code cuda use the implementation in CUDA device code -b, --block-size <BLOCKSIZE> the block size for the cuda version possible methods: bfs use the BFS method to find the element floyd use the floyd-warshall method to find the element -s, --search <VERTEX> the vertex being searched for (default: 5000) -i, --initial <INITIAL> where to start from (default: 0) <instance> path to the graph instance
Você pode entrar em contato comigo pelo seguinte e-mail:
hcpsilva@inf.ufrgs.br