我正在编写一个程序来计算国际象棋变体的残局表库。填充表库的算法是这样工作的:
- 从一个巨大的数组开始
unsigned char
,每个成员代表一个位置(我们总是假设轮到白方)。一个数组成员即使位置输了,如果它赢了,它是奇数,如果它是0xff
无效的,0xfe
如果它是平局。 - 遍历数组,用 标记每个非法位置,与
0xff
白色配对的每个位置以及用 标记0x00
所有其他位置0x0fe
。 - 遍历数组,只考虑标记的位置
0xfe
。检查是否有移动导致数组成员为偶数的位置,如果有,则将1加上该位置的编号写入当前位置对应的成员中。如果所有动作都指向奇数表示的位置(即这是一个失败的位置),则将该位置标记为这些数字中的最高值的一加,以表明最强的防守需要多长时间。 - 重复第三步,直到数组不再改变。
为了速度,我想并行化第三步。仔细阅读会发现,在每次迭代中,我们只会将一个值(迭代次数)写入数组。以下策略获得:
- 将数组拆分为n 个部分,让一个线程处理每个部分。让当前迭代为i。
- 如果一个线程必须从数组中读取一个成员并且它等于i,则将其视为设置为,
0xfe
因为这意味着该成员只是由另一个线程同时写入。
现在显然这个程序中有一个竞争条件,但这没关系,因为如果没有任何粉红色的大象char
(如果 a以原子方式编写,则不存在),我们总是能得到正确的结果。但是,由于理论上存在竞争条件,C 编译器可能会声明我的程序未定义并格式化我的硬盘。
在不违反 C 内存模型的任何约束并且不会导致严重减速(例如通过添加锁)的情况下,我可以做些什么来并行化该算法?
简化的问题描述
这是一个简化的算法,它演示了相同的概念,但去掉了所有不重要的东西:
- 从数组开始
unsigned char a[n]
。每个数组成员为 0 或 1。 - 对于设置为 0 的每个数组成员:如果其他一些数组成员等于 0 或 2,则将此数组成员设置为 2。检查的数组成员取决于我们要更新的数组成员的索引。索引和我们需要检查的数组成员之间没有简单的关系,它本质上是随机的。
由于我们只将 0 更改为 2,因此我们处理数组条目的顺序无关紧要,即使在技术上并行执行时存在竞争条件(因为我们同时读取/写入同一个对象) . 我如何告诉编译器它不应该在不牺牲性能的情况下关心竞态条件?