[Caml-list] SMP multithreading
Wolfgang Draxinger
I've just read
http://caml.inria.fr/pub/ml-archives/caml-list/2002/11/64c14acb90cb14bedb2cacb73338fb15.en.html
in particular this paragraph:
| What about hyperthreading? Well, I believe it's the last convulsive
| movement of SMP's corpse :-) We'll see how it goes market-wise. At
| any rate, the speedups announced for hyperthreading in the Pentium 4
| are below a factor of 1.5; probably not enough to offset the overhead
| of making the OCaml runtime system thread-safe.
This reads just like the "640k ought be enough for everyone". Multicore
systems are the standard today. Even the cheapest consumer machines
come with at least two cores. Once can easily get 6 core machines today.
Still thinking SMP was a niche and was dying?
So, what're the developments regarding SMP multithreading OCaml?
Cheers
Wolfgang
_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
Edgar Friendly
> Hi,
>
> I've just read
> http://caml.inria.fr/pub/ml-archives/caml-list/2002/11/64c14acb90cb14bedb2cacb73338fb15.en.html
> in particular this paragraph:
> | What about hyperthreading? Well, I believe it's the last convulsive
> | movement of SMP's corpse :-) We'll see how it goes market-wise. At
> | any rate, the speedups announced for hyperthreading in the Pentium 4
> | are below a factor of 1.5; probably not enough to offset the overhead
> | of making the OCaml runtime system thread-safe.
>
> This reads just like the "640k ought be enough for everyone". Multicore
> systems are the standard today. Even the cheapest consumer machines
> come with at least two cores. Once can easily get 6 core machines today.
>
> Still thinking SMP was a niche and was dying?
>
> So, what're the developments regarding SMP multithreading OCaml?
>
>
> Cheers
>
> Wolfgang
>
share some possibly new thoughts on this ever-living topic.
It looks like high-performance computing of the near future will be
built out of many machines (message passing), each with many cores
(SMP). One could use message passing for all communication in such a
system, but a hybrid approach might be best for this architecture, with
use of shared memory within each box and message passing between. Of
course the best choice depends strongly on the particular task.
In the long run, it'll likely be a combination of a few large, powerful
cores (Intel-CPU style w/ the capability to run a single thread as fast
as possible) with many many smaller compute engines (GPGPUs or the like,
optimized for power and area, closely coupled with memory) that provides
the highest performance density.
The question of how to program such an architecture seems as if it's
being answered without the functional community's input. What can we
contribute?
E.
Sylvain Le Gall
On 15-11-2010, Wolfgang Draxinger <wdraxinge...@draxit.de> wrote:
> Hi,
>
> I've just read
> http://caml.inria.fr/pub/ml-archives/caml-list/2002/11/64c14acb90cb14bedb2cacb73338fb15.en.html
> in particular this paragraph:
>| What about hyperthreading? Well, I believe it's the last convulsive
>| movement of SMP's corpse :-) We'll see how it goes market-wise. At
>| any rate, the speedups announced for hyperthreading in the Pentium 4
>| are below a factor of 1.5; probably not enough to offset the overhead
>| of making the OCaml runtime system thread-safe.
>
> This reads just like the "640k ought be enough for everyone". Multicore
> systems are the standard today. Even the cheapest consumer machines
> come with at least two cores. Once can easily get 6 core machines today.
>
> Still thinking SMP was a niche and was dying?
>
Hyperthreading was never remarkable about performance or whatever and is
probably not pure SMP (emulated SMP maybe?).
> So, what're the developments regarding SMP multithreading OCaml?
>
There are various development regarding this subject (most recent
first):
- Plasma (MapReduce in OCaml)
http://plasma.camlcity.org/plasma/index.html
- OC4MC (OCaml for MultiCore)
http://www.algo-prog.info/ocmc/web/
- ocamlp3l
http://camlp3l.inria.fr/eng.htm
- jocaml
http://jocaml.inria.fr/
- ocamlmpi
http://forge.ocamlcore.org/projects/ocamlmpi/
All these projects try to tackle the challenge of SMP from different
point of view. Maybe you'll find what your answer in one of them.
Regards,
Sylvain Le Gall
Gerd Stolpmann
Yes, that's generally the right question. Current hardware is a kind of
experiment - vendors have only taken the multicore path because it is
right now the easiest way of improving the performance potential,
although it is questionable whether (non-server) applications can really
benefit from it (excluding here server apps because for these
parallelization is relatively easy to get). Future hardware will
probably be even more different - however, it is still unclear which
design paths will be taken. Could be manycores (many CPUs with
non-uniform RAM), could be specialized compute units. Maybe we'll see
again a separation of consumer and datacenter markets - the former
optimizing for numeric simulation applications (i.e. games), the latter
for high-throughput data paths and parallel CPU power. The problem here
is that this is all speculation.
There are some things we can do to improve the situation (and some ideas
are not realistic):
* A probably not-so-difficult improvement would be better message
passing between independent but local processes. I've started an
experiment for such a mechanism
(http://projects.camlcity.org/projects/dl/ocamlnet-3.0.3/doc/html-main/Netcamlbox.html), which tries to exploit that GC-managed memory has a well-known structure. With more help from the GC this could be made even better (safer, fewer corner cases).
* We need more frameworks for parallel programming. I'm currently
developing Plasma, a Map/Reduce framework. Using a framework has
the big advantage that the whole program is structured so it
profits from parallelization, and that it is possible to train
developers for it that have no idea about parallelization. There
are probably more algorithm schemes where this is possible.
* I have a lot of doubts whether FP languages ever run well on SMP
with a bigger number of cores. The problem is the relatively
high memory allocation rate - the GC has to work a lot harder
than in imperative languages. The OC4MC project uses
thread-local minor heaps because of this. Probably this is not
enough, and one even needs thread-local major heaps (plus a
third generation for values accessed by several threads). All in
all you could get the same effect by instantiating the ocaml
runtime several times (if this were possible), let each runtime
run in its own thread, and provide some extra functionality for
passing values between threads and for sharing values. This
would not be exactly the SMP model, but would allow a number of
parallelization techniques, and is probably future-proof as it
encourages message passing over sharing. This is certainly worth
experimentation.
* One can also tackle the problem from the multi-processing side:
Provide better mechanisms for message passing (see above) and
value sharing. (That's probably the path I'll follow for my own
experiments - no modifications of the runtime, but play tricks
with the OS.)
* 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.
* Looking for more "automatic" speedups: I would more look for
parallelizing parts of the GC (e.g. parallelized sweep), but
this is probably running quickly against the memory bandwidth
limit. Maybe using 2 cores for the GC would result in an
improvement, and more cores get you nothing extra. At least
worth an experiment.
Gerd
>
> E.
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
--
------------------------------------------------------------
Gerd Stolpmann, Bad Nauheimer Str.3, 64289 Darmstadt,Germany
ge...@gerd-stolpmann.de http://www.gerd-stolpmann.de
Phone: +49-6151-153855 Fax: +49-6151-997714
------------------------------------------------------------
Norman Hardy
On 2010 Nov 15, at 22:46 , Edgar Friendly wrote:
> It looks like high-performance computing of the near future will be built out of many machines (message passing), each with many cores (SMP). One could use message passing for all communication in such a system, but a hybrid approach might be best for this architecture, with use of shared memory within each box and message passing between. Of course the best choice depends strongly on the particular task.
>
> In the long run, it'll likely be a combination of a few large, powerful cores (Intel-CPU style w/ the capability to run a single thread as fast as possible) with many many smaller compute engines (GPGPUs or the like, optimized for power and area, closely coupled with memory) that provides the highest performance density.
OCaml code should be able to share immutable OCaml data with other processes just as it shares libraries.
See http://cap-lore.com/Software/pch.html .
Some of the ideas there might be improved with hardware support.
Admission: If I had read all of the interesting pointers given on this thread I would never finish sending this e-mail.
Eray Ozkural
> 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.
--
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
Gerd Stolpmann
>
>
> On Tue, Nov 16, 2010 at 7:04 PM, Gerd Stolpmann
> <in...@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.
Gerd
Eray Ozkural
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,
Wolfgang Draxinger
Eray Ozkural <exama...@gmail.com> wrote:
> [readworthy text]
I'd like to point out how the big competitor to OCaml deals with it.
The GHC Haskell system has SMP parallization built in for some time,
and it does it quite well.
Wolfgang
Eray Ozkural
wdraxinge...@draxit.de> wrote:
> On Wed, 17 Nov 2010 01:04:54 +0200
> Eray Ozkural <exama...@gmail.com> wrote:
>
> > [readworthy text]
>
> I'd like to point out how the big competitor to OCaml deals with it.
> The GHC Haskell system has SMP parallization built in for some time,
> and it does it quite well.
>
I think I tested the parallel features just once in the distant past,
something like that would be so useful for ocaml :) Explicit threading that
is suited to functional programming with a syntax independent of the actual
thread implementation. The par combinator looks like fun to use. Wishlist
item definitely :)
Cheers,
Jon Harrop
> I'd like to point out how the big competitor to OCaml deals with it.
> The GHC Haskell system has SMP parallization built in for some time,
> and it does it quite well.
I beg to differ. Upon trying to reproduce many of the Haskell community's
results, I found that even their own parallel Haskell programs often exhibit
huge slowdowns. This is because Haskell's unpredictable performance leads to
unpredictable granularity and, consequently, more time can be spent
administering the tiny parallel computations than is gained by doing so.
The results I found here are typical:
http://flyingfrogblog.blogspot.com/2010/01/naive-parallelism-with-hlvm.html
Note that the absolute performance peaks at an unpredictable number of cores
only in the case of Haskell. This is because the GC does not scale beyond
about 4 cores for any Haskell programs doing significant amounts of
allocation, which is basically all Haskell programs because allocations are
everywhere in Haskell.
Ultimately, running on all cores attains no speedup at all with Haskell in
that case. This was branded "the last core slowdown" but the slowdown
clearly started well before all 8 cores. There was a significant development
towards improving this situation but it won't fix the granularity problem:
http://hackage.haskell.org/trac/ghc/blog/new-gc-preview
The paper "Regular, shape-polymorphic, parallel arrays in Haskell" cites
2.5x speedups when existing techniques were not only already getting 7x
speedups but better absolute performance as well. Cache complexity is the
problem, as I explained here:
http://flyingfrogblog.blogspot.com/2010/06/regular-shape-polymorphic-paralle
l.html
Probably the best solution for multicore programming is Cilk. This technique
has already been adopted both in Intel's TBB and Microsoft's .NET 4 but,
AFAIK, the only functional language with access to it is F#. There are some
great papers on multicore-friendly cache oblivious algorithms written in
Cilk:
http://www.fftw.org/~athena/papers/tocs08.pdf
Note, in particular, that Cilk is not only much faster but also much easier
to use than explicit message passing.
To do something like this, threads need to be able to run in parallel and
mutate the same shared heap. Although that is objectively easy (I did it in
HLVM), OCaml's reliance upon very high allocation rates, efficient
collection of young garbage and a ridiculous density of pointers in the heap
make it a *lot* harder.
Cheers,
Jon.
Jon Harrop
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.
Eray Ozkural
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 <
jonathand...@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-lis...@yquem.inria.fr [mailto:
> caml-lis...@yquem.inria.fr] *On Behalf Of *Eray Ozkural
> *Sent:* 16 November 2010 23:05
> *To:* Gerd Stolpmann
> *Cc:* caml...@yquem.inria.fr
> *Subject:* Re: [Caml-list] SMP multithreading
Goswin von Brederlow
> Hi,
>
> On 15-11-2010, Wolfgang Draxinger <wdraxinge...@draxit.de> wrote:
>> Hi,
>>
>> I've just read
>> http://caml.inria.fr/pub/ml-archives/caml-list/2002/11/64c14acb90cb14bedb2cacb73338fb15.en.html
>> in particular this paragraph:
>>| What about hyperthreading? Well, I believe it's the last convulsive
>>| movement of SMP's corpse :-) We'll see how it goes market-wise. At
>>| any rate, the speedups announced for hyperthreading in the Pentium 4
>>| are below a factor of 1.5; probably not enough to offset the overhead
>>| of making the OCaml runtime system thread-safe.
>>
>> This reads just like the "640k ought be enough for everyone". Multicore
>> systems are the standard today. Even the cheapest consumer machines
>> come with at least two cores. Once can easily get 6 core machines today.
>>
>> Still thinking SMP was a niche and was dying?
>>
>
> Hyperthreading was never remarkable about performance or whatever and is
> probably not pure SMP (emulated SMP maybe?).
Hyperthreading is a hack to better utilize idle cpu sub units. The CPU
has multiple complete sets of registers, one per hyper thread. Execution
of the threads is interleaved. Now when one thread is doing some
floating point operation the cpu switches over to another thread and
lets it do some integer aritmetic. But that assumes the threads are
using different sub units. If they are using the same unit then they
just block each other and no speedup occurs.
The speedup of hyperthreading is purely from avoiding dead cycles when
one thread waits for something. On te other hand the cache is shared
between threads so per thread it is smaller and more easily
trashed. Hyperthreading can be much slower too.
MfG
Goswin
Sylvain Le Gall
Indeed, the HT extension was designed to reduce pipeline bubbles, which
most of the time occurs when you need to load data from a slow memory
(slow = RAM as opposed to L1/L2 cache).
In the old time of my P4, ocaml was performing quite well on the
processor. One story about it: while compiling cameleon on it, I often
get into "thermal warning" (the CPU was overheating). I think it could
have been related to the fact the CPU idle level was very low (e.g. no
pipeline bubble). I always thought that this was related to the fact the
minor heap can be stored inside the cache and that reduces the hit/miss
factor (i.e. avoid fetching data in RAM). I have never really tested
this hypothesis. Maybe you can tell me your opinion about this?
Regards,
Sylvain Le Gall
Eray Ozkural
> On Wed, Nov 17, 2010 at 06:27:14AM +0200, Eray Ozkural wrote:
> > 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.
>
> Could you share a pointer to a paper describing this compiler?
>
>
I can't reveal much, but just to point out that there are indeed more
sophisticated compilers than gcc:
http://www.research.ibm.com/vliw/compiler.html
So, uh, there are compilers that turn loops into threads, and also
parallelize independent blocks.... Both coarse-grain and fine-grain
parallelization strategies in existing compiler research can be effectively
applied to the multi-core architectures. In fact, some of the more advanced
compilers (like that of the RAW architecture) must be able to target it
already, but who knows. :) Just consider that most of the parallelization
technology is language independent, they can be applied to any imperative
language. So, would such a thing be able to work on ocaml generated
binaries? Most definitely, I believe, it is in principle possible to start
from the sequential binary and emit parallel code!
Eray Ozkural
On Wed, Nov 17, 2010 at 11:15 PM, Jon Harrop <
jonathand...@googlemail.com> wrote:
> Can you cite any papers from this century? ;-)
>
>
>
> Cheers,
>
> Jon.
>
>
>
> *From:* Eray Ozkural [mailto:exama...@gmail.com]
> *Sent:* 17 November 2010 13:41
> *To:* Eray Ozkural; Jon Harrop; caml...@yquem.inria.fr
>
> *Subject:* Re: [Caml-list] SMP multithreading
>
>
>
David Allsopp
> It looks like high-performance computing of the near future will be built
> out of many machines (message passing), each with many cores (SMP). One
> could use message passing for all communication in such a system, but a
> hybrid approach might be best for this architecture, with use of shared
> memory within each box and message passing between. Of course the best
> choice depends strongly on the particular task.
Absolutely - and the problem in OCaml seems to be that shared memory parallelism is just branded as evil and ignored...
> In the long run, it'll likely be a combination of a few large, powerful
> cores (Intel-CPU style w/ the capability to run a single thread as fast as
> possible) with many many smaller compute engines (GPGPUs or the like,
> optimized for power and area, closely coupled with memory) that provides
> the highest performance density.
I think the central thing that we can be utterly sure about is that desktops will always have *> 1* general purpose CPU. Maybe not be an ever-increasing number of cores but definitely more than one.
> The question of how to program such an architecture seems as if it's being
> answered without the functional community's input. What can we contribute?
It has often seemed to me when SMP has been discussed in the past on this list that it almost gets dismissed out of hand because it doesn't look future-proof or because we're worried about what's round the corner in technology terms.
To me the principal question is not about whether a parallel/thread-safe GC will scale to 12, 16 or even the 2048 cores on something like http://www.hpc.cam.ac.uk/services/darwin.html but whether it will hurt a single-threaded application - i.e. whether you will still be able to implement message passing libraries and other scalable techniques without the parallel GC getting in the way of what you're doing. A parallel/thread-safe GC should be aiming to provide the same sort of contract as the present one - it "just works" for most things and in a few borderline cases (like HPC - yes, it's a borderline case) you'll need to tune your code or tweak GC parameters because it's causing some problems or because in your particular application squeezing every cycle out of the CPU is important. As long as the GC isn't (hugely) slower than the present one in OCaml then we can continue to use libraries, frameworks and technologies-still-to-come on top of a parallel/thread-safe GC which simply i
gnores shared memory thread-level parallelism just by not instantiating threads.
The argument always seems to focus on utterly maxing out all possible available resources (CPU time, memory bandwidth, etc.) rather than on whether it's simply faster than what we're doing able to do at the moment on the same system. Of course, it may be that the only way to do that is to have different garbage collectors - one invoked when threads.cmxa is linked and then the normal one otherwise (that's so easy to type out as a sentence, summarising a vast amount of potential work!!)
Multithreading in OCaml seems to be focused on jumping the entire width of the river of concurrency in one go, rather than coming up with stepping stones to cross it in bits...
David
Christophe Raffalli
Hello,
And OCaml on GPU ? We just tested a recent GPU card with 480 processors
at 900Mhz ... this is
qui impressive ... and supported by matlab via cuda-lapack
(http://www.culatools.com/) ...
I imagine we could at least use cuda-lapack from OCaml ?
Cheers,
Christophe
Eray Ozkural
This is one of the more recent papers a quick search turns up, but you have
to keep in mind that thread extraction is only one problem among many for a
parallelizing compiler. I think the keyword you are looking for is "thread
extraction". And here probably, it's the simplest kind of extraction... Food
for some thought: assume that you have a very good compiler pass that
extracts all possible threads in the sequential code, can you name any other
problems the compiler must solve to achieve good performance?
I can't talk at all about the project I worked on, but as I mentioned
previously, familiarize yourself with the RAW project, it was similar in
some respects to the project I worked in:
http://groups.csail.mit.edu/cag/raw/
This should, at least a bit, dispel the illusion that parallelizing
compilers are helpless when they confront C code. Reading the OS/400 book
had opened my mind about OS design, perhaps reading about recent computer
architecture research projects will open others' eyes about compilers, and
how useful they really can be!
Also, I believe there ought to be some textbooks about multi-core
architectures and relevant compilation strategies, let me post it if I find
a comprehensive reference.
The dream compiler would have all the cool linear algebra capabilities of
HPF + the more general/free-form kinds of parallelization strategies in
recent compilers.
Ok, so what you really want to do is, parallelize applications that can
benefit from them. Not file utils or web browsers. If you are so curious,
stuff like povray would be in the test suite. Sometimes the parallelizing
compiler parallelizes computations that a programmer wouldn't bother due to
program complexity, here a basic block, there a basic block, some pipelining
communication/computation overlap there.... I think it's a safe bet to say
that, with all the general lameness surrounding parallel programming
languages, parallelizing compilers will be very important in the near
future.
Cheers,
Christophe TROESTLER
This is certainly possible since they say that the standard LAPACK
functions are available. If you try, let us know!
Best,
C.
Eray Ozkural
one of the papers below, so there is indeed something like a "lock-free
garbage collector". Then, why do we worry about much synchronization
overhead? I don't quite understand.
Maurice Herlihy<http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/h/Herlihy:Maurice.html>,
J. Eliot B. Moss: Lock-Free Garbage Collection for Multiprocessors. IEEE
Trans. Parallel Distrib. Syst.
3<http://www.informatik.uni-trier.de/~ley/db/journals/tpds/tpds3.html#HerlihyM92>(3):
304-311 (1992)
http://doi.ieeecomputersociety.org/10.1109/71.139204
Hui Gao, Jan Friso
Groote<http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/g/Groote:Jan_Friso.html>
, Wim H. Hesselink<http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/h/Hesselink:Wim_H=.html>:
Lock-free parallel and concurrent garbage collection by mark&sweep. Sci.
Comput. Program.
64<http://www.informatik.uni-trier.de/~ley/db/journals/scp/scp64.html#GaoGH07>(3):
341-374 (2007)
http://portal.acm.org/citation.cfm?id=1223239
Java's new garbage collector is lock-free? At any rate, we really needn't
fall behind a mega-lame language like Java :) The first paper is from 1992,
enough time for the knowledge to diffuse. The second 2007 paper is probably
what Jon was referring to earlier.
In my mind, you can use one of these, and use special pool allocation
algorithms for small objects, and also use static lifetime analysis to
bypass the garbage collection in many cases. Since there are many runtime
designers here, I wonder, is there a language runtime that does all three of
these?
Cheers,
Eray
<http://doi.ieeecomputersociety.org/10.1109/71.139204>
> ignores shared memory thread-level parallelism just by not instantiating
> threads.
>
> The argument always seems to focus on utterly maxing out all possible
> available resources (CPU time, memory bandwidth, etc.) rather than on
> whether it's simply faster than what we're doing able to do at the moment on
> the same system. Of course, it may be that the only way to do that is to
> have different garbage collectors - one invoked when threads.cmxa is linked
> and then the normal one otherwise (that's so easy to type out as a sentence,
> summarising a vast amount of potential work!!)
>
> Multithreading in OCaml seems to be focused on jumping the entire width of
> the river of concurrency in one go, rather than coming up with stepping
> stones to cross it in bits...
>
>
> David
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
--
Goswin von Brederlow
> On Thu, 18 Nov 2010 00:08:19 +0100, Christophe Raffalli wrote:
>>
>> And OCaml on GPU ? We just tested a recent GPU card with 480
>> processors at 900Mhz ... this is qui impressive ... and supported by
>> matlab via cuda-lapack (http://www.culatools.com/) ... I imagine we
>> could at least use cuda-lapack from OCaml ?
>
> This is certainly possible since they say that the standard LAPACK
> functions are available. If you try, let us know!
>
> Best,
> C.
And the functions should enter/leave_blocking_section() in the C stubs
so you can have 480 ocaml threads. All of them can run some lapack code
while always only one can run ocaml code at any one time. If the lapack
functions take long enough almost all threads will be running.
This is actually a quick way to use multiple cores with ocaml. Find a
often called function that takes considerable time and offload it to C
with enter/leave_blocking_section() around it. Isn't always possible and
you need to use BigArray for data or copy the arguments.
MfG
Goswin
Goswin von Brederlow
>> This is actually a quick way to use multiple cores with ocaml. Find a
>> often called function that takes considerable time and offload it to C
>
> Or HLVM, F#, Scala, Clojure or any of the other languages that permit shared
> memory parallelism. C is particularly poor in this regard so I would not
> just restrict yourself to C...
>
> Cheers,
> Jon.
I'm not talking about any shared memory parallelism here. The
parallelism is completly restricted to the ocaml side. You just find
some single threaded job that takes long, rewrite it as external
function and release the ocaml lock while it is running.
For example in my code I compute the sha256 sum of a block of
data. Since I use a C library for sha256 anyway the function is already
external. All I had to do was switch the interface from using string to
Bigarray and add enter/leave_blocking_section(). After that multiple
threads can compute the sha256 sum for blocks of data in parallel and my
code run 3.7 times faster with 4 cores.