Classification of concurrency patterns

[Joe Armstrong]

I'm interested in trying to classify and name a number of different
parallelization strategies.

We often use expressions like MPC "message passing concurrency" and
SPC "shared state concurrency" this is not what I'm interested in.

I'm interested in classifying and naming the strategies we use to
write parallel code. We could *implement* these strategies using MPC
or SSC.

I've chosen my own names for these below, I have no idea if there are
standard names for these classifications, this is what I've called them:

1) Divide and conquer concurrency
2) Pipeline concurrency
3) Map reduce concurrency
4) Identical Job concurrency
5) Grid concurrency
6) Job queue concurrency

They mean the following:

1) Divide and conquer concurrency

Divide the problem into K jobs which can be performed in parallel.
Perform the jobs
Recombine the results

2) Pipeline concurrency

Divide the problem into K jobs that can be performed in a pipeline.
The output of the first job must be the input of the second and so on.
Run all the steps in parallel

3) Map reduce concurrency

    This is similar to 1). Only the recombination step involves
merging results that
   have the same Key.

4) Identical Job concurrency

    Here the problem does not have to be split into K parts, we
already have N identical
    jobs to do (identical means jobs that will consume similar resources)

   There is no recombination step. There are N results.

5) Grid concurrency

    Divide the problem into N*M identical jobs that can be solved on a
NxM grid of processors.
    Each processor can only talk to its direct neighbors

6) Job queue concurrency

    Divide the problem into a set of named workers (who do jobs). Each
worker has an input
    job queue. Workers consume jobs from their job queues and send the
result to other workers.

    Note:  [1] Paul Morrison calls this flow based programming
               [2] This is AMQP


----


That was my first attempt at naming and classifying these patterns.

I'd be interested to know alternative names for the same things, and
names of systems that employ
the above strategies, and of course missing strategies.

If we could name and classify these things then we could start writing
gen_divide_and_conquer
gen_pipe etc.

/Joe