Information Technology Reference
In-Depth Information
evenly among the processors, which are to work concurrently, with coordination in
the form of information exchange and synchronization. The purpose of information
exchange is to provide private data to other processors that need them, whereas syn-
chronization has the purpose of keeping the processors at same pace when desired.
Both forms of coordination require the processors to communicate with each other.
Moreover, for parallel computing to be beneficial, it is necessary that all the proces-
sors have a sufficient work load, and that the extra work caused by parallelization is
limited.
Parallelism and Work Division
Parallelism in a computational problem arises from the existence of computations
that can be carried out concurrently. The two most common forms of parallelism
in scientific computing are
task parallelism
and
data parallelism
. Task parallelism
arises from a set of standalone computational tasks that have a clear distinction
between each other. Some of the tasks may need to follow the completion of other
tasks. The possibility of parallel computing in this context arises from the concurrent
execution of multiple tasks, possibly with some interaction between each other.
A simple example of task parallelism is parameter analysis: for example, a coef-
ficient of a partial differential equation (PDE) is perturbed systematically to study
its impact on the solution of the PDE. Here, each different value of the coef-
ficient requires a new solution of the PDE, and all these different PDE-solving
processes can proceed totally independently of each other. Therefore, one-PDE
solving process, i.e., a computational task, can be assigned to one processor.
In the case that a certain dependency exists among (some of) the tasks, it is
necessary to set up a dependency graph involving all the tasks. Parallel execution
starts with the tasks that depend on nobody else and progressively includes more
and more tasks that become ready to execute. When there are more waiting tasks
than available processors, a dynamically updated job queue needs to be set up and
possibly administered by a master processor. The worker processors can then each
take one task off the queue, work on the assigned task, and come back for more
until the queue is empty. Also, the worker processors may need to communicate
with each other, if the assigned tasks require interaction.
When the number of tasks is small and the number of processors is large, an extra
difficulty arises, because multiple processors have to share the work of one task. This
is a more challenging case for parallel computing and requires further work division.
The answer to this problem is data parallelism, which is a much more widespread
source of parallelism in scientific computing than task parallelism. Data parallelism
has many types and loosely means that identical or similar operations can be carried
out concurrently on different sections of a data structure. Data parallelism can be
considered as extreme task parallelism, because the operations applied on each unit
of the data structure can be considered a small task. Data parallelism can thus pro-
duce, if needed, fine-grain parallelization, whereas task parallelism normally results
in coarse-grain parallelization. The somewhat vague distinction between the two
