Lab08: Global Reduce and Interval Slicing
Objective
To run an MPI program. Topics include series that converge slowly, MPI_Reduce on data local to each process.
Background
It turns out that arctan(x) = x - x^3/3 + x^5/5 - x^7/7 + . . . Substituting 1 for x we arrive at arctan(1) = 1 - 1/3 + 1/5 - 1/7 + . . . But arctan(1) is just pi/4, so pi is equal to four times the infinite sum 1 - 1/3 + 1/5 - 1/7 + . . . This sum converges very slowly, so we will have to calculate it for millions of terms if we want to get an accurate approximation for pi.
Download the file gregory.c that contains an unacceptable, non-parallel solution to this problem. Note that this program requires a command-line argument specifying the maximum denominator for a term in the series. To run this program using one hundred thousand as the max denominator type mpirun N gregory 100000 when you run the program. Note also that even numbers are not used as denominators, so that you effectively get 50000 terms in the series for this example.
Assignment
Edit the file gregory.c such that each process computes the sum of every kth term, where k is the number of nodes in the topology. Have each node compute a nodetotal value for the sum of its terms, then use the MPI reduce function to add all the node totals into a single world total using a single command.
Sample Output (original program)
Pi = 3.14157265358977788594074809225276 for 100000 iterations.
Pi = 3.14157265358977788594074809225276 for 100000 iterations.
Pi = 3.14157265358977788594074809225276 for 100000 iterations.
Pi = 3.14157265358977788594074809225276 for 100000 iterations.
Pi = 3.14157265358977788594074809225276 for 100000 iterations.
Pi = 3.14157265358977788594074809225276 for 100000 iterations.
Pi = 3.14157265358977788594074809225276 for 100000 iterations.
Pi = 3.14157265358977788594074809225276 for 100000 iterations.
Pi = 3.14157265358977788594074809225276 for 100000 iterations.
Pi = 3.14157265358977788594074809225276 for 100000 iterations.
Pi = 3.14157265358977788594074809225276 for 100000 iterations.
Pi = 3.14157265358977788594074809225276 for 100000 iterations.
Pi = 3.14157265358977788594074809225276 for 100000 iterations.
Pi = 3.14157265358977788594074809225276 for 100000 iterations.
Sample Output (your solution)
Node: 0, interval = 0.9543851637803872
Node: 8, interval = 0.9543851637803872
Node: 4, interval = 0.9543851637803872
Node: 6, interval = 0.9543851637803872
Node: 2, interval = 0.9543851637803872
Node: 10, interval = 0.9543851637803872
Node: 12, interval = 0.9543851637803872
Node: 13, interval = 0.9543851637803872
Node: 1, interval = 0.9543851637803872
Node: 7, interval = 0.9543851637803872
Node: 3, interval = 0.9543851637803872
Node: 11, interval = 0.9543851637803872
Node: 5, interval = 0.9543851637803872
Node: 9, interval = 0.9543851637803872
Pi = 3.14157265358979786995519134507049 for 100000 intervals.