Homework 3
Assigned 26 Apr 2006
Due 8 May 2006
25 points


M1, 4 pts.  Suppose you want to do a 2-D FFT of an n by n image
(The 2D FFT is simply a 1D FFT of each row and column.)  How fast
can you do this with (a.) n processors, (b.) n*log(n) processors,
and (c.) n^2 processors, assuming no cost for messages?


M2, 5 pts.  Consider the fully distributed implementation of
Moore's Algorithm, from section 7.4.3 of your text.

(a.) Is the algorithm correct?  Either give an example of a graph
for which it fails, or show it is correct by either showing it is
equivalent to some better-known single-source algorithm, or give 
a proof, e.g., by induction on updated distances, of correctness.

(b.) Give upper and lower bounds on the parallel runtime, assuming
N vertices, that all vertices are reachable from the start vertex,
and with one processor per vertex.


M3, 4 pts.  Consider the method of termination detection with
acknowledgment messages, as discussed in section 7.3.2 of your
text.  Suppose we have N processes, and they have all finished
their work.  What would be the fewest possible number of steps
needed to detect global termination?  What would the most be?


M4, 4 pts.  Consider the comparison of block and strip methods for
partitioning a grid, as discussed on p 187 of your text.  Suppose
we have a particular t_startup, t_data, and n.  For what values of
p is block partition better than strip partition?


M5, 4 pts.  Consider the problem of doing a reduction on a
square grid with N processors.  We saw an example of that took 
2 * (sqrt(N) - 1) steps.  Can this be improved?


M6, 4 pts. In the MarPar SIMD language, the IF and ELSE parts
of a plural IF statement (an IF statement where the boolean is
a variable on the processor array) are computed in two stages:
the IF part is first executed simultaneously on the processors
for which the boolean is true, and then the ELSE part where the
boolean is false.  Since the active sets are disjoint it might
seem that the IF and ELSE parts could be executed concurrently.
Give two reasons why this was not done.