Introduction to Algorithms, Third Edition

Chapter notes
Parallel computers, models for parallel computers, and algorithmic models for par-
allel programming have been around in various forms for years. Prior editions of
this book included material on sorting networks and the PRAM (Parallel Random-
Access Machine) model. The data-parallel model [48, 168] is another popular al-
gorithmic programming model, which features operations on vectors and matrices
as primitives.

---

812
Chapter 27
Multithreaded Algorithms
Graham [149] and Brent [55] showed that there exist schedulers achieving the
bound of Theorem 27.1. Eager, Zahorjan, and Lazowska [98] showed that any
greedy scheduler achieves this bound and proposed the methodology of using work
and span (although not by those names) to analyze parallel algorithms. Blelloch
[47] developed an algorithmic programming model based on work and span (which
he called the “depth” of the computation) for data-parallel programming. Blumofe
and Leiserson [52] gave a distributed scheduling algorithm for dynamic multi-
threading based on randomized “work-stealing” and showed that it achieves the
bound E
ŒT
P
T
1
=P
C
O.T
1
/
. Arora, Blumofe, and Plaxton [19] and Blelloch,
Gibbons, and Matias [49] also provided provably good algorithms for scheduling
dynamic multithreaded computations.
The multithreaded pseudocode and programming model were heavily influenced
by the Cilk [51, 118] project at MIT and the Cilk++ [71] extensions to C++ dis-
tributed by Cilk Arts, Inc. Many of the multithreaded algorithms in this chapter
appeared in unpublished lecture notes by C. E. Leiserson and H. Prokop and have
been implemented in Cilk or Cilk++. The multithreaded merge-sorting algorithm
was inspired by an algorithm of Akl [12].
The notion of sequential consistency is due to Lamport [223].

---