どのアルゴリズムが並列プロセッサで動作するときに最適ですか？

Question

複数のプロセッサを搭載したマシンで大きな問題を解決しようとすると、どのアルゴリズムがこの問題を解決するのに最適でしょうか？

ダイナミックプログラミング、貪欲または分裂と征服のアルゴリズムですか？

Answer 1

これは非常に幅広い質問であり、解決しようとしている特定の問題に依存しますが、アルゴリズムがそのステップを並行して実行できるかどうかについては、これは、1つのステップの結果が別のステップの結果に依存しない場合にのみ実行できます。

• ここでは欲張りアルゴリズムについては何も言えません。それらは、ローカルで最良の次のステップをとることとしてのみ定義されています。
• 分割と征服では、問題を別々の部分に分割します。それぞれの部分は個別に解決できます。したがって、これはしばしば並行して実行するのに適しています。
• 動的プログラミングはある種の分割と征服と見ることができますが、今は問題の小さな部分を解決しており、それを使って大きな部分を解決するなどです。たとえば、ナップザックの問題は、動的プログラミングのユースケースとしてよく使用されます。小さなナップザックから始めて問題を解決し、そこからソリューションを構築することができます。ここで問題となるのは、各ソリューションがより小さな問題の解決に依存していることです。個々のステップをスレッド間で分割できない限り、これを並列化することはできません。

一般に、分裂と征服は、物事を並行して実行するための最善の策と思われます。

Answer 2

ダイナミックプログラミングでは、個々のソリューションを探しているスレッド間で同期させる必要がある配列を使用します。

グリーディは一種のシングルスレッドです。マルチスレッド化することはできますが、大きな利点はありません。とにかく、スレッドプールを使って最高5つのマッチでショットすることができます。これは実装が最も簡単です。

分割と征服は再帰的です。新しいスレッドを生成するにはまだ同期が必要ですが、複数のプロセッサの利点をはっきりと取ることができます。マルチスレッドを実装するのが2番目に簡単な方法だと思います。

解決する必要がある問題の性質によって、プロセッサコア番号ではなく、どのプログラミング方法を使用するかが決まります。

スレッド間のコンテキスト切り替えにかかる時間も考慮してください。