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 Qn. 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(z1,z2,...,zn) if the source's address is (a1,...,an).
    Hint: Start with n=2 or n=3 and generalize to any n.
In both cases assume that
  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 tm\approx td<< ts.