Parallel C Programming with OpenMP and MPI

• 12th Oct, 2021
• 17:56 PM

#include
#include
#include
#include  
#include

static int N = 10000000;  // size of array
static int RangeSize = 1000;  // range for each thread to work

static bool isPrime(int n)
{
    bool prime = true;

    if (n < 2){ // if n is 0 or 1 then it is not prime i.e. return prime = false
        prime = false;
    }

    for (int k = 2; k <= sqrt(n) && prime; k++){
        if (n % k == 0) // checks whether a number is divisible by numbers other than number itself
            prime = false;
    }

    return prime;
}

// function to return the frequency of prime number between lower bound and upper bound 
int PrimeCounter(int lb, int ub)
{
    int freq = 0;
    for (int k = lb; k < ub; k++){
        if (isPrime(k)) //
            freq++;
    }

    return freq;
}

int main(int argc, char* argv[]) 
{
    int size = N/RangeSize + 1 + (N%RangeSize != 0 ); // calculates size of index ( N%Rangesize != 0 implies if N is not divisible by RangeSize then add 1 to size)
    int* index = (int*)malloc(sizeof(int)* size);

    // loop to assign the range to index array so that each thread have their corresponding lower and upper bound
    for (int i=0; i         if (i*RangeSize <= N)
            index[i] = i*RangeSize;
        else
            index[i] = N;
    }
    //printf("size = %d , value = %d\n",size,index[size-1] );
    // start from here
    double start_time = omp_get_wtime();

    int nThreads;

    // get number of threads 
    #pragma omp parallel
    {
        nThreads = omp_get_num_threads();
    }

    int freq = 0;
    int* result = (int*)malloc(sizeof(int)*(nThreads));
    
    #pragma omp parallel for
    for (int i=0; i         int tid = omp_get_thread_num(); // gets thread id
        result[tid] += PrimeCounter(index[i],index[i+1]); // each thread calculates the frequency of their corresponding lower and upper bound and stores it in result[tid]
    }

    // caluclates total frequency calcuated by each thread
    for (int i=0; i         freq += result[i];

    double end_time = omp_get_wtime();
    double computation_time = end_time - start_time;

    printf("Number of primes in range %d to %d = %d\n", 1,N,freq);
    printf("%lf millisecs ( %lf secs )\n",computation_time*1000,computation_time);

}

*****************************************************************************************************************

#include
#include
#include
#include  
#include

static int N = 10000000;
static int RangeSize = 1000;

static bool isPrime(int n)
{
    bool prime = true;

    if (n < 2){
        prime = false;
    }

    for (int k = 2; k <= sqrt(n) && prime; k++){
        if (n % k == 0)
            prime = false;
    }

    return prime;
}

int PrimeCounter(int lb, int ub)
{
    int freq = 0;
    for (int k = lb; k < ub; k++){
        if (isPrime(k))
            freq++;
    }

    return freq;
}

int main(int argc, char* argv[]) 
{
    int len = N/RangeSize + 1 + (N%RangeSize != 0 );
    int* index = (int*)malloc(sizeof(int)* len);
    int freq = 0;

    int rank;
    int size;
    int i, j, k;
    double start_time; 
    double end_time;
    int start_ind;
    int end_ind;
    int range;
    int tagM = 1,tagS = 8;
    MPI_Status status; 
    MPI_Request request;
    MPI_Init(&argc, &argv); //initialize MPI operations
    MPI_Comm_rank(MPI_COMM_WORLD, &rank); //get the rank
    MPI_Comm_size(MPI_COMM_WORLD, &size); //get number of processes

    int* result = (int*)malloc(sizeof(int)*(size));

    /* master initializes work*/

    if (rank == 0) {

        for (int i=0; i             if (i*RangeSize <= N)
                index[i] = i*RangeSize;
            else
                index[i] = N;
        }

        start_time = MPI_Wtime();
        // master processor calulates start index and end index and send it to the other processors
        for (i = 1; i < size; i++) {
            range = (len / (size - 1)); 
            start_ind = (i - 1) * range;
            if (((i + 1) == size)) {
                end_ind = len; 
            } else {
                end_ind = start_ind + range;
            }
            
            /* master thread sends start and end index to processor i */
            //send the low bound first without blocking, to the intended slave
            MPI_Send(&start_ind, 1, MPI_INT, i, tagM, MPI_COMM_WORLD); // second arguement is 1 i.e sending a single number to processor i with a tagM for recognition
            //next send the upper bound without blocking, to the intended slave
            MPI_Send(&end_ind, 1, MPI_INT, i, tagM + 1, MPI_COMM_WORLD);
            //finally send the allocated row range of [A] without blocking, to the intended slave
            MPI_Send(&index[start_ind], (end_ind - start_ind + 1), MPI_INT, i, tagM + 2, MPI_COMM_WORLD);
            
        }
    }
    
    if (rank > 0) {
        //receive low bound from the master
        MPI_Recv(&start_ind, 1, MPI_INT, 0, tagM, MPI_COMM_WORLD, &status); // processor i receives data with tagM from master processor 
        //next receive upper bound from the master
        MPI_Recv(&end_ind, 1, MPI_INT, 0, tagM + 1, MPI_COMM_WORLD, &status);
        //finally receive row range of [A] to be processed from the master
        MPI_Recv(&index[start_ind], (end_ind - start_ind + 1), MPI_INT, 0, tagM + 2, MPI_COMM_WORLD, &status);

        // calculate number of prime number
      
        result[rank] = 0; 
        // each processor calculates the frequency assigned by the master thread and store in result in index equal to rank of the processor
        for (int i=start_ind; i             if (index[i+1] <= N){
                result[rank] += PrimeCounter(index[i],index[i+1]);
            }
        }

        //send start index of processor without blocking to the master
        MPI_Send(&start_ind, 1, MPI_INT, 0, tagS, MPI_COMM_WORLD); // sends back  start index to master thread for confirmation
        //send end index of processor without blocking to the master
        MPI_Send(&end_ind, 1, MPI_INT, 0, tagS + 1, MPI_COMM_WORLD);
        //send result without blocking to the master
        MPI_Send(&result[rank], 1, MPI_INT, 0, tagS + 2, MPI_COMM_WORLD); // sends the result calculated to the master thread 
       
    }
    // master receives the processed array from slaves
    if (rank == 0) {
        for (i = 1; i < size; i++) {
            //receive start index from a slave
            MPI_Recv(&start_ind, 1, MPI_INT, i, tagS, MPI_COMM_WORLD, &status);
            //receive end index from a slave
            MPI_Recv(&end_ind, 1, MPI_INT, i, tagS + 1, MPI_COMM_WORLD, &status);
            //receive result from a slave
            MPI_Recv(&result[i], 1, MPI_INT, i, tagS + 2, MPI_COMM_WORLD, &status);
        }

        // master thread calculated total frequency from result received by slave processors
        for (i=1; i             freq += result[i];
        }
        end_time = MPI_Wtime();
        double computation_time = end_time - start_time;
        printf("Number of primes in range %d to %d = %d\n", 1,N,freq);
        printf("%lf millisecs ( %lf secs )\n",computation_time*1000,computation_time);

    }
    MPI_Finalize(); //finalize MPI operations
}