Homework #3
Due Tuesday 5/1/2003 in class.
Electric turnin required.
[worth 20 points  + 10% bonus if handed in by 9pm on Weds 4/30/03]

1. Problem 2.14 from the text [page 79]. Note that the Hamming distance H(A,B) is the number of non-zero bits in the representation of A xor B.
    
2. All-to-all broadcast.
   In an all-to-all broadcast operation (see text pp 157-165), each process broadcasts its data to all others. Thus, if each process starts with one chunk of data, it will end with p chunks of data, where p-1 of the chunks come from the other  processors. The text discusses a ring algorithm for all-to-all. broadcasts on page 158-160. Another approach is to have the processes perform concurrent one-to-all broadcasts. Analyze the performance of this second approach using the ring algorithm for the one-to-all broadcasts. Compare the resultant performance model against that of the all-to-all ring algorithm given on page 164 of the text. Note any performance advantages or disadvantages.
    
3. Problem 4.8 from the text [page 191].
    
4. Problem 4.16 from the text [page192] k-to-all broadcast.
   In a one-to-all broadcast, a single  root process transmits a chunk of data to all the other processes. For k a power of 2, a k-to-all broadcast transmits of different m-word messages from k > p sources. Give an algorithm for k-to-all broadcast that has a total communication time of alog p +  bm (k log (p/k) + k -1 ) on a d-cube where p = 2^d. Assume that the messages cannot be split.
    
5. Problem 5.1 from  the text [page 228].
    
6. Problem 5.7 from the text [page 230].
    
7. Problem 9.26 from the text, parts (a) and (c) [page 425]
    

Turnin instructions.

If trasnmitting a web document send a tar file that untars into a directory given by your login ID. Be sure and include a main file "index.html" from which your submission may be accesssed. You may include word or pdf files, and plot files as necessary, but be sure they are all included to avoid a lateness penalty.