multithreading - 多线程洪水填充

Question

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

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

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

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

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

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

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

Answer 1

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

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

至于你的具体问题，我不得不承认，我对洪水填充算法并不熟悉，所以我不能立即勾勒出一个粗略的方法。

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

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

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

无锁实现 could be several times faster .

如果您使用 Java Java Concurrency in Practice by Goetz是一本关于锁 strip 化之类的好书。