Paper Info
Title
The Communication Analysis of Implementation in Breadth First Search Algorithm.
Abstract
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 primitivesu0027 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.
Year
Venue
Field
2016
iThings/GreenCom/CPSCom/SmartData
Data processing,Algorithm design,Computer science,Parallel computing,Breadth-first search,Communication in small groups,Models of communication,Network calculus,Communication Analysis,Computer cluster
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Yichun Sun100.34
Xiaodong Yi25920.16
Hengzhu Liu38623.28