in reply to Re: [OT]: threading recursive subroutines.
in thread [OT]: threading recursive subroutines.
Thank you for the Speculative parallelisation link, It is exactly the type of response I was looking for.
As the authors note in their for abstract:
Prior research has focused mainly on parallelising loops. Recursive procedures, which are also frequently used in real-world applications, have attracted much less attention
Their list of references may also lead to some further interesting stuff, though all to often I hit the road block of no longer having access to the AoCM and IEEE repositories :( But just often enough the authors of such papers make them available on their own websites for free, and these are much easier to find once you have titles and keywords to look for.
Do you have a specific type of problem in mind?
My sample case is Ackermann–Péter variation of the Ackermann function, chosen specifically because it doesn't lend itself to trivial recursion elimination, but can be relatively easily parallelised manually.
Other examples are any number of inherently recursive algorithms like binary search, tree manipulations, sorts et al.
I'm not really sure what my goal is. Having again just had inordinate difficulty in trying to parallelise a recursive algorithm, and recognised that I went through the same dead ends and misdirections that I went through on previous occasions when trying to do the same things for different algorithms, I got to wondering if anyone had done any research into the subject, and my attempted searches turned up a whole lot of nothing.
It feels like there should be a set of steps and constraints one could follow to approach the problem, but from my research these do not yet exist. Which of course could mean that they could not exist. But with the lack of research on the subject, it could also mean that they just haven't been looked for; or that they are not easy to find. So, at this point, I'm just looking thank you :)
For example. It seems to me that for a recursive algorithm--that is not tail recursive--to be a suitable candidate for parallelisation, it requires that it has multiple--two or more--recursive calls at each level. Many do. This is an essential signature of a whole group of divide-and-conquer algorithms.
So, I'm not sure where I am going with this, but you have my profound thanks for helping me on my way :)