Efficient sequential and parallel versions of MST-solvers for multi-core CPU-chips and GPUs

Abstract

The Minimum Spanning Tree (MST) problem is a well known graph problem that plays an important role in various scientific fields. Graph algorithms are known to be irregular, namely due to the unpredictable memory access patterns and workload distribution among the graph vertices. These problems place additional challenges on novel parallel computing systems, namely those that resort to a mix of shared and distributed memory paradigms and to heterogeneous computing environment with attached computing accelerators, such as many-core CPU-chips and GPU devices. This dissertation addresses these challenges, as to develop efficient implementations of MST-solvers. Sequential implementations of the three key MST algorithms - Borůvka’s, Kruskal’s and Prim’s algorithm - have been implemented, tested and compared in terms of performance. Parallel implementations of Prim’s and Borůvka’s algorithms were also implemented and tested using the same suite of widely used road-network graphs. This comparative analysis included a first-hand comprehensive empirical comparison of several disclosed state of the art third-party CPU and GPU implementations of MST-solvers. A parallel algorithmic variant of Borůvka’s algorithm was devised, which exhibited speedups that outperformed all other tested competitors. The functionality of this variant is shown to be easily ported to other shared and distributed memory systems, including heterogeneous systems with GPU devices, without placing constraints on the graph size or hurting performance.

O problema da árvore de extensão mínima (MST) é um problema de grafos muito conhecido e tem um papel importante em várias áreas científicas. Os algoritmos de grafos são conhecidos por serem irregulares, nomeadamente devido aos padrões de acesso à memória imprevisíveis, e à distribuição de trabalho pelos vértices do grafo. Estes problemas impoem um maior desafio nas novas plataformas de computação paralela, em particular aquelas que recorrem à mistura de memoria partilhada e distribuída, e a ambientes heterogéneos com aceleradores, como os many-core CPUs e dispositivos GPU. Esta dissertação aborda estes desafios, a fim de desenvolver implementações eficientes de MST-solvers. Os três principais algoritmos de MST - Borůvka, Kruskal e Prim- foram implementados em sequencial, testadas e comparadas em termos de performance. Implementações paralelas dos algoritmos de Prim e Borůvka também foram implementadas e testadas usando o mesmo conjunto de grafos de estradas rodoviárias. Esta análise comparativa inclui uma comparação empírica de primeira-mão de vários MSTsolvers de terceiros. Foi desenvolvida uma variante algorítmica paralela do algoritmo de Borůvka, que mostrou ganhos de desempenho que superam a concorrência. É mostrado que a funcionalidade desta variante é facilmente portada, sem restringir o tamanho dos grafos ou prejudicar o desempenho, para outros sistemas de memória partilhada e distribuída, aonde se incluem sistemas heterogéneos com dispositivos GPU.