Section#14: Homework 6
(CS838: Topics in parallel computing, CS1221, Thu, Mar 18, 1999, 8:00-9:15 a.m.)

1. Prove that the upper bound on link congestion during the direct-exchange AAS in WH 1-port full-duplex M(z₁,z₂) in Subsection 14.4.2 is

   max(z1,z2)/2.
   

   Note that the mesh uses XY-routing.
2. Derive expression for the communication latency of an optimal combining all-to-all broadcast on a store-and-forward 1-port full-duplex T(z₁,z₂), where z₁,z₂ are odd numbers.
   • In one round, one node can exchange one message with only one neighbor.
   • Initially, every node holds one packet of size \mu.
   • The communication latency of exchanging a packet of size M between two neighbors is

     t(M)=ts+M tm.
     

   • Make sure that the algorithm is NOHO and NODUP. This gives you the exact message sizes in every step and therefore exact latency.
   • Solve the problem first for 1-D torus (algorithm 2 in Subsection 13.1.3) and then generalize the solution to 2-D torus as suggested by Figure 13.6.
   • If z₁\not=z₂, does the latency depend on whether the nodes perform first the horizontal AAB and then the vertical one or vice versa?
   • How these results change if z₁ and z₂ are any integers, not only odd?
   • If possible, try to generalize these results to arbitrary T(z₁,...,z_n).