Section#14: Homework 6
(CS838: Topics in parallel computing, CS1221, Thu, Mar 18, 1999, 8:00-9:15 a.m.)
Communication latency II
Also today's homework asks you to solve two problems, the first one very easy.
- Prove that the upper bound on link congestion during the direct-exchange
AAS in WH 1-port full-duplex M(z1,z2) in Subsection 14.4.2 is
Note that the mesh uses XY-routing.
- Derive expression for the communication latency of an optimal
combining all-to-all broadcast on a store-and-forward 1-port
full-duplex T(z1,z2), where z1,z2 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
- 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
- If z1\not=z2, 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 z1 and z2 are any integers, not only odd?
- If possible, try to generalize these results to arbitrary T(z1,...,zn).