Многопоточное сито Эратосфена — очень-очень долго

Я пытаюсь создать многопоточное сито Эратосфена.

Количество потоков по умолчанию установлено равным 4, хотя они могут быть указаны пользователем в качестве аргумента командной строки.

Я пытаюсь отметить все интервалы простого числа в массиве одновременно с несколькими разными потоками. Итак, массив, содержащий 0 или 1, разбивается на arrayElements/threadNumber.

Каждый поток имеет указанную начальную позицию и конечную позицию массива для проверки интервалов простого числа внутри.

Так, например, давайте предположим, что число, до которого вы хотите дойти, равно 20, и у вас есть 4 потока. Поток 0 начнется с 0 и дойдет до 20/4-1. Следующий начнется с 20/4*threadNumber и дойдет до (20/4*nextThreadNumber)-1 и так далее.

Затем я должен проверить, находится ли найденное простое число в области массива одного из потоков. Это потому, что если это так, это простое число НЕ МОЖЕТ быть помечено как не простое. У меня возникла проблема, потому что простые числа после выхода за пределы первого потока будут помечены как непростые, потому что простое число делится само на себя.

Как вы можете видеть ниже, я определяю, делится ли startPosition на простое число. Если это так, я устанавливаю это как начальную точку «ищущего nonPrime» этого потока и увеличиваю ее на простое значение, отмечая каждый экземпляр в пределах диапазона как неосновной. Если это не так, то я вычисляю следующее не простое число (на основе простого числа) и ставлю его в качестве начала.

В конце всего этого, это ваш обычный "Проход через массив с интервалами PrimeNumber, помечая каждый экземпляр как не простой".

Короче говоря, я должен заставить это работать с числами до диапазона 32-битного целого числа (что составляет 2 миллиарда или около того). Он отлично работает с меньшими числами, но после некоторых тестов производительности на 1,4 миллиона чисел это занимает 13,4 секунды. На 5,4 миллиона уходит 37,3 секунды. Для 10 миллионов требуется 68 секунд. Для 2 миллиардов он просто продолжает работать (я дал ему поработать 10 минут или больше), и конца ему не видно.

Итак, как я могу улучшить свой код? Из-за чего так долго? Кажется, это не быстрее, чем однопоточная реализация (я установил аргумент потока равным 1 для однопоточной реализации, и для 10 миллионов чисел требуется 56 секунд)

Итак, вот код, с

определить maxNum 10483646

Резьбовая функция:

   int numThreads; //number of threads
    int innerCounter;
    int composite[maxNum];


//need to find all prime numbers up to unsigned 32 bit integer
//creating n threads, (start to 1/n -1) 0,  (1/n to 2/n -1) , (2/n to 3/n -1) until it's (n-1/n to n/n) are starting positions for looking for primes so threads aren't accessing same area
void* markPrimes(int i){
    //Prime number should be innerCounter
    //printf("Threaded process: %d\n", i);
    //starting position in array: (maxNum/threadNum) * i
    //ending position in array: ((maxNum/threadNum)) * (i+1) - 1
    int startingPosition;
    int compositeCounter;
    int firstNonPrime;
    int endingPosition;
    int primeInRange;


        startingPosition = (double)(maxNum/numThreads) * i;
        endingPosition = (double)(maxNum/numThreads) * (i+1)-1;
        if(i == numThreads-1){
            endingPosition = maxNum;
        }

        if(startingPosition <= innerCounter && innerCounter <= endingPosition){ //the prime number is in range, and should be ignored
            primeInRange = 1;
        }

        firstNonPrime = startingPosition%innerCounter;
        if(firstNonPrime != 0){
            int temp = innerCounter - firstNonPrime;
            firstNonPrime = temp + startingPosition;
        }else{
            firstNonPrime = startingPosition;
        }
        if(primeInRange == 1){
            firstNonPrime = innerCounter + innerCounter;
        }

    if(firstNonPrime <= endingPosition){


        for(compositeCounter = firstNonPrime; compositeCounter <= endingPosition; compositeCounter += innerCounter){

                        composite[compositeCounter] = 1;

                    }
    }
    return (void*)0;
}

А теперь основная функция, которая имеет остальную часть алгоритма и создает потоки:

int main(int argc, char** argv[]){

    clock_t start; //start time
    clock_t stop; //end time
    double total_time;
    int rc;
    int nextNum;
    int prevNum = 0;
    int i;
    int numPrimes;
    //unsigned int maxNum = INT_MAX; //maximum unsigned integer value to go up until
    //bit array for threads to check primes for
    for(i = 0; i < maxNum+1; i++){
        composite[i] = 0;
    }
    if(argc > 1){
        numThreads = atoi(argv[1]); //argument given for n number of threads
    }else{
        numThreads = 4; //default if no argument given is 4 threads
    }
    pthread_t threads[numThreads]; //array of threads
    start = clock(); //start timing

    //Sieve algorithm here! When prime found, spawn threads!
    int outerCounter = 1;
    while(outerCounter < sqrt(maxNum)){
        //searching numbers above the current for prime numbers

        for(innerCounter = outerCounter+1; innerCounter <= maxNum; innerCounter++){
            //not composite

            if(composite[innerCounter] == 0){
                //setting all multiples of innerCounter to 1, creating threads to split up the work!

                for(i = 0; i < numThreads; i++){

                    rc = pthread_create(&threads[i], NULL, markPrimes, (void*) i);

                    //Detecting Error
                    if(rc){
                        //perror("Thread creation error!");
                        //exit(-1);
                    }
                }
                for(i = 1; i < numThreads; i++){
                    pthread_join(threads[i], NULL);
                }
                outerCounter = innerCounter;
                numPrimes++;

            }
        }
    }

    stop = clock(); //stop timing
    total_time = (double)(stop - start) / CLOCKS_PER_SEC;


    printf("Time for threads: %.5f\n", total_time);
    printf("Number of primes: %d\n", numPrimes-1);

    return 0;
}

Заранее благодарю всех за терпение и помощь!

Изменить: я должен использовать pthreads

Редактировать 2: я использовал Как спать или приостанавливать a PThread в c в Linux в качестве примера, чтобы попробовать выполнить некоторую условную блокировку и разблокировку. Поскольку я действительно хочу приостановить и возобновить маркировку простых чисел. Я поместил оператор while (с операторами блокировки и разблокировки) в свою поточную функцию в виде группы выше, где обнаружены разделы запуска/остановки. Я помещаю маркировку int в 1, когда внутри моего внутреннего оператора if алгоритма с операторами блокировки/разблокировки находится простое число, и устанавливаю эту переменную в 0 сразу за пределами этого оператора if с операторами блокировки/разблокировки.

Это то, что я должен делать?