CODEWITHSUNDEEP
cmpi
name
name

Reputation: 419

How to get processors to split up work?

I'm trying to get all the prime numbers in a range of numbers using MPI. My program works as intended, however I want try to split up the work more evenly. For example, whenever I run it with 2 processors the rank 0 processor gets only one prime number while the other gets all the other ones.

Here is my prime function: 

//returns 1 is a number is prime 0 otherwise
int IsPrime(int id, int number) {
  int i; 
  if (number <=1 ) return 0;
    if (number % 2 == 0 && number > 2) return 0;

  for (i=3; i < number/2  ; i+=2) {
      if (number % i == 0) return 0;
    }
     return 1;  
}

Here is some of my main: 

int main (int argc, char *argv[]) 
{
  int count;            /* Solutions found by this proc */
  double elapsed_time;  /* Time to find, count solutions */
  int global_count;     /* Total number of solutions */
  int i;
  int id;               /* Process rank */
  int p;                /* Number of processes */
  char hostname[1024];

  MPI_Init (&argc, &argv);

  MPI_Comm_rank (MPI_COMM_WORLD, &id);
  MPI_Comm_size (MPI_COMM_WORLD, &p);

  hostname[1023] = '\0';
  gethostname(hostname, 1023);
  printf("MPI rank %d on host %s\n", id, hostname);

  /* Start timer */
  MPI_Barrier (MPI_COMM_WORLD);
  elapsed_time = - MPI_Wtime();

  for(i = id ; i <= prime; i+=p)
  {
    //trying to divide the word done by processors
   if(IsPrime(id,i))
    {
      printf("%d) is prime: %d \n", id, i);
      count++; 
    }
  }

  MPI_Reduce (&count, &global_count, 1, MPI_INT, MPI_SUM, 0,
          MPI_COMM_WORLD);

Any help will be much appreciated! Thanks!

Upvotes: 2

Views: 179

Answers (2)

Zulan
Zulan

Reputation: 22670

Given that the largest imbalance comes from all even numbers except 2 not being prime, you can just skip those in the loop and add 2 manually. Not only does this improve load balance, it also saves you a whole lot of function calls that return false anyway.

If you further need to improve balance, you can split the numbers into chunks of some fixed size and alternate the chunks between workers. It may be an interesting mathematical exercise to find a good chunk size.

I would refrain from resorting to dynamic work assignment, as this is quite difficult to do with MPI, in particular it is hard to implement this in a scalable way.

Upvotes: 1

RoiHatam
RoiHatam

Reputation: 896

This is not an answer to your original question. Your IsPrime function is not optimal. The complexity of your function is O[n]. The following function complexity is O[sqrt(n)]. Using the following function instead of yours will boost your performance before even using threads.

#include <math.h>

bool isPrime(unsigned int num){
    if(num < 2){
            return false;
    }

    unsigned int size = (unsigned int)sqrt(num);
    for(unsigned int i=2 ; i <= size ; i++){
            if(num % i == 0){
                    return false;
            }
    }

    return true;
}

Upvotes: 2

Related Questions