是否有并行洪水填充实施？

Question

我有openMP和MPI供我使用,并且想知道是否有人遇到任何泛洪填充算法的并行版本(最好是在c中).如果没有,我会对如何进行并行化的草图感兴趣 - 它是否可能基于递归？

维基百科有一篇非常好的文章,如果你需要在洪水填充上刷新你的记忆.

非常感谢您的帮助.

Answer 1

洪水填充没有“固有的”递归，只是要做一些工作，您需要一些有关先前发现的“边界”单元的信息。如果您以这种方式考虑，那么很明显并行是非常可能的：即使只有一个队列，您也可以使用四个线程（每个方向一个线程），并且仅当每个单元都检查了单元格时才移动队列的尾部。线。或等同地，四个队列。以这种方式思考，甚至​​可以想象将空间划分为多个队列-也许是由坐标范围存储的。

一个基本问题是，问题定义通常包括以下条件：没有单元被重新访问。这意味着每个工作人员都需要一张最新的地图，其中已经（全局）考虑了这些单元。可变的全球信息在性能上是有问题的，尽管不难想出办法来限制在全球传播更新的必要性...