The Communication Analysis of Implementation in Breadth First Search Algorithm

摘要

Breadth first search (BFS), specially deals with large graph involving millions of vertices and edges, is a key component in processing bio-informatics, social networks etc. Since the scale of data stored and queried increasing, the performance of BFS algorithm is not satisfied in large amounts of data processing. For efficiently utilizing the processing power of modern processors, researchers optimized the algorithm and proposed four major types of implementation: 1D top-down BFS, 1D bottom-up BFS, 2D top-down BFS, 2D bottom-up BFS. These four types of implementation apply in different parallel computing system according specific conditions. In this paper we construct a MPI communication delay model to analysis these four types of BFS algorithm implementation. Our MPI communication model is based on MPI primitives. We break the four types of BFS algorithm implementation into MPI group communications and non-blocking communications. We extrapolate the latency of non-blocking communication by function of discrete data fitting and applying with network calculus. We take the MPI non-blocking communication as a basic unit to derive MPI group communication latency by analysing MPI primitives. We adopt logic communication and physical communication to discuss the MPI primitives' latency. We seek to obtain the optimal communication buffer in these four types of BFS algorithm implementation. And we try to provide a quantitative solution to choose a suitable topology in communication. Finally we use our experimental platform (a cluster computing system) to validate the proposed model.algorithm implementation. And we try to provide a quantitative solution to choose a suitable topology in communication. Finally we use our experimental platform (a cluster computing system) to validate the proposed model.