[Haskell-cafe] Dynamic thread management?

[Stefan O'Rear]

On Thu, Aug 23, 2007 at 06:27:43AM +0100, Hugh Perkins wrote:
> On 8/22/07, Brandon Michael Moore <brandon at heave.ugcs.caltech.edu> wrote:
> > Automatic threading is inherently limited by data dependencies.
> > You can't run a function that branches on an argument in parallel
> > with the computation producing that argument. Even with arbitrarily
> > many processors and no communication overhead there is a limit to
> > how much parallelism you can squeeze from any given program.
> 
> Yes.  Its worse than that in fact, because many real-world problems
> will involve functions that have side-effects, but we know the
> side-effects dont matter.  The parallelisation algo of course doesnt
> know they dont matter (unless we tell it).
> 
> Example: imagine we want to copy files from one machine to five
> others.  Copying a file has a clear side-effect, but since we're
> copying to 5 independent machines, we can copy to each machine in
> parallel.  The algo doesnt know that this is ok.

Actually, the algorithm was right, and the intuitive argument is wrong.
Suppose all five computers are actually re-exporting network filesystem
hosted on a sixth server, and the file names alias.  By overruling the
algorithm, you've introduced a corner case bug that will go unnoticed
for years.

> > If you have cores to waste, you might try rewrites like
> >
> > f x
> > =>
> > case x of
> >  C1 a1 a2 -> f (C1 a1 a2)
> >  C2 b -> f (C2 b)
> >  C3 -> f C3
> >
> > and then speculatively execute several of the case branches.
> > If you don't throw away too much type information you should
> > even be able to do it at runtime.
> 
> That's a good observation.  Sortof anti-laziness :-D

It's called speculative execution, and microprocessors have been doing
it for many years as part of their built-in automatic parallelization
circuitry.

(If you think emulator-based autoparallelization is going to be easy,
consider that it takes a couple million transistors to do a reasonable
job - and a chunk of 90's silicon can already do a million things at
once, so you're at a huge starting disadvantage.  Just my two cents.)

Stefan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070822/8254a297/attachment.bin