Introduction to Algorithms, Third Edition

parallel for
construct, all the iterations
should be independent. Between a
spawn
and the corresponding
sync
, the code
of the spawned child should be independent of the code of the parent, including
code executed by additional spawned or called children. Note that arguments to a
spawned child are evaluated in the parent before the actual spawn occurs, and thus
the evaluation of arguments to a spawned subroutine is in series with any accesses
to those arguments after the spawn.

---

790
Chapter 27
Multithreaded Algorithms
As an example of how easy it is to generate code with races, here is a faulty
implementation of multithreaded matrix-vector multiplication that achieves a span
of
‚.
lg
n/
by parallelizing the inner
for
loop:
M
AT
-V
EC
-W
RONG
.A; x/
1
n
D
A:
rows
2
let
y
be a new vector of length
n
3
parallel for
i
D
1
to
n
4
y
i
D
0
5
parallel for
i
D
1
to
n
6
parallel for
j
D
1
to
n
7
y
i
D
y
i
C
a
ij
x
j
8
return
y
This procedure is, unfortunately, incorrect due to races on updating
y
i
in line 7,
which executes concurrently for all
n
values of
j
. Exercise 27.1-6 asks you to give
a correct implementation with
‚.
lg
n/
span.
A multithreaded algorithm with races can sometimes be correct. As an exam-
ple, two parallel threads might store the same value into a shared variable, and it
wouldn’t matter which stored the value first. Generally, however, we shall consider
code with races to be illegal.