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 concurrent, separable, fragment of code that occurs in diverse scenarios with some frequency. By themselves these code fragments generally do not solve complete problems of interest. Some examples are: reductions, prefix scans, and ghost cell updates.
We will show the reduction in section 5.7, the prefix scan in section 5.6, and ghost cell updates in section 8.4.2.