|
A parallel algorithm is a collection of tasks and a partial ordering between them.
|
Design goals:
-
Match tasks to the available processors (exploit parallelism).
-
Minimize ordering (avoid unnecessary synchronization points).
-
Recognize ways parallelism can be helped by changing ordering
|
Sources of parallelism:
-
Data parallelism: updating array elements simultaneously.
-
Functional parallelism: conceptually different tasks which combine to solve the problem. This happens at fine and coarse grain size
-
fine is "internal" such as I/O and computation; coarse is "external" such as separate modules linked together
|
