Introduction to Algorithms, Third Edition

concurrency platforms
, which provide a layer of software
that coordinates, schedules, and manages the parallel-computing resources. Some
concurrency platforms are built as runtime libraries, but others provide full-fledged
parallel languages with compiler and runtime support.
Dynamic multithreaded programming
One important class of concurrency platform is
dynamic multithreading
, which is
the model we shall adopt in this chapter. Dynamic multithreading allows program-
mers to specify parallelism in applications without worrying about communication
protocols, load balancing, and other vagaries of static-thread programming. The
concurrency platform contains a scheduler, which load-balances the computation
automatically, thereby greatly simplifying the programmer’s chore. Although the
functionality of dynamic-multithreading environments is still evolving, almost all
support two features: nested parallelism and parallel loops. Nested parallelism
allows a subroutine to be “spawned,” allowing the caller to proceed while the
spawned subroutine is computing its result. A parallel loop is like an ordinary
for
loop, except that the iterations of the loop can execute concurrently.
These two features form the basis of the model for dynamic multithreading that
we shall study in this chapter. A key aspect of this model is that the programmer
needs to specify only the logical parallelism within a computation, and the threads
within the underlying concurrency platform schedule and load-balance the compu-
tation among themselves. We shall investigate multithreaded algorithms written for

---

774
Chapter 27
Multithreaded Algorithms
this model, as well how the underlying concurrency platform can schedule compu-
tations efficiently.
Our model for dynamic multithreading offers several important advantages:
It is a simple extension of our serial programming model. We can describe a
multithreaded algorithm by adding to our pseudocode just three “concurrency”
keywords: