如何有效地并行设置位向量的位？

Question

考虑其中的位向量N(N大)和M数字数组(M中等,通常小得多N),每个都在范围内0..N-1指示必须将向量的哪个位设置为1.后一个数组未排序.位向量只是一个整数数组,具体而言__m256i,每个__m256i结构中包含256位.

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

首选语言是C++(MSVC++ 2017工具集v141),汇编也很棒.首选CPU是x86_64(内在函数没问题).如果有任何益处,AVX2是理想的.

Answer 1

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

完全并发基线

您可以简单地将数组划分M为多个分区，并让每个线程在其自己的共享T分区上工作。主要问题是，由于未排序，所有线程都可以访问 的任何元素，从而破坏彼此的工作。为了避免这种情况，您必须使用原子操作，例如对共享数组的每次修改，或者提出一些锁定方案。这两种方法都可能会降低性能（即，使用原子操作来设置位可能比等效的单线程代码慢一个数量级）。MNMNstd::atomic::fetch_orN

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

私人N

避免“共享 N”问题（需要对 N 的所有突变进行原子操作）的一个相对明显的想法是简单地为每个 T 提供 N 的私有副本，并在最后通过 合并它们or。

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

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²的不相交分区上工作。

这两个步骤O(M)和第二步与单线程情况相同，因此并行化的开销是第一步。我怀疑第一个速度与第二个速度大致相同，也可能慢 2-4 倍，具体取决于实现和硬件，因此您可以期望在具有多个内核的计算机上获得加速，但如果只有 2 或 4 个内核，则可能会加速不会有任何好转。

如果 的分布M不平滑，使得第一步中创建的分区大小差异很大，那么它的工作效果就会很差，因为某些线程会承担更多的工作。一个简单的策略是创建10 * T分区，而不是仅创建分区T，并让第二遍中的线程全部消耗同一分区队列中的资源，直到完成。通过这种方式，您可以更均匀地分散工作，除非阵列M非常拥挤。在这种情况下，您可能会考虑对第一步进行细化，首先本质上创建元素的分桶直方图，然后是减少阶段，查看组合直方图以创建良好的分区。

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

⁰ ...并且还来自“分配长度为 N 的私有数组”步骤，尽管这可能相当快。

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

²为了使其从线程的角度真正脱节，您需要确保分区N落在“字节边界”上，甚至可能是缓存行边界上，以避免错误共享（尽管后者可能不是一个大问题，因为它仅发生在每个分区的边缘，处理顺序意味着您不太可能出现争用）。

⁴在实践中，使用共享的基线并发解决方案的确切“顺序”N很难定义，因为会出现争用，因此O(M/T)当足够大时，扩展将会崩溃T。如果我们假设N相当大并且T仅限于最多十几个核心的典型硬件并发性，那么这可能是一个不错的近似值。