如何在n个线程上均匀分配n个对象的全对测试工作？

Question

3

一个典型的单线程循环，遍历了一组包含n个对象的所有可能（无序）对：

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        ProcessPair(i, j);

假设你有 n 个线程可用。实现上述内容的并行处理的显而易见的方法如下：

for (int j = threadIndex + 1; j < n; j++)
    ProcessPair(threadIndex, j);

但是这并不能平均地分配工作到各个线程中。第一个线程将处理 n-1 对，而最后一个线程则不会处理任何一对。

有没有简单的方法可以将 n(n-1)/2 对分成若干部分，以便每个线程处理相同数量的对（±1），并仅根据其 threadIndex 和 n 确定其应该处理哪些对？

这个有趣的问题是我在 GPU 上玩物理学并开始实现 brute force all-pairs collision detection 时遇到的（我知道，我应该使用广义相位算法）。我想组合数系统可能是关键所在，但是我还没想出如何把所有的东西组合起来。

- Trillian

使用一个单独的计数器变量，然后调用 ProcessPair(dispatchCounter % numberOfThreads, i, j) 怎么样？ - zneak

@zneak，我不确定这有什么帮助？目标是对于每个可能的集合{i,j}，其中i≠j，调用一次ProcessPair(i,j)。 - Trillian

一种通用的方法是找到集合 {i,j} 和数字范围 [1..n(n-1)/2] 之间的双射。 - Niklas B.

一个“明显”的双射是 f(i,j) = j - i - 1 + n(n-1)/2 - (n-i)(n-i-1)/2（只是将矩阵单元格从上到下，从左到右进行编号）:P 不幸的是，它比较笨拙，不像 Ehsan 的解决方案那样优雅。 - Niklas B.

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ehsan Kia · Accepted Answer

我对此进行了一些尝试，并得出了一个似乎是正确的解决方案。我没有证明它是否有效或平衡，但按照我的逻辑推断，它在逻辑上似乎是有意义的。

简而言之：如果您处于偶数索引位置，请检查所有比您小的偶数索引和所有比您大的奇数索引。如果您处于奇数索引位置，请检查所有比您小的奇数索引和所有比您大的偶数索引。

很容易看出，每个线程最多会与不超过N/2个其他线程进行比较，因为我们以步长为2遍历整个列表。