代码之家 › 专栏 › 技术社区 › David Z

在线程之间划分循环迭代

loops multithreading

David Z · 技术社区 · 17 年前

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,产生了可爱的图形;-)但后来我想,我的计算机上有两个内核,为什么不让这个程序多线程,这样我就可以运行两倍的速度呢?

现在,我的循环总共运行,比方说,大约10亿次计算,我需要一些方法将它们在线程之间分开。我想我应该把计算分为“任务”——比如说最外层循环的每个迭代都是一个任务——并将任务分发给线程。我考虑过

只需给出线程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);
}

8 回复 | 直到 17 年前

Renze de Waal 17 年前

第一种方法很简单。如果期望负载在螺纹上均匀平衡,这也足够了。在某些情况下,特别是如果bin_索引的复杂性非常依赖于参数值,则其中一个线程可能会比其他线程的任务更重。记住:任务在最后一个线程完成时完成。

请注意,将计算放在单独的线程中可能会有问题。当多个线程同时执行bin_索引时,请确保该索引正常工作。小心使用全局或静态变量来获得中间结果。

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

sharptooth 17 年前

除非你真的看到你需要这个,否则不要开始让事情复杂化。同步问题(特别是在多线程而不是多进程的情况下)可能非常痛苦。

Adrian Grigore 17 年前

据我所知, OpenMP 虽然我不得不承认我自己还没有使用过它,但它只是为你正在尝试做的事情而设计的。基本上,它似乎可以归结为只包含一个标题并添加一个pragma子句。

你也可以用英特尔的 Thread Building Blocks 图书馆

Jérôme 17 年前

默认情况下,该库现在包含在gcc中

在您的示例中,您只需添加以下pragma:

#pragma omp parallel shared(histogram)
{
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;
}

有了这个pragma,编译器将添加一些指令来创建线程,启动它们,在访问 histogram

当然,结果不应该是最优的,就好像你用手工编码一样。但如果您没有负载平衡问题,您可能会接近2倍的速度。实际上,这只是写在矩阵中,没有空间依赖关系。

FryGuy 17 年前

void HistogramThread(int i1, Action<int[]> HandleResults)
{
    int[] histogram = new int[HistogramSize];

    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;

    HandleResults(histogram);
}

int[] CalculateHistogram()
{
    int[] histogram = new int[HistogramSize];

    ThreadPool pool; // I don't know syntax off the top of my head
    for (int i1=0; i1<N; i1++)
    {
       pool.AddNewThread(HistogramThread, i1, delegate(int[] h)
       {
           lock (histogram)
           {
               for (int i=0; i<HistogramSize; i++)
                   histogram[i] += h[i];
           }
       });
    }
    pool.WaitForAllThreadsToFinish();

    return histogram;
}

这样你就不需要共享任何内存,直到结束。

bzlm 17 年前

如果您曾经在.NET中这样做,请使用 Parallel Extensions .

Dan Fish 17 年前

如果您想编写多线程数字处理代码(将来您将要做很多),我建议您考虑使用像OCaml或Haskell这样的函数式语言。

Joe Soul-bringer 17 年前

您的单线程应用程序正在持续分配内存。要获得任何加速,您的几个线程还需要不断地分配给内存。如果一次只分配一个线程,您将不会得到任何加速。因此,如果你的作业受到保护,整个练习就会失败。

危险的 方法,因为您在没有保护的情况下分配给共享内存。但这似乎值得冒险(如果x2加速很重要的话)。如果可以确定bin_index(i1、i2、i3、i4)的所有值在循环的划分中都是不同的,那么它应该可以工作,因为数组分配将被分配到共享内存中的不同位置。尽管如此,我们还是应该认真研究这样的方法。

编辑:

查看您的bin_索引(i1、i2、i3、i4),我怀疑您的流程如果不付出相当大的努力就无法并行化。