Parallel patterns: graph search
Juan Gómez-Luna and Izzat El Hajj
Abstract
This chapter presents the parallel graph search pattern. Since graph search computation is about examining the vertex values, there is very little computation on these values once they are 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 CSR storage format for sparse matrix that helps minimize the consumption of memory bandwidth. We then introduce work queues, an important class of parallel data structures that supports work-efficient iterative algorithms that require dynamic discovery and collection of the data to be processed. We will show that the privatization ...
Get Programming Massively Parallel Processors, 3rd 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.
