0

我正在尝试创建一个多线程的埃拉托色尼筛

线程数默认设置为 4，但用户可以将它们指定为命令行参数。

我试图用几个不同的线程同时标记数组中素数的所有间隔。因此，包含 0 或 1 的数组被拆分为 arrayElements/threadNumber。

每个线程都有一个指定的数组的起始位置和结束位置，以便它检查其中的素数间隔。

因此，例如让我们假设您想要达到的数字是 20，并且您有 4 个线程。线程 0 将从 0 开始并上升到 20/4-1。下一个将从 20/4*threadNumber 开始，一直到 (20/4*nextThreadNumber)-1，依此类推。

然后我必须检查找到的素数是否在其中一个线程的数组区域内。这是因为如果是，则该素数不能被标记为非素数。我遇到了一个问题，因为素数在超出第一个线程的范围后会被标记为非素数，因为素数会自行相除。

正如您在下面看到的，我发现startingPosition 是否可以被素数整除。如果是，我将其设置为该线程的“非素数搜索”起点，并从那里增加素数，将范围内的每个实例标记为非素数。如果不是，那么我计算下一个非素数是什么（基于素数）并将其作为开始。

在这一切结束时，这是您通常的“以素数为间隔循环遍历数组，将每个实例标记为非素数”。

长话短说，我必须让这个数字达到 32 位整数（大约 20 亿）的范围。它适用于较小的数字，但在对 140 万个数字进行一些基准测试后，它需要 13.4 秒。540 万只需要 37.3 秒。1000 万只需要 68 秒。对于 20 亿，它只是继续工作（我让它运行了 10 分钟或更长时间），看不到尽头。

那么，我该如何改进我的代码呢？是什么导致它需要这么长时间？它似乎并不比单线程实现快（我将线程参数设置为 1 表示单线程，1000 万个数字需要 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：我以How to sleep or pause a PThread in c on Linux作为示例来尝试指导一些条件锁定和解锁。因为我确实想暂停和取消暂停素数的标记。我将 while 语句（使用 lock 和 unlock 语句）作为一个组放在我的线程函数中，在其中发现了 start/stop 部分。当在具有锁定/解锁语句的算法的内部 if 语句中找到素数时，我将 int 的标记设置为 1，并在具有锁定/解锁语句的 if 语句之外将该变量设置为 0。

那是我应该做的吗？

4

0 回答 0