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

1. Derive expression for the communication latency of an optimal noncombining one-to-all scatter on a wormhole all-port hypercube Q_n. Ignore the time overhead of packet combining and disassembling.
2. Derive expression for the communication latency of an optimal combining one-to-all scatter on a wormhole all-port mesh M(z₁,z₂,...,z_n) if the source's address is (a₁,...,a_n).
   Hint: Start with n=2 or n=3 and generalize to any n.

1. the source has a packet of size M for every other processor
2. the basic point-to-point latency of a packet of size m over distance d is

   t(m,d)=ts+dtd+mtm
   

   where t_m\approx t_d<< t_s.