5 Parallel algorithms and patterns
This chapter covers
- What parallel algorithms and patterns are and why they are important
- How to compare the performance of different algorithms
- What distinguishes parallel algorithms from algorithms in general
- The importance of parallel patterns
Algorithms are at the core of computational science. Along with data structures, covered in the previous chapter, algorithms form the basis of all computational applications. For this reason, it is important to give careful thought to the key algorithms in your code. Let’s define what we mean by parallel algorithms and parallel patterns
Definition:
Parallel Algorithm -- a well-defined, step-by-step computational procedure that emphasizes concurrency to solve a problem. Examples of algorithms include: sorting, searching, optimization, and matrix operations.
Definition:
Parallel Pattern -- a commonly occurring sequence of independent, potentially concurrent operations that occurs in diverse scenarios with some frequency. Examples are: reductions, prefix scans, and ghost cell updates.
We will show the reduction in section 5.6, the prefix scan in section 5.5, and ghost cell updates in section 8.4.2.
In one context, a parallel procedure may be considered an algorithm, and in another, it may be a pattern. The real difference is whether it is accomplishing the main goal or is just part of a larger context. Recognizing patterns that are “parallel friendly” is important to prepare for later parallelization efforts.