Optimization communication for BFS based on 1D-partition
Chengyao Liu · Journal of Physics Conference Series · 2020
Abstract Parallel Breadth First Search (BFS) is a famous algorithm in Graph500, a benchmark function for evaluating data-intensive applications on supercomputers. For parallel breadth first search (BFS) algorithms on large-scale distributed memory systems, the cost of communication is usually much higher than the arithmetic cost, which limits the scalability of the algorithm. However, the specific communication model of Graph500 brings challenges to computing in large-scale graphs. First, we use an adjustment method to delete redundant data in messages. Second, a data compression method was used to further reduce comm-unication. Evaluation results show that the performance of this method is more efficient than graph500 benchmark.