# JetCracker

Life-time learner's blog

## MPI: Calculating sum 1/n! in parallel

Hello.
I’ve spend several hours to understand how to programme in MPI and how to calculate the sum of 1/n! in parallel (it’s my task from university). (By the way, why do I have study this shit? I don’t think I will be working in the field of parallel/distributed computing.)

But finally I wrote a decent programme, which showed not bad results. And I am very excited to share with you!

```// Task 1. Sum(1/n!)
// Author: Anton Danshin
#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv) {
double result;
int n = 0;
if(argc>1)
n = atoi(argv);

double startwtime = 0.0;
double endwtime;

// Initialize the MPI environment
MPI_Init(&argc, &argv);
// Find out rank, size
int world_rank;
MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
int world_size;
MPI_Comm_size(MPI_COMM_WORLD, &world_size);

if(world_rank==0)
startwtime = MPI_Wtime();

MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

double a = 0.0;
double f = 1.0;
double s = 0.0;

int i;
int t = n/world_size;
if(n%world_size) t++;
for(i = (n/world_size)*world_rank; i<world_rank*(n/world_size)+t; i++) {
if(i+1>n)
break;
f /= (double)(i+1);
s += f;
}

// Receive A and F from previous node
double a_p, f_p = 1.0;
if(world_rank > 0) {
MPI_Recv(&f_p, 1, MPI_DOUBLE, world_rank-1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
f *= f_p;
}
s *=f_p;

// Send my A nad F to the next node
if(world_rank < world_size-1) {
MPI_Send(&f, 1, MPI_DOUBLE, world_rank+1, 0, MPI_COMM_WORLD);
}

MPI_Reduce(&s, &result, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

if(world_rank==0) {
endwtime = MPI_Wtime();
printf("Result: %.10f\n", result+1);
printf("Time elapsed: %fms\n", (endwtime-startwtime)*1000);
}

MPI_Finalize();
}
```

I don’t have time to describe the algorithm. I promise that I’ll do that if I have time.

Here is a result of execution:

```rogvold@rogvold:~\$ mpirun -np 1 ./a.out 1000000000
Result: 2.7182818285
Time elapsed: 7946.033955ms
rogvold@rogvold:~\$ mpirun -np 2 ./a.out 1000000000
Result: 2.7182818285
Time elapsed: 4858.652115ms
rogvold@rogvold:~\$ mpirun -np 3 ./a.out 1000000000
Result: 2.7182818285
Time elapsed: 3493.057966ms
```

The programme was executed on my friend’s laptop (Intel Core i7). But he was watching a movie at the time of execution, and the processor was “a little bit busy”. Tomorrow I will test my programme on our 16-core computer at my university.

UPDATE (28 March 2012):

I’ve implemented a cascade binary algorithm (каскадная схема метода сдваивания). Turns out it is not the best solution. The best solution is a solution above (geometry parallelism, геометрический параллелизм + конвейерный метод). ```// Task 1. Sum(1/n!)
// Author: Anton Danshin, MIPT
#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv) {
double result;
int n = 0;
if (argc > 1)
n = atoi(argv);

double startwtime = 0.0;
double endwtime;

// Initialise the MPI environment
MPI_Init(&argc, &argv);
// Find out rank, size
int world_rank;
MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
int world_size;
MPI_Comm_size(MPI_COMM_WORLD, &world_size);

if (world_rank == 0)
startwtime = MPI_Wtime();

MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

double f = 1.0;
double s = 0.0;

int i;
int t = n / world_size;
if (n % world_size) t++;
for (i = (n / world_size) * world_rank; i < world_rank * (n / world_size) + t; i++) {
if (i + 1 > n)
break;
f /= (double) (i + 1);
s += f;
}

double s_p, f_p = 1.0;
unsigned int r = 2;
while (r / 2 < world_size) {
if (world_rank % r == 0) {
if (world_rank + r / 2 < world_size) {
MPI_Recv(&f_p, 1, MPI_DOUBLE, world_rank + r / 2, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
MPI_Recv(&s_p, 1, MPI_DOUBLE, world_rank + r / 2, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
s += f*s_p;
f *= f_p;
}
r <<= 1;
} else {
MPI_Send(&f, 1, MPI_DOUBLE, world_rank - r / 2, 0, MPI_COMM_WORLD);
MPI_Send(&s, 1, MPI_DOUBLE, world_rank - r / 2, 0, MPI_COMM_WORLD);
break;
}
}

if (world_rank == 0) {
endwtime = MPI_Wtime();
printf("Result: %.10f\n", s + 1);
printf("Time elapsed: %.3f ms\n", (endwtime - startwtime)*1000);
}

MPI_Finalize();
}
```

As you may noticed, I did’t use MPI_Reduce command here.

Any suggestions on how to improve the code? 😉

Anton Danshin

### 8 responses to “MPI: Calculating sum 1/n! in parallel”

1. jetcracker March 7, 2012 at 03:58

I’ve tested it on our 16-core computer: the acceleration is almost linear!!!! E(p) ~ 0.98

2. Pingback: SUM(1/N!) problem « Kevin's Weblog

3. Elvan-ı Seb'a February 20, 2015 at 02:50

Thank you for sharing your codes, I suppose we have similar feelings about learning this Anyway your posts have been very useful. 🙂