[Nets-seminars] UCL Electronic Engineering Seminar 9th May 2014

[Richard G. Clegg]

So, our seminars start again on Friday next week with a visitor from 
Cambridge.  The talk will be at 16:00 on 9th May 2014 in GS/102 (66-72 
gower street).  If you are coming from outside UCL please let me know so 
I can arrange access.

Title: Scale-up Graph Processing in Single Computer: A Storage-centric View

The determinant of performance in scale-up graph processing on single 
computers is the speed at which graphs can be fetched from storage: 
either from disk into memory or from memory into CPU-cache. Executing 
algorithms that follow edges inevitably results in random access to the 
storage medium for the graph, which can often be the determinant of 
performance, 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 edges to be read from secondary storage, whereas indexed 
access only requires access to the edges that will be needed. I will 
compare two contrasting approaches and demonstrate the benefit of each; 
then 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: 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/.

-- 
Richard G. Clegg,
Dept of Elec. Eng.,
University College London
http://www.richardclegg.org/