Introduction to Algorithms, Third Edition

shared memory
, where
each processor can directly access any location of memory. Other parallel com-
puters employ
distributed memory
, where each processor’s memory is private, and
an explicit message must be sent between processors in order for one processor to
access the memory of another. With the advent of multicore technology, however,
every new laptop and desktop machine is now a shared-memory parallel computer,

---

Chapter 27
Multithreaded Algorithms
773
and the trend appears to be toward shared-memory multiprocessing. Although time
will tell, that is the approach we shall take in this chapter.
One common means of programming chip multiprocessors and other shared-
memory parallel computers is by using
static threading
, which provides a software
abstraction of “virtual processors,” or
threads
, sharing a common memory. Each
thread maintains an associated program counter and can execute code indepen-
dently of the other threads. The operating system loads a thread onto a processor
for execution and switches it out when another thread needs to run. Although the
operating system allows programmers to create and destroy threads, these opera-
tions are comparatively slow. Thus, for most applications, threads persist for the
duration of a computation, which is why we call them “static.”
Unfortunately, programming a shared-memory parallel computer directly using
static threads is difficult and error-prone. One reason is that dynamically parti-
tioning the work among the threads so that each thread receives approximately
the same load turns out to be a complicated undertaking. For any but the sim-
plest of applications, the programmer must use complex communication protocols
to implement a scheduler to load-balance the work. This state of affairs has led
toward the creation of