3

スレッドを理解しようとしています。複数のスレッドに素数を計算させようとしています。1 つのスレッドで最初の数値を計算してから、次のスレッドで次の数値を計算し、次の数値を計算し、最上位のスレッドを見つけてそれを印刷します。

したがって、1 から 50 までから始めます。新しい番号を新しいスレッドに渡します。それが私たちが望んでいることだと思います。

ここに私がこれまで持っているものがあります。

void* compute_prime (void* arg)
{
//pthread_mutex_lock(&lock);
int candidate = 2;
int n = *((int*) arg);

while (1) {
int factor;
int is_prime = 1;

/* Test primality by successive division.  */
for (factor = 2; factor < candidate; ++factor)
  if (candidate % factor == 0) {
    is_prime = 0;
    break;
  }
/* Is this the prime number we're looking for?  */
if (is_prime) {
  if (--n == 0)
    /* Return the desired prime number as the thread return value.  */

    return (void*) candidate;
}
++candidate;
}

return NULL;
}




int main ()
{
int which_prime = 50;
int isPrime1, isPrime2, isPrime3, isPrime4;
fprintf (stderr, "main thread pid is %d\n", (int) getpid ());
for(master_list; master_list < which_prime; master_list++)
{
//do{

// pthread_mutex_lock(&lock); 

pthread_create (&thread1, NULL, &compute_prime, &master_list);
//master_list++;
//pthread_mutex_unlock(&lock);

//}while(master_list < which_prime);

}

return 0;
}

私の出力。

main thread pid is 508
Thread1 Found the prime number:  3.
Thread2 Found the prime number:  3.
Thread3 Found the prime number:  3.
Thread4 Found the prime number:  3.
Thread1 Found the prime number:  7.
Thread2 Found the prime number:  7.
Thread3 Found the prime number:  7.
Thread4 Found the prime number:  7.
Thread1 Found the prime number:  13.
Thread2 Found the prime number:  13.
Thread3 Found the prime number:  13.
Thread4 Found the prime number:  13.

等....

これは私が欲しいものです。しかし、すべてのスレッドが同じ素数を見つける必要はありません。彼らは異なる素数を見つけているはずです。スレッドの前に変数をインクリメントしても、まだ機能しません。動作させようとしたコードをコメントアウトしました。私は何をする必要がありますか？私が明確だったことを願っています。

4

2 に答える 2

1

素数の列挙は恥ずかしいほど並列ではありません。つまり、問題を独立した計算に分解するのは簡単ではありません。ふるいと試行分割には、以前の素数の履歴が必要です (または少なくとも大幅に改善されます)。

並列素数計算のトピックに関する真剣な研究があると確信しています。私の頭の上から、多くの数で並行して実行できる確率的素数テストに頼ることをお勧めします。これにより、他のメカニズム (コードで既に使用されている試行分割など) でテストする必要がある数値のセットが大幅にフィルター処理されます。

候補よりも小さいすべての数値で試行分割を本当に実行したい場合(素数だけではなく、より典型的で非常に効率的です)、スレッドに対してN、各スレッドcandidateを異なる基数 (3, 5) で開始することをお勧めします。 、7、...) であり、各スレッドは増分candidateする2*Nため、すべてが一意の数値セットにヒットします (現在は 2 から開始して 1 ずつ増分していますが、偶数は決して素数ではないことに最終的に気付くと思います... )

于 2012-10-18T00:42:00.807 に答える
0

あなたの質問に対する直接の答えは、master_list整数のアドレスを渡しているということです。これは、nが何であるかを理解するために、すべてのスレッドが同じ場所を探していることを意味します。したがって、ロック、インクリメント、ロック解除を行っても、すべてのスレッドが同じように動作するのは当然のことです。intの配列を割り当てて、各スレッドに個別の要素を見てもらいます。うまくいけば、重複を排除する必要があります。

そうは言っても、その変更を加えても、改善できることはたくさんあります。全体像の適切な説明については、ベンジャクソンの回答を参照してください。

于 2012-10-18T01:00:24.960 に答える