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)
InstructionsHomework Assignment 3 (due Thurs Sept. 18)
InstructionsHomework Assignment 4 (due Thurs Sept. 25)
InstructionsHomework Assignment 5 (due Sat Oct. 4)
InstructionsReading
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.