3
$\begingroup$

Quoted from http://en.wikipedia.org/wiki/Task_parallelism:

Task parallelism (also known as function parallelism and control parallelism) is a form of parallelization of computer code across multiple processors in parallel computing environments. Task parallelism focuses on distributing execution processes (threads) across different parallel computing nodes. It contrasts to data parallelism as another form of parallelism.

  1. I was wondering if there is some correspondence between Flynn's taxonomy (SISD, SIMD, MISD and MIMD), and "task parallelism and data parallelism"? For example,

    does task parallelism mean multiple-instruction in Flynn's taxonomy, so one can say "task parallelism = MISD+MIMD"?

    does data parallelism mean multiple-data in Flynn's taxonomy, so one can say "data parallelism = SIMD+MIMD"?

  2. If there is no exact correspondence between the two classification methods, how shall one understand their differences and relations?

Thanks and regards!

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ @Robert I pinged the CSTheory mods in their chat to see if this question would be on topic there. $\endgroup$ – Anna Lear Jul 18 '11 at 17:20
2
$\begingroup$

Task/Data parallelism is a simple classification that lies at the algorithm-level of a computation.

Flynn's taxonomy describes low-level machine architectures or models.

Trying to draw lines between both completely ignores the vast sea of complexity that lies between those two levels. Using an example; You can do task, data and pipeline parallelism perfectly on a SISD for example. Stating that you cannot ignores the vast complexity of today's operating systems.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Task parallelism and data parallelism are different approaches to handling MIMD. Thus Flynn's taxonomy is irrelevant.

The difference is simple. In data parallelism you hand out data to different CPUs that are doing the same thing with their data. In task parallelism you hand tasks out to different machines and send data where it needs to go.

Of course in the real world you don't do one or the other, you do both. For instance you run a MapReduce. In your map, sort and reduce phases there is a lot of data parallelism as many different nodes are doing the same thing with the data that they are receiving. However there is also task parallelism because you might have a central supervisor, nodes doing mapping, nodes doing sorting, and nodes who are ready to reduce, all at the same time.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! About "Task parallelism and data parallelism are different approaches to handling MIMD. Thus Flynn's taxonomy is irrelevant.", in data parallelism en.wikipedia.org/wiki/Data_parallelism, there is SIMD $\endgroup$ – Tim Jul 18 '11 at 17:48
  • 2
    $\begingroup$ @Tim True, good point. And there is no way to do task parallelism with SIMD. But my point remains that Flynn's taxonomy is addressing the architecture of the machine(s) you have available, while task vs data parallelism is discussing how you are handling parallelism in your software solution. Also Flynn's taxonomy is pretty much binary, while task/data parallelism are two poles in a continuum. $\endgroup$ – btilly Jul 18 '11 at 19:04
  • $\begingroup$ Just want to stress here that Data/Task parallelism is a very primitive and naive view on the parallel world. In practice you indeed often do combinations, but you also have pipeline and tournament parallelism. (tournament parallelism is: whoever finishes first returns final result, > linear speedup) $\endgroup$ – Beef Aug 18 '11 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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