RE: [Caml-list] Efficient OCaml multicore -- roadmap?

[Jon Harrop <jonathandeanharrop@googlemail.com>]

Dario wrote:
> Fabrice wrote:
> > Of course, sharing structured mutable data between threads will not be
> > possible, but actually, it is a good thing if you want to write
> > correct programs ;-)
> 
> This is a good point that is often neglected in multicore discussions.

There be dragons.

There is a critical separation of concerns here. On one side you have parallel programming for multicores, the sole objective of which is to increase throughput on those machines. On the other side you have concurrent programming, which is primarily concerned with handling the complexity of non-determinism and often latency as well as throughput. These are two different concepts with different goals and different solutions.

Due to the memory hierarchy on a multicore, mutating shared data is basically essential if you want to get decent performance from a parallel program. If you don't do this, you end up with cache misses from all cores contending for shared memory and, therefore, no performance gain from more cores.

You can easily see this effect by considering the following embarrassingly-parallel serial program:

  Array.init 10000 (fun _ -> Array.init 10000 float)

This is trivial to parallelize in F#:

  Array.Parallel.init 10000 (fun _ -> Array.init 10000 float)

But I see just 2.4x speedup going from 1 to 8 cores by doing this because of the massive contention for shared memory. Specifically, the memory bandwidth on this 2x quadcore Xeon box is enough to feed 2.4 of these cores but not all 8 of them.

The Haskell guys got this wrong:

  http://flyingfrogblog.blogspot.com/2010/06/regular-shape-polymorphic-parallel.html

Their parallel Laplace code is a particularly good example because it uses the anti-pattern:

  for t=0 to m-1 do
    parallel for i=0 to n-1 do
      for j=0 to n-1 do
        ... xs.(i).(j) ...

This is bad because there is no correlation (aka "temporal locality") between the tasks spawned by the inner parallel "for" loop and the cores they run on. Consequently, each iteration of the outer serial "for" loop requires different data on different cores and the machine is swamped with cache misses so they see (surprise!) only 2.4x speedup on their 8-core Xeon when other solution get faster serial performance and 5-7x speedups on 8-core Xeons.

One solution that attains excellent performance on multicores optimizes the algorithm by reducing the asymptotic cache miss rate (aka "cache complexity") by decomposing the space-time (t, i, j) into trapezoids and relying upon an implementation that uses work-stealing queues where child tasks executed on the same core as their parent task with high probability. See the excellent paper "Cache oblivious stencil computations" by Matteo Frigo (of FFTW fame) for more details:

  http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.115.6578&rep=rep1&type=pdf

This style of parallel programming is now the defacto standard for multicores, with popular implementations provided by both the Intel TBB and Microsoft TPL (in .NET 4).

Mutating shared data is a bad idea in the context of concurrent programming where throughput is not important and handling non-determinism is usually the main headache. Here, you can sacrifice throughput by introducing abstractions that make it much easier to write correct programs. Abstractions like agents.

> What kind of language constructs would also be introduced in order to manage the concurrency between the multiple threads?

Just use message passing between agents. For a concrete implementation, look at the MailboxProcessor in the F# standard library.

Cheers,
Jon.