JUNE 18–22, 2017

Presentation Details

Name: EvoGraph: On-The-Fly Efficient Mining of Evolving Graphs on GPU
Time: Tuesday, June 20, 2017
08:30 am - 09:00 am
Room:   Panorama 3
Messe Frankfurt
Breaks:07:30 am - 10:00 am Welcome Coffee
Speaker:   Shuaiwen Song, PNNL
Abstract:   With the prevalence of the World Wide Web and social net- works, there has been a growing interest in high performance analytics for constantly-evolving dynamic graphs. Modern GPUs provide massive amount of parallelism for efficient graph processing, but the challenges remain due to their lack of support for the near real-time streaming na- ture of dynamic graphs. Specifically, due to the current high volume and velocity of graph data combined with the complexity of user queries, traditional processing methods by first storing the updates and then re- peatedly running static graph analytics on a sequence of versions or snap- shots are deemed undesirable and computational infeasible on GPU. We present EvoGraph, a highly efficient and scalable GPU-based dynamic graph analytics framework that incrementally processes graphs on-the-fly using fixed-sized batches of updates. The runtime realizes this vision with a user friendly programming model, along with a vertex property-based optimization to choose between static and incremental execution; and ef- ficient utilization of all hardware resources using GPU streams, including its computational and data movement engines. Extensive experimental evaluations for a wide variety of graph inputs and algorithms demon- strate that EvoGraph achieves up to 429 million updates/sec and over 232x speedup compared to the competing frameworks such as STINGER.