Re: [Caml-list] SMP multithreading

[Eray Ozkural <examachine@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 9601 bytes --]

Oh well, I'm not so surprised that the fine-grain task-parallelism with (?)
dynamic load-balancing strategy doesn't get much speedup. Doing HPC with
Haskell is a bit like using Java for writing parallel programs, you might as
well use a C-64 and Commodore BASIC. And yes, some people do use Java with
MPI. Java people have benchmarks too :) But for some reason I had difficulty
using Java and Haskell even with medium size problems.

On the other hand, a lot more can be achieved with a parallelizing compiler
that uses profiling and static analysis. As I said even in C good results
can be achieved, I've seen that, so I know it's doable with ocaml, just a
difficult kind of compiler. The functional features would expose more
concurrency.

At any rate, implicit parallelism isn't the same as a parallelizing
compiler, it's better, because you would be using primitives, that the
compiler knows to its heart. That's like combining the best of both worlds,
I think, because obviously parallelizing compilers can work best on the
easier kinds of parallelism. It can pull more tricks than many assume, but
it would still not replace a parallel algorithm designer.  You don't really
expect to give quicksort as input and get hypercube quicksort as output in
these parallelizing compilers that apply a number of heuristic
transformations to the code, but in many problems they can be made to
generate pretty good code. The best part is once you have it you can apply
it to every program, it's one of the cheapest ways to get speedup, so I'd
say it's worthwhile for ocaml right now. Just not the way GHC does.

On Wed, Nov 17, 2010 at 5:47 AM, Jon Harrop <
jonathandeanharrop@googlemail.com> wrote:

> 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
> away.
>
>
>
> I share your dream but I doubt it will ever be realized.
>
>
>
> Cheers,
>
> Jon.
>
>
>
> *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>
> wrote:
>
> 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
> :)
>
> Best,
>
>
> --
> Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
> http://groups.yahoo.com/group/ai-philosophy
> http://myspace.com/arizanesil http://myspace.com/malfunct
>



-- 
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy
http://myspace.com/arizanesil http://myspace.com/malfunct

[-- Attachment #2: Type: text/html, Size: 12257 bytes --]