Parallel Breadth-first Search Algorithms

With the development of computer science, the search technology of graphs hasemerged in linguistics, logic, physics, chemistry, electronics, communication,mathematics and some other fields of science. Especially with the fast progress ofinternet technology and the appearance of parallel computer systems, parallel managehas in an unprecedented boom period and the problem of traversing graphs is more andmore important. Breadth-First search algorithm is a basic problem of graph theory andalso a hot problem. The parallelism of Breadth-First search algorithm has been anurgent problem.First of all, this paper introduces the status about parallel breadth-first searchalgorithms. Secondly, we replace the shared queue with a new “bag” data structurewhich is more amenable for code parallelization with the cilk++run-time model, andthis is a fine-grained parallel algorithms based on layer synchronization theory. Thirdly,we achieve a parallel breadth-first search algorithms based on one-dimensionaldecomposition of the adjacency matrix corresponding to the graph. Finally, analyzingthe methods present of parallel breadth-first search and combining with the currentparallel system conditions we have, this paper proposes a new method of parallelbreadth-first algorithm. This algorithm combines the level-synchronous theory andtwo-dimension partition thought of the adjacency matrix. Plenty of experiments provethat this new algorithm reaches a better performance of time complexity, and moresuitable for distributed memory systems.