Exploração Paralela Eficiente de Grafos em CPU e GPU Multi-Core

Grafos são uma representação de dados fundamental que tem sido amplamente utilizada em vários domínios. Em aplicações baseadas em grafos, uma exploração sistemática do grafo, como uma busca em largura (BFS), frequentemente serve como um componente chave no processamento de seus imensos conjuntos de dados. Neste artigo, apresentamos um novo método para implementar o algoritmo BFS paralelo em CPUs multi-core, que explora uma propriedade fundamental de instâncias de grafos do mundo real de formas aleatórias. Ao utilizar a largura de banda da memória de forma mais eficiente, nosso método mostra desempenho melhorado em relação à implementação atual de ponta e aumenta sua vantagem à medida que o tamanho do grafo aumenta. Então, propomos um método híbrido que, para cada nível do algoritmo BFS, escolhe dinamicamente a melhor implementação entre: uma execução sequencial, dois métodos diferentes de execução multicore e uma execução em GPU. Essa abordagem híbrida fornece o melhor desempenho para cada tamanho de grafo, ao mesmo tempo em que evita um desempenho ruim em cenários de pior caso em grafos de alto diâmetro. Finalmente, estudamos os efeitos da arquitetura subjacente no desempenho do BFS, comparando múltiplos sistemas CPU e GPU, um sistema GPU de alto desempenho teve desempenho equivalente a um sistema CPU de alto desempenho com quatro soquetes.