Introduction to Algorithms, Third Edition

parallel for
j
D
2
to
n
3
parallel for
i
D
1
to
j
1
4
exchange
a
ij
with
a
j i
Analyze the work, span, and parallelism of this algorithm.
27.1-8
Suppose that we replace the
parallel for
loop in line 3 of P-T
RANSPOSE
(see Ex-
ercise 27.1-7) with an ordinary
for
loop. Analyze the work, span, and parallelism
of the resulting algorithm.
27.1-9
For how many processors do the two versions of the chess programs run equally
fast, assuming that
T
P
D
T
1
=P
C
T
1
?
27.2
Multithreaded matrix multiplication
In this section, we examine how to multithread matrix multiplication, a problem
whose serial running time we studied in Section 4.2. We’ll look at multithreaded
algorithms based on the standard triply nested loop, as well as divide-and-conquer
algorithms.
Multithreaded matrix multiplication
The first algorithm we study is the straighforward algorithm based on parallelizing
the loops in the procedure S
QUARE
-M
ATRIX
-M
ULTIPLY
on page 75:

---

27.2
Multithreaded matrix multiplication
793
P-S
QUARE
-M
ATRIX
-M
ULTIPLY
.A; B/
1
n
D
A:
rows
2
let
C
be a new
n
n
matrix
3
parallel for
i
D
1
to
n
4
parallel for
j
D
1
to
n
5
c
ij
D
0
6