## 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(z*_{1},z_{2}) in Subsection 14.4.2 is
max(z_{1},z_{2})/2.

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(z*_{1},z_{2}), where *z*_{1},z_{2} 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)=t_{s}+M t_{m}.

- 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*_{1}\not=z_{2}, 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*_{1} and *z*_{2} are any integers, not only odd?
- If possible, try to generalize these results to arbitrary
*T(z*_{1},...,z_{n}).