Home
Download
Contact
Publications
Graph has been extensively used to abstract complex systems and interactions in emerging ”big data” applications, such as social network analysis, WWW, biological systems and data mining. With the increasing growth in these areas, petabyte-sized graph datasets are produced for knowledge discovery. Basically the knowledge hidden in a large graph includes important entities, anomalous patterns, strong connected entities and so on.
In this project we intend to optimize graph traversal on multi-cores and multi-core clusters. We propose a new asynchronous hybrid parallel BFS algorithm for large scale graphs on multi-core clusters, exploiting both inter-node and intra-node parallelism. The algorithm exploits both intra-node and inter-node parallelism: core-level and memory-level parallelism to improve throughput on multi-core architectures, and pipeline-level parallelism of asynchronous communication to improve scalability on distributed memory architectures.
Experiment on a 32-nodes / 384-cores SMP cluster shows our code is capable to process 1.45 billion edges per second, comparable to a 18,688-nodes/ 224,256-cores Cray XT5-HE according to the published the Graph 500 list (June 2011).
Our code is hosted at gitorious.org (link).
Here is a step by step manual of how to compile and test our code.
Welcome to feed back to Huiwei Lv and Guangming Tan.