Parallelism in SMP

Just as for distributed-memory programming, parallelism can be expressed in different ways, with the two main ones being data parallelism and task_parallelism.

Data Parallelism

In data parallelism we divide the data into smaller parts and work on each part individually, then if necessary collect results and go to next phase.

In distributed-memory programming, data decomposition must be handled by the programmer by means such as adjusting loop bounds or modifying the algorithm to be valid over the same loop bounds for each of the subdomains. Most of our MPI examples involve this type of data decomposition.

In shared-memory programming, the programmer does not usually explicitly break down the data; the threading library distributes the work across the running threads.

In both cases, the operations performed within the loop should be safe to run concurrently, with no dependencies. MPI can handle dependencies through communication within the loop, but this is not advisable as it is highly inefficient and can lead to errors. On the other hand, it is fundamental to multithreaded programming that the operations be independent of others in the same loop.

Task Parallelism

In task parallelism the program performs multiple tasks at the same time on the data. The tasks must be independent of each other.

Many familiar user applications employ task threading. A Web browser may use one thread for rendering HTML and another for downloading the data in the background. A word processor may have separate threads to respond to keystrokes, check spelling, and display the page.

Some authors limit “parallelization” to data parallelism and refer to task parallelism as concurrency. Tasks run in their own threads concurrently but are not necessarily as tightly coordinated as in data parallelism.