Enabling application-aware flexible graph partition mechanism forrnparallel graph processing systems

摘要

With the emerging of the large-scale graph data, Pregel-like graph parallel processing systems have been anrnessential tool to efficiently process the graph data. The first step to use the Pregel-like systems is to partitionrnthe graph into multiple blocks and distribute them on multiple machines. The partition strategy plays arnsignificant role in determining the performance because a good partition could both ensure load balancernand optimize network communication overhead, and vice versa. However, existing partition strategies failrnto meet the requirements because they suffer from the following drawbacks: (1) they ignore the applicationrnfeatures and (2) they ignore the multi-application feature in productive environment. To overcome thoserndrawbacks, we proposed the superblock partition strategy, which utilizes the atomic blocks generated byrnpre-processing of the original graph and could be constructed and re-constructed dynamically accordingrnto the submitted applications in real time. The hash-based and clustering-based pre-partition methods arerncovered in details. The application feature extraction method and heuristic superblock partition algorithmrnare proposed to construct the superblocks. Experimental results show that the superblock partition strategyrncould boost the graph processing performance and its partition efficiency also outperforms the hash-basedrnand topology optimal partition strategy. Copyright © 2016 John Wiley & Sons, Ltd.