是否有一個平行的洪水填充實施？

Question

我有我的openMP和MPI，並想知道是否有人遇到過任何洪水填充算法（最好在c）的並行版本。如果沒有，我會對如何平行化草圖感興趣 - 它是否有可能基於遞歸？

如果您需要刷新洪水填充的內存，維基百科的相當不錯article。

非常感謝您的幫助。

Answer 1

洪水填充沒有什麼「內在」遞歸，只是爲了做一些工作，您需要一些關於先前發現的「邊界」單元的信息。如果你這樣想，很明顯並行性是非常可能的：即使只有一個隊列，也可以使用四個線程（每個方向一個線程），並且只在每個單元檢查完單元后才移動隊列的尾部線。或相當於四個隊列。用這種方式思考，人們甚至可以想象將空間分割成多個隊列 - 也許是座標範圍。

一個基本的問題是，問題定義通常包括沒有細胞再次訪問的前提條件。這意味着每個工作人員需要一個最新的地圖（全局）考慮哪些單元格。可變全局信息在性能方面存在問題，儘管不難想出限制全球傳播更新的必要性的方法......