1) Consider the parallel algorithm of prefix sum on a d-dimensional hypercube and analyze its communication cost.
2) Analyze its theoretical performance in terms of serial runtime, parallel runtime, speedup, efficiency and scalability, assuming that the communication cost can be ignored.
3) Write C / MPI program to implement the parallel algorithm (on hypercube) to calculate the prefix sum of n numbers 0, 1, 2, …, n-1 and measure its performance.
4) Directly call MPI_Scan function to calculate the prefix sum of the array of n numbers 0, 1, 2, …, n-1 and measure its performance.
5) Write a report that include (i) prefix sum parallel algorithm (on a hypercube) and its communication cost, (ii) theoretical performance analysis in terms of serial runtime, parallel runtime, speedup, efficiency and scalability, (iii) details of programming and implementation, (iv) description of how to compile and execute your programs, including screenshots with your account info and the performance results, (v) comparison of actual performance between your implementation and MPI_Scan with respect to different n and p, where p is the number of processors you use to run your MPI code, and (vi) discussion and conclusion. You need to present the performance results in a table and draw figures to show the speedup and efficiency corresponding to your implementation, MPI_Scan (default implementation) and theoretical performance in (v).