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_explicit和atomic_store_explicit操作具有较弱内存顺序的操作（即memory_order_relaxed在您的示例中）

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