假设您想将此工作划分为多个T线程。这是一个非常有趣的问题，因为它是不平凡并行通过划分和不同的解决方案，可申请不同大小的N和M。

完全并行基准

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

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

私人N

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

不幸的是，这种解决方案是O(N) + O(M/T)原来的单线程解决方案，O(M)而上面的“原子”解决方案是O(M/T)4。因为我们知道N >> M在这种情况下这可能是一个较差的权衡。仍然需要注意的是，每个术语中的隐藏常数都非常不同：O(N)来自合并步骤0的术语可以使用256位宽的vpor指令，这意味着吞吐量接近200-500位/周期（如果已缓存）
），而O(M/T)我估计的位设置步骤接近1位/周期。因此，即使大小为N的10或100倍，这种方法对于中度T当然也可能是最好的方法M。

M的分区

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

一种简单的算法（如果 平滑分布的 话M）会很好 地 工作：首先将的值划分为M多个T存储桶，其中存储桶的值在range内[0, N/T), [N/T, 2N/T], ..., [(T-1)N/T, N)。也就是说，N分成T不相交的区域，然后找到M属于每个区域的值。您可以通过为T每个线程分配相等大小的块M，并让它们每个创建T分区，然后在
逻辑上将 它们1 合并 在一起，从而在上T分配分区，从而将工作分散到各个线程中M。

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

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

如果的分布M不 平滑 ，使得第一步中创建的分区大小非常不同，则它将工作不佳，因为某些线程将承担更多的工作。一个简单的策略是创建10 * T而不是仅创建分区，T并让第二遍中的线程全部从相同的分区队列中消耗直到完成。这样，您可以更均匀地分散工作，除非阵列M非常集中。在这种情况下，您可以考虑对第一步进行优化，首先从本质上创建元素的桶状直方图，然后在reduce阶段查看组合的直方图以创建良好的分区。

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

0 …，也可以从“分配长度为N的私有数组”步骤开始，尽管这可能非常快。

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

2要使其真正与线程分离，您要确保将分区划分为N“字节边界”，甚至还可以确保缓存行边界以避免虚假共享（尽管后者可能不是大问题，因为它仅发生在每个分区的边缘，并且处理的顺序意味着您不太可能争用。

4在实践中，N很难使用共享定义基线并发解决方案的确切“顺序”，因为将存在争用，因此O(M/T)缩放比例将分解得足够大T。如果我们假设N它很大，T并且仅限于最多十二个内核的典型硬件并发性，那么大概是可以的。