MPI programming help!

Hello all,

We are using this method to find all the prime numbers.
Attachment 11111


Our work didn't use the MPI_Isend() or MPI_Irecv() commands. The following is the MPI parallel part code.The highlighted is the explanation.

We use two dimensional vector to represent the array. The first column (p[i][0]) is the value, the second column (p[i][1]) is the status. If the status is 0, then it means that the corresponding value p[i][0] has been checked and deleted. If the status is 1, then that means the number p[i][0] is still in the list waiting for check.

Could you please take some time to give us some working direction?

Thank you for your time.



MPI Code:

Code:

---

    MPI_Comm_rank( MPI_COMM_WORLD, &rank ); 
    MPI_Comm_size( MPI_COMM_WORLD, &size );
    int temp;

    while (minnum <=floor(sqrt(upperlimit)))  // loop for every different "minnum"
    {

        if (rank==0)
        {
        pset.push_back(minnum);      // store the value of "minnum" into prime set "pset"
        }
       
        for (int i=rank;i<upperlimit-1;i+=size)  // divide array into "size" groups
        {
            if (p[i][0]%minnum==0 & p[i][1]==1) {        //p[i][1]==1 means number i has never been deleted.
                p[i][1]=0;                                                // p[i][1]==0 means number i has been deleted.
            }
        }

        for (int i=rank;i<upperlimit-1;i+=size)    // find the min value in every rank.
        {
            if (p[i][1]==1) {
                temp=i+2;
                break;
            }
        }
     
        // MPI_Waitall (count,&array_of_requests,&array_of_statuses) 
// we want to use this command, but we do not use MPI_Isend(), so there is no array status and request.

        MPI_Allreduce(&temp,&minnum,size,MPI_INT,MPI_MIN,MPI_COMM_WORLD); 
// find the global min value using collective command

        // MPI_Bcast(&minnum,1,MPI_INT,0,MPI_COMM_WORLD); 
// we think there is no need to broadcast.
       
    }
   
    for (int i=rank;i<upperlimit-1;i+=size)          // when add the remaining prime number to the prime set pset.
    {
        if (p[i][1]==1) {
            pset.push_back(p[i][0]);                   
        }
    }

---

Welcome to the fourm, Shuaizheng! :cool:

I don't know anything about MPI yet, but I know a bit about using the Sieve of Eratosthenes.

1) if you use calloc() to create your sieve array, you will get all zero's in it. Now reverse your logic (so all the non-primes are marked out with a one, instead). The advantage is that you only need a one dimension sieve array.

if(sieve[indexNumber] is 0), then the indexNumber is prime, as the for loop works forward.

2) you don't need to mark out duplicates of 2. They will be skipped. Assign sieve[0] to 1 since 1 is not prime. Start your for loop which checks for primality, at 3, and increment it by +=2.

Assign p[0] = 2;

Below is the ENTIRE block of code to mark the sieve[] and also, find all the primes, in my program:

SieveSize is a define as the largest prime number the program will find+1

pcnt is an int, and counts the number of primes found
it all serves as the index into the primes array named p[].

The second (inner) for loop, is my own math, because what I had before had far too many repeated values. It is accurate for < 86,028,000, but untested above that value.

Code:

---

for(i=3;i<SieveSize;i+=2) {
  if(!s[i]) {      //it's a prime
      ++pcnt; 
      p[pcnt]=i;  //add the prime into the array of primes
      //mark off all it's multiples in the sieve array
      for(k=3,j = i*k;j<SieveSize;j=(i*(k+=2))) {
        s[j] = 1;
      }
  } 
}

---

If you look at the "fastest printing to a console" thread, KCfromNC has posted some VERY nice code for finding primes.

Thank you Adak!

I am totally new here. I solved the problem. The major problem is that I need to synchronize the message among or processes(MPI_Waitall()).

Your code is of great help!!! I just start C programming this year.

I really appreciate your post!

Shuai

Quote:

---

Originally Posted by Adak

Welcome to the fourm, Shuaizheng! :cool:

I don't know anything about MPI yet, but I know a bit about using the Sieve of Eratosthenes.

1) if you use calloc() to create your sieve array, you will get all zero's in it. Now reverse your logic (so all the non-primes are marked out with a one, instead). The advantage is that you only need a one dimension sieve array.

if(sieve[indexNumber] is 0), then the indexNumber is prime, as the for loop works forward.

2) you don't need to mark out duplicates of 2. They will be skipped. Assign sieve[0] to 1 since 1 is not prime. Start your for loop which checks for primality, at 3, and increment it by +=2.

Assign p[0] = 2;

Below is the ENTIRE block of code to mark the sieve[] and also, find all the primes, in my program:

SieveSize is a define as the largest prime number the program will find+1

pcnt is an int, and counts the number of primes found
it all serves as the index into the primes array named p[].

The second (inner) for loop, is my own math, because what I had before had far too many repeated values. It is accurate for < 86,028,000, but untested above that value.

Code:

---

for(i=3;i<SieveSize;i+=2) {
  if(!s[i]) {      //it's a prime
      ++pcnt; 
      p[pcnt]=i;  //add the prime into the array of primes
      //mark off all it's multiples in the sieve array
      for(k=3,j = i*k;j<SieveSize;j=(i*(k+=2))) {
        s[j] = 1;
      }
  } 
}

---

If you look at the "fastest printing to a console" thread, KCfromNC has posted some VERY nice code for finding primes.

---

You're making fine progress then, Shuai.

Congrats on getting your bug fixed in your program, and you're quite welcome.