MPI programming help!

This is a discussion on MPI programming help! within the C Programming forums, part of the General Programming Boards category; Hello all, We are using this method to find all the prime numbers. Our work didn't use the MPI_Isend() or ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    2

    MPI programming help!

    Hello all,

    We are using this method to find all the prime numbers.
    Name:  Capture.PNG
Views: 413
Size:  27.1 KB


    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]);                     
            }
        }
    Last edited by shuaizheng; 11-15-2011 at 05:51 AM.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Welcome to the fourm, Shuaizheng!

    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.

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    2
    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 View Post
    Welcome to the fourm, Shuaizheng!

    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.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You're making fine progress then, Shuai.

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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. About Device Driver Programming And Socket Programming
    By pritesh in forum Linux Programming
    Replies: 6
    Last Post: 01-23-2010, 03:46 AM
  2. Replies: 1
    Last Post: 08-19-2007, 04:55 AM
  3. small programming job VCPP / Object Oriented Programming
    By calgonite in forum Projects and Job Recruitment
    Replies: 10
    Last Post: 01-04-2006, 11:48 PM
  4. Total newb to programming here... Question about the many programming languages. Ty!
    By tsubotakid1 in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 10-05-2003, 11:32 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21