multithreading - 多线程洪水填充

Question

我正在尝试将现有的单线程洪水填充算法转换为多线程算法。

输入: - 二维位数组及其暗淡 - 填充开始的 xy 坐标

输出: - 具有更新位的相同二维位数组

问题: - 当时只有 1 个线程可以写入数组中给定的 64 位(8x8 像素)，也没有其他线程可以在写入时读取此 64 位 block

我已经开始使用队列方法和线程池，因此一旦线程完成其工作，它就可以从队列中获取另一个任务。

您将如何组织符合“问题”语句的线程同步？

主要问题是如何将读/写锁分配给给定的内存块？

Answer 1

通常，您希望尽可能粗略地划分数据并最大限度地减少线程之间的通信。通信包括共享数据结构，甚至是无锁数据结构。特别是那些有具有写访问权限的共享变量的地方。

上述一般“粗略”策略避免了阻止扩展的常见陷阱(例如 false sharing )。

至于您的具体问题，我必须承认，我对洪水填充算法并不熟悉，因此我无法立即制定出粗略的方法。

但是，如果粗略方法不可行并且需要锁定单个单元格的策略，lock striping在这种情况下可能是一种值得研究的方法。

无锁实现是另一种可能性。如果另一个线程在同一个 8x8 像素 64 位 block 中写入，则可以使用比较和交换类型操作结合重试逻辑来执行写入(VS 上的 InterlockedCompareExchange64)。

完全放松读锁定是可能的。如果两个线程最终绘制相同的像素，它可能只会浪费一些周期，但不会破坏结果。

无锁实现 could be several times faster .

如果您使用 Java Java Concurrency in Practice by Goetz是一本关于锁条纹等内容的好书。