Past Event: Oden Institute Seminar

Reducing Data Movements in Graph Processing: from Distributed System to Emerging Technology

Xuehai Qian, Assistant Professor, University of Southern California

Abstract

The "Big Data revolution" demands unprecedented data processing capability. To meet such demand, the parallel and distributed processing are ubiquitously applied with the increasing computing resources consisting of many-core CPUs, more scalable and cost-effective memory and storage, and other technologies. The distributed and parallel data processing incur significant data movement between machines and across memory hierarchy in the same machine. The data movements not only affect performance but also consume significant energy. A recent study showed that data movements between CPUs and off-chip memory consumes two orders of magnitude more energy and a floating point operation. In this talk, I will introduce our vertically integrated approach on reducing data movement in graph processing applications in various scales from distributed system to emerging technology. First, I will present a novel 3D graph partitioning for distributed graph processing leads to significant reduction of data communication and performance improvement. Second, I will present an expressive programming model designed for semi-external single machine graph processing systems that enables the beyond neighborhood and other constraints. Our system provides up to tens or even thousands times of speedup compared to the state-of-the-art system. Third, I will discuss the acceleration of graph processing at architecture level with PIM and ReRAM, an emerging memory technology with in-situ computation. Finally, I will briefly discuss other research topics in our group and several future research directions. 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 contributions 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.