CS  441:  MODERN COMPUTER ARCHITECTURE
                  --------------------------------------

                            Assignment #4
                            -------------
                          Due date: 04/09/99



     1. (a) Draw a 16 X 16 Omega network.

        (b) Consider a bit reversal permutation, br, defined as:
              br(i) = i_0 i_1 . . . i_n-1,   0<=i<=N-1 
              where the binary representation of i is i_n-1 . . . . i_1 i_0
              and N = 2^n.
            Can this permutation be supported on the 16 X 16 Omega
            without blocking? If not, identify the most heavily used
            links and determine how many packets they see.

        (c) Repeat part (b) for an N X N Omega network.



     2. (a) Consider an n X n mesh with wrap-arounds (toroid). Assume 
            that each link is bi-directional and full duplex. Also,
            a packet transfer across a link takes 1 cycle (including
            switching delay within a node). 
            Our goal is to present a schedule and routing algorithm 
            to implement all-to-all communication in the shortest
            possible time. (This communication pattern is encountered
            in, for example, the parallel implementation of FFT and
            in partitioned sampled sort discussed in class.)
            What is the total time for all-to-all communication?
            (The trick is to keep both directions of each link busy
             during every cycle.) 

         (b) What is the optimal time for all-to-all communication
             in an  n X n X n  mesh with wrap-arounds?

         (c) Extra credit part: What would your answer to (a) be for
             an mXn mesh with wrap-arounds for m!=n ?            



     3. Problem 7.6, p. 631 of text.