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