TianheGraph: Topology-aware Graph Processing

Abstract

Many real-world graph data can have billions to trillions of edges. Processing graphs at such scales requires the efficient use of parallel computing systems. However, current graph processing engines and methods struggle to scale beyond a few dozen computing nodes because they (i) cannot efficiently store and process graph data on this scale due to the huge memory footprint incurred and (ii) do not account for the variations in communication costs across different levels of the interconnection hierarchy. We introduce TianheGraph, a software approach to reduce the memory footprint of graphs and optimize graph processing on large-scale parallel systems with complex hardware interconnection components. TianheGraph integrates a new space-time-efficient graph compression technique to reduce the memory footprint of large-scale graphs. It provides a novel graph partitioning method to improve load balancing and minimize communication overhead across various levels of the interconnection hierarchy. We evaluate TianheGraph by applying it to fundamental graph operations on synthetic and real-world graphs, using up to 79,024 computing nodes and over 1.2 million processor cores. Our extensive experiments show that TianheGraph outperforms state-of-the-art parallel graph processing engines in throughput and scalability. Moreover, TianheGraph outperformed the top-ranked systems on the Graph 500 list at the time of submission.