The first step in developing a parallel program is determining which parts of your problem can be computed in parallel. There are two main strategies for parallelizing a problem: parallelizing data processing or parallelizing function calls.

Data Parallelism

If your application involves applying the same operations to a large collection of relatively independent data, you may opt to leverage data parallelism. In data parallel design, each parallel worker applies the same operations to a different segment of the data. When your problem involves data parallelism:

• Each worker does the same work on a unique piece of data.
• Data placement is an essential part of a data-parallel algorithm.
• Follow the "owner computes" principle. Divide the data among workers. Each worker is responsible for whatever computation is needed to process its data.

Problems involving data parallelism are:

• Typically more scalable than functional parallelism (see below).
• Programmable at a high level (compiler directives or pragmas) with OpenMP, especially on a shared memory machine.
• Programmable at a lower level (subroutine calls) using a message-passing library like MPI, especially on a distributed memory machine.

Functional Parallelism

Alternatively, if your application features widespread, unavoidable data dependencies, you may choose to utilize functional parallelism (also called task parallelism). In functional parallel design, each parallel worker performs different operations on the data. When your problem involves functional parallelism:

• Each worker performs a different "function" or executes a different code section.
• First, identify functions, then look at the data requirements.
• Message-passing libraries help facilitate communications among functions.

The example below illustrates a particular kind of functional parallelism called pipelining:

In this example, each of the three workers performs one of the filtering computations. The data is divided into independent segments, and the filtering functions run in parallel. Initially, only the first worker has data to process, but once it finishes processing the first segment, the second worker can start. As the second worker is processing the first data segment (D1), the first worker processes the second data segment (D2). Soon, all the workers are busy processing different data segments, each in a different processing stage. While each data segment is processed sequentially, the computation is parallel because each worker can work on a different segment. Note that functional parallelism was only possible in this case because some data parallelism also exists in the problem (the data could be divided into relatively independent segments).

Data and functional parallelism can be used in combination. A program can be partitioned by function; each function can then be partitioned by data. In addition, there are some cases in which the distinction between the two categories blurs.