Parallel distributed breadth first search on GPU

In this paper we propose a highly optimized parallel and distributed BFS on GPU for Graph500 benchmark. We evaluate the performance of our implementation using TSUBAME2.0 supercomputer. We achieve 317 GTEPS (billion traversed edges per second) with scale 35 (a large graph with 34.4 billion vertices...

Full description

Saved in:
Bibliographic Details
Main Authors: Ueno, Koji, Suzumura, Toyotaro
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Benchmark testing
BFS
Encoding
GPU
Graph500
Graphics processing units
Kernel
Partitioning algorithms
Supercomputer
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we propose a highly optimized parallel and distributed BFS on GPU for Graph500 benchmark. We evaluate the performance of our implementation using TSUBAME2.0 supercomputer. We achieve 317 GTEPS (billion traversed edges per second) with scale 35 (a large graph with 34.4 billion vertices and 550 billion edges) using 1366 nodes and 4096 GPUs. With this score, TSUBAME2.0 supercomputer is ranked fourth in the ranking list announced in June 2012. We analyze the performance of our implementation and the result shows that inter-node communication limits the performance of our GPU implementation. We also propose SIMD Variable-Length Quantity (VLQ) encoding for compression of communication data with GPU.
ISSN:1094-7256
2640-0316
DOI:10.1109/HiPC.2013.6799136