| Author |
Message |
Joe Seigh
Guest
|
|
| Back to top |
|
 |
Torben Ęgidius Mogensen
Guest
|
 Posted:
Thu Aug 25, 2005 4:15 pm Post subject:
Re: Not enough parallelism in programming |
|
|
Joe Seigh <jseigh_01@xemaps.com> writes:
I think what he says is that SIMD is good for GPUs because their
workload suits this model, but that general-purpose CPUs that offer
parallelism in the form of MIMD or other won't find many programs
capable of exploiting said parallelism. This is mainly due to
mainstream programmming methodologies and languages being inherently
sequential. One reason for this is that independent subcomputations
are neither marked as such, nor are they easily recognisable as such
because the programming model uses a global updatable store where any
subprocess is able to use and modify the same storage as any other.
Research in automatically recognising parallelism in programs written
in mainstream languages has largely failed (with the exception of
numerical code written in Fortran), so IMO we need either to use
languages where parallelism is either explicit (and verifiably
independent) or recognizable with methods sufficiently robust that
small code changes won't break parallelism. The latter will probably
require restrictions that almost amount to explicit declaration of
parallelism, so the first way may be the way to go.
But it is incredibly hard to get a new language accepted in industry.
You need to convince people that switching is worth the investment in
compilers and IDEs, retraining of personnel, slower development until
programmers get used to the new model, the hassle of interfacing old
code to new, etc. If the main benefit is better exploitation of
paralellism, few people will bother to change, as few programs are
time-critical enough for parallelism to matter. And even when they
are, people often find it easier to invest in faster hardware than
recode their programs.
As for universities offering parallel programming languages as
undergraduate topics, students are already quite critical of
universities using languages that are not perceived as mainstream
enough to be useful to have on your CV when you go looking for a job.
So getting them to accept something that seems esoteric and very
specialist won't be easy.
Torben |
|
| Back to top |
|
|
Torben Ęgidius Mogensen
Guest
|
| Posted:
Thu Aug 25, 2005 4:15 pm Post subject:
Re: Not enough parallelism in programming |
|
|
Joe Seigh <jseigh_01@xemaps.com> writes:
| Quote: | Torben Ęgidius Mogensen wrote:
Joe Seigh <jseigh_01@xemaps.com> writes:
At least in the opinion of this person here
http://www.eetimes.com/news/latest/showArticle.jhtml;jsessionid=JZEMR0B52MV2CQSNDBESKHA?articleID=169300057
I'm not sure what he's getting at though. Does he think multi-cores are
not the way to go but SIMD like the GPUs? Or is MIMD ok, we're just not
getting enough threads to run?
I think what he says is that SIMD is good for GPUs because their
workload suits this model, but that general-purpose CPUs that offer
parallelism in the form of MIMD or other won't find many programs
capable of exploiting said parallelism.
But is he just saying this because he has the "embarrassingly parallel"
easy part. Why complain about the skill set out there when the scarcity
of skills is to your advantage. Get out of the graphics market, write
your own highly parallelized game engine and own the game industry which
makes more money than Hollywood. Piece of cake if you already know how
to write parallel programs.
|
I don't think graphics engines are the problem, they are fairly easy
to parallelise on GPUs (which are more or less designed for this). It
is (almost) every other program that is the problem.
Torben |
|
| Back to top |
|
|
Joe Seigh
Guest
|
| Posted:
Thu Aug 25, 2005 4:15 pm Post subject:
Re: Not enough parallelism in programming |
|
|
Torben Ęgidius Mogensen wrote:
| Quote: | Joe Seigh <jseigh_01@xemaps.com> writes:
At least in the opinion of this person here
http://www.eetimes.com/news/latest/showArticle.jhtml;jsessionid=JZEMR0B52MV2CQSNDBESKHA?articleID=169300057
I'm not sure what he's getting at though. Does he think multi-cores are
not the way to go but SIMD like the GPUs? Or is MIMD ok, we're just not
getting enough threads to run?
I think what he says is that SIMD is good for GPUs because their
workload suits this model, but that general-purpose CPUs that offer
parallelism in the form of MIMD or other won't find many programs
capable of exploiting said parallelism. This is mainly due to
mainstream programmming methodologies and languages being inherently
sequential. One reason for this is that independent subcomputations
are neither marked as such, nor are they easily recognisable as such
because the programming model uses a global updatable store where any
subprocess is able to use and modify the same storage as any other.
|
[...]
But is he just saying this because he has the "embarrassingly parallel"
easy part. Why complain about the skill set out there when the scarcity
of skills is to your advantage. Get out of the graphics market, write
your own highly parallelized game engine and own the game industry which
makes more money than Hollywood. Piece of cake if you already know how
to write parallel programs.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software. |
|
| Back to top |
|
|
Nick Maclaren
Guest
|
| Posted:
Thu Aug 25, 2005 4:15 pm Post subject:
Re: Not enough parallelism in programming |
|
|
In article <1124982035.647275.201420@z14g2000cwz.googlegroups.com>,
"Andy Freeman" <anamax@earthlink.net> writes:
|> Torben =C6gidius Mogensen wrote:
|> > IMO we need either to use
|> > languages where parallelism is either explicit (and verifiably
|> > independent)
|>
|> It isn't much of an exaggeration to say that programmers can't
|> correctly use explicit parallelism.
Well, many of those around here can, at least up to the same
standards as most programmers can use most programming languages.
|> Yes, they think that they can, but most parallel programs with
|> non-trivial interaction shows that they're wrong. (Yes, those
|> programs seem to work much of the time, but they fail often
|> enough to demonstrate that we're mostly lucky.)
Not in the domains where people do that seriously - admittedly
rather specialised. As I said at SunHPC, getting arbitrary
parallel designs right is a nightmare task, but there are several
restricted models that are feasible to debug. Experienced
parallel programmers use one of them.
For example, using lockstep models (BSP, MPI collectives etc.)
is feasible. So are many classes of dataflow.
Regards,
Nick Maclaren. |
|
| Back to top |
|
|
Andy Freeman
Guest
|
| Posted:
Thu Aug 25, 2005 4:15 pm Post subject:
Re: Not enough parallelism in programming |
|
|
Torben Ęgidius Mogensen wrote:
| Quote: | IMO we need either to use
languages where parallelism is either explicit (and verifiably
independent)
|
It isn't much of an exaggeration to say that programmers can't
correctly use explicit parallelism.
Yes, they think that they can, but most parallel programs with
non-trivial interaction shows that they're wrong. (Yes, those
programs seem to work much of the time, but they fail often
enough to demonstrate that we're mostly lucky.)
This inability shouldn't be all that surprising. Programmers
also have problems writing non-trivial sequential programs.
-andy |
|
| Back to top |
|
|
Stephen Fuld
Guest
|
| Posted:
Thu Aug 25, 2005 4:15 pm Post subject:
Re: Not enough parallelism in programming |
|
|
""Torben Ęgidius Mogensen"" <torbenm@app-6.diku.dk> wrote in message
news:7zll2qtcx5.fsf@app-6.diku.dk...
snip
| Quote: | we need either to use
languages where parallelism is either explicit (and verifiably
independent)
|
I'd like to explore this further. ISTM that there are only a few languages
that have any explicit way to declare parallelism and that they differ in
the "level" of parallelism they express. For example, I believe that Occam
expresses parallelism at a very low level (even evaluation of a single
expression can be specified to be in parallel. But COBOL offers explicit
parallelism at the level similar to a full thread. I'm not sure which, if
either of these is the "right" thing to do.
So, the questions are
- Is there an existing language that expresses parallelism at the right
level for multi-core/multithreaded core to take advantage of? Is it easy
for programmers to use the language productivly?
- If not what would such a language look like? That is, what level of
parallelism is appropriate? How would the semantics/syntax be designed to
make program development easiest and most bug free?
--
- Stephen Fuld
e-mail address disguised to prevent spam |
|
| Back to top |
|
|
Torben Ęgidius Mogensen
Guest
|
| Posted:
Thu Aug 25, 2005 9:15 pm Post subject:
Re: Not enough parallelism in programming |
|
|
"Stephen Fuld" <s.fuld@PleaseRemove.att.net> writes:
| Quote: | ""Torben Ęgidius Mogensen"" <torbenm@app-6.diku.dk> wrote in message
news:7zll2qtcx5.fsf@app-6.diku.dk...
snip
we need either to use
languages where parallelism is either explicit (and verifiably
independent)
I'd like to explore this further. ISTM that there are only a few languages
that have any explicit way to declare parallelism and that they differ in
the "level" of parallelism they express. For example, I believe that Occam
expresses parallelism at a very low level (even evaluation of a single
expression can be specified to be in parallel. But COBOL offers explicit
parallelism at the level similar to a full thread. I'm not sure which, if
either of these is the "right" thing to do.
So, the questions are
- Is there an existing language that expresses parallelism at the right
level for multi-core/multithreaded core to take advantage of? Is it easy
for programmers to use the language productivly?
- If not what would such a language look like? That is, what level of
parallelism is appropriate? How would the semantics/syntax be designed to
make program development easiest and most bug free?
|
Functional programmers have long argued that pure functional (or
value-oriented) programming is well suited for this. If you can't
modify store that has already been written, you don't need to
synchronise on every memoy access. The main isea is to run a function
in parallel with evaluation of its arguments, so it is only when you
access such an argument that you need synchronise. Lazy functional
languages have a simlar synchronisation mechanism already, so it will
cost relatively little. The main problem is that not all calls are
worth parallelising (even though it would be safe to do so), so you
need some way of guiding the decision of whether to spawn or not.
Static analysis is probably insufficient, but you can have user
annotations that say that if a condition is true, you spawn, otherwise
not. Wrong annotations will only mean slower pograms, not faulty
ones, so it is fairly safe to leave this to programmers.
Torben |
|
| Back to top |
|
|
Greg Lindahl
Guest
|
| Posted:
Thu Aug 25, 2005 10:42 pm Post subject:
Re: Not enough parallelism in programming |
|
|
In article <hHkPe.133637$5N3.100234@bgtnsc05-news.ops.worldnet.att.net>,
Stephen Fuld <s.fuld@PleaseRemove.att.net> wrote:
| Quote: | I'd like to explore this further. ISTM that there are only a few languages
that have any explicit way to declare parallelism and that they differ in
the "level" of parallelism they express.
|
After 30 years of research, there are more than just a few which have
been proposed, experimented with, and spilled much ink on papers about
the results, etc.
I'm not sure what you hope to accomplish with a comp.arch discussion
of such a huge body of work.
-- g |
|
| Back to top |
|
|
Nick Maclaren
Guest
|
| Posted:
Thu Aug 25, 2005 11:08 pm Post subject:
Re: Not enough parallelism in programming |
|
|
In article <430e0315$1@news.meer.net>, Greg Lindahl <lindahl@pbm.com> wrote:
| Quote: | In article <hHkPe.133637$5N3.100234@bgtnsc05-news.ops.worldnet.att.net>,
Stephen Fuld <s.fuld@PleaseRemove.att.net> wrote:
I'd like to explore this further. ISTM that there are only a few languages
that have any explicit way to declare parallelism and that they differ in
the "level" of parallelism they express.
After 30 years of research, there are more than just a few which have
been proposed, experimented with, and spilled much ink on papers about
the results, etc.
|
A good 30 years. To be fair, there are only a few that have been
used, successfully, by people whose interest is not in parallelism
as such. But even that number is larger than most people realise.
| Quote: | I'm not sure what you hope to accomplish with a comp.arch discussion
of such a huge body of work.
|
Well, one could have a general discussion of parallel paradigms,
but even that is not a small topic.
Regards,
Nick Maclaren. |
|
| Back to top |
|
|
Dan Koren
Guest
|
| Posted:
Thu Aug 25, 2005 11:28 pm Post subject:
Re: Not enough parallelism in programming |
|
|
"Stephen Fuld" <s.fuld@PleaseRemove.att.net> wrote in message
news:hHkPe.133637$5N3.100234@bgtnsc05-news.ops.worldnet.att.net...
| Quote: |
""Torben Ęgidius Mogensen"" <torbenm@app-6.diku.dk> wrote in message
news:7zll2qtcx5.fsf@app-6.diku.dk...
snip
we need either to use
languages where parallelism is either explicit (and verifiably
independent)
I'd like to explore this further. ISTM that there are only a few
languages that have any explicit way to declare parallelism and that they
differ in the "level" of parallelism they express. For example, I believe
that Occam expresses parallelism at a very low level (even evaluation of a
single expression can be specified to be in parallel. But COBOL offers
explicit parallelism at the level similar to a full thread. I'm not sure
which, if either of these is the "right" thing to do.
So, the questions are
- Is there an existing language that expresses parallelism at the right
level for multi-core/multithreaded core to take advantage of?
|
Yes: APL.
| Quote: | Is it easy for programmers to use the language productivly?
|
Yes: this is why APL and its descendants (APL2, A, J, K) are
the darlings of the financial community.
| Quote: | - If not what would such a language look like?
|
It would look pretty much like APL with a couple of extensions.
| Quote: | That is, what level of parallelism is appropriate? How would the
semantics/syntax be designed to make program development easiest and most
bug free?
|
The builtin exception handling mechanism would look up the name
of the developer every time an exception truggers, and print out
immediately a pink slip ;-)
dk |
|
| Back to top |
|
|
Randy
Guest
|
| Posted:
Thu Aug 25, 2005 11:45 pm Post subject:
Re: Not enough parallelism in programming |
|
|
Torben Ęgidius Mogensen wrote:
| Quote: | Joe Seigh <jseigh_01@xemaps.com> writes:
Torben Ęgidius Mogensen wrote:
....
I think what he says is that SIMD is good for GPUs because their
workload suits this model, but that general-purpose CPUs that offer
parallelism in the form of MIMD or other won't find many programs
capable of exploiting said parallelism.
But is he just saying this because he has the "embarrassingly parallel"
easy part. Why complain about the skill set out there when the scarcity
of skills is to your advantage. Get out of the graphics market, write
your own highly parallelized game engine and own the game industry which
makes more money than Hollywood. Piece of cake if you already know how
to write parallel programs.
I don't think graphics engines are the problem, they are fairly easy
to parallelise on GPUs (which are more or less designed for this). It
is (almost) every other program that is the problem.
Torben
|
Right. The problem is that too few independent threads are being
created in the average app (by the programmer and/or the compiler), thus
the second core remains idle.
How to fix this? Compilers of today's primary languages (C/C++, Java,
Fortran) are unable to identify substantial independent threads within
serial programs. OoO-CPUs can do this to some degree, but their
"threads" are very short (perhaps 5-10 instructions), or they arise from
the splitting of loops (which is how graphics pipelines get their SIMD
parallelism). Neither approach works scalably well in serial programs
(since their loops are few and short threads don't delegate efficiently
onto other cores).
The answer? Threads will have to arise from 1) the introduction of new
languages that support implicit parallelism to produce longer threads,
or 2) a populist mastery of explicit PRAM-ish parallel programming
techniques within traditional languages (e.g. POSIX threads, OpenMP,
etc). The former is a problem since it's essentially impossible to sell
industry on the value of novel languages. The latter is a problem since
programmers are going to have to better understand how to identify and
minimize data and control *dependencies* in their code, and since few
tools exist to make this work easier (e.g. KAP's "Guide", now Intel's).
Maybe the best approach would be to explore a middle ground, some sort
of standardized extensions to existing languages that introduce
threading along with some coordination primitives that make their use a
lot prettier (and ideally enable validation). Both C++ and Java support
threads, but they're explicit, uncoordinated, and unvalidated. I think
what we need is native language extensions like coroutines, but that can
be coordinated axiomatically within the language (by defining data
dependencies, their scope, and allowing modification of those axioms as
the program runs and threads come and go and their execution priorities
evolve, as well as providing as much consistency validation as
possible). This might take form as a coherent alternative to OpenMP
that also spawns threads but puts more effort into constraining their
dependencies rather than just splitting loops.
Data-parallel C was in some ways similar to OpenMP. It was accepted as
a ISO? standard, but went nowhere in the early 90's (although it's
probably preferable to OpenMP). However, data parallel isn't the right
approach to programming general purpose multicore CPUs. At least SPMD
and probably MIMD will be necessary.
Randy
--
Randy Crawford http://www.ruf.rice.edu/~rand rand AT rice DOT edu
"If English was good enough for Jesus Christ, it ought to be good enough
for the children of Texas." -- Texas Governor Ma Ferguson (1924) |
|
| Back to top |
|
|
Rupert Pigott
Guest
|
| Posted:
Fri Aug 26, 2005 12:15 am Post subject:
Re: Not enough parallelism in programming |
|
|
MitchAlsup@aol.com wrote:
| Quote: | I think the problem is different.
All synchronization in current machines is memory based. Memory latency
remains rather constant as processor frequency scales to every higher
numbers. So 10 years ago when CPUs were at 200 MHz and main memory was
150 ns away, one could conceivably perform 30 instructions between
synchronization events (and 300 instructions between synchronizations
is vastly more reasonable). Now we have 3GHz machines with 120ns memory
access times. So the granularity for synchronization is 20X worse today
than it was just 10 years ago! As the size of granulation changes, the
structure of the parallel computation should change to follow.
|
That is a very good point, one I've been worrying about that a bit
over the last decade. I think Jon Jakson has the right approach
here, he's looking at an MTA style core with flat memory model (as
far as latency goes). My feeling is that this approach could really
help because you have the option using explicit the *in-order*
execution to achieve zero overhead comms/sync as well as the option
of the slower higher-order methods.
It's not a free lunch though, so there's the "Small Matter of
Programming" to take care of later, but at least the HW gives you
plenty of options when it comes to granularity.
Cheers,
Rupert |
|
| Back to top |
|
|
Nick Maclaren
Guest
|
| Posted:
Fri Aug 26, 2005 12:15 am Post subject:
Re: Not enough parallelism in programming |
|
|
In article <1124999873.769799.54500@o13g2000cwo.googlegroups.com>,
<MitchAlsup@aol.com> wrote:
| Quote: | I think the problem is different.
All synchronization in current machines is memory based. ...
|
I wish :-(
The vast majority is far worse. Because of a lack of support by both
the hardware and operating system, most is system-call based. This
is sometimes "optimised" by using spin loops to attempt to use memory
as a poor man's substitute for the proper primitives. Both of these
approaches are unsatisfactory, at best.
But we don't even get that, because at least Unix schedulers are based
around clock interrupts, often with a huge interval. I don't think
that Microsoft ones are any better. As soon as you allow the scheduler
a look in, you are liable to be blocked for 10 mS - even if there is
no other process that should be run!
Regards,
Nick Maclaren. |
|
| Back to top |
|
|
Joe Seigh
Guest
|
| Posted:
Fri Aug 26, 2005 12:15 am Post subject:
Re: Not enough parallelism in programming |
|
|
Nick Maclaren wrote:
| Quote: | In article <1124999873.769799.54500@o13g2000cwo.googlegroups.com>,
MitchAlsup@aol.com> wrote:
I think the problem is different.
All synchronization in current machines is memory based. ...
I wish :-(
The vast majority is far worse. Because of a lack of support by both
the hardware and operating system, most is system-call based. This
is sometimes "optimised" by using spin loops to attempt to use memory
as a poor man's substitute for the proper primitives. Both of these
approaches are unsatisfactory, at best.
But we don't even get that, because at least Unix schedulers are based
around clock interrupts, often with a huge interval. I don't think
that Microsoft ones are any better. As soon as you allow the scheduler
a look in, you are liable to be blocked for 10 mS - even if there is
no other process that should be run!
|
Scheduler artifacts are fun to deal with. On OS X it appears that for
short sleeps using nanosleep() rather than setting a kernel timer
event, the thread just gets put on the ready queue, the assumption
being it would take you at least that much time to get dispatched again
based on cpu speed and dispatcher code path. Except if there are lots
of threads already on the run queue it could be a very long wait.
I think the previous poster is refering to synchronizing memory itself
rather than by some other mechanism like the TOD clock or direct
processor to processor communication.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software. |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in