The International Conference for High Performance Computing, Networking, Storage and Analysis
Exploring Hybrid Hardware and Data Placement Strategies for the Graph 500 Challenge.
Authors: Scott Sallinen (University of British Columbia), Daniel Borges (University of British Columbia), Abdullah Gharaibeh (University of British Columbia), Matei Ripeanu (University of British Columbia)
Abstract: Our research presents our experience with exploring the configuration space and data placement strategies for Breadth First Search (BFS) on large-scale graphs in the context of a hybrid, GPU+CPU architecture and the Graph 500 challenge. Recent work on GPU graph traversal has often targeted relatively small graphs that fit on device memory only; our goal is to process large graphs that stretch the limits of single-node commodity machines. When processing large graphs with tens of billions of edges or more, the techniques we explore are crucial to obtain an optimal performance level on hybrid CPU+GPU architectures. In particular, we show that the following configuration options can significantly impact performance: (i) the partitioning strategy, (ii) the placement of the graph partitions in memory in a ‘sorted by degree’ order, and (iii) the strategy to manage memory used for the GPU partitions when the graph no longer fits in the device memory.