Re: [Boost-users] Graph-Based Threaded Algorithms

Subject: Re: [Boost-users] Graph-Based Threaded Algorithms
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2008-12-23 12:54:55

> I am looking for some guidance from some of the graph and thread experts
> out there.
> I have a graph that I want to execute a breadth-first search (BFS) on.
>  When each node is visited, it spawns a thread to execute some work.  I must
> not execute a child node before the parent execution is completed, but I
> also want to maximize concurrency. In other words, I don't want to
> "serialize" the BFS to force proper execution ordering.
>
> Are there any ideas of how to accomplish this efficiently?
>

It's been a while since I've done any serous MT programming, so I'm a bit
rusty and probably a little behind the times.

For the sake of argument, let's say your nor using a thread pool and don't
have any limits on the number of threads you can spawn. You could associate
a condition variable with each vertex using a property map, and make that
available to your BFS visitor. By overriding on_tree_edge, you can get
access to the parent/child vertices in the BFS tree. Your child vertex can
spawn a new thread and wait on the condition variable associated with the
parent. IIRC this means that you can have multiple children waiting on the
parent. When the parent thread is done, it notifies the condition variable,
waking up all of its dependant children. Of course, children wouldn't have
to wait if the parent had already finished, so you'll probably want to make
sure that there's a valid and initialized condition variable before waiting
on it.

Since you probably do have limits on the number of threads you're spawning,
you might use a thread pool to control the pace at which the BFS proceeds.
For example, the main thread can't continue while there are no threads
available.

I think that's the way that I'd start...

Andrew Sutton
andrew.n.sutton_at_[hidden]