2.6.1 素数を発見するためのプログラム

次のファイル omp_prime.c のスレッドは、is_prime() 関数を実行することによって整数が素数であるかどうかをチェックします。

11 int is_prime(int v)
    12 {
    13     int i;
    14     int bound = floor(sqrt ((double)v)) + 1;
    15      
    16     for (i = 2; i < bound; i++) {
    17         /* 判定済み合成数のチェックは不要 */ 
    18         if (!pflag[i]) 
    19             continue;
    20         if (v % i == 0) { 
    21             pflag[v] = 0;
    22             return 0;
    23         }
    24     }
    25     return (v > 1); 
    26 }

スレッドアナライザは、行 21 の pflag[] への write と行 18 の pflag[] の read との間にデータ競合があると報告します。ただし、このデータ競合は、最終結果の正確さに影響しないため良性です。行 18 では、スレッドが、与えられた i 値について、pflag[i] がゼロかどうかをチェックします。pflag[i] がゼロの場合は、i は既知の合成数 (言い換えると、i は非素数になることで知られている) であることを意味します。このため、v が i で割り切れるかどうかをチェックする必要はなく、v が何らかの素数で割り切れるかどうかをチェックすればよいだけです。その結果、pflag[i] がゼロの場合、スレッドは次の i 値に進みます。pflag[i] がゼロでなく、かつ v が i で割り切れる場合、スレッドは pflag[v] にゼロを代入して、v が素数ではないことを示します。

正確さの観点からは、複数のスレッドが同じ pflag[] 要素をチェックし、その要素に同時に書き込みを行うことは重要ではありません。pflag[] 要素の初期値は 1 です。スレッドは要素の更新時に、その要素にゼロを代入します。すなわち、スレッドは、その要素用の同じメモリーバイト内の同じビットにゼロをストアします。現在のアーキテクチャーでは、そうしたストアは不可分 (アトミック) とみなして差し支えありません。このことは、スレッドによるその要素の読み取り時、読み取られる値は 1 かゼロのいずれかであることを意味します。 pflag[] 要素に値ゼロが代入される前に、要素のチェックが行われる (行 18) と、スレッドは行 20 〜 23 を実行します。その間、別のスレッドが同じ pflag[] 要素にゼロを代入しても (行 21)、最終結果は変わりません。基本的に、このことは、最初のスレッドによる行 20 〜 23 の実行が不必要だったことを意味します。