parallelism vs concurrency revisited (and diagrammed)

228 views
Skip to first unread message

Eric Y. Kow

unread,
Mar 17, 2011, 5:54:04 AM3/17/11
to parallel...@googlegroups.com
Hi everybody,

This is a semi-followup to my first posting about building up a parallel
Haskell concept map. Unfortunately, I don't have much news on the
jargon maps I was hoping to build; but along the way I've started toying
with a different kind of map, one focusing on the distinction between
parallelism and concurrency.

Thanks to that first thread, I have learned to think of parallelism and
concurrency as neither the same, nor polar opposites or opposite ends of
a spectrum, but as orthogonal concepts. The idea then is you could have

~P ~C : classic Haskell
P ~C : par, pseq, etc (where Haskell shines)
~P C : forkIO, MVar, etc; time-slicing on one CPU
P C : same as above, but w threads on multiple CPUs

Unfortunately our use language does not help to make this clear.
Consider the following interleaving of concepts:

- on the one hand, we say parallelism without concurrency is
abstract, higher level, programmer-friendly, etc;
- on the other hand, parallelism is presented as a low-level
thing (the fact of running on multiple CPUs), and concurrency
is talked about as an abstraction
- you can achieve parallelism by making explicit use of
concurrency abstractions
- the GHC manual says things like "by making use of multiple CPUs it is
possible to run concurrent threads in parallel, and this is exactly
what GHC's SMP parallelism support does"

To untangle these apparent contradictions, one has to realise that we
can use words like "parallel" and "concurrent" in many several ways,
to talk about

1. programmer intentions (P)
2. what happens in the hardware (H)
3. in everyday English

Making this distinction clear helps me to untangle statements like
"achieving parallelism using concurrency but with GHC's SMP
parallelism support enabled", by realising that we're talking about
P-parallelism in the first instance and H-parallelism in the second.

OK this much is clear after having the benefit of discussion and good
old fashioned head-scratching. My question now is how to make this
readily apparent? I want to target the kind of programmer that doesn't
really have the luxury of head-scratching and idle reflection. Attached
is one approach, using a layered representation to communicate the ways
that parallelism and concurrency appear to be interleaved.
Unfortunately, it doesn't appear to leave much room for much else, eg.
things like STM. I'll be working on something more like the original
concept maps to explore this further, but in the meantime, what do you
think?

How can we communicate this more effectively?

Many thanks!

--
Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
For a faster response, try +44 (0)1273 64 2905 or
xmpp:ko...@jabber.fr (Jabber or Google Talk only)

parallel-vs-concurrent.png

Simon Marlow

unread,
Mar 18, 2011, 5:01:14 AM3/18/11
to parallel...@googlegroups.com
Hi Eric,

The diagram is clever, and correct, but somehow I have the feeling it won't help to straighten out the picture for someone who doesn't already understand it (I could be wrong of course). I'm wondering about factoring it a bit differently. This involves inventing a new term "Pure Parallelism" which I'm open to suggestions for renaming:

Parallelism:
Speeding up a program by using multiple processors.

In Haskell we provide two ways to achieve parallelism:
- Concurrency, which can be used for parallelising IO.
- Pure parallelism, which can be used to speed up pure (non-IO)
parts of the program.

Concurrency (Control.Concurrent):
Multiple threads of control that execute "at the same time".
- Threads are in the IO monad
- IO operations from multiple threads are interleaved
non-deterministically
- communication between threads must be explicitly programmed
- Threads may execute on multiple processors simultaneously
- dangers: [[race conditions]] and [[deadlocks]]

Pure Parallelism (Control.Parallel):
Speeding up a pure computation using multiple processors.
- Pure parallelism has these advantages:
- guaranteed deterministic (same result every time)
- no [[race conditions]] or [[deadlocks]]

Rule of thumb: use Pure Parallelism if you can, Concurrency otherwise.


Cheers,
Simon

Eric Kow

unread,
Mar 18, 2011, 8:19:06 AM3/18/11
to parallel...@googlegroups.com
Hi Simon,

On Fri, Mar 18, 2011 at 09:01:14 +0000, Simon Marlow wrote:
> The diagram is clever, and correct, but somehow I have the feeling it
> won't help to straighten out the picture for someone who doesn't
> already understand it (I could be wrong of course).

Thanks for the feedback!

Now that I've been polluted enough to make the diagram anyway, I find
it hard to put myself into me-from-last-week's shoes, much less to say
somebody else's. Having lots of different perspectives (and alternative
approaches) is useful, at least short of gathering some sort of
empirical evidence from fellow newbies :-)

The different factoring sounds like an interesting tack, subordinating
concurrency to parallelism and introducing "pure" parallelism as a
distinct concept. Having a distinct word/phrase for the right things
makes language a lot easier like your "use pure parallelism if you can",
and maybe something like "Haskell is a great language because it
supports pure parallelism".

I'll have to consider the implications more (all the while being careful
not to let myself get carried away trying to solve the newbie problem!),
and you may see me lifting this and dumping it straight onto the Haskell
wiki, convenient links and all.

Eric

PS: I noticed my first version may have been a bit small.
Hopefully, this is a bit easier to read
http://i.imgur.com/fxLNf.png

signature.asc

Simon Marlow

unread,
Mar 18, 2011, 8:49:31 AM3/18/11
to parallel...@googlegroups.com
> Hi Simon,
>
> On Fri, Mar 18, 2011 at 09:01:14 +0000, Simon Marlow wrote:
> > The diagram is clever, and correct, but somehow I have the feeling it
> > won't help to straighten out the picture for someone who doesn't
> > already understand it (I could be wrong of course).
>
> Thanks for the feedback!
>
> Now that I've been polluted enough to make the diagram anyway, I find it
> hard to put myself into me-from-last-week's shoes, much less to say somebody
> else's. Having lots of different perspectives (and alternative
> approaches) is useful, at least short of gathering some sort of empirical
> evidence from fellow newbies :-)
>
> The different factoring sounds like an interesting tack, subordinating
> concurrency to parallelism and introducing "pure" parallelism as a distinct
> concept. Having a distinct word/phrase for the right things makes language
> a lot easier like your "use pure parallelism if you can", and maybe
> something like "Haskell is a great language because it supports pure
> parallelism".

FWIW some people (outside the Haskell community) call it "Deterministic concurrency" or "Deterministic parallelism", whereas we in the Haskell community tend to shorten it to "Parallelism". I think having a good term for this would be useful - we're often using the word "Parallel" to mean different things.

Cheers,
Simon

Manuel M T Chakravarty

unread,
Mar 18, 2011, 9:10:19 AM3/18/11
to parallel...@googlegroups.com
I strongly support Simon's proposal.

Manuel


Simon Marlow:

Paul Bone

unread,
Mar 19, 2011, 8:18:28 AM3/19/11
to parallel...@googlegroups.com
On Fri, Mar 18, 2011 at 09:01:14AM +0000, Simon Marlow wrote:
> Hi Eric,
>
> The diagram is clever, and correct, but somehow I have the feeling it won't help to straighten out the picture for someone who doesn't already understand it (I could be wrong of course). I'm wondering about factoring it a bit differently. This involves inventing a new term "Pure Parallelism" which I'm open to suggestions for renaming:
>
> Parallelism:
> Speeding up a program by using multiple processors.
>
> In Haskell we provide two ways to achieve parallelism:
> - Concurrency, which can be used for parallelising IO.
> - Pure parallelism, which can be used to speed up pure (non-IO)
> parts of the program.
>
> Concurrency (Control.Concurrent):
> Multiple threads of control that execute "at the same time".
> - Threads are in the IO monad
> - IO operations from multiple threads are interleaved
> non-deterministically
> - communication between threads must be explicitly programmed
> - Threads may execute on multiple processors simultaneously
> - dangers: [[race conditions]] and [[deadlocks]]
>
> Pure Parallelism (Control.Parallel):
> Speeding up a pure computation using multiple processors.
> - Pure parallelism has these advantages:
> - guaranteed deterministic (same result every time)
> - no [[race conditions]] or [[deadlocks]]

In general I like this distinction.

Specifically I've heard people call Pure Parallelism, Determinstic Parallelism.
Emphacising the fact that the program is semantically deterministc. But this
may confuse the issue if determinism means different things in different
contexts (and to different people).

I really don't mind what it's called.

signature.asc
Reply all
Reply to author
Forward
0 new messages