二次算法的并行化

Question

假设我有一个N个元素的向量(数组,列表,等等......)V,假设V ₀到V _(N-1).对于每个元素V _i,需要针对每个索引j计算函数f(V _i,V _j)(包括情况i = j).该函数是对称的,因此一旦计算出f(V _i,V _j),就不需要重新计算f(V _j,V _i).然后我们对函数进行N(N + 1)/ 2次总评估,使其成为O(N ²)算法.让我们假设计算f所花费的时间相对较长但是一致.

现在,我想并行执行算法.我需要确定(某些M个)工作线程的调度,以便两个线程不会同时使用相同的内存部分(即相同的元素).例如,f(V ₁,V ₂)可以与f(V ₃,V ₄)平行评估,但不与f(V ₂,V ₃)平行.工作流程分为几个步骤,每个步骤,每个工作线程执行一次f的评估.然后线程被同步,之后它们继续进行下一步,依此类推.

问题是,我如何确定(最好是最佳)每个线程的时间表作为一系列索引对(i,j),以便解决完整的问题(即考虑到对称性,每个索引对只访问一次)？虽然直接答案当然是好的,但我也很欣赏指向算法甚至相关网站/文献的指针.

Answer 1

这让我想起了一个常见的体育赛程安排问题:在N队的联赛中,安排N-1个比赛日,这样每个队伍每天都有一场比赛,每场比赛一次.

下棋,对这个问题有一个很有说服力的解决方案.将所有电路板并排排列在长桌上.一名球员总是在同一把椅子上.其他玩家在跳过该玩家的同一方向围绕桌子旋转.