The Butterfly network is an interconnection network composed of log p levels (as the omega
network). In a Butterfly network, each switching node i at a level l is connected to the identically
numbered element at level l + 1 and to a switching node whose number differs from itself only at
the lth most significant bit. Therefore, switching node Si is connected to element Sj at level l
if j = i or j = i ? 2
logp – l
A. Consider a Butterfly network with eight processing nodes connected to eight memory banks:
i. (10 points) How many stages are needed?
ii. (25 points) Sketch the network showing input, output, as well as switching nodes.
iii. (15 points) What is the diameter and bisection width of this network? Explain your
iv. (10 points) knowing that messages in butterfly network are self-routed. In other words,
each stage uses one destination bit for routing purposes where “0” means route up and
“1” means route down. Show the routing of a message from node 0 to node 4.
B. (15 points) Device a formula for computing cost of a butterfly network with p nodes.
C. (25 points) Show the equivalence of a Butterfly network and an Omega network.
Hint: Rearrange the switches of an omega network so that it looks like a Butterfly