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.Graph500 This article discusses the possibility of speeding up BFS through the use of parallel computing.
Serial breadth-first search
In the conventional sequential BFS algorithm, two data structures are created to store the frontier and the next frontier. The frontier contains all vertices that have the same distance (also called "level") from the source vertex, these vertices need to be explored in BFS. Every neighbor of these vertices will be checked, some of these neighbors which are not explored yet will be discovered and put into the next frontier. At the beginning of the BFS algorithm, a given source vertex s is the only vertex in the frontier. All direct neighbors of s are visited in the first step, which form the next frontier. After each layer-traversal, the "next frontier" is switched to the frontier and new vertices will be stored in the new next frontier. The following pseudo-code outlines the idea of it, in which the data structures for the frontier and next frontier are called FS and NS respectively.
1 define bfs_sequential(graph(V,E), source s): 2 for all v in V do 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;
First step of parallelization
As a simple and intuitive solution, the classic Parallel Random Access Machine (PRAM) approach is just an extension of the sequential algorithm that is shown above. The two for-loops (line 7 and line 8) can be executed in parallel. The update of the next frontier (line 10) and the increase of distance (line 11) need to be atomic. Atomic operations are program operations that can only run entirely without interruption and pause (i.e. "all or nothing").
However, there are two problems in this simple parallelization. Firstly, the distance-checking (line 9) and distance-updating operations (line 11) introduce two benign races. The reason of race is that a neighbor of one vertex can also be the neighbor of another vertex in the frontier. As a result, the distance of this neighbor may be examined and updated more than one time. Although these races waste resource and lead to unnecessary overhead, with the help of synchronization, they don't influence the correctness of BFS, so these races are benign. Secondly, in spite of the speedup of each layer-traversal due to parallel processing, a barrier synchronization is needed after every layer in order to completely discover all neighbor vertices in the frontier. This layer-by-layer synchronization indicates that the steps of needed communication equals the longest distance between two vertices, O(d), where O is the big O notation and d is the graph diameter.
This simple parallelization's asymptotic complexity is the same as that of the sequential algorithm in the worst case. Better BFS parallelization can be achieved with optimizations, such as:
Mitigating barrier synchronization. Barrier synchronization is necessary after each layer-traversal to ensure correctness. Reducing the cost of barrier synchronization is an effective way to speed up parallel BFS. Load-balancing for neighbor discovery. Because there is a barrier synchronization after each layer-traversal, every processing unit must wait for the last one to finish its work. Therefore, the processing unit with the most neighbors decides the time consumption of this layer. With the optimization of load-balancing, the time of layer-traversal can be reduced. Improving the locality of memory references. In parallel systems with distributed memory, remote memory references are accessing data from other processing units, which usually incurs extra communication cost compared to local memory access. A more efficient data structure design or organization of data can reduce the need for remote memory access, hence reducing the total communication cost.
Parallel BFS with shared memory
Compared to parallel BFS with distributed memory, shared memory provides higher memory-bandwidth and lower latency due to direct access by all processors. Therefore, the overhead of message passing, which is necessary for distributed memory access, is avoided."Designing multithreaded algorithms for breadth-first search and st-connectivity on the Cray MTA-2.", Bader, David A., and Kamesh Madduri. 2006 International Conference on Parallel Processing (ICPP'06). IEEE, 2006.
However, the number of vertices in each layer and the number of neighbors of each vertex are shown to be highly irregular, which leads to highly irregular memory accesses and work distribution of BFS. In parallel BFS, this feature reduces the benefits from parallelization due to unbalanced load. As a result, it is very important to make the parallel BFS with shared memory load-balanced. Moreover, exploring data-locality can also speed up parallel execution.
Parallel BFS algorithms with shared memory can be divided into two types: container centric approaches and vertex centric approaches."Level-synchronous parallel breadth-first search algorithms for multicore and multiprocessor systems.", Rudolf, and Mathias Makulla. FC 14 (2014): 26-31.] In the container centric approach, two data structures are created to store the current frontier and the next vertex frontier. The next vertex frontier is switched to the current frontier at the end of each iteration. There is a trade-off between the cost of synchronization and data locality according to the location of data. These two data structures can be held in every processing unit (such as a thread) which supports data locality but needs extra load balancing mechanisms. Alternatively, they can be stored globally to provide implicit load balancing, where special data structures are used for concurrent access, which requires additional effort for synchronization.
Besides, data organization of containers can be optimized. The typical data structure in serial BFS and some parallel BFS is a FIFO Queue, as it is simple and fast (insertion and delete operations have constant time cost).
Another alternative is the bag-structure."A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers).", Leiserson, Charles E., and Tao B. Schardl. Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures. ACM, 2010. The insertion operation in a bag takes O(logn) time in the worst-case, whereas it takes only constant amortized time which is as fast as FIFO. Furthermore, union of two bags takes Θ(lgn) time where n is the number of elements in the smaller bag. The bag-split operation also takes Θ(lgn) time. With the help of bag-structure, a certain number of vertices (according to granularity parameter) are stored in one bag and the bag-structure becomes the basic parallel entity. Moreover, the reducer can be combined with the bag-structure to write vertices in parallel and traverse them efficiently.
The vertex centric approach treats a vertex as parallel entity，which enables parallel iteration. Each vertex is assigned to a parallel entity. This vertex centric approach might only work well if the graph depth is very low. Graph depth in BFS is defined as the maximum distance from any vertex in the graph to the source vertex. Therefore, the vertex centric approach is well-suited for GPUs if every thread is mapped to exactly one vertex.
Parallel BFS with distributed memory
In the distributed memory model, each processing unit has its own memory. Because of this, processing units must communicate via message passing to share their local data and access remote data.
1-D partitioning
1D partitioning is the simplest way to combine the parallel BFS with distributed memory. It is based on vertex partitioning. Load balancing is still an important issue for data partitioning, which determines how we can benefit from parallelization. In other words, each processing unit with distributed memory should be in charge of approximately the same number of vertices and their outgoing edges. For the implementation of data storage, each processor can store an adjacency matrix of its local vertices, in which each row for each vertex is a row of outgoing edges represented by destination vertex indices.
As opposed to shared memory BFS, the neighbor vertex from one processing unit may be stored in another processing unit. As a result, each processing unit is responsible to tell other processing units about traversal status by sending them messages. Moreover, each processing unit should also deal with the messages from all other processing units to construct its local next vertex frontier. Obviously, one all-to-all communication (which means each unit has different messages for all others) is necessary in each step when exchanging the current frontier and the next vertex frontier.
The following pseudo-code of a 1-D distributed memory BFS"A scalable distributed parallel breadth-first search algorithm on BlueGene/L.", Yoo, Andy, et al. Proceedings of the 2005 ACM/IEEE conference on Supercomputing. IEEE Computer Society, 2005. was originally designed for IBM BlueGene/L systems, which have a 3D torus network architecture. Because the synchronization is the main extra cost for parallelized BFS, the authors of this paper also developed a scalable all-to-all communication based on point-to-point communications. After that, they also reduced the number of point-to-point communication, taking advantage of its high-bandwidth torus network.
The main steps of BFS traversal in the following algorithm are:
processor view (line 8): construct the frontier FS with vertices from local storage global view (line 10–11): terminate the traversal if FS from all processors are empty processor view (line 13): construct the next frontier based on the neighbors vertex of its FS, although some of their neighbors may be stored in other processors global view (line 15–18): run an all-to-all communication to let each processor know, which local vertices should be put into its local next frontier NS processor view (line 20–22): receive messages from all other processors, update the distance value of their local vertices in the current frontier, change its NS to FS
1 define 1_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; 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 <= j < p do: 16 N_j = {vertices in NS owned by processor j} 17 send N_j to processor j 18 receive N_j_rcv from processor j 19 //combine the received message to form local next vertex frontier then update the level for them 20 NS_rcv = Union(N_j_rcv) 21 for v in NS_rcv and d[v] == -1 do 22 d[v] = level + 1
Combined with multi-threading, the following pseudo code of 1D distributed memory BFS also specifies thread stack and thread barrier, which comes from the paper."Parallel breadth-first search on distributed memory systems.", Buluç, Aydin, and Kamesh Madduri. Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. ACM, 2011.