c++ - 如何有效地并行设置位 vector 的位？

Question

考虑 N 的位 vector 其中的位( N 很大)和 M 的数组数字( M 中等，通常比 N 小得多)，每个都在 0..N-1 范围内指示 vector 的哪一位必须设置为 1 .后一个数组未排序。位 vector 只是一个整数数组，特别是 __m256i ，其中每个 __m256i 被打包成 256 位结构体。

如何在多个线程中有效地拆分这项工作？

首选语言是C++(MSVC++2017工具集v141)，汇编也很棒。首选 CPU 是 x86_64(内在没问题)。如果有任何好处，则需要 AVX2。

Answer 1

假设您想将这项工作分配给 T线程。这是一个非常有趣的问题，因为它不能通过分区简单地并行化，并且各种解决方案可能适用于不同大小的 N和 M .

完全并发基线

您可以简单地分割数组 M进入 T分区并让每个线程在自己的 M 分区上工作与共享 N .主要问题是因为M未排序，所有线程都可以访问 N 的任何元素因此跺脚彼此的工作。为了避免这种情况，您必须使用诸如 std::atomic::fetch_or 之类的原子操作。对于共享 N 的每次修改数组，或者想出一些锁定方案。这两种方法都可能会降低性能(即，使用原子操作设置位可能比等效的单线程代码慢一个数量级)。

让我们看看可能更快的想法。

私有(private)N

避免需要对 N 的所有突变进行原子操作的“共享 N”问题的一个相对明显的想法是简单地给每个 T 一个 N 的私有(private)拷贝，并在最后通过 or 合并它们。 .

不幸的是，这个解决方案是 O(N) + O(M/T)而原来的单线程解决方案是 O(M)上面的“原子”解决方案类似于 O(M/T) 4.既然我们知道N >> M在这种情况下，这可能是一个糟糕的权衡。不过，值得注意的是，每一项中的隐藏常量非常不同:O(N)来自合并 step0 的术语可以使用 256 位宽 vpor指令，意味着吞吐量接近 200-500 位/周期(如果缓存)，而位设置步骤是 O(M/T)我估计接近 1 位/周期。因此，即使 N 的大小，这种方法肯定是中等 T 的最佳方法。是 M 大小的 10 或 100 倍.

M的分区

这里的基本思想是对 M 中的索引进行分区。这样每个工作线程就可以在 N 的不相交部分上工作大批。如 M已排序，那将是微不足道的，但事实并非如此，所以......

一个简单的算法，如果 M 运行良好平滑分布到第一个分区 M 的值进入 T存储桶，其中存储桶的值在 [0, N/T), [N/T, 2N/T], ..., [(T-1)N/T, N) 范围内.即除N进入 T不相交的区域，然后找到 M 的值落入他们每个人。您可以将这项工作传播到 T通过为每个线程分配相等大小的块 M ，并让他们各自创建 T分区，然后在最后将它们逻辑合并 1，这样您就有了 T M 的分区.

第二步是实际设置所有位:为每个线程分配一个分区 T它可以以“单线程”方式设置位，即不用担心并发更新，因为每个线程都在 N 的不相交分区上工作2.

两个步骤 O(M)并且第二步与单线程情况相同，因此并行化的开销是第一步。我怀疑第一个的速度范围从与第二个大致相同的速度到可能慢 2-4 倍，具体取决于实现和硬件，因此您可以期望在具有许多内核的机器上加速，但只有 2 或 4 个可能不会更好。

如分布M不平滑，因此在第一步中创建的分区具有非常不同的大小，它会工作得很糟糕，因为某些线程会得到更多的工作。一个简单的策略是创建 say 10 * T分区，而不仅仅是 T并让第二遍中的线程都从相同的分区队列中消耗，直到完成。通过这种方式，您可以更均匀地分配工作，除非数组 M非常拥挤。在这种情况下，您可能会考虑对第一步进行细化，它首先基本上创建元素的分桶直方图，然后是一个减少阶段，该阶段查看组合直方图以创建良好的分区。

本质上，我们只是逐步将第一阶段细化为一种并行排序/分区算法，对此已有大量文献。您甚至可能会发现完整(并行)排序是最快的，因为它将在位设置阶段非常有帮助，因为访问将按顺序进行并且具有最佳的空间局部性(分别有助于预取和缓存)。

0 ... 也来自“分配长度为 N 的私有(private)数组”步骤，尽管这可能非常快。

1 概念上最简单的合并形式是简单地复制每个线程的 M 分区，这样您就拥有了所有 M 的连续分区。 ，但在实践中，如果分区很大，您可以将分区留在原处并将它们链接在一起，这会给使用代码增加一些复杂性，但避免了压缩步骤。

2 从线程的角度来看，要使其真正不相交，您需要确保N 的分区。落在“字节边界”上，甚至缓存行边界上以避免错误共享(尽管后者可能不是大问题，因为它只发生在每个分区的边缘，并且处理顺序意味着您不太可能发生争用)。

4 在实践中，使用共享的基线并发解决方案的确切“顺序”N很难定义，因为会有争用，所以 O(M/T)如果足够大，缩放会分解 T .如果我们假设 N相当大和T仅限于最多十几个核心的典型硬件并发，因此它可能是一个不错的近似值。