Estimating Pi by Calculating Area Under the Curve

Problem Write-up

Sequential Code

file: cross_platform_examples/piIntegration/seq_pi_done/seq_pi_done.c

Build inside seq_pi_done directory:

make seq_pi_done

Execute on the command line inside seq_pi_done directory:

./seq_pi_done <number of bins>

To do:

Run and compile the code experimenting with the number of bins. Compare the source code to the output. What do you notice about the accuracy of our estimation of pi as the number of bins increase?

Record execution times using 125 million, 250 million, 500 million, 1 billion, and 2 billion for the number of bins.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/****************************************************************************
* Program: Sequential Pi Calculation
* This PI program was taken from Argonne National Laboratory.
* Sequential version made by Hannah Sonsalla, Macalester College
****************************************************************************/

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void getInput(int argc, char* argv[], int* n);

void getInput(int argc, char* argv[], int* n){
	if(argc != 2){
		fprintf(stderr, "usage: %s <number of bins> \n", argv[0]);
        fflush(stderr);
        *n = -1;
	} else {
		*n = atoi(argv[1]);
	}

    if (*n <= 0) {
        exit(-1);
    }
}

int main(int argc, char *argv[]) {

   int  i,
        n;                                              /* the number of bins */

    double PI25DT = 3.141592653589793238462643;         /* 25-digit-PI*/
  
    double pi,                                          /* value of PI in total*/
           step,                                        /* the step */
           sum,                                         /* sum of area under the curve */
           x;

    clock_t start_time,          /* starting time */
           end_time;            /* ending time */

    getInput(argc, argv, &n);
    printf("number of bins is %d\n", n);
    start_time = clock();

    step = 1.0 / (double) n;
    sum = 0.0;
    for (i = 1; i <= n; i += 1) {
        x = step * ((double)i - 0.5);
        sum += (4.0/(1.0 + x*x));
    }

    pi = step * sum;

    printf("Pi is approximately %.16f, Error is %.16f\n", pi, fabs(pi - PI25DT));
    end_time = clock();
    printf("Time of calculating PI is: %f seconds \n", (double)(end_time-start_time)/CLOCKS_PER_SEC);
   
    return 0;
}

OpenMP Code

file: cross_platform_examples/piIntegration/omp_pi_done/omp_pi_done.c

Build inside omp_pi_done directory:

make omp_pi_done

Execute on the command line inside omp_pi_done directory:

./omp_pi_done <number of threads> <number of bins>

To do:

Find the speedup and efficiency of this program. To do so, you will need your execution times above from the sequential version of calculating pi using the Monte Carlo method.

Use 2, 4, 8, 12, 14, and 16 for the number of processes and 125 million, 250 million, 500 million, 1 billion, and 2 billion for the number of bins.

Make a copy of the template provided at this link and record the execution times from each combination in the execution time table. The speedup and efficiency of each combination will automatically be calculated and corresponding speedup and efficiency graphs will be made.

MPI Code

file: cross_platform_examples/piIntegration/mpi_pi_done/mpi_pi_done.c

Build inside mpi_pi_done directory:

make mpi_pi_done

Execute on the command line inside mpi_pi_done directory:

mpirun -np <N> ./mpi_pi_done <number of bins>

Note

This command is going to run all processes on the machine on which you type it. You will need a separate machines file for running the code on a cluster of machines. This note applies for all examples utilizing MPI.

To do:

Find the speedup and efficiency of this program the same way you did previously for the OpenMP version. To do so, you will need your execution times from the sequential version of calculating pi using the Monte Carlo method above.

Use 2, 4, 8, 12, 14, and 16 for the number of processes and 125 million, 250 million, 500 million, 1 billion, and 2 billion for the number of bins.

Make a copy of the template provided here and record the execution times from each combination in the execution time table. The speedup and efficiency of each combination will automatically be calculated and corresponding speedup and efficiency graphs will be made.

Compare the speedup and efficiency of this program to the speedup and efficiency of the OpenMP program. What do you observe?

MPI+OpenMP Hybrid Code

file: cross_platform_examples/piIntegration/hybrid_pi_done/hybrid_pi_done.c

Build inside hybrid_pi_done directory:

make hybrid_pi_done

Execute on the command line inside hybrid_pi_done directory:

mpirun -np <N> ./hybrid_pi_done <number of threads> <number of bins>

To do:

Try the hybrid program with different number of processes and different number of threads. What combinations of processes and threads seem to run faster? Why might this be the case?

Run the program using 4 processes, 4 threads and 500,000,000 bins. Compare the execution time to the time it took to run the MPI program using 4 processes and 125,000,000 bins. How do the times compare?

Run the program using 4 processes, 4 threads and 2,000,000,000 bins. Compare the execution time to the time it took to run the MPI program using 4 processes and 500,000,000 bins. Can you explain this behavior?