algorithm - すべての分割統治アルゴリズムで並列処理を利用できますか?

Question

私はアルゴリズムの授業を取っていますが、並列処理を利用して分割統治アルゴリズムを実装できるようです。これは常に当てはまりますか？

Answer 1

はい、しかし必ずしも効率的ではありません。

分割統治アルゴリズムは、タスク レベルの並列処理に最適 (理解しやすい) です。これらのタスクは再帰的であり、再帰的なタスクはタスク ツリー階層として説明できます。タスク ツリー階層は、異なるパラメーターを使用した関数の複数の呼び出しとして表示できます。一部の関数呼び出しは、他の実行 (つまり、その子) を待機します。これは、並列の専門用語で *wait*o または結合として使用できます (非同期で実行される場合、または同期実行で直接使用できる場合) (ブロッキング呼び出しは結果を自動的に待機します)。これらの操作はすべて、すべての並列フレームワークで実際に利用できます。

ただし、パラメーターのデータ サイズによっては、並列タスク間の通信にコストがかかる場合があります。問題を小さな部分に分割して分散する (複数のコンピューターで実行する場合はネットワーク経由、またはマルチコア コンピューティングの場合はプロセス間で) と、部分を実行するよりも時間がかかる場合、パフォーマンスは向上しません。実際、パフォーマンスが低下します。

C/C++ での OpenMP のタスクやPython でのSCOOPなどのタスク階層を許可するフレームワークを使用すると、シリアルの分割統治アルゴリズムを対応する並列アルゴリズムに簡単に変換できます(さらに多くのものが利用可能です)。