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
SMP multithreading
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2010-11-17 (03:47)
From: Jon Harrop <jonathandeanharrop@g...>
Subject: RE: [Caml-list] SMP multithreading
Granularity and cache complexity are the reasons why not. If you find
anything and everything that can be done in parallel and parallelize it then
you generally obtain only slowdowns. An essential trick is to exploit
locality via mutation but, of course, purely functional programming sucks at
that by design not least because it is striving to abstract that concept


I share your dream but I doubt it will ever be realized.





From: caml-list-bounces@yquem.inria.fr
[mailto:caml-list-bounces@yquem.inria.fr] On Behalf Of Eray Ozkural
Sent: 16 November 2010 23:05
To: Gerd Stolpmann
Cc: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] SMP multithreading



On Wed, Nov 17, 2010 at 12:13 AM, Gerd Stolpmann <info@gerd-stolpmann.de>

Am Dienstag, den 16.11.2010, 22:35 +0200 schrieb Eray Ozkural:

> On Tue, Nov 16, 2010 at 7:04 PM, Gerd Stolpmann
> <info@gerd-stolpmann.de> wrote:
>         Am Montag, den 15.11.2010, 22:46 -0800 schrieb Edgar
>         Friendly:
>              * As somebody mentioned "implicit parallelization": Don't
>         expect
>                anything from this. Even if a good compiler finds ways
>         to
>                parallelize 20% of the code (which would be a lot), the
>         runtime
>                effect would be marginal. 80% of the code is run at
>         normal speed
>                (hopefully) and dominates the runtime behavior. The
>         point is
>                that such compiler-driven code improvements are only
>         local
>                optimizations. For getting good parallelization results
>         you need
>                to restructure the design of the program - well, maybe
>                compiler2.0 can do this at some time, but this is not
>         in sight.
> I think you are underestimating parallelizing compilers.

I was more citing Amdahl's law, and did not want to criticize any effort
in this area. It's more the usefulness for the majority of problems. How
useful is the best parallelizing compiler if only a small part of the
program _can_ actually benefit from it? Think about it. If you are not
working in an area where many subroutines can be sped up, you consider
this way of parallelizing as a waste of time. And this is still true for
the majority of problems. Also, for many problems that can be tackled,
the scalability is very limited.

What makes you think only 20% of the code can be parallelized? I've worked
in such a compiler project, and there were way too many opportunities for
parallelization in ordinary C code, let alone a functional language;
implicit parallelism would work wonders there. Of course you may think
whatever you were thinking, but I know that a high degree of parallelism can
be achieved through a functional language. I can't tell you much more
though. If you think that a very small portion of the code can be
parallelized you probably do not appreciate the kinds of static and dynamic
analysis those compilers perform. Of course if you are thinking of applying
it to some office or e-mail application, this might not be the case, but
automatic parallelization strategies would work best when you apply them to
a computationally intensive program.

The really limiting factor for current functional languages would be their
reliance on inherently sequential primitives like list processing, which may
in some cases limit the compiler to only pipeline parallelism (something
non-trivial to do by hand actually). Instead they would have to get their
basic forms from high-level parallel PLs (which might mean rewriting a lot
of things). The programs could look like something out of a category theory
textbook then. But I think even without modification you could get a lot of
speedup from ocaml code by applying state-of-the-art automatic
parallelization techniques. By the way, how much of the serial work is
parallelized that's what matters rather than the code length that is. Even
if the parallelism is not so obvious, the analysis can find out which
iterations are parallelizable, which variables have which kinds of
dependencies, memory dependencies, etc. etc. In the public, there is this
perception that automatic parallelization does not work, which is wrong,
while it is true that the popular compiler vendors do not understand much in
this regard, all I've seen (in popular products) are lame attempts to
generate vector instructions....

That is not to say, that implicit parallelization of current code can
replace parallel algorithm design (which is AI-complete). Rather, I think,
implicit parallelization is one of the things that will help parallel
computing people: by having them work at a more abstract level, exposing
more concurrency through functional forms, yet avoiding writing low-level
comms code. High-level explicit parallelism is also quite favorable, as
there may be many situations where, say, dynamic load-balancing approaches
are suitable. The approach of HPF might be relevant here, with the
programmer making annotations to guide the distribution of data structures,
and the rest inferred from code.

So whoever says that isn't possible, probably hasn't read up much in the
computer architecture community. Probably even expert PL researchers may be
misled here, as they have made the quoted remark or similar remarks about
multi-core/SMP  architectures. It was known for a very long time (20+ years)
that the clock speeds would hit a wall and then we'd have to expend more
area. This is true regardless of the underlying architecture/technology
actually. Mother nature is parallel. It is the sequence that is an
abstraction. And I wonder what is more natural than expressing a solution to
a problem in terms of functions and sets? The kind of non-leaky abstractions
required can be provided by a type-safe functional language and then the
compiler will have a lot more to work on than C code, although analysis can
reveal much about even C code. With the correct heuristics, it might decide
on good data and task distribution strategies, translating say a set
constructor notation to an efficient parallel algorithm, why not??

What I say applies to parallelization based on analysis, of course for
functional languages, other parallelization strategies are also possible, I
suppose low-level task parallelization and dynamic load-balancing strategies
(where functions or closures are distributed) are the most popular (the
reasoning being there can be many independent function evaluations
concurrently), I wonder if it has been attempted at all for ocaml? The
impurity of the language can be dealt with easily. And is there anyone who
might make suggestions to somebody who would like to work on automatic
parallelization of ocaml code? I actually think it might be fun to try some
of the simpler strategies and see how they yield on current hardware
platforms like multi-core and GPU. We ideally wouldn't like just good
automatic parallelization of, say, linear algebra code, but also cool stuff
like functional data structures. Recursive procedures can be mapped to
threads, it might match best hand-written parallelizations, actually, and
you'd get platform independence as a bonus if the compiler is well-designed


Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://myspace.com/arizanesil http://myspace.com/malfunct