CS342: Active Exercise#3 Broadcast and Summation in the logP Model (You will have one hour on Wednesday 9/25/96 to work on this exercise, and one hour on Monday 9/30/96. Your group's report is due Friday, 10/4/96, 5PM). In class we have discussed the problem of summing N numbers on an EREW PRAM, and noted that it could be solved in O(NlogN) time on N processors by simulating a completely balanced binary tree. A related problem is that broadcasting a data item from one processor to N others; it is easy to see that on an EREW PRAM this can be accomplished by the simulation of a complete binary tree as well. In class we have also introduced the logP model. In this exercise you are to revisit the two problems of broadcasting and summing in the logP model. Devise an algorithm for broadcasting a datum from one processor to N others in the logP model. Work out at least one example carefully with small values of L,o,g,p. Can you say anything analytically about the running time of the algorithm? Do the same for the problem of summation. (To be done once you have learned MPI, which we will begin in the next class.) Implement your algorithm using MPI in our laboratory. Gather data on its performance on 3,6,9,12 processors. Compare this performance to the broadcast primitive provided by MPI. What conclusions can you draw? What are L,o,g,p for our laboratory?