### Homeworks for Fall 2008

#### Homework Assignment 1 (due Tues Sep 9)

Textbook problem Ch1 #2: Describe how the pair-wise summation computation can be changed to find the maximum element of an array. Describe what computionation must be done at each node in the tree and work through on example (for an array of 8 entries).

Textbook problem Ch1 #3: Reformulate the
pair-wise summation program to solve the Count3s computation in log
*n* time, assuming the number of processors *P* is
*n/2* (like in class today). The Count3s problem is simply to
count the number of threes in an integer array. Like the summation
problem, the result is a scalar.

#### Homework Assignment 2 (due Thurs Sept. 18)

Instructions#### Homework Assignment 3 (due Thurs Sept. 18)

Instructions#### Homework Assignment 4 (due Thurs Sept. 25)

Instructions#### Homework Assignment 5 (due Sat Oct. 4)

Instructions#### Reading

Throughout the MPI section of the course, we will be reading a journal article that compares different sorting algorithms on a supercomputer called the Connection Machine 2 (CM-2). For background on the CM-2, see its entry in Wikipedia. For an interesting article from*Physics Today*about physicist Richard Feynman's involvement check out this link. The Richard Feynman article and the sorting algorithm paper are both required reading, but only the Feynman article is to be read in one sitting.

Note: If the above link is broken, search for the sorting
paper on Google. Its reference is :

G.E. Blelloch, C.E. Leiserson,
B.M. Maggs, C.G. Plaxton, S.J. Smith, M. Zagha, A Comparison of Sorting
Algorithms for the Connection Machine CM-2, Proc. 3rd Annual ACM
Symposium on Parallel Algorithms and Architectures, 1991.