Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

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.

In reply to Re^2: [OT]: threading recursive subroutines. by BrowserUk
in thread [OT]: threading recursive subroutines. by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others rifling through the Monastery: (11)
    As of 2014-08-28 23:44 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      The best computer themed movie is:











      Results (275 votes), past polls