5 Parallel algorithms and patterns

 

This chapter covers

  • What parallel algorithms and patterns are and their importance
  • How to compare the performance of different algorithms
  • What distinguishes parallel algorithms from other algorithms

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. To begin, let’s define what we mean by parallel algorithms and parallel patterns.

  • A parallel algorithm is 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.
  • A parallel pattern is 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 include reductions, prefix scans, and ghost cell updates.

5.1 Algorithm analysis for parallel computing applications

5.2 Performance models versus algorithmic complexity

5.3 Parallel algorithms: What are they?

5.4 What is a hash function?

5.5 Spatial hashing: A highly-parallel algorithm

5.5.1 Using perfect hashing for spatial mesh operations

5.5.2 Using compact hashing for spatial mesh operations

5.6 Prefix sum (scan) pattern and its importance in parallel computing

5.6.1 Step-efficient parallel scan operation

5.6.2 Work-efficient parallel scan operation

5.6.3 Parallel scan operations for large arrays

5.7 Parallel global sum: Addressing the problem of associativity

5.8 Future of parallel algorithm research

5.9 Further explorations

5.9.1 Additional reading

5.9.2 Exercises

Summary