SCHEDULE: NOV 15-20, 2015

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

Enterprise: Breadth-First Graph Traversal on GPUs

SESSION: Graph Algorithms and Benchmarks

EVENT TYPE: Papers

EVENT TAG(S): Performance, Graphs, Data-Intensive Computing, Algorithms

TIME: 2:00PM - 2:30PM

SESSION CHAIR(S): Umit Catalyurek

AUTHOR(S):Hang Liu, H. Howie Huang

ROOM:18CD

ABSTRACT:

The Breadth-First Search (BFS) algorithm serves as the foundation for many big data applications and analytics workloads. While Graphics Processing Unit (GPU) offers massive parallelism, achieving high-performance BFS on GPUs entails efficient scheduling of a large number of GPU threads and effective utilization of GPU memory hierarchy. In this paper, we present a new BFS system, Enterprise, which utilizes three novel techniques to eliminate the performance bottlenecks: (1) streamlined GPU threads scheduling; (2) GPU workload balancing; and (3) GPU based BFS direction optimization. Enterprise achieves up to 76 billion traversed edges per second (TEPS) on a single NVIDIA Kepler K40, and up to 122 billion TEPS on two GPUs that ranks No. 45 in the Graph 500 on November 2014. Enterprise is also very energy-efficient as No. 1 in the GreenGraph 500 (small data category), delivering 446 million TEPS per watt.

Chair/Author Details:

Umit Catalyurek (Chair) - Ohio State University|

Hang Liu - George Washington University

H. Howie Huang - George Washington University

  Click here to download .ics calendar file

  Click here to download .vcs calendar file

  Click here to add event to your Google Calendar

Paper provided by the ACM Digital Library

Paper also available from IEEE Computer Society