From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 31DEBBB84 for ; Sun, 21 Sep 2008 22:41:12 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ag0CAMJN1khA6ba4mmdsb2JhbACCKpA1PgEBAQEBCAsKBxEDmwuFaAEC X-IronPort-AV: E=Sophos;i="4.32,442,1217800800"; d="scan'208";a="15196338" Received: from nf-out-0910.google.com ([64.233.182.184]) by mail2-smtp-roc.national.inria.fr with ESMTP; 21 Sep 2008 22:41:11 +0200 Received: by nf-out-0910.google.com with SMTP id b11so436918nfh.13 for ; Sun, 21 Sep 2008 13:41:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=gamma; h=domainkey-signature:received:received:organization:to:subject:date :user-agent:references:in-reply-to:mime-version:content-type :content-transfer-encoding:content-disposition:message-id:from; bh=/iroj8wQtbsX/6S788jtT1vpGlMToSxR/De7GWjCx28=; b=lEM0VW0nyqhzTrzD5lQcsVTZphxTrtl//vKmzY44gNpvFKbvvFQtKxOHbFdABRA/Tk KrInpoY7Zbz5buJC04iMSQUcpDOUNfIGmORo4yT6wae/3sCXWw2X+zi8us+TtbLOQIIk b1zN6I8RSd01tJ0g7oOqORY3HoWhWFn99JYHQ= DomainKey-Signature: a=rsa-sha1; c=nofws; d=googlemail.com; s=gamma; h=organization:to:subject:date:user-agent:references:in-reply-to :mime-version:content-type:content-transfer-encoding :content-disposition:message-id:from; b=EpOesJuW0vkLwbd12Rq9YA0aWmlria4fcPfMQu2UpRwNrPdVohHAsMAX8VUsW46FQN dYjgGxQQBp0p3dc5833W+7W+f3i63bxi76usi5HVdPmX8H+cDU3S55T9RFx1sT4qMiZG l4MlTdbO2BfzQB5dIEGNJzWJV1RK1+kUuIXl8= Received: by 10.210.46.4 with SMTP id t4mr3774090ebt.179.1222029671467; Sun, 21 Sep 2008 13:41:11 -0700 (PDT) Received: from leper.local ( [86.140.183.215]) by mx.google.com with ESMTPS id f13sm8577793gvd.10.2008.09.21.13.41.10 (version=TLSv1/SSLv3 cipher=RC4-MD5); Sun, 21 Sep 2008 13:41:11 -0700 (PDT) Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] thousands of CPU cores Date: Sun, 21 Sep 2008 22:41:43 +0100 User-Agent: KMail/1.9.9 References: <20080711093032.GA24400@annexia.org> <48D69AEB.3090603@laposte.net> In-Reply-To: <48D69AEB.3090603@laposte.net> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Message-Id: <200809212241.43298.jon@ffconsultancy.com> From: Jon Harrop X-Spam: no; 0.00; quaternions:01 algebra:01 ocaml:01 functors:01 ocaml's:01 ocaml:01 non-trivial:01 ocaml's:01 parallelism:01 frog:98 wrote:01 caml-list:01 arithmetic:01 arbitrary:02 linear:02 On Sunday 21 September 2008 20:05:15 Micha=EBl Gr=FCnewald 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= =20 almost entirely from the inefficiency of the gather operation which is O(n^= 2)=20 and serial in OCaml but would be O(1) and parallel if each thread could wri= te=20 results directly into a shared data structure. This is a fundamental problem that afflicts all parallel algorithms that=20 gather a non-trivial result. In fact, matrix multiplication is not even wor= st=20 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= =20 current problems with parallelism are not limited to slow interthread=20 communication. The good news is that the parallel GC is coming along nicely and this will = be=20 a solved problem before long... :-) =2D-=20 Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e