parallel Haskell concept map?
Eric Kow
Kevin Hammond
I'm writing a book with Phil Trinder on Parallel Haskell. We can give you the current glossary entries if that helps?
Obviously we'll look at the ones you're defining.
> <parallel.png>
Best Wishes,
Kevin
--------
Kevin Hammond, Professor of Computer Science, University of St Andrews
T: +44-1334 463241 F: +44-1334-463278 W: http://www.cs.st-andrews.ac.uk/~kh
In accordance with University policy on electronic mail, this email reflects the opinions of the individual concerned, may contain confidential or copyright information that should not be copied or distributed without permission, may be of a private or personal nature unless explicitly indicated otherwise, and should not under any circumstances be taken as an official statement of University policy or procedure (see http://www.st-and.ac.uk).
The University of St Andrews is a charity registered in Scotland : No SC013532
Jost Berthold
Your diagramme looks like a good starting point, Yet, the first thing
is, it is more a table than a diagram. In my view, the transition from
parallel to concurrent/distributed is not really a fixed borderline (for
instance, look at Haskell contributions to the "progamming language
shootout", they look rather imperative and use concurrent Haskell, but
for the purpose of speeding up, parallelism).
There are some scientific papers around that might help understanding,
especially one:
"Parallel and Distributed Haskells" by P.Trinder, H.W.Loidl and
R.Pointon, in a special issue of JFP.
http://www.lmgtfy.com/?q=parallel%20and%20distributed%20Haskells
While already a bit older (2002), it collects a number of research
oriented approaches to parallel Haskell not showing in your overview,
gives a historic perspective, and includes a simple scheme in two
dimensions (location-awareness and explicitness) that will help improve
yours.
To fill the "hole" in red, you can put the word "Eden" (and I would say
move it up a bit), and there is an ongoing Haskell+MPI reimplementation
(the first one was in 2000).
Finally, thanks for bringing this up! The idea to collect "a big
picture" in this forum is very good. I am forwarding this message to
another list (including Phil Trinder and Hans-Wolfgang Loidl, btw) for
information.
Jost
Oleg Lobachev
On Feb 24, 2011, at 10:29 , Eric Kow wrote:
> Maybe some sort of map would help? My hope is that something that
> puts all these concepts on the same page and relates them together
> (without trying to explain them) could help fellow newbies to build
> up their confidence.
As a more narrow task of a classification of parallel Haskell dialects, I would suggest some kind of a single-dimension classification. An example would be the PCAM from Foster's 1995 book "Designing and building parallel programs". Foster separates four phases, partitioning, communication, agglomeration and mapping. For a classification--inspired by Rita Loogen's lectures--one would need to denote, what phases are done by the compiler and what phases are left to the programmer. So, we can denote a semi-explicit parallel language as P---, as only partitioning is the programmer's task. A "control" parallel language would be PCA-. The explicit language would be PCAM.
In a broader context, you will need to identify paradigms (e.g., SMP), approaches (e.g., STM) and software tools (e.g., Eden TV).
Greetings,
Oleg
Paul Bone
> Hello parallel Haskell fans!
>
> ------------------
> 1. Should I maintain the dashed line separating Parallelism and
> Concurrency? Or is this something that's better treated as
> being on a continuum (NB: from the user's perspective)?
>
I'd like to comment on this point in particular. The confusion between
Parallelism and Concurrency is one of my pet hates, and it's also something
that many people misunderstand.
Parallelism - is about using more than one processor (or SIMD instructions on a
single processor) during execution to speed up a program. The program does not
necessarily need to be written for parallelism. That is to say parallelism is
an implementation detail and one that it is only realized at runtime. For
example an arbitrary pure functional program can be evaluated in parallel if
the compiler and runtime support it, or the same program can be evaluated
sequentially.
Concurrency - is about expressing concurrent 'threads' of execution in a
program. This is a programming abstraction and helps the programmer separate
concerns within a program. Consider a web server serving many documents to many
clients simultaneously. The programmer may wish to use threads, using one
thread per client making it easier to manage concurrent actions.
These concepts are often confused because a programmer usually needs
concurrency to achieve parallelism, and therefore thinks that concurrency is
parallelism. This is possibly more confusing now that mutlicore CPUs are
ubiquitous, since in most cases concurrency will create parallelism (provided
that the compiler and runtime system support it).
Despite this there are cases where concurrency doesn't imply parallelism, one
example is the use of generators in Python. There are also cases where
parallelism doesn't imply concurrency, such as auto-parallelizing compilers.
Therefore, when classifying technologies as Parallel or Concurrent I believe
that these concepts should be kept separate. Everything can be classified as:
+ Neither Parallel or Concurrent.
+ Parallel but not Concurrent.
+ Concurrent but not Parallel.
+ Both Parallel and Concurrent.
Trinder, Philip W
A few thoughts:
What are you trying to do with your diagram? Is it to introduce
parallelism and concurrency options to Haskell programmers? What do you
plan to do with it? Could we use it if we like it?
Assuming you plan to introduce parallelism and concurrency options to
Haskell programmers, here are some comments.
* Please write 'Evaluation Strategies', rather than 'Strategies'
* Suggest you don't cover
+ MPI (it's too low level) or
+ Distributed Haskells - too experimental for most Haskell programmers
* Some aspects you've missed:
+ What Haskell implementations support the models. Perhaps this doesn't
matter if you assume people only use GHC, but even then they may need to
know that there's no parallelism in ghci
+ The distinction between shared memory and distributed memory
architectures. Currently GHC only supports shared-memory parallelism,
and not distributed memory. Example distributed memory implementations
are GUM and Eden.
> > 1. Should I maintain the dashed line separating Parallelism and
> > Concurrency? Or is this something that's better treated as
> > being on a continuum (NB: from the user's perspective)?
Yes, they are fundamentally different. Concurrent (IO) threads are
stateful, require mandatory scheduling etc.
> > 2. How do you feel about the attempt to arrange concepts on a
> > continnum of use it now! <-> current research? Note that my
> > classification may be incorrect (given my ignorance), but I
> > wonder if more generally there is a more useful Y-axis
> > dimension for fellow newbies.
Fine.
HTH,
Phil
--
Heriot-Watt University is a Scottish charity
registered under charity number SC000278.
Simon Marlow
> I'd like to put some of my cluelessness to service for the parallel Haskell
> the community.
>
> There seems to be a profusion of concepts and acronynms (eg. STM, SMP, GPH,
> CnC, NDP, DpH) related to parallel Haskell. I suspect that this could be
> intimidating for people who are new to parallelism and concurrency and/or to
> Haskell itself. It might create the impression that you have to learn a lot
> of stuff to get started (which seems false), or perhaps create a "tyranny of
> choice" situation (argh! where do I start?)
The diagram is a good start, and I like the idea. We should have something like this on the front page of parallel.haskell.org. My main suggestion would be to separate it into two:
- one aimed at *users*, people who want to pick up the existing tools
and write concurrent or parallel programs. For this audience the
picture can be simplified considerably by removing all of the
experimental stuff (e.g. I'd leave out CnC, CHP, DPH, etc.). For
parallelism we have par/pseq and Strategies, for concurrency we have
forkIO, MVars and STM - these are the technologies we fully support.
- the full picture, including all experimental and research topics, and
libraries on Hackage such as Orc and parallel-io.
I like the way you made a top-level distinction between concurrency and parallelism. The quicker users understand the distinction, the easier their lives will be.
> PPS. I gather from the name of our mailing list that we are convering
> towards "Parallel Haskell" as a catch-all term for Haskell
> Parallelism and Concurrency? Is that right? It's very helpful to
> have a *short* name (one word is nice, ie. X or Haskell X)
> that captures the essence of what we're doing. "Multicore" seems
> like another candidate (seeing Don's Multicore Haskell Now!
> slides), but I get a feeling that something more abstract would be
> preferable.
Cheers,
Simon
Eric Kow
Paul Bone
> Paul Bone
> ======================================================================
> > These concepts are often confused because a programmer usually needs
> > concurrency to achieve parallelism, and therefore thinks that concurrency
> is
> > parallelism
>
> Could I just confirm what you mean mean when you say a programmer
> /usually/ needs concurrency (as opposed to always)? Reading your
> separation of the concepts, I think you are saying that programmers
> often manipulate some thread-of-execution abstraction to get parallelism
> (as Jost points out about the shootout code). Would using things like
> par/pseq or NDP thus count as "not using concurrency to achieve
> parallelism"?
Yes. I don't think par/pseq are about concurrency (nor are evaluation
stratergies). They're hints* to the compiler/runtime about where parallel
evaluation should be used. But they're not about concurrency because the
programmer doesn't use them to express the program in a different way (such as
they would with STM, message passing etc)
*I'm not sure how people prefer to classify par. They could be called hints
as they will be sparked but that doesn't gaurentee that they'll be executed in
parallel. Perhaps 'pragma' is a better term.
In general (imperative and declarative languages) programmers usually need
concurrency to gain parallelism. In particular, threads are often used for
this. I only mention this because I think it's how people become confused
about the terms parallel and concurrent.
> > Therefore, when classifying technologies as Parallel or Concurrent I
> believe
> > that these concepts should be kept separate. Everything can be classified
> as:
> > + Neither Parallel or Concurrent.
> > + Parallel but not Concurrent.
> > + Concurrent but not Parallel.
> > + Both Parallel and Concurrent.
>
> Viewing Parallel and Concurrent as orthogonal concepts is helping me
> to see things a bit more clearly, thanks! I'll be experimenting to see
> if reflecting this in the diagram is useful for my needs.
I'm glad! I was worried that I was being preachy, or that everyone on the list
already knew and I was beating a dead horse.
> Simon Marlow
> ======================================================================
> > My main suggestion would be to separate it into two:
>
> I think I like this idea. I still might play with the combined diagram
> for a while, at least to the extent that users may find it helpful to
> see "distractor" concepts being explicitly mentioned (for example,
> having unsupported technologies represent in faded texts) as I mentioned
> to Phil. But if that should fail, two diagrams it is (also good
> because each diagram can have radically different perspectives, axes,
> representation schemes, etc).
Can I vote-up this idea?