
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 }