3
$\begingroup$

Do anyone know if there exist any widely used parallel computing programming paradigms/models not based on a master/slave concept?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
6
$\begingroup$

For parallel models I see them as communication-based or work decomposition-based:

Communication-based models

  • Shared memory: implicit communication via sharing memory.
  • Message passing: explicit communication by passing messages between parallel programs.

Work partitioning models

  • Domain decomposition. Problem domain is divided into sub-domains, problem is solved by solving all the sub-problems.

  • Task-based decomposition: compute work is organised in the form of tasks (it could also be objects). Tasks could be homogeneous or each task could perform different work. Examples for this can be seen in OpenMP, Intel thread building blocks, starPU/Quark.

    • Implicit dependencies: constructs are used to implicitly represent relations between tasks, think of OpenMP and its #pragma omp parallel for.
    • Explicit dependencies: relations between task are the core of the representation. A good discussion is given here

Paradigms examples

  • Single program multiple data (SPMD): Domain decomposition.
  • Parallel functional programming: implicit task model.
  • Master-slave paradigm: explicit task-based model.
  • Divide and conquer: domain decomposition.
  • GPU computing: most commonly domain decomposition.
  • Work pool and/or parallel queues: task-based model or domain decomposition.

With the heterogeneity and hierarchical structure of parallel computing architectures currently available, programs tend to mix models and paradigms to better match the architecture. Consider for instance message passing between nodes while using shared memory intra-node, that would match with a divide and conquer approach to distribute work across the nodes while locally each sub-domain could be solved using SPMD over multiple cores, a GPU, or both.

Improve this answer
$\endgroup$
8
$\begingroup$

Almost no HPC is done with master-slave, because it doesn't scale. It's all "peer-to-peer" in some sense. You design a decomposition of the problem - domain decomposition, frequency-space decomposition, something - and each task is assigned it's piece of the decomposition; they then work on their parts of the problem, exchanging data back and forth between each other as necessary.

The closest thing you'll see to master-slave is something like "work-stealing" which can be thought of as a distributed, peer-to-peer task queue; but even that isn't something I've seen used at really large scale; usually there's a more complicated load balancing step taken.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ I disagree that master-slave is not used. It's often an excellent way to get cheap gains. For example, I was consulting on a problem in which a very unusual correlation statistic had to be computed pairwise between a huge number of column vectors. The unusual statistic involved checking indices where one of the vectors was greater than the other, and so it was impossible to decompose it meaningfully. But with a reasonable cluster, all the person needed to do was rewrite their code into a decent language (they chose Fortran) and do pairwise master-slave for groups of vectors. $\endgroup$
    – user563
    Mar 15, 2012 at 0:58
  • $\begingroup$ I'm sure there could be a more advanced HPC paradigm for that situation, but my point is that in order to do master-slave, it only required writing one additional function and some small overhead code. It was really easy, didn't slow the person down in needless details, and sped up their existing program many order of magnitude. In this sense, people should think about master-slave frequently. Don't reach for a really big hammer unless it's a really big nail... $\endgroup$
    – user563
    Mar 15, 2012 at 1:00
  • 1
    $\begingroup$ Nonetheless, almost no HPC is done with master-slave. $\endgroup$
    – user389
    Mar 15, 2012 at 12:10
3
$\begingroup$

There's also pipelining (or 'functional parallelism'), where different nodes run different parts of the process. This is generally only useful for problems that are embarrassingly parallel but where each part is still a pretty hefty problem (an example commonly given is astronomical image processing, where you have lots of images and several steps to perform on each one). It also requires careful load balancing.

Improve this answer
$\endgroup$
2
$\begingroup$

Yes, there's the Thread Pool, in which all threads of a parallel code access a list of tasks and compute them asynchronously.

In OpenMP + pseudocode, this could be implemented as follows:

#pragma omp parallel
while ( there are still tasks ) {

    #pragma omp critical
    {
        get a task T from the task list.
    }

    exectue task T;

    }

This model, however, is based on some form or another of shared-memory parallelism. In a distributed-memory system you could have the task list reside on one of the nodes, but then any other node would have to be able to access it without stopping that node. I don't see how this can be done without reverting to a master/slave model though.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.