Scale-up Graph Processing in Single Computer, talk by Dr Eiko Yoneki, University of Cambridge

ABSTRACT

Processing graphs that have billions of vertices and edges in a single computer requires secondary storage as external memory. Executing algorithms results in access to such secondary storage and performance of I/O takes in important role, regardless of the algorithmic complexity or runtime efficiency of the actual algorithm in use. A storage-centric viewpoint would suggest a solution to this problem in recognising that graphs represent a unique workload, and therefore should be treated as such by adopting novel ways to access graph structured data. Two approaches have emerged: using indexed random access or streaming sequential access. Streaming sequential access takes advantage of the fact that sequential access bandwidth is much larger than random access bandwidth, but it requires all graph data to be read from secondary storage, whereas indexed access only requires access to the required part of graph data. I will compare two contrasting approaches and demonstrate the benefit of each, introduce a new hybrid approach that dynamically chooses, for each iteration of a graph algorithm, between indexed and streaming access. I will also briefly introduce our ongoing work on hybrid graph computation task scheduling using Accelerated Processing Units (APUs), where GPU cores are integrated into CPU chip design. This approach gives significant performance improvement on skewed graph computation workload.

BIO

Dr Eiko Yoneki is an EPSRC Research Fellow in the Systems Research Group of the University of Cambridge Computer Laboratory. Her current research focuses on the exploration of new abstractions for supporting the design and implementation of robust and heterogeneous large-scale graph data processing, ranging from cluster computing to single computer environments. More information can be found at http://www.cl.cam.ac.uk/~ey204/.

Date/time: 
Friday, May 23, 2014, 10:30
Location: 
SICS, room Knuth
Isafjordsgatan 22
Kista
Sweden
SE