マルチスレッドのエラトステネスのふるいを作成しようとしています
スレッド数はデフォルトで 4 に設定されていますが、ユーザーがコマンド ライン引数として指定することもできます。
いくつかの異なるスレッドと同時に、配列内の素数のすべての間隔をマークしようとしています。したがって、0 または 1 を含む配列は、arrayElements/threadNumber に分割されます。
各スレッドには、配列の指定された開始位置と終了位置があり、素数の間隔をチェックします。
たとえば、最大にしたい数が 20 で、スレッドが 4 つあるとします。スレッド 0 は 0 から始まり、20/4-1 まで上がります。次は 20/4*threadNumber から始まり、(20/4*nextThreadNumber)-1 まで続きます。
次に、見つかった素数がいずれかのスレッドの配列領域内にあるかどうかを確認する必要があります。これは、そうである場合、その素数を非素数としてマークできないためです。最初のスレッドの境界を超えた後、素数がそれ自体を分割するため、素数が非素数としてマークされるため、問題が発生していました。
以下に示すように、startingPosition が素数で割り切れるかどうかを調べます。そうであれば、それをそのスレッドの「nonPrime seek」の開始点として設定し、そこから素数を増やして、範囲内の各インスタンスを非素数としてマークします。そうでない場合は、次の非素数を (素数に基づいて) 計算し、それを開始点とします。
このすべての終わりに、それはあなたの通常の「素数の間隔で配列をループし、各インスタンスを非素数としてマークする」です。
簡単に言えば、これを 32 ビット整数 (20 億程度) の範囲までの数値で機能させる必要があります。数値が小さい場合は問題なく動作しますが、140 万の数値でいくつかのベンチマーク テストを行った後、13.4 秒かかりました。540 万の場合、37.3 秒かかります。1,000 万の場合、68 秒かかります。20億の場合、終わりが見えずに動作し続けます（10分以上実行しました）.
では、どうすればコードを改善できますか? 時間がかかる原因は何ですか？シングルスレッドの実装よりも高速ではないようです (シングルスレッドのスレッド引数を 1 に設定し、1,000 万の数値で 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: Linux の c で PThread をスリープまたは一時停止する方法を例として使用して、条件付きのロックとロック解除を試してみました。基本的に素数のマーキングを一時停止および一時停止したいので。開始/停止セクションが検出される場所の上のグループとして、スレッド化された関数に while ステートメント (lock ステートメントと unlock ステートメントを含む) を配置しました。lock/unlock ステートメントを含むアルゴリズムの内側の if ステートメント内で素数が見つかった場合は、int のマーキングを 1 に設定し、lock/unlock ステートメントを含む if ステートメントのすぐ外側でその変数を 0 に設定します。
それは私がやるべきことですか？