Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Say, I am using a simple recursive algo for fibonacci , which would be executed as:

fib(5) -> fib(4)+fib(3)
            |      |
      fib(3)+fib(2)|
                fib(2)+fib(1)

and so on

Now, the execution will still be sequential. Instead of that, how would I code this so that fib(4) and fib(3) are calculated by spawning 2 separate threads, then in fib(4), 2 threads are spawned for fib(3) and fib(2). Same for when fib(3) is split to fib(2) and fib(1) ?

(I'm aware that Dynamic programming would be a much better approach for Fibonacci, just used it as an easy example here)

(if someone could share a code sample in C\C++\C# as well, that would be ideal)

share|improve this question
2  
Of course this is possible – and sometimes it will even be useful. The only condition is that fib should be a pure function (which presumably is the case here). A nice property then is that if the sequential recursive version is correct, the parallel version will be correct as well. But if it is incorrect and features infinite recursion, you will have suddenly created a fork bomb. –  amon May 11 at 15:58
    
Is thread pooling possible in this case? I think it's not, since the thread that calculates fib(n) won't finish until it gets the results from both fib(n-1) and fib(n-2). This will cause a deadlock, since in order for a thread to finish and return to the poll it'll need to take another thread from the pool. Is there a way around this? –  Idan Arye May 11 at 16:20
1  
You might find Recursive calculations using Mapreduce on Stack Overflow an interesting read. –  MichaelT May 12 at 0:15

4 Answers 4

up vote 17 down vote accepted

This is possible but a really bad idea; work out the number of threads you will spawn when calculating fib(16), say, and then multiply that by the cost of a thread. Threads are insanely expensive; doing this for the task you describe is like hiring a different typist to type each character of a novel.

That said, recursive algorithms are often good candidates for parallelization, particularly if they split the job into two smaller jobs that can be performed independently. The trick is to know when to stop parallelizing.

In general, you want to parallelize only "embarrassingly parallel" tasks. That is, tasks which are computationally expensive and can be computed independently. Many people forget about the first part. Threads are so expensive that it only makes sense to make one when you have a huge amount of work for them to do, and moreover, that you can devote an entire processor to the thread. If you have 8 processors then making 80 threads is going to force them to share the processor, slowing each one of them down tremendously. You do better to make only 8 threads and let each have 100% access to the processor when you have an embarrassingly parallel task to perform.

Libraries like the Task Parallel Library in .NET are designed to automatically figure out how much parallelism is efficient; you might consider researching its design if this subject interests you.

share|improve this answer

Of course it's possible, but for such a small example (and, indeed, for many that are much larger) the amount of plumbing/concurrency control code you'd have to write would obscure the business code to the point that it wouldn't be a good idea unless you really, really, really need Fibonacci numbers computed very fast.

It's almost always more readable and maintainable to formulate your algorithm normally and then let a concurrency library/language extension such as TBB or GCD take care of how to actually distribute the steps to threads.

share|improve this answer

In your example you are calculating fib(3) twice, which leads to double execution of the whole fib(1) and fib(2), for higher numbers it is even worse.

You will gain probably speed over the nonrecursive solution, but it will cost a lot more in resources (processors) than it's worth.

share|improve this answer

The question has two answers, actually.

Can recursion be done in parallel? Would that make sense?

Yes, of course. In most (all?) cases, a recursive algorithm can be rewritten in a way without recursion, leading to an algorithm that is quite often easily parallelizable. Not always, but often.

Think Quicksort, or iterating through a directory tree. In both cases a queue could be used to hold all the intermediate results resp. sub-directories found. The queue can be processed in parallel, eventually creating more entries until the task has been completed successfully.

What about the fib() example?

Unfortunately, the Fibonacci function is a bad choice, because the input values complety depend on previously calculated results. This dependency makes it hard to do it in parallel if you start every time with 1 and 1.

However, if you need to do Fibonacci calculations more often, it could be a good idea to store (or cache) pre-calculated results in order to avoid all calculations up to that point. The concept behind is quite similar to rainbow tables.

Lets say, you cache every 10th Fibo number pair up to 10.000. Start this initialization routine on a background thread. Now, if someone asks for Fibo number 5246, the algorithm simply picks up the pair from 5240 and start calculation from that point forward. If the 5240 pair is not yet there, just wait for it.

This way the calculation of many randomly choosen fibo numbers could be done very efficiently and in parallel, because it is very unlikely that two threads will have to calculate the same numbers - and even then, it would not be much of a problem.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.