私は自由に使える openMP と MPI を持っており、フラッド フィル アルゴリズムの並列バージョン (できれば c) に遭遇した人がいるかどうか疑問に思っていました。そうでない場合は、それを並列化する方法のスケッチに興味があります-再帰に基づいていることを考えると、それは可能ですか?
フラッド フィルに関する記憶をリフレッシュする必要がある場合は、ウィキペディアにかなり良い記事があります。
助けてくれて本当にありがとうございます。
質問する
2717 次
1 に答える
5
フラッドフィルについて「本質的に」再帰的なものは何もありません。作業を行うには、以前に発見された「フロンティア」セルに関する情報が必要なだけです。そのように考えると、並列処理が非常に可能であることは明らかです。キューが 1 つの場合でも、4 つのスレッド (各方向に 1 つ) を使用し、セルが各スレッドによって検査されたときにのみキューの末尾を移動できます。スレッド。または同等に、4 つのキュー。このように考えると、スペースを複数のキューに分割することを想像することさえできます。おそらく、座標範囲によってバケット化されます。
基本的な問題の 1 つは、通常、問題の定義にセルを再訪しないという条件が含まれていることです。これは、各ワーカーが (グローバルに) 考慮されたセルの最新のマップを必要とすることを意味します。変更可能なグローバル情報は、パフォーマンスに関して問題がありますが、更新をグローバルに伝播する必要性を制限する方法を考えるのは難しくありません...
于 2013-07-15T01:31:04.787 に答える