CSE 160 Homework 2

Due 5/5 at the beginning of Section.

Show your work for all problems.

1. Go to http://www.mpi-forum.org/index.html. Provide a one paragraph description for each of 3 completely new types of functionality provided in MPI-2 that are not available in MPI-1.1.

2. What is MPICH? What is the difference between MPI and MPICH?

3. Define machine granularity to be

(max) number (MFLOP) of computations which can be executed

in 1 second

---------------------------------------------------------------------------------------------------------------

(max) size message (MB) which can be transferred in 1 second

a. What is the machine granularity of SDSC’s Blue Horizon?

b. What is the machine granularity of University of Michigan’s IBM SP? (an NPACI partner resource)

4. Consider the workqueue paradigm discussed in class. Assume that the work is divided into uniform blocks, all of which take the same time to execute for any input. Let blocksize be the number of MB required to send a block to a processor. Let blocktime be the number of MFLOPS required to execute a single block.

We say that a particular blocksize can be amortized if the time it takes to execute a block is at least the time it takes to send the data for the block. This means that if we concurrently perform computation and communication, the communication time is absorbed into the computation time.

Consider the following scenarios and answer the following questions by doing a “back-of-the-envelope” calculation. Show your work:

How many blocks are required to amortize all communication (i.e. so that the amount of computation performed is = to the amount of communication performed) under the following scenarios:

a. Processors are on the Blue Horizon.

A Processor requests a block

The Block is transferred to processor

The Processor executes for 200 MFLOPS

Output is transferred to Output node while processor requests the next block

What is the maximal blocksize which amortizes the computation time?

b. Processors are on the University of Michigan SP-2

The blocksize is 100 MB

A Processor requests a block

A Block is transferred to processor

Processor executes for blocktime MFLOPS

Output is retained at processor

What is the minimal blocktime which will amortize the communication time?

c. Give a function for blocktime which involves block-size and machine granularity G, i.e.

blocktime= f(blocksize, G)

5. Consider the Jacobi2D algorithm given in class for an NXN array of data points. Consider the following performance parameters:

t_comm. = communication time to update one data item

t_comp = computation time for one data item

t_block(n,m) = computation time for one block of

dimensions (n,m)

a. Give an expression for t_block(n,m) for one iteration of Jacobi (with no computation of maxdiff) where n is the number of rows and m is the number of columns of a contiguous block in the data array. (Assume that ghost regions have been defined so that all blocks do the same amount of communication and computation).

b. A square block has n=m and a strip has n=N. Assuming the target MPP has machine granularity G, and that all update data can be transferred in a single message, give expressions of the execution time for the square block time t_block(n,n) for one iteration of Jacobi with no calculation of maxdiff. Give an expression for the strip time t_block(N,m) for one iteration of Jacobi with no calculation of maxdiff.

c. Which decomposition is likely to be more performance-efficient on the Blue Horizon: p blocks or p strips? Which decomposition is likely to be more efficient on the uAPE lab cluster: p blocks or p strips? Justify your answer.