在线程之间划分循环迭代

Question

我最近编写了一个小数字运算程序,它基本上遍历一个N维网格,并在每个点执行一些计算.

for (int i1 = 0; i1 < N; i1++)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        histogram[bin_index(i1, i2, i3, i4)] += 1; // see bottom of question

它运行良好,yadda yadda yadda,可爱的图形结果;-)然后我想,我的计算机上有2个核心,为什么不让这个程序多线程,所以我可以运行它两倍的速度？

现在,我的循环总共运行了大约十亿次计算,我需要一些方法将它们分散在线程中.我想我应该将计算分组为"任务" - 比如最外层循环的每次迭代都是一项任务 - 然后将任务分发给线程.我考虑过了

• 只给线程#n最外层循环的所有迭代i1 % nthreads == n- 基本上预先确定哪些任务进入哪些线程
• 尝试设置一些互斥保护变量,该变量保存i1下一个需要执行的任务的参数(在本例中) - 动态地将任务分配给线程

有什么理由选择一种方法而不是另一种方法？还是我没想过的另一种方法？它甚至重要吗？

顺便说一下,我用C编写了这个特定的程序,但我想我也会在其他语言中再做同样的事情,所以答案不一定是C特定的.(如果有人知道用于Linux的C库可以做这种事情,我很想知道它)

编辑:在这种情况下bin_index是一个确定性函数,除了它自己的局部变量之外不会改变任何东西.像这样的东西:

int bin_index(int i1, int i2, int i3, int i4) {
    // w, d, h are constant floats
    float x1 = i1 * w / N,  x2 = i2 * w / N, y1 = i3 * d / N, y2 = i4 * d / N;
    float l = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + h * h);
    float th = acos(h / l);
    // th_max is a constant float (previously computed as a function of w, d, h)
    return (int)(th / th_max);
}

(虽然我很感谢所有的评论,甚至那些不适用于确定性的bin_index的评论)

Answer 1

第一种方法很简单。如果您希望负载在线程上均匀平衡，那么这也足够了。在某些情况下，特别是如果 bin_index 的复杂性非常依赖于参数值，则其中一个线程可能会比其他线程执行更繁重的任务。请记住：当最后一个线程完成时，任务就完成了。

第二种方法稍微复杂一些，但如果任务足够细粒度（任务数量远大于线程数量），则可以更均匀地平衡负载。

请注意，将计算放在单独的线程中可能会遇到问题。确保 bin_index 在多个线程同时执行时正常工作。请注意对中间结果使用全局或静态变量。

此外，“histogram[bin_index(i1, i2, i3, i4)] += 1”可能会被另一个线程中断，导致结果不正确（如果赋值获取该值，递增该值并将结果值存储在大批）。您可以为每个线程引入一个本地直方图，并在所有线程完成时将结果合并为一个直方图。您还可以确保只有一个线程同时修改直方图，但这可能会导致线程在大多数情况下相互阻塞。