September 2016
Intermediate to advanced
774 pages
24h 26m
English
F. Busato; N. Bombieri University of Verona, Verona, Italy
This chapter introduces the topic of graph algorithms on graphics processing units (GPUs). It starts by presenting and comparing the most important data structures and techniques applied for representing and analyzing graphs on state-of-the-art GPUs. It then presents the theory and an updated review of the most efficient implementations of graph algorithms for GPUs. In particular, the chapter focuses on graph traversal algorithms (breadth-first search), single-source shortest path (Djikstra, Bellman-Ford, delta stepping, hybrids), and all-pairs shortest path (Floyd-Warshall). By the end of the chapter, load balancing and memory access ...
Read now
Unlock full access