Sunday, August 31, 2014

parallel laziness

I've just started reading Paul Bone's thesis: https://mercurylang.org/documentation/papers/pbone_phd_thesis.pdf. I got to the bit that said "laziness makes parallelization harder". That set me thinking. Here is some idle speculation.

When we are executing our lazy program we can look at every possible expression in our program, and classify them:

  • There are expressions that we need to evaluate to advance the next IO. This includes all subexpressions that we will definitely need to evaluate.
    • These have subexpressions that we might or might not need to evaluate. In wombat these will always be in closures. Note that creating those closures (filling in the values of identifiers) is also an expression.
  • On the other side of the coin, and working from the bottom up instead of top down, there are expressions that we could evaluate because we have all the parameters.
    • And conceivably we could order these by how likely the value is to be useful, either for the current IO or for possible future IOs. And conceivably we could improve this ordering as time goes on, based on the actual behaviour of the program.
So one can imagine a program that has as many cores as the operating system wants to give it at any particular time. And those cores can beaver away on all the available work that can be done...

And doesn't this remind me of work that was going on in the next lab when I was younger: http://www.eganfamily.id.au/archive30nov2007/monash/research/projects/CCC/index.html. (Actually their lab was up the road at RMIT since it was a joint CSIRO-RMIT project.)
[update!! And I got this wrong: the Prof Greg Egan is not the the Greg Egan (http://gregegan.customer.netspace.net.au/) who is an author and amateur (I presume) mathematician who collaborates with John Baez]. I also see Mark Rawling in the photo. Later we (mostly Mark) wrote a C++ library for reactive programming that is somewhat related to this post. And I now remember that I applied for a job with that CSIRAC2 project, because of my interest in functional programming which they were using. I didn't get it :-(.

3 comments:

  1. "And doesn't this remind me of work that was going on in the next lab when I was younger: http://www.eganfamily.id.au/archive30nov2007/monash/research/projects/CCC/index.html. (Actually their lab was up the road at RMIT since it was a joint CSIRO-RMIT project.) And now, for the first time, I realise that that is the Greg Egan (http://gregegan.customer.netspace.net.au/) who is an author and amateur (I presume) mathematician who collaborates with John Baez."

    Sorry to intrude on your blog, but I'm Greg Egan the author, and I'm not Greg Egan the engineer from Monash. I actually mention that other Greg Egan on the second page you link to, where I implore people to stop stealing his photo and passing it off as me!

    ReplyDelete
  2. Hi,

    The second category, computations that might be needed and can be executed earlier in parallel, is known as specultative parallelisation or speculative execution. I have avoided speculative execution, in all forms, for my work on Mercury as it would make things even more complicated. That doesn't mean that it's not a valuable idea that people shouldn't work on.

    A good paper on the topic is Harris and Singh: Feedback directed implicit parallelism. http://timharris.uk/papers/2007-fdip.pdf. There are other references in my thesis, (pages 7-9).

    ReplyDelete