Graph traversal
With special contributions from John Owens and Juan Gómez-Luna
Abstract
This chapter presents the parallel graph traversal pattern. Since graph search computation is about examining the vertex values, there is very little computation on these values once they have been loaded from memory. As a result, the speed of graph search is typically limited by memory bandwidth. This chapter presents a graph data format similar to the compressed sparse row storage format for sparse matrix that helps to minimize the consumption of memory bandwidth. Various strategies for parallelizing graph computations are introduced, including vertex-centric push and pull parallelization and edge-centric parallelization. The use of frontiers is ...
Get Programming Massively Parallel Processors, 4th Edition 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.
