Drawing heavily from Blelloch’s work on the vector model and scan operations, we work our way up to performing a parallel version of the quicksort algorithm on a shared-memory machine with p processors. We first see how to perform reduction and scan operations in parallel. We then examine parallel meld and permute operations, which lead to unsegmented partitioning in parallel. We then introduce segmented operations and modify our partitioning procedure to work with segmented operations, leading to a fully parallel version of quicksort.
Python code appears for most, but not all, of the operations in this chapter. We omit ...
Get Topics in Parallel and Distributed Computing now with O’Reilly online learning.
O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.