In this project we'll implement a parallel version of Breadth-First Search in Ligra. Given a graph, $G = (V,E)$, and a source node $s$, a Breadth-First Search processes the graph level by level, starting from $s$. The output of the algorithm is an array $A$ s.t. $\forall v \in V, A[v]$ holds the parent of $v$ in the breadth-first tree rooted at $s$.
One of the main goals of Ligra is to abstract away implementation specific details
about how the graph is represented (Is the graph compressed/uncompressed? Is it
directed/undirected?). The standard way of implementing an algorithm in Ligra is
to implement a method, Compute, which has the following signature:
template <class vertex>
void Compute(graph<vertex>& G, commandLine P);
To get started, cd into the tutorial/ directory and open up the file BFS.C.
We will examine the code piece by piece.
#include "ligra.h"
template <class vertex>
void Compute(graph<vertex>& G, commandLine P) {
long start = P.getOptionLongValue("-r",0);
long n = GA.n;
//creates Parents array, initialized to all -1, except for start
long* Parents = new long[n];
parallel_for(long i=0;i<n;i++) Parents[i] = -1;
Parents[start] = start;
}
So far, we have set up the variables and data necessary for the algorithm.
We use parallel_for to initialize memory in parallel. This statement
is just a macro that is replaced by either a parallel loop if we are using
OpenMP or Cilk, or a standard for loop if OpenMP or CILK is unavailable. Note that
all memory we allocate in the body of Compute must be explicitly freed
in order to prevent memory leaks.
We can express a frontier generated by the BFS with the vertexSubset
datatype in Ligra, 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
vertexSubset Frontier(n, source); // creates initial frontier
Now, we need to describe the logic to produce the next frontier given the current
frontier. Enter edgeMap. edgeMap allows us to process the out edges of a
vertexSubset, and produce a new vertexSubset. Please see the
api for more details.
The behavior of edgeMap is intended to be customized by providing a
user-defined structure. edgeMap expects a parameter of some template class
F that has the following fields:
struct F {
F(...) { ... }
inline bool update (long s, long d) {
// logic for how to process the edge (s,d)
}
inline bool updateAtomic (long s, long d) {
// logic for how to process the edge (s,d)
}
inline bool cond (long d) {
// return 1 if update should be applied on and edge (s,d)
// return 0 otherwise
}
};
There is a subtle, but important distinction between update and updateAtomic 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 BFS_F where
updateAtomic: atomically update Parents array. We can implement this using a
compare and swap operation. A simple, implementation independent version
is provided by the framework as CAS in ligra/utils.h.cond: avoid revisiting previously visited vertices.struct BFS_F {
long* Parents;
BFS_F(long* _Parents) : Parents(_Parents) { }
inline bool updateAtomic (long s, long d) { // atomically update
return (CAS(&Parents[d],(long)-1,s));
}
inline bool update (long s, long d) { // defer to updateAtomic
return updateAtomic(s, d);
}
//cond function checks if vertex has been visited yet
inline bool cond (long d) { return (Parents[d] == -1); }
};
Add this code before the definition of Compute.
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.
All we need to do to finish up the BFS is to actually call edgeMap, and
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:
while(!Frontier.isEmpty()){ //loop until frontier is empty
vertexSubset output = edgeMap(GA, Frontier, BFS_F(Parents));
Frontier.del();
Frontier = output; //set new frontier
}
The last step is to just free any memory allocated in the body of Compute. Our
finished BFS algorithm should look as follows:
#include "ligra.h"
struct BFS_F {
long* Parents;
BFS_F(long* _Parents) : Parents(_Parents) {}
inline bool updateAtomic(long s, long d) { // atomically update
return (CAS(&Parents[d],(long)-1,s));
}
inline bool update(long s, long d){ // defer to updateAtomic
return updateAtomic(s, d);
}
//cond function checks if vertex has been visited yet
inline bool cond(long d) { return (Parents[d] == -1); }
};
template <class vertex>
void Compute(graph<vertex>& GA, commandLine P) {
long start = P.getOptionLongValue("-r",0);
long n = GA.n;
//creates Parents array, initialized to all -1, except for start
long* Parents = new long[n];
parallel_for(long i=0;i<n;i++) Parents[i] = -1;
Parents[start] = start;
vertexSubset Frontier(n,start); //creates initial frontier
while(!Frontier.isEmpty()){ //loop until frontier is empty
vertexSubset output = edgeMap(GA, Frontier, BFS_F(Parents));
Frontier.del();
Frontier = output; //set new frontier
}
Frontier.del();
free(Parents);
}
Compile the application by running make, which will produce a binary called
BFS.
Let's try running our program on one of the test-inputs provided by ligra in the inputs/
directory. Note that the -s flag tells Ligra that the graph is symmetric (undirected) and the -r flag indicates the source vertex.
./BFS -s -r 1 ../inputs/rMatGraph_J_5_100
Running time : 0.000234
Running time : 0.000359
Running time : 0.000243
Great! We've successfully implemented a shared memory breadth-first search using Ligra. In the remaining tutorials, we will consider more complicated graph algorithms and introduce the remaining parts of the Ligra API.