samedi 16 septembre 2023

Problems with Parallel sieve of Eratosthenes

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 :

enter image description here

and this is the result when I set num_threads = 2 :

enter image description here

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