0% found this document useful (0 votes)
132 viewsUntitled
Uploaded by
RahtCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
132 viewsUntitled
Uploaded by
RahtCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
/ 25
in
o®
Exercises
‘Adonced Computer Wrchiecue
Problem 2.1 Define the following terms related
to paralelsm and dependence relations:
(2), Computational granularity.
(©) Communication latency.
(0) Flow dependence.
(@) Anticependence.
(€) Output dependence.
(®) UO dependence.
(g) Contol dependence.
(h)_ Resource dependence.
() Bernstein conditions.
(i) Degree of parallelism.
Problem 2.2 Define the following terms for
various system interconnect architectures:
(a) Node degree.
(b) Neowork diameter,
(©) Bisection bandwidth
(@) Satic connection networks.
(©) Dynamic connection networks.
(9 Nonblockig neeworks.
(6) Multicast and broadcast
(h) Mesh versus torus.
() Symmetry in networks.
(i Mukisage neoworks.
(9 Crossbar networks.
() Digital buses.
Problem 2.3 Answer the following questions on
program flow mechanisms and computer models:
(a) Compare control-flow, dataflow, and
reduction computers in terms ofthe program
flow mechanism used.
(©) Comment onthe advantages and
disadvantages in contral complexity, potential
for parallelism, and cost-ffectiveness of the
above computer modes
(©) What are the differences between scring
reduction and graph reduction machines!
Problem 2.4. Performa data dependence analysis,
‘on each of the following Fortran program fragments,
Show the dapendence grapheamong the smtemente
with justification
@ St A=B+D
82 C#Ax3
Sh AZA+C
Sz E=AI2
© st X=sIN)
sa: Z=xX+W
sh Y=-25xw
St: X= COS@)
(© Determine the data dependences in
he same and adpcent iterations of the
following Do-loop.
Do 101=1,N
SI: A( +1) = 80-1) +C()
s2: B() =A() xK
83 Bq)-1
Problem 2.5 Aralyze the dita dependences
among the following scatements in a given program:
Sl: LoadR1,1024 RI = 1024/
52: Load R2,M(10) /R2 — Memory(10)!
$3: Add RI, R2 IRI — (RI) + (R2/
S4: Store M(1024),RI_ /Memory( 1024) — (RI)!
$5: Store M((R2)), 1024 Memory(€4) (RAY.
& Add R6,R3,R5 IR6-— (RB) + (RY.
Tr Store X,R6 —_IMem(X) of _one-pass
permutations compared with the total
rumter of permutations achievable in one or
more passes through the necwork?
Problem 2.15 Topologically equivalent networks
are these whose graph representations are iso-
morphic with the same interconnection capabili-
tice. Prove the topological equivalence among the
‘Omega, Flip,and Baseline networks.
fa) Prove that the Omega network (Fig, 224)
4s copologicaly equivalent co the Basdine
rretwork (Fig.2.25b),
(b) The Flip network (Fig. 2.27) is constructed
Using inverse perfect shuffle (Fig. 2.140) for
intersage connections. Prove that the Flip
network is topolegicaly equivalent to the
Baseline network.
(©) Based on the results obtained in (a} and (b),
prove the topological equivalence between
the Fip retwork and the Omega network,
Fig. 2.27 A16% 16 Fp revwork (Courtesy of
Ken Batcher; reprinted from Proc. lat
Gof. Poale Processing, 1976)
Problem 2.16 Answer the following questions
for the kary n-cube network
(@) How many nodes does the network contain?
(©) Whats the network ciameter?
(©) What is the bisection bandwidth?
(@) Whavis the node degree?
(©) Exphin the graph-theoreticrebtionship
among Kary n-cube neoworks and rings,
meshes, tori, binary n-cubes, and Omega
networks
(©) Bephin the atference between a conventional
torus and a folded torus.
(@) Under the assumption of constant wire
bisection, why do low-dimensional networks
(con) have lower lseency and higher hotspot
throughput than high-dimensional networks
(hypercubes)?
Problem 2.17 Read the paper on fat trees by
Leiserson, which appeared in IEEE Trans. Computers,pp. 892-901, Oct. 1985. Answer the following
‘questions related to the organtzation ard application
of fat trees:
fa) Explain the advantages of using binary fat
trees over conventional binary trees 3 a
multiprocessor interconnection network.
(©) A univers fot tre is defined a a fat tree of
nodes with root capacity w, where n®?
