очевидно, ОП уже получил ответ, в комментариях, и проблема решена сейчас.
Я написал программу для простых чисел (сито из эратосфена), которая выполняется с использованием pthreads.
Это моя первая многопоточная программа, и я не знаю, почему моя программа занимает примерно 3 минуты. время выполнить. Это слишком много времени!
Может кто-нибудь сказать мне, где именно я не прав
#include<iostream>
#include<cstring>
#include<pthread.h>
#include<time.h>
using namespace std;
//set limits
#define LIMIT 100000001
#define THREAD_LIMIT 8
//declare buffers
bool num[LIMIT];
unsigned long long num_of_prime = 1; // 2 is counted as prime initially
unsigned long long sum_prime = 2; // 2 is counted in sum of primes
void *search(void *);
int main()
{
clock_t start_time = clock(); // start clock stamp
pthread_t thread[THREAD_LIMIT];
int thread_val=-1,j=-1;
unsigned long long i=3;
bool *max_prime[10]; // stores max. 10 prime numbers
memset(num,0,LIMIT); // initialize buffer with 0
while(i<LIMIT)
{
if(num[i]==0)
{
num_of_prime++;
sum_prime +=i;
j = ++j%10;
max_prime[j]=num+i;
thread_val=++thread_val%THREAD_LIMIT;
pthread_join(thread[thread_val],NULL); // wait till the current thread ends
pthread_create(&thread[thread_val],NULL,search,(void *)i); // fork thread function to flag composite numbers
}
i+=2; // only odd numbers
}
// end all threads
for(i=0;i<THREAD_LIMIT;i++)
{
pthread_join(thread[i],NULL);
}
cout<<"Execution time: "<<((double)(clock() - start_time))/CLOCKS_PER_SEC<<"\n";
cout<<"Number of Primes: "<<num_of_prime<<"\n";
cout<<"Sum of Primes: "<<sum_prime<<"\n";
cout<<"List of 10 Max. Primes: "<<"\n";
for(i=0;i<10;i++)
{
j=++j%10;
cout<<(max_prime[j]-num)<<"\n";
}
return 0;
}
void *search(void *n)
{
unsigned long long jump = (unsigned long long int)n;
unsigned long long position = jump*jump; // Jump to N*N th comppsite number
bool *posn = num;
jump<<=1;
while(position<LIMIT)
{
(*(posn+position))?(position+=jump):(*(posn+position)=1,position+=jump);
}
return NULL;
}
контрсилы:
Только 8 потоков могут быть разветвлены.
N: 10 ^ 8
Как я могу улучшить эффективность этого кода (особенно в разветвлении & присоединяясь к темам)?
Мой опыт показывает, что перебрасывание некоторых потоков в задачу ускоряет, но, к сожалению, мало, для простых чисел до больших N.
Я попытался разделить сито на куски, по одному на нить. Один поток генерирует список простых чисел до sqrt (N), затем все потоки хрустят в своей части сита, выбивая кратные простые числа. Идея заключалась в том, чтобы как можно меньше взаимодействовать между нитями — они все хрустят на своей части сита, независимо.
Ваш код появляется, чтобы начать новый поток, чтобы выбить кратные для каждого найденного простого числа. Затраты на запуск / остановку такого количества потоков наполняют меня тревогой! Будь я проклят, если смогу увидеть, как ты не можешь перепутать потоки друг с другом, но я полагаю, что нет?
FWIW, для простых чисел до 10 ^ 8, я управляю:
без резьбы: прошло 0,160 с, пользователь — 0,140 с
5 потоков: 0,040 секунд прошло, 0,130 секунд пользователя.
на относительно скромной машине x86_64.
Для 10 ^ 10:
без резьбы: прошло 39,260 с, пользователь — 37,910 с
5 потоков: 23,680 секунд прошло, 110,120 секунд пользователя.
что глубоко разочаровывает. Я думаю, что проблема в том, что кэш забивается … код обрабатывает каждое простое число по очереди и выбивает все его кратные значения, поэтому перемещается от одного конца куска к другому, а затем возвращается к началу. На самом деле, может быть, лучше отбросить, скажем, 512 К сита для всех простых чисел, а затем повторить.