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.
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.
… excerpt ends here. Continue reading the full article.
