In this tutorial we'll implement a parallel version of Breadth-First Search in GBBS. Given a graph, , and a source node , a Breadth-First Search processes the graph level by level, starting from . The output of the algorithm is an array s.t. holds the parent of in the breadth-first tree rooted at .
In what follows we will reimplement the BFS algorithm shown in the file above and go through all of the steps to create a new benchmark in GBBS.
To get started, cd into the
benchmarks/BFS directory and create a
BFS_tutorial. Create two new files in this directory,
We will start with the interesting algorithmic code in
Let's start by creating a stub for the BFS function:
One of the goals of GBBS is to abstract away implementation specific details about how the graph is represented. Towards this goal, the algorithm implementations in GBBS typically take the graph type as a template argument, as shown above. This approach lets us run the same code on the graph whether it is compressed or uncompressed, and directed or undirected.
uintE type name is an integer type used to represent vertex-ids
in GBBS (the analogous type for edge-ids is
uintT although we won't
use it in this implementation).
The BFS function's signature indicates that it takes as input a graph, and a source vertex-id and returns a sequence of integers representing the parent of each vertex in the BFS tree.
Next, modify the BFS implementation to the following:
Here, we set
W to the weight-type in the provided graph. For
unweighted graphs, this is the type of an empty struct (with no data),
and otherwise it is the graph's weight type, e.g.,
Next, we set the
Parents array to a sequence containing (
elements where the i'th element is some suitable null value, in this
case the maximum unsigned
UINT_E_MAX. Note that the
initialization of this sequence will happen in parallel when we use a
We also set the parent of the source vertex to itself.
So far, we have set up the variables and data necessary for the algorithm, and we're ready to start the interesting parts of the BFS.
#Representing a Frontier
We can express a frontier generated by the BFS with the
datatype (from the Ligra interface), which lets us represent a subset
of the vertices. Each level of the traversal will be represented by a
vertexSubset. The initial
vertexSubset, is just a set containing
our source node can be constructed the following constructor
#Traversing a Frontier
Now, we need to describe the logic to produce the next frontier given the current
edgeMap (from the Ligra interface)
allows us to process the out edges of a
vertexSubset, and produce a
The behavior of
edgeMap is intended to be customized by providing a
edgeMap expects a parameter of some template
F that has the following fields:
There is an important distinction between
that we will discuss later. For now, we will make sure that all
update logic is atomic. Atomicity is important because if the
vertex has more than one in-edge from the current frontier, then
multiple calls to
update can happen in parallel which may result in
an incorrect result.
For our BFS, let's implement a struct
updateAtomic: atomically update
Parentsarray. We can implement this using a compare and swap operation, which is provided in the
cond: avoid revisiting previously visited vertices by checking if
Parents[v] == UINT_E_MAX.
Add this code before the definition of
Notice that while
BFS_F will correctly produce the next frontier, the
tree computed by the BFS is still non-deterministic! We will discuss how to
fix this in a later section.
#Implementing Traversal Logic
All we need to do to finish up the BFS is to actually call
add a termination condition that signifies when the traversal is finished.
Given a current frontier, our condition should just apply the edgeMap while
the current frontier is non-empty. In code:
#The Final Algorithm
Our finished BFS algorithm should look as follows:
At this point we have created a BFS implementation
#Wrapping up: BFS.cc and Build-files.
Lastly, let's see what code we need to add in order to create a binary to
run BFS on graph inputs. Place the following code in
The main points of interest in this code are the
which is a macro defined by GBBS (see
gbbs/benchmark.h) that first loads
the graph supplied as input by the user, and calls
false flag passed to this macro indicates that this application does not
modify the input graph. The macro expects a runner function that takes as
input a graph and a
commandLine object which supplies the command-line
arguments provided by the user.
Lastly, if you are using Bazel add a file called
BUILD with the following
contents to this directory:
This BUILD file contains two build rules, which tells Bazel how to build
the desired outputs, such as executable binaries (
cc_library). Build rules are also called targets, and point to
a specific set of source files and dependencies. A target can also point to
other targets, as seen in the dependencies for
You can read more about Bazel here.
Using Bazel you can compile the application the BFS application as follows:
make you can copy the makefile from
benchmarks/BFS/NondeterministicBFS/makefile, and run
Let's try running our program on one of the test-inputs provided by Ligra in the
The flags above indicate the following:
-sflag indicates that the graph is symmetric.
-roundsflag indicates the number of times to run the benchmark.
-srcflag indicates the source vertex.
Great! We've successfully implemented a shared memory breadth-first search in GBBS. You should now have all of the pieces needed to implement new benchmarks in GBBS.