[cpp-threads] RE: "Agenda" for august 23-25 concurrency meeting

[Nick Maclaren]

"Robison, Arch" <arch.robison at intel.com> wrote:
> 
> > And historically, almost no algorithms/programs have ever been
> > found to require such strong guarantees. We once challenged
> > people to come up with non-toy examples, and never got any.
> 
> If you have a non-toy example algorithm that shows a need for causality
> or total store order, I would very much like to see it and show it to
> our hardware architects.  

Oh, THAT'S easy!  NO problem.  Of course, if you had asked for a non-toy
and SANE algorithm, I would have a harder job :-)

Seriously.  If you take a good many serial algorithms (including FFTs,
sorting, Dirichlet tesselation and others) and modify them for maximum
parallelism, you end up with ones that will work (and work well) if and
only if the system provides efficient, globally consistent memory.
Nobody with Half a Clue does that because, in real systems, they either
won't work or will run like drains.  Blocked drains.

This is of purely theoretical interest, because there is very good
evidence that the efficiency restriction is almost a natural law.
The aspect that is of PRACTICAL relevance is that it is a complete
waste of time to provide global consistency and an automatic mechanism
for parallelising arbitrary programs.  It can be done, and it will very
often work (i.e. deliver parallelism) but will not improve performance.


Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QH, England.
Email:  nmm1 at cam.ac.uk
Tel.:  +44 1223 334761    Fax:  +44 1223 334679