-5

It is very tough to convert a sequential code which has recursion in it to an equivalent parallel code written in openmp,CUDA or MPI . Why is it so ?

talonmies
  • 70,661
  • 34
  • 192
  • 269
Abhishek Shridhar
  • 1
  • 1
  • 6
    Your question contains dangling dependencies which have not been calculated yet: which code, what exactly means tough, and who/where are you quoting or citing from exactly? – StarShine Nov 08 '17 at 16:06

1 Answers1

-2

If a piece of code has been written as a recursive algorithm, there is a good chance that the calculations performed in each level of recursion depends on the results of the next. This would imply that it is hard to do the calculations from different recursive steps in parallel.

Another way of thinking about this is to imagine flattening out the recursion into iteration (see for example Can every recursion be converted into iteration?). A recursive algorithm is likely to generate a flattened version where each iterations depend on the results from other iterations, making it hard to do the iterations in parallel.

Martin Cook
  • 554
  • 5
  • 15
  • 2
    This is only partially accurate. Imagine, if you will, a tree with 4 branches at each non-terminal, and the same depth all the way across. One easy option for parallelising a search for an element in the tree given that you have 4 processes would be to give each processor one of the branches from the root. There are some recursive algorithms which parallelise rather easily without conversion to iteration. – High Performance Mark Nov 08 '17 at 16:46
  • 1
    I would go further and say it's at best highly misleading if not plain wrong. 1) it's perfectly possible to parallelize recursive code without flattening it using tasks or similar paradigms. 2) In a flattened recursive algorithm an iteration does not necessarily depend on the previous iteration. The only case for which this answer is appropriate would be if there is always a single recursive call. – Zulan Nov 08 '17 at 19:29
  • @HighPerformanceMark That feels more like parallelising within a step, rather than doing different recursive steps in parallel, which is what I assumed was the goal. But I do take your point -- algorithms that incorporate recursion can take all forms, and might well have pieces that are easy to do in parallel. I will try to rephrase so that my reasoning is more of an example. – Martin Cook Nov 08 '17 at 20:38