multithreading - 成对并行循环

Question

C++11 中在多线程中执行成对计算的最佳方法是什么？我的意思是，我有一个元素向量，我想为每对不同元素计算一个函数。需要注意的是，我不能同时在多个线程中使用相同的元素，例如元素的状态在计算过程中不断变化，计算依赖于此。

Answer 1

一种简单的方法是按偏移量对这些对进行分组。

如果 v 是向量，则元素 N 相距 (mod v.size()) 形成两个对的集合。每个对的集合本身都不包含重叠。

检查 10 元素向量 0 1 2 3 4 5 6 7 8 9。 1 相隔的对是:

0 1, 1 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 8, 8 9, 9 0

如果您通过“奇偶校验”将它们分成两个集合，我们会得到:

0 1, 2 3, 4 5, 6 7, 8 9 
1 2, 3 4, 5 6, 7 8, 9 0

您可以并行处理上述每个集合。收集完成后，同步，然后处理下一个收集。

类似的技巧适用于 2 个不同的人。

0 2, 1 3, 4 6, 5 7
2 4, 3 5, 6 8, 7 9

还有剩菜:

8 0, 9 1

对于从 1 到 n/2 的每个偏移量，都有 2 个“集合”和剩余部分。

这里是 4 的偏移量:

0 4, 1 5, 2 6, 3 7
4 8, 5 9, 6 0, 7 1

还有剩菜

8 2, 9 3

(我天真地认为剩菜的大小是向量大小 mod 偏移量)

计算这些集合(以及剩余的)并不难；安排线程排队并在正确的线程中有效地获取正确的任务更加困难。

有 N 个选择 2，或 (n^2+n)/2 对。这种分割为您提供了 O(1.5n) 个集合和剩余元素，每个集合的大小最多为 n/2，并且每个集合内都具有完全并行性。

<小时/>

如果您遇到某些元素比其他元素昂贵得多的情况，因此等待每个集合完成会导致过多的空闲线程，您可以添加细粒度同步。

维护原子 bool 向量。使用它来指示您当前正在处理一个元素。始终“锁定”(设置为 true，并在设置为 true 之前检查它是否为 false)较低的索引在较高的索引之前。

如果您设法锁定两者，请处理掉。然后清除它们。

如果失败，请记住该任务以供稍后使用，并继续执行其他任务。当排队的任务太多时，请等待条件变量，尝试检查并设置要在 spin-lambda 中锁定的原子 bool 值。

清除锁时定期启动条件变量。您执行此操作的频率取决于分析。您可能可以在不获取互斥体的情况下踢出(但有时您必须在清除 bool 值后获取互斥体以处理可能导致线程饥饿的竞争条件)。

按照上述收集系统指示的顺序对任务进行排队，这样可以减少线程冲突的可能性。但有了这个系统，即使有一项任务落后了，工作仍然可以进行。

它增加了复杂性和同步性，这很容易使其比纯集合/群组慢。