SC15 Austin, TX

Energy-Efficient Graph Traversal on Integrated CPU-GPU Architecture

Authors: Heng Lin (Tsinghua University), Jidong Zhai (Tsinghua University), Wenguang Chen (Tsinghua University)

Abstract: Recently, architecture designers tend to integrate CPUs and raphics Processing Units(GPUs) on the same chip to produce energy-efficient designs. On the other hand, graph applications are becoming increasingly important for big data analysis. Among the graph analysis algorithms, Breadth-First Search (BFS) is the most representative one and also an important building block for other algorithms. Despite previous efforts, it remains an important problem to get optimal performance for BFS on integrated architectures. In this paper, we propose an adaptive algorithm to atomically find the optimal algorithm on the suitable devices, which can get 1.6X speedup compared with the state-of-the-art algorithms in an energy consumption index, namely TEPS/Watt(Traversed Edges Per Second every Watt).

Poster: pdf
Two-page extended abstract: pdf

Poster Index