Jump to content
Jud

Recursion in a multi-threaded program

Recommended Posts

I've written several multi-threaded programs with the parallel library, usually using tasks but one or two using parallel for.  I have a new one that is more natural for parallel for.  The problem is that this is the first one that must use recursion.  Inside the loop there is some initial stuff and then it calls a procedure that calls itself, and that isn't working.

 

If the parallel loop only has one iteration, e.g. parallel.for(1,1 ... ) or parallel.for(2,2 ... ), it works.  But for actual work, with the recursion and parallel.for, it locks up.

How can I get a recursive procedure to work in a multi-threaded program?

 

Share this post


Link to post

It is nothing like Fibonacci.  It is a depth-first search on a graph.  I'm not trying to make the recursion itself recursive - each time through the loop makes an independent call to the recursive procedure.  The instances of the procedure don't have anything to do with each other and there is no global data.  That is, I need to make parallel calls to the procedure; the recursion itself is not parallel.

 

Edited by Jud

Share this post


Link to post

Follow-up.

 

When I put a recursive Fibonacci function in the parallel.for and ran it on various inputs, it worked.  When I called a recursive procedure to do Depth First Search (DFS) on a graph, it would not work if it was doing more than one in parallel. 

 

But then I made a small procedure to start the recursive calls to the DFS procedure and put that small procedure inside the parallel.for instead of the actual call to the DFS procedure, it works!

 

Just in case someone asks about this.

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×