Parallel breadth-first search
The breadth-first-search algorithm is a way to explore the vertices of a graph layer by layer.
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The breadth-first-search algorithm is a way to explore the vertices of a graph layer by layer. It is a basic algorithm in graph theory which can be used as a part of other graph algorithms. For instance, BFS is used by Dinic's algorithm to find maximum flow in a graph.
Moreover, BFS is also one of the kernel algorithms in Graph500 benchmark, which is a benchmark for data-intensive supercomputing problems. This article discusses the possibility of speeding up BFS through the use of parallel computing.
3 d[v] = -1; 4 d[s] = 0; level = 1; FS = {}; NS = {}; 5 push(s, FS); 6 while FS !empty do 7 for u in FS do 8 for each neighbour v of u do 9 if d[v] = -1 then 10 push(v, NS); 11 d[v] = level; 12 FS = NS, NS = {}, level = level + 1; 4 d[v] = -1; 5 d[s] = 0; level = 0; FS = {}; NS = {}; 6 //begin BFS traversal 7 while True do: 8 FS = {the set of local vertices with level} 9 //all vertices traversed 10 if FS = {} for all processors then: 11 terminate the while loop 12 //construct the NS based on local vertices in current frontier 13 NS = {neighbors of vertices in FS, both local and not local vertices} 14 //synchronization: all-to-all communication 15 for 0 i,j (1) to A i,j (C) blocks. The conventional 1D partitioning is equivalent to the 2D partitioning with R=1 or C=1.
In general, the parallel edge processing based on 2D partitioning can be organized in 2 communication phases, which are "expand" phase and "fold" phase. In the "expand" phase, if the edge list for a given vertex is the column of the adjacency matrix, then for each vertex v in the frontier, the owner of v is responsible to tell other processors in its processor column that v is visited.
That's because each processor only stores partial edge lists of vertices. After this communication, each processor can traverse the column of according to the vertices and find out their neighbors to form the next frontier. In the "fold" phase, vertices in resulting next frontier are sent to their owner processors to form the new frontier locally.
With 2D partitioning, these processors are in the same processor row. The main steps of BFS traversal in this 2D partitioning algorithm are(for each processor): expand phase (line 13–15): based on local vertices, only send messages to processors in processor-column to tell them these vertices are in the frontier, receive messages from these processors.
(line 17–18): merge all receiving messages and form the net frontier N. Notice that not all vertices from received messages should be put into the next frontier, some of them may be visited already. The next frontier only contains vertices that has the distance value −1. fold phase (line 20–23): based on the local vertices in next frontier, send messages to owner processors of these vertices in processor-row.
(line 25–28): merge all receiving messages and update the distance value of vertices in the next frontier. The pseudo-code below describes more details of 2D BFS algorithm, which comes from the paper: 1 define 2_D_distributed_memory_BFS( graph(V,E), source s): 2 // normal initialization 3 for all v in V do 4 d[v] = -1; 5 d[s] = 0; 6 // begin BFS traversal 7 for l = 0 to infinite do: 8 F = {the set of local vertices with level l} 9 // all vertices traversed 10 if F = {} for all processors then: 11 terminate the while loop 12 // traverse vertices by sending message to selected processor 13 for all processor q in this processor-column do: 14 Send F to processor q 15 Receive F q r from q 16 // deal with the receiving information after the frontier traversal 17 F r = Union{F q r } for all q 18 N = {neighbors of vertices in F r using edge lists on this processor} 19 // broadcast the neighbor vertices by sending message to their owner processor 20 for all processor q in this processor-row do: 21 N q = {vertices in N owned by processor q} 22 Send N q to processor q 23 Receive N q r from q 24 // form the next frontier used for next layer traversal 25 N r = Union{N q r } for all q 26 // layer distance update 27 for v in N r and d(v) = -1 do: 28 level = l + 1 In 2D partitioning, only columns or rows of processors participate in communication in "expand" or "fold" phase respectively.
This is the advantage of 2D partitioning over 1D partitioning, because all processors are involved in the all-to-all communication operation in 1D partitioning. Besides, 2D partitioning is also more flexible for better load balancing, which makes a more scalable and storage-efficient approach much easier.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1325818269 under CC BY-SA 4.0; modifications have been made.