Parallel algorithms¶

Category: Parallelism · Status: stub · Lessons: chapter 07, Parallelism

One line: Sorting, searching, graph and numeric algorithms rebuilt so that their work splits across cores — not always by the obvious split.

Also called: parallel sort, parallel search.

How it connects¶


Rust	Rayon's `par_sort` ↗ and the other parallel slice methods
C++	the standard algorithms with an execution policy ↗ (C++17), such as `std::sort(std::execution::par, ...)`
Java	`Arrays.parallelSort` ↗

In this library: Splitting a sum across workers
In the books: An Introduction to Parallel Programming, Peter S. Pacheco, Matthew Malensek — ch. 1, 'Why parallel computing'
In the books: C++ Concurrency in Action, Anthony Williams — ch. 10, 'Parallel algorithms'
In the books: Pro TBB, Michael Voss, Rafael Asenjo, James Reinders — ch. 2, 'Generic Parallel Algorithms'
In the books: Concurrency with Modern C++, Rainer Grimm — ch. 1, 'Concurrency with Modern C++' → 'C++17: Parallel Algorithms of the Standard Template Library'
In the books: Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein — ch. 26, 'Parallel Algorithms'
In the books: The Art of Multiprocessor Programming, Maurice Herlihy, Nir Shavit — ch. 12, 'Counting, Sorting, and Distributed Coordination' → 'Sorting Networks'
In the books: Parallel Programming with Python, Jan Palach — ch. 2, 'Designing Parallel Algorithms'
Reference: Wikipedia: Parallel algorithm ↗