Многопоточное сито Эратосфена - очень и очень долго
Я пытаюсь создать многопоточное сито Эратосфена
Количество потоков по умолчанию установлено равным 4, хотя они могут быть указаны пользователем в качестве аргумента командной строки.
Я пытаюсь пометить все интервалы простого числа в массиве одновременно несколькими различными потоками. Таким образом, массив, содержащий 0 или 1, разбивается на arrayElements/threadNumber.
Каждый поток имеет заданную начальную и конечную позиции массива, чтобы он мог проверять интервалы простого числа внутри.
Например, предположим, что число, на которое вы хотите перейти, равно 20, и у вас есть 4 потока. Поток 0 начнется с 0 и достигнет 20/4-1. Следующий будет начинаться с 20/4*threadNumber и подниматься до (20/4*nextThreadNumber)-1 и так далее.
Затем я должен проверить, находится ли найденное простое число в области массива одного из потоков. Это потому, что если это так, то простое число НЕ МОЖЕТ быть помечено как непростое. У меня была проблема, потому что простые числа, выходящие за пределы первого потока, будут помечены как не простые, потому что простое число делится.
Как вы можете видеть ниже, я нахожу, если начальная позиция делится на простое число. Если это так, я устанавливаю это как начальную точку "nonPrime seek" этого потока и увеличиваю ее от простого числа, отмечая каждый экземпляр в пределах диапазона как nonprime. Если это не так, тогда я вычисляю, что является следующим не простым числом (на основе простого числа), и ставлю это в качестве начала.
В конце концов, это ваш обычный "цикл по массиву с интервалами от PrimeNumber, помечая каждый экземпляр как не простой".
Короче говоря, мне нужно, чтобы это работало с числами вплоть до 32-битного целого числа (что составляет 2 миллиарда или около того). Он отлично работает с меньшими числами, но после некоторых сравнительных тестов на 1,4 миллиона чисел это занимает 13,4 секунды. На 5,4 миллиона уходит 37,3 секунды. На 10 миллионов уходит 68 секунд. Для 2 миллиардов он просто продолжает работать (я позволил ему работать в течение 10 или более минут) без конца.
Итак, как я могу улучшить свой код? Что заставляет это так долго? Похоже, что это не так быстро, как однопоточная реализация (я установил аргумент потока в 1 для однопотокового, и это займет 56 секунд для 10 миллионов номеров)
Итак, вот код, с
определить 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: я использовал Как спать или приостановить PThread в c на Linux в качестве примера, чтобы попытаться направить некоторые условные блокировки и разблокировки. Так как я действительно хочу сделать паузу и сделать паузу разметкой простых чисел. Я поместил оператор while (с операторами lock и unlock) в свою многопоточную функцию как группа выше, где обнаружены секции start / stop. Я помещаю разметку int в 1, когда в моем внутреннем операторе алгоритма встречается простое число с помощью операторов блокировки и разблокировки, и устанавливаю эту переменную равной 0 только вне этого оператора if с помощью операторов блокировки / разблокировки.
Это то, что я должен делать?