0

显然，OP已经在评论中得到了答案，现在问题已经解决。

我编写了一个使用 pthread 执行的素数程序（eratosthenes 筛）。

这是我的第一个多线程程序，我不知道为什么我的程序大约需要 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 个线程。

数量：10^8

如何提高此代码的效率（尤其是在分叉和加入线程时）？

4

1 回答 1

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 秒用户。

这是非常令人失望的。我认为问题在于缓存被淹没了......代码依次处理每个素数并剔除其所有倍数，因此从一个块的一端扫到另一端，然后回到开头。实际上，对于所有素数来说，在筛子的 512K 处敲击可能会更好，然后重复。

于 2014-09-12T00:49:34.537 回答