Graph algorithms on GPUs
F. Busato; N. Bombieri University of Verona, Verona, Italy
Abstract
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 ...
Get Advances in GPU Research and Practice now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
