CSE 160, Spring 2004                                     University of California, San Diego

 

Homework #4

Due Friday 5/7/04 in section
Late assignments will not be accepted

[10 points]




  1. K-ary d-cubes.
    The k-ary d-cube is an interconnection network with kd nodes. As discussed in class,  there are k nodes along all d axes and there are  end-around connections.

    1. Derive the diameter and  the bisection bandwidth of a k-ary d-cube.
    2. A ring is a special case of  1-cube. Give a formula that maps a ring with kd nodes onto a  k-ary d-cube with kd nodes.  There are many possible mappings, but choose just one.

  2. Parallel prefix.

The prefix sum  (also called a sum-scan) of a sequence of numbers xk is in turn a sequence of running sums Sk defined as follows

–        S0 = 0

–          Sk = Sk-1 + xk

 

Thus, scan (3,1,4,0,2) = (3,4,8,8,10)

 

a.       Design an algorithm for prefix sum based on the ring interconnect.

b.      Derive an accompanying performance model

 

 

3.      Time constrained scaling.

 

a.       Devise an efficient parallel algorithm for adding up a list of N numbers on P processors. Assume that there P divides N evenly and that N >> P
(i.e. N > 10*P or more)

b.       Now, determine the largest problem that can be solved in time T = 10000 time units on 500 processors, where the message startup costs alpha= 200 time units, and addition costs 1 time unit.






 

4.      Performance modeling.
In class we derived a performance model for a 5-point 2D Jacobi solver which is used to solve Poisson’s equation.

a.       In some applications, a more accurate way to solve the equation is to use the so-called 9-point stencil. One such stencil is shown in Fig 10.24 of the text .  (See “Higher order Difference Methods,: pp 323-324).  Derive a performance model for this stencil, expressing the parallel running time TP as a function of P and N.  Assume that the problem size square, that is, the solution mesh is
N ´ N.  Break out the computation and communication costs and compare against that of the 5-point stencil.  Which stencil incurs a higher communication cost?

b.      There is a different 9-point stencil that uses all 8 nearest neighbors as shown below.  A straightforward approach to updating ghost cells requires communication from the 8 nearest neighbor processors. However, there is a  different communication algorithm that involves only 4 neighbors along the Manhattan directions. Derive this algorithm and compare the communication cost with that of the direct method of communicating with all 8 neighbors.  Determine which method incurs a higher communication overhead, expressed as a  fraction of TP, Express your answer in terms of the parameters alpha, beta, N, and P.