Graph-Based Threaded Algorithms
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? James --- James C. Sutherland Assistant Professor, Chemical Engineering The University of Utah 50 S. Central Campus Dr, 3290 MEB Salt Lake City, UT 84112-9203 (801) 585-1246 http://www.che.utah.edu/~sutherland
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@gmail.com
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.
Thank you for the tips, Andrew. What about the case where we have a child waiting on multiple parents? That seems like a bit more difficult case...? James
Thank you for the tips, Andrew. What about the case where we have a child waiting on multiple parents? That seems like a bit more difficult case...?
It should never happen if you're responding to the on_tree_edge. The nice thing is that the discovery of edges in a BFS (and DFS and the MST algorithms) is that id builds a tree, meaning that every node has only one parent. If you do have multiple parents (aka polytree)... I'm not sure. You could invert the process and have each child start waiting on a semaphore initialized with its number of parents (I forget the exact terminology). Each parent signals the semaphore when its done, and the child thread will be woken up when the semaphore reaches 0. I think you can do this with condition variables also. Andrew Sutton andrew.n.sutton@gmail.com
________________________________
Date: Tue, 23 Dec 2008 12:54:55 -0500 From: andrew.n.sutton@gmail.com To: boost-users@lists.boost.org Subject: Re: [Boost-users] Graph-Based Threaded Algorithms
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?
For the sake of argument, I'll assume you have a multi-processor system and the work assigned to each thread is large compared to the fixed costs of spawning etc. Before you just relegate everything to the thread scheduler, consider what benefits your may get from cache coherency and see if doing everything on one thread, or even refactoring the threads' work to maximize coherency within each one, can be used to reduce cache thrashing. The prefethcer can do better if your code makes predictable memory accesses. It is also important to think about literal multi-processor targets as opposed to multi-core. In the latter case, cache coherency can an issue ( see my earlier post citing an IEEE article on some problems others have found). I would generally be worried about memory access patterns first and if you do use threads make sure they don't fight over the cache. They are great when you have asynchronous unpredictable events or can split up work among processors but I wouldn't use them as the first line of attack even on multi-core targets when you can benefit from more predictable execution order.
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@gmail.com
_________________________________________________________________ Send e-mail faster without improving your typing skills. http://windowslive.com/online/hotmail?ocid=TXT_TAGLM_WL_hotmail_acq_speed_12...
participants (3)
-
Andrew Sutton -
James C. Sutherland -
Mike Marchywka