Как улучшить разветвление / присоединение многопоточной программы?

очевидно, ОП уже получил ответ, в комментариях, и проблема решена сейчас.

Я написал программу для простых чисел (сито из эратосфена), которая выполняется с использованием 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

Как я могу улучшить эффективность этого кода (особенно в разветвлении & присоединяясь к темам)?

0

Решение

Мой опыт показывает, что перебрасывание некоторых потоков в задачу ускоряет, но, к сожалению, мало, для простых чисел до больших 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 К сита для всех простых чисел, а затем повторить.

0

Другие решения


По вопросам рекламы [email protected]