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

Question

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)

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

Yes it can! My simplest example I can give you is imagine a binary tree of numbers. For some reason you want to add up all the numbers in a binary tree. Well to do so, you need to add value of the root node to the value of the left/right node....but the node itself may be the root of another tree (a subtree to the original tree)
Instead of calculating the sum of the left subtree, then then the sum of the right...then add them to the value of the root...you can calculate the sum of the left and right sub-tree in parallel.

Answer 6

One problem is that the standard recursive algorithm for the fibonacci function is just awfully bad, since the number of calls to calculate fib (n) is equal to fib (n) which is a very fast growing. So I would really refuse to discuss that one.

Let's look at a more reasonable recursive algorithm, Quicksort. It sorts an array by doing the following: If the array is small then sort it using Bubblesort, Insertion sort, or whatever. Otherwise: Pick one element of the array. Put all the smaller elements to one side, all the larger elements to the other side. Sort the side with the smaller elements. Sort the side with the larger elements.

To avoid arbitrarily deep recursion, the usual method is that the quick sort function will do a recursive call for the smaller of the two sides (the one with fewer elements) and handle the larger side itself.

Now you have a very simple way to use multiple threads: Instead of making a recursive call to sort the smaller side, start a thread; then sort the bigger half, then wait for the thread to finish. But starting threads is expensive. So you measure how long it takes on average to sort n elements, compared to the time for creating a thread. From that you find the smallest n such that it is worthwhile to create a new thread. So if the smaller side that needs to be sorted is below that size, you do a recursive call. Otherwise, you sort that half in a new thread.