我可以使用 openMP 和 MPI，并且想知道是否有人遇到过任何洪水填充算法的并行版本（最好在 c 中）。如果没有，我会对如何并行化它的草图感兴趣 - 考虑到它基于递归，它甚至可能吗？
如果您需要刷新关于洪水填充的记忆，维基百科有一篇非常好的文章。
非常感谢您的帮助。
问问题
2717 次
1 回答
5
洪水填充没有“固有”递归，只是为了做一些工作，你需要一些关于先前发现的“边界”单元的信息。如果您这样想，很明显并行性是非常可能的：即使使用单个队列，您也可以使用四个线程（每个方向一个），并且仅在每个线程检查单元格时才移动队列的尾部线。或者等效地，四个队列。以这种方式思考，人们甚至可以想象将空间划分为多个队列——也许是按坐标范围划分的。
一个基本问题是问题定义通常包含一个条件，即永远不会重新访问任何单元格。这意味着每个工作人员都需要一个最新的地图，其中包含已考虑的单元格（全局）。可变的全局信息在性能方面是有问题的，尽管不难想办法限制在全球范围内传播更新的必要性......
于 2013-07-15T01:31:04.787 回答