[erlang-questions] Re: Classification of concurrency patterns

[Eric Newhuis (personal)]

What about leased state concurrency?  I think I made that phrase up.  I'm thinking Linda and tuplespaces and things like async versions of Javaspaces.  ...all having a reduced instruction set.  Are these covered in your current list?

On May 19, 2010, at 8:50 AM, Joe Armstrong wrote:

> 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
>> 
> 
> ________________________________________________________________
> erlang-questions (at) erlang.org mailing list.
> See http://www.erlang.org/faq.html
> To unsubscribe; mailto:erlang-questions-unsubscribe@REDACTED
>