Classification of concurrency patterns

[Joe Armstrong]

Found these they are looking at a similar problem

http://www.drdobbs.com/architecture-and-design/224900184
http://parlab.eecs.berkeley.edu/wiki/patterns/patterns

/Joe


On Wed, May 12, 2010 at 9:31 AM, Joe Armstrong <erlang@REDACTED> wrote:
> 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
>