Information Technology Reference
In-Depth Information
a
b
c
d
e
a
b
c
a
a
c
b
a
b
a
b
c
a
b
c
d
e
a
c
a
b
c
e
b
a
b
d
a
b
c
d
(b)
(a)
Figure 7.23
Components of an efficient prefix circuit.
7.32 Sho
w
that
e
ach computation
c
ycle of a
p
-processor EREW PRAM can be simulated on
a
√
p
×
√
p
mesh in
O
(
D
√
p
)
steps, where
D
is the maximum number of processors
accessing memory locations stored at a given vertex of the mesh.
7.33 Show that each computation cycle of a
p
-processor EREW PRAM can be simulated
on a
p
-processor linear array in
O
(
Dp
)
steps, where
D
is the maximum number of
processors accessing memory locations stored at a given vertex of the array.
THE BSP AND LOGP MODELS
7.34 Design an algorithm for the
p
-processor BSP and/or LogP models to multiply two
n
n
matrices when each matrix entry occurs once and entries are uniformly distributed over
the
p
processors. Given the parameters of the models, determine for which values of
n
your algorithm is efficient.
Hint:
The performance of your algorithm will be dependent on the initial placement
of data.
7.35 Design an algorithm for the
p
-processor BSP and/or LogP models for the segmented
prefix function. Given the parameters of the models, determine for which values of
n
your algorithm is efficient.
×
Chapter Notes
A discussion of parallel algorithms and architectures up to about 1980 can be found in the topic
by Hockney and Jesshope [
135
]. A number of recent textbooks provide extensive coverage of
Search WWH ::
Custom Search