Parallel Algorithms
A parallel algorithm is a collection of tasks and a partial ordering between them.
Design goals: We will return to this later on
- 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: We will discuss this now
- 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