GraphWorld: Ultra-fast Graph Engine for World-Wide Web Searching

摘要

Graph has recently enabled substantial advances to the Web. Processing worldwide graphs with millions to billions, even trillions of edges in large-scale high-performance systems is pressing, but current graph processing engines are designed for small-scale graph processing beyond a few tens of computing nodes and are unable to scale well to large parallel systems because they are oblivious to imbalanced communication across the communication grid. Therefore, we present GraphWorld, a better approach to optimizing graph search in large parallel systems for world-wide web crawling and indexing.GraphWorld (i) features a new graph partitioning method to achieve better load balancing and minimize communication overhead across the row and column directions; (ii) designs an efficient hardware prefetching and caching mechanism that can gather, traverse, and scatter pipeline vertices to accelerate graph processing; and (iii) proposes υBFS: vectorization-based BFS for leveraging vectorization units equipped in modern high performance processors to further improve graph search.In addition, we used real-world graphs and benchmarks to demonstrate the effectiveness of GraphWorld. In particular, the GraphWorld-based Graph 500 tests on the Tianhe supercomputer are superior to the fastest systems in the latest Graph 500 lists. We finally apply GraphWorld to real-life graphs for the worldwide search of the Web, which outperforms the state-of-the-art graph partitioning and graph system by orders of magnitude.