Here are some things I’d like to see in a parallel algorithms book. I’m particularly focussed on a book covering fundamental algorithms much more than CUDA implementations.

Fundamental ideas

Parallel threads

Race conditions

Atomic operations

Sequential versus parallel complexity

Binary tree / divide-and-conquer algorithms

Reduction

Scan

Recurrence equation

Cyclic reduction for tridiagonal equations

FFT

Butterfly network

Other applications?

Wavefront parallelisation

Gauss-Seidel iteration

ILU preconditioning

Multi-frontal direct sparse solver

Task parallelism

Task DAGs and their parallel execution

Relevance to dense linear algebra

N-body problems

Construction and updating of oct-tree structures

Parallel implementation of multipole methods

Partitioning, renumbering and coloring

Parmetis, PT-Scotch and similar partitioning algorithms

Parallel partition refinement and load balancing

Relevance to renumbering for improved locality

Coloring to avoid race conditions

Sequential greedy coloring

Parallel randomised coloring

Sorting algorithms

Radix sort

Merge sort

SkipList insert sort