Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change

Re: [OT]: threading recursive subroutines.

by dHarry (Abbot)
on Feb 02, 2011 at 11:22 UTC ( #885719=note: print w/replies, xml ) Need Help??

in reply to [OT]: threading recursive subroutines.

I don't do much with threads, what I use is standard stuff in the JEE environment. Java handles things a bit different I think (making some sacrifices for the sake of simplicity). I recently stumbled upon Speculative parallelisation. Maybe it is of use to you.

Do you have a specific type of problem in mind? I myself am thinking about reducing a complex scheduling problem by spawning threads to optimize things locally and later combine the results into a global solution. I have indications that I might get away with such an approach. I haven't make much progress though.



  • Comment on Re: [OT]: threading recursive subroutines.

Replies are listed 'Best First'.
Re^2: [OT]: threading recursive subroutines.
by BrowserUk (Pope) on Feb 02, 2011 at 23:18 UTC

    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 :)

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://885719]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (3)
As of 2018-05-25 04:18 GMT
Find Nodes?
    Voting Booth?