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[1]);

  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!)
// Cascade binary algorithm
// 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[1]);

    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

Advertisements

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

  1. Pingback: How to install MPI in Ubuntu « JetCracker

  2. 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

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

  4. Pingback: [MPI] Solving the advection equation in parallel « JetCracker

  5. Pingback: [MPI] Calculating integral in parallel « JetCracker

  6. Pingback: Spring 2012: Overall stats « JetCracker

  7. Pingback: ทดลองง่ายๆ OpenMPI คลัสเตอร์ บน Raspberry Pi | Unofficial of Raspberry Pi Fan in Thailand

  8. 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. 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: