Graph Algorithms with fork/join

The equivalent of the hello world for parallel languages is the quicksort algorithm. The quicksort algorithm is based on the divide et impera principle, which makes it a good candidate for parallelization. In this article we will go past arrays and apply parallelism to more complex data structures such as graphs.

We will start by performing a DFS (Depth First Search). Given a starting node, visit all other reachable nodes. This algorithm can be adapted to solve many problems. Let’s see the basic form of this algorithm:

public void dfs(Node n) {
  Set<Node> visitedNodes = new HashSet<Node>();
  dfs(n, visitedNodes);
}

private void dfs(Node n, Set<Node> visitedNodes) {
  if (!visitedNodes.contains(n)) {
    doSomeStuff(n);
    visitedNodes.add(n);
    for(Node neighbor: n.getNeighbors()) {
      dfs(neighbor, visitedNodes);
    }
  }
}

The straightforward translation using the fork/join framework would look like:

public class DFS extends RecursiveAction {
  public DFS(Node n) { this(n, new HashSet<Node>()); }

  private DFS(Node n, Set<Node> visitedNodes) {
    this.n = n;
    this.visitedNodes = visitedNodes;
  }

  public void compute() {
    if (!visitedNodes.contains(n)) {
      doSomeStuff(n);
      visitedNodes.add(n);
      DFS[] subtasks = new DFS[n.getNeighbors().size()];
      for(int i = 0; i < n.getNeighbors().size(); i++) {
        subtasks[i] = new DFS(n.getNeighbors().get(i), visitedNodes);
      }
      forkJoin(subtasks);
    }
  }
}

You may have noticed that this code is actually not thread safe. If we have a subgraph with a diamond topology, we may end up visiting a node more than once. In the failing scenario one thread will check whether node has been visited, and while it’s visiting the node, another thread would arrive to the same node via a different route, seeing that the node hasn’t been visited and start visiting it.

In order to fix that we must add a bit of synchronization. First of all we will mark a node as being visited even before visiting it, then we will define a critical section around the check and mark operations:

  public void compute() {
    boolean shouldVisit;
    synchronized(visitedNodes) {
      shouldVisit = !visitedNodes.contains(n);
      visitedNodes.add(n);
    }
    if (shouldVisit) {
      doSomeStuff(n);
      DFS[] subtasks = new DFS[n.getNeighbors().size()];
      for(int i = 0; i < n.getNeighbors().size(); i++) {
        subtasks[i] = new DFS(n.getNeighbors().get(i), visitedNodes);
      }
      forkJoin(subtasks);
    }
  }

Ok, so now we have a working algorithm, but there still is a problem. Can you spot it? Try to figure out a solution.
I will post the solution in my next post and talk a little bit about a parallel BFS (Breadth First Search).

Advertisements

One comment

  1. Looking forward to the rest of your solution so I can do one in Erlang and we’ll compare them 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s