7

我正在编写一个程序来计算国际象棋变体的残局表库。填充表库的算法是这样工作的:

  1. 从一个巨大的数组开始unsigned char,每个成员代表一个位置(我们总是假设轮到白方)。一个数组成员即使位置输了,如果它赢了,它是奇数,如果它是0xff无效的,0xfe如果它是平局。
  2. 遍历数组,用 标记每个非法位置,与0xff白色配对的每个位置以及用 标记0x00所有其他位置0x0fe
  3. 遍历数组,只考虑标记的位置0xfe。检查是否有移动导致数组成员为偶数的位置,如果有,则将1加上该位置的编号写入当前位置对应的成员中。如果所有动作都指向奇数表示的位置(即这是一个失败的位置),则将该位置标记为这些数字中的最高值的一加,以表明最强的防守需要多长时间。
  4. 重复第三步,直到数组不再改变。

为了速度,我想并行化第三步。仔细阅读会发现,在每次迭代中,我们只会将一个值(迭代次数)写入数组。以下策略获得:

  • 将数组拆分为n 个部分,让一个线程处理每个部分。让当前迭代为i
  • 如果一个线程必须从数组中读取一个成员并且它等于i,则将其视为设置为,0xfe因为这意味着该成员只是由另一个线程同时写入。

现在显然这个程序中有一个竞争条件,但这没关系,因为如果没有任何粉红色的大象char(如果 a以原子方式编写,则不存在),我们总是能得到正确的结果。但是,由于理论上存在竞争条件,C 编译器可能会声明我的程序未定义并格式化我的硬盘。

在不违反 C 内存模型的任何约束并且不会导致严重减速(例如通过添加锁)的情况下,我可以做些什么来并行化该算法?

简化的问题描述

这是一个简化的算法,它演示了相同的概念,但去掉了所有不重要的东西:

  1. 从数组开始unsigned char a[n]。每个数组成员为 0 或 1。
  2. 对于设置为 0 的每个数组成员:如果其​​他一些数组成员等于 0 或 2,则将此数组成员设置为 2。检查的数组成员取决于我们要更新的数组成员的索引。索引和我们需要检查的数组成员之间没有简单的关系,它本质上是随机的。

由于我们只将 0 更改为 2,因此我们处理数组条目的顺序无关紧要,即使在技术上并行执行时存在竞争条件(因为我们同时读取/写入同一个对象) . 我如何告诉编译器它不应该在不牺牲性能的情况下关心竞态条件?

4

1 回答 1

5

这就是_AtomicC11 中类型限定符的用途。您可以将您的数组声明为

_Atomic unsigned char a[n];

这意味着可以原子地读取或写入数组的每个元素。

在 C11 之前,没有标准的方法来做到这一点,但通常,根据实现,某些数据类型对于读写来说是原子的。要知道它们是什么,您必须查看您正在使用的实现的文档。


请注意,C11_Atomic访问的默认内存顺序是memory_order_seq_cst(顺序一致性),如果您不需要,您可以使用atomic_load_explicitatomic_store_explicit操作具有较弱内存顺序的操作(即memory_order_relaxed在您的示例中)

于 2016-07-25T16:58:25.743 回答