是否有并行的洪水填充实施方案? [英] Is there a parallel flood fill implementation?

问题描述

我可以使用openMP和MPI，并且想知道是否有人遇到了任何泛洪填充算法的并行版本(最好在c中).如果没有，我会对如何并行化草图感兴趣-甚至可以基于递归给出它吗?

I've got openMP and MPI at my disposal, and was wondering if anyone has come across a parallel version of any flood fill algorithm (preferably in c). If not, I'd be interested in sketches of how to do parallelise it - is it even possible given its based on recursion?

如果您需要刷新洪水记录，则Wikipedia有一个相当不错的文章.

Wikipedia's got a pretty good article if you need to refresh your memory on flood fills.

非常感谢您的帮助.

推荐答案

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

There's nothing "inherently" recursive about flood-fill, just that to do some work, you need some information about previously-discovered "frontier" cells. If you think of it that way, it's clear that parallelism is eminently possible: even with a single queue, you could use four threads (one for each direction), and only move the tail of the queue when the cell has been examined by each thread. or equivalently, four queues. thinking in this way, one might even imagine partitioning the space into multiple queues - bucketed by coordinate ranges, perhaps.

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

one basic problem is that the problem definition usually includes the proviso that no cell is ever revisited. this implies that each worker needs an up-to-date map of which cells have been considered (globally). mutable global information is problematic, performance-wise, though it's not hard to think of ways to limit the necessity for propagating updates globally...

这篇关于是否有并行的洪水填充实施方案?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！