English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
thousands of CPU cores
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2008-09-21 (20:41)
From: Jon Harrop <jonathandeanharrop@g...>
Subject: Re: [Caml-list] thousands of CPU cores
On Sunday 21 September 2008 20:05:15 Michaël Grünewald wrote:
> This is true while your are concerned with matrix over the real or
> complex numbers, but if you want to use arbitrary precision arithmetic,
> finite fields, quaternions or any ring you like, then you are stuck.
> Linear algebra is useful in every mathematical field, not just numerical
> computing.
> It is not ridiculous at all to code matrix routines in OCaml, since you
> can use functors to use your routines with any kind of scalar, not just
> complex numbers. And I already had to code dense matrix operations for
> these reasons.
> BTW, if anybody here knows presentations about matrix implementation(s),
> I would be very glad to know about it.

Exactly. OCaml's poor performance in the case of nxn matrix multiply stems 
almost entirely from the inefficiency of the gather operation which is O(n^2) 
and serial in OCaml but would be O(1) and parallel if each thread could write 
results directly into a shared data structure.

This is a fundamental problem that afflicts all parallel algorithms that 
gather a non-trivial result. In fact, matrix multiplication is not even worst 
case because gather is only O(n^2) of an O(n^3) total.

Also, note that matrix multiplication is embarassingly parallel. So OCaml's 
current problems with parallelism are not limited to slow interthread 

The good news is that the parallel GC is coming along nicely and this will be 
a solved problem before long... :-)

Dr Jon Harrop, Flying Frog Consultancy Ltd.