H~2Pregel: A partition-based hybrid hierarchical graph computation approach

摘要

A partition-based hybrid hierarchical graph computation approach, called H~2Pregel is proposed to address the redundant supersteps and inefficient computation problems due to low access locality. The H2Pregel preprocesses the input graph through a distributed recode algorithm to ensure the continuity and sequence of vertex ids, then employs a hybrid approach to combine the advantages of both synchronous and asynchronous models, and hierarchically computes the high proportion of interior messages generated by high quality partition algorithms. Moreover, H~2Pregel leverages configurable parallel threads to accelerate local computation by "sub-supersteps", and employs an exterior messages stealing optimization to avoid extra communication overheads between tasks. We implemented H~2Pregel on Giraph, a classic open source system based on Pregel. The evaluation results on large-scale graphs show that, compared with Pregel in three partition algorithms, H~2Pregel can achieve average speedups by 1.12-4.52 times and decrease average communication messages by 23.5%-55.5%, and average supersteps by 15.8%-82.0%.