currently I have a problem related with Parallelization of sieve of Eratosthenes..here is my code :
const long int lastNumber = 1*1000*1000*1000LL;
#include <iostream>
#include <vector>
#include <cmath>
#include <thread>
#include <cassert>
#include <sys/time.h>
using namespace std;
double seconds()
{
timeval now;
gettimeofday(&now, NULL);
return now.tv_sec + now.tv_usec/1000000.0;
}
// simple parallel sieve of Eratosthenes
void multithread_calc(int memorySize_chunk_lb, int lastNumberSqrt_chunk_lb, int lastNumber_chunk_lb,int memorySize_chunk, int lastNumberSqrt_chunk, int lastNumber_chunk, int& found_chunk)
{
// initialize
char *isPrime = new char[memorySize_chunk+1];
for (int i = memorySize_chunk_lb; i <= memorySize_chunk; i++) //0
{
isPrime[i] = 1;
}
// find all odd non-primes
for (int i = lastNumberSqrt_chunk_lb; i <= lastNumberSqrt_chunk; i += 2) //3
{
if (isPrime[i/2])
{
for (int j = i*i; j <= lastNumber_chunk; j += 2*i)
{
isPrime[j/2] = 0;
}
}
}
// sieve is complete, count primes
found_chunk = lastNumber_chunk >= 2 ? 1 : 0;
for (int i = lastNumber_chunk_lb; i <= memorySize_chunk; i++) //1
found_chunk += isPrime[i];
delete[] isPrime;
}
int eratosthenes(int lastNumber)
{
int found = 0;
const int lastNumberSqrt = (int)sqrt((double)lastNumber);
int memorySize = (lastNumber-1)/2;
//things that will be divided :
//int lastNumberSqrt
//int memorySize
//int lastNumber
int chunk_memorySize;
int chunk_lastNumberSqrt;
int chunk_lastNumber;
//set lower bound
int chunk_memorySize_lb=0;
int chunk_lastNumberSqrt_lb=3;
int chunk_lastNumber_lb=1;
int num_threads = 2;
int chunk_memorySize_part = memorySize/num_threads;
int chunk_lastNumberSqrt_part = lastNumberSqrt/num_threads;
int chunk_lastNumber_part = lastNumber/num_threads;
vector<thread> threads;
for(int i = 0; i<num_threads; i++){
if(i>0)
{
chunk_memorySize_lb=i*chunk_memorySize_part;
chunk_lastNumberSqrt_lb=i*chunk_lastNumberSqrt_part;
chunk_lastNumber_lb=i*chunk_lastNumber_part;
}
chunk_memorySize = (i+1)*chunk_memorySize_part;
chunk_lastNumberSqrt = (i+1)*chunk_lastNumberSqrt_part;
chunk_lastNumber = (i+1)*chunk_lastNumber_part;
auto th = thread(&multithread_calc,chunk_memorySize_lb,chunk_lastNumberSqrt_lb,chunk_lastNumber_lb,chunk_memorySize,chunk_lastNumberSqrt,chunk_lastNumber,ref(found));
threads.push_back(move(th));
assert(!th.joinable());
}
// Wait for all threads to finish
for (auto &thread : threads)
{
thread.join();
}
return found;
}
int main(int argc, char* argv[])
{
int found = 0;
printf("Primes between 2 and %d\n\n", lastNumber);
printf("Simple Sieve\n");
double startTime = seconds();
found = eratosthenes(lastNumber);
double duration = seconds() - startTime;
printf("%d primes found in %.3fs\n\n", found, duration);
system("PAUSE");
return 0;
}
actually I get correct result when I use num_threads = 1, but the more I increase the thread number, the less prime number I get...in my case, it gets divided results whenever I tried to increase the thread...do you know how to solve this problem?? Any help will be very appreciated, thx.
this is the result when I set num_threads = 1 :
and this is the result when I set num_threads = 2 :
Do you know what's the problem with this program and how to solve this?? Any help will be very appreciated..
Aucun commentaire:
Enregistrer un commentaire