Introduction to Algorithms, Third Edition

parallel for
loop contains
n
iterations
of the inner (serial)
for
loop. The span of the remaining code in the procedure
is constant, and thus the span is dominated by the doubly nested loops, yielding
an overall span of
‚.n/
for the whole procedure. Since the work is
‚.n
2
/
, the
parallelism is
‚.n
2
/=‚.n/
D
‚.n/
. (Exercise 27.1-6 asks you to provide an
implementation with even more parallelism.)
Race conditions
A multithreaded algorithm is
deterministic
if it always does the same thing on the
same input, no matter how the instructions are scheduled on the multicore com-
puter. It is
nondeterministic
if its behavior might vary from run to run. Often, a
multithreaded algorithm that is intended to be deterministic fails to be, because it
contains a “determinacy race.”
Race conditions are the bane of concurrency. Famous race bugs include the
Therac-25 radiation therapy machine, which killed three people and injured sev-

---

788
Chapter 27
Multithreaded Algorithms
eral others, and the North American Blackout of 2003, which left over 50 million
people without power. These pernicious bugs are notoriously hard to find. You can
run tests in the lab for days without a failure only to discover that your software
sporadically crashes in the field.
A
determinacy race
occurs when two logically parallel instructions access the
same memory location and at least one of the instructions performs a write. The
following procedure illustrates a race condition:
R
ACE
-E
XAMPLE
. /
1
x
D
0
2