エラトステネスの同時ふるいアルゴリズムが逐次バージョンより遅いのはなぜですか?

エラトステネスによる素数は同時実行より逐次的に速い?

一般に、同時実行アルゴリズムは逐次アルゴリズムよりも高速であると考えられています。ただし、指定されたコードでは、エラトステネスのふるいアルゴリズムの同時バージョンは逐次バージョンよりも遅くなります。この記事では、この予期しない結果の背後にある理由を調査し、提供されたコードの潜在的な問題を強調し、順次実装と同時実装の両方のパフォーマンスを向上させるためのいくつかの最適化を提案します。

コード分析

順次実装

PrimesSeq クラスは、エラトステネスのふるいアルゴリズムの逐次バージョンを実装します。バイト配列 bitArr を使用してふるいを表します。配列内の各ビットは数値を表し、ビットが設定されている場合、その数値は非素数としてマークされます。このアルゴリズムは、2 から開始してふるいを繰り返し、現在の数値のすべての倍数を非素数としてマークします。 isPrime 関数は、ふるい内の対応するビットが設定されていないかをチェックすることで、数値が素数であるかどうかをチェックします。 printAllPrimes 関数は、アルゴリズムによって検出されたすべての素数を出力します。

同時実装

PrimesPara クラスは、エラトステネスのふるいアルゴリズムの同時バージョンを実装します。ふるいを複数のチャンクに分割し、各チャンクを別個のスレッドに割り当てます。各スレッドは、それに割り当てられた数値の倍数を非素数としてマークする責任があります。メインスレッドは、初期プライムの生成とスレッドの開始を担当します。 crossOut 関数は、数値を非素数としてマークするために使用されます。 generateErastothenesConcurrently 関数は素数を同時に生成します。

パフォーマンスの比較

指定されたコードでは、アルゴリズムの同時バージョンは逐次バージョンよりも約 10 倍遅くなります。通常、同時アルゴリズムは逐次アルゴリズムより高速であるため、これは予想外です。

同時実装のボトルネック

提供されたコードには潜在的なボトルネックがいくつかあります。

• スレッドの作成と同期のオーバーヘッド: 複数のスレッドの作成と同期にはコストがかかる場合があります。この場合、同時実装により sieve のチャンクごとにスレッドが作成され、大幅なオーバーヘッドが追加される可能性があります。
• 偽共有: 複数のスレッドが同じメモリ位置にアクセスすると、それらのスレッドが干渉する可能性があります。相互に影響し、パフォーマンスの低下を引き起こします。この場合、スレッドは bitArr 配列を共有するため、誤った共有が発生する可能性があります。
• 負荷の不均衡: ふるいがスレッド間で均等に分割されていない場合、一部のスレッドでより多くの作業が発生する可能性があります。

最適化

順次実装と同時実装の両方に適用できる最適化がいくつかあります。

• より効率的なデータ構造を使用する: ふるいを表すためにバイト配列を使用する代わりに、ビットセットやスパース配列などのより効率的なデータ構造を使用できます。これにより、メモリ使用量が削減され、パフォーマンスが向上します。
• スレッドの作成と同期のオーバーヘッドを削減します: 可能であれば、使用するスレッドの数を減らして、スレッドの作成と同期のオーバーヘッドを最小限に抑える必要があります。
• フォールス シェアリングを減らす: フォールス シェアリングは、パディングを使用するか、フォールス シェアリングの影響を受けない別のデータ構造を使用することで減らすことができます。
• 負荷のバランスをとる: すべてのスレッドが実行する作業量がほぼ同じになるように、ふるいをスレッド間で均等に分割する必要があります。

結論

一般に、同時アルゴリズムは順次アルゴリズムよりも高速です。場合によっては、逐次アルゴリズムの方が高速である可能性があります。エラトステネスの篩アルゴリズムの場合、スレッドの作成と同期、フォールス シェアリング、負荷の不均衡のオーバーヘッドが同時実行のメリットを上回る可能性があります。

この記事で説明する最適化を適用することで、次のことが可能になります。エラトステネスのふるいアルゴリズムの逐次実装と同時実装の両方のパフォーマンスを向上させます。

以上がエラトステネスの同時ふるいアルゴリズムが逐次バージョンより遅いのはなぜですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。