#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
}
