Date: October 7, 2016
Speaker: Prof. Xuehai Qian (University of Southern California)
Location: DBH 6011
Time: 11am – 12pm
Host: Harry Xu
Title: Breaking the Myth of “Think as a Vertex”
Abstract: The importance of iterative graph algorithms has grown due to their widespread use in graph analytics. Many real-world problems, such as online social networks, web graphs, user-item matrices, and more, can be represented as graph computing problems. Recently, several graph processing frameworks based on the principle of “think like a vertex” are developed where user-defined programs can be implemented from the perspective of a vertex rather than a graph.
In this talk I will try to break the myth of several assumptions in the current frameworks. In distributed graph processing, for certain applications, the property of vertices can be further divided, which leads to a new 3D partitioning method. It could greatly reduce the inter-node communication and improve performance. For out-of-core systems, the semi-external memory graph processing keeps all vertices in memory. Unfortunately, current programming models schedule vertices only once each iteration or fully asynchronously and only allow vertices to see their neighborhoods. We propose a new programming model that lifts the two constrains, making it possible to develop better algorithms with much less number of iterations. We implemented a distributed graph processing system “CUBE” and an out-of-core system “CLIP” based on the insights. We show that CUBE outperforms state-of-the-art graph-parallel system PowerLyra by up to 4.7x (up to 7.3x speedup against PowerGraph). With much less number of iterations, CLIP can run tens or sometimes even thousands times faster than state-of-the-art systems X-Stream and GridGraph.
Bio: Xuehai Qian is an assistant professor at the Ming Hsieh Department of Electrical Engineering and the Department of Computer Science at the University of Southern California. He has a Ph.D. from the Computer Science Department at University of Illinois at Urbana-Champaign. He has made several contribution to parallel computer architecture, including cache coherence for atomic block execution, memory consistency check, architectural support for deterministic record and replay. His recent research interests include system/architectural supports for graph processing, transactions for Non-Volatile Memory and acceleration of machine learning and graph processing using emerging technologies.
Return to the Fall 2016 CS Seminar Series Schedule