循环修改增强数据并行性能

Loop Modifications to Enhance Data-Parallel Performance (PDF 226KB)

摘要

在数据并行应用中,相同的独立操作针对不同数据重复执行。循环通常是数据并行应用的最密集计算段,因此循环优化直接影响性能。当面对嵌套循环时,分配给线程的计算粒度将直接影响性能。循环转换如分裂(循环裂变)与合并(循环融合)的嵌套式循环可促使并行化,并提高工作效率。

本文是“英特尔多线程应用开发指南”系列的一部分,该系列介绍了针对英特尔® 平台开发高效多线程应用的指导原则。
 

背景

循环优化为提高数据并行应用性能提供了一个很好的机会。这些优化,例如循环融合、循环交换和循环展开等可帮助改善粒度、负载平衡和数据本地化,同时最大限度地减少同步化和其他并行费用。一般来说,高迭代计数循环为并行化的最佳候选,尤其是当运行线程数量较少时。一个高迭代计数能够实现更好的负载平衡,因为分配给线程的大量任务均具有可用性。然而,仍需考虑每迭代需要完成的工作量。除非另有说明,否则本章节所讨论的内容前提均是假设一个循环内的每个迭代计算量与该循环内的其他迭代计算量(大致)相同。

针对如下示例代码的工作分享结构,考虑使用 OpenMP* 的一个循环场景。当循环迭代分布多于四个线程时,低迭代计数将会导致负载不平衡。 如果一个迭代运行仅需几微秒,那么这种不平衡可能不会造成严重影响。然而,如果每个迭代运行均需一个小时,那么在第四个迭代运行完成时,将会有三个线程处于一小时的闲置状态。与此形成鲜明对比的是具有1003一小时迭代和四个线程的相同循环。在这种情况下,任务执行十天后,一小时的闲置时间就显得微不足道。
 

#pragma omp for
for (i = 0; i < 13; i++)
{...}


 

建议

对于多嵌套式循环,选择最外层循环对于并行化来说最为安全。这种方法通常会生成最为粗糙的粒度。确保工作能够平均分配给每个线程。如果因最外层循环的迭代计数较低而无法实施平均分配,那么具有较大迭代计数的内层循环可能是线程的最佳候选。例如,考虑下面具有四个嵌套循环的代码:
 

void processQuadArray (int imx, int jmx, int kmx,
  double**** w, double**** ws)
{
  for (int nv = 0; nv < 5; nv++)
    for (int k = 0; k < kmx; k++)
      for (int j = 0; j < jmx; j++)
        for (int i = 0; i < imx; i++)
          ws[nv][k][j][i] = Process(w[nv][k][j][i]);
}

采用任何非五个数量的线程,并行外部循环都将会导致负载不平衡和闲置线程。如果阵列维数 imxjmxkmx 非常大的话,那么将会导致非常严重的效率低下问题。并行其中一个内部循环是这种情况下的最好选择。

这是最安全的做法,可避免工作分享结构底端含有隐性障碍。所有 OpenMP 工作分享结构(例如,段、一个)均在结构块底端含有一个隐性障碍。所有线程必须在执行继续之前在此障碍处集合。有时,这些障碍很不必要,并且会给性能带来消极影响。使用 OpenMP nowait 子句来消除这些障碍,如下面这个示例:
 

void processQuadArray (int imx, int jmx, int kmx,
  double**** w, double**** ws)
{
  #pragma omp parallel shared(w, ws)
  {
    int nv, k, j, i;
    for (nv = 0; nv < 5; nv++)
      for (k = 0; k < kmx; k++)
        #pragma omp for nowait
          for (j = 0; j < jmx; j++)
            for (i = 0; i < imx; i++)
              ws[nv][k][j][i] = Process(w[nv][k][j][i]);
  }
}

由于最内层循环的计算都是独立的,因此在进行下一次迭代之前,线程没有必要在隐性障碍处等待。如果每迭代的工作量是不平等的,nowait 子句可使线程继续进行有用工作,而非闲置在隐性障碍处。

如果一个循环带有一种可防止循环被并行执行的循环传递相关性,那么循环体可能会被分裂成单独的循环,进而被并行执行。一个循环体被划分为两个或两个以上的循环被称为“循环分裂”。下面的示例演示了循环分裂过程,一个具有循环传递相关性的循环体创建出新的循环,进而能够被并行执行。
 

float *a, *b;
int i;
for (i = 1; i < N; i++) {
  if (b[i] > 0.0) 
    a[i] = 2.0 * b[i];
  else 
    a[i] = 2.0 * fabs(b[i]);
  b[i] = a[i-1];
}

a 阵列内的元素任务均是独立的,无需考虑相应 b 元素的符号。在 b 中的一个元素的每个任务均独立于其他任务,但却依赖于所需 a 元素的任务完成情况。因此,正如所写的一样,上述循环不能被并行处理。

但是,若将一个循环体分裂成两个独立的操作,这两个操作均可被并行执行。例如,英特尔® 线程构建模块(英特尔® TBB)parallel_for 算法可应用于每一个生成的循环:

float *a, *b;

parallel_for (1, N, 1, 
  [&](int i) {
    if (b[i] > 0.0) 
      a[i] = 2.0 * b[i];
    else 
      a[i] = 2.0 * fabs(b[i]);
    });
parallel_for (1, N, 1, 
  [&](int i) {
    b[i] = a[i-1];
  });

在第二次 parallel_for 调用执行之前,第一次 parallel_for 调用的返回确保了一个阵列内所有更新均已在 b 阵列更新开始之前完成。

另一循环分裂的使用将增加数据的局部性。考虑一下下面的筛形代码:
 

for (i = 0; i < list_len; i++)
  for (j = prime[i]; j < N; j += prime[i])
    marked[j] = 1;

外层循环选择主阵列内层循环的起始索引和步长。内层循环通过已标记阵列的长度运行,将 ‘1’ 值存入所选择的元素中。如果标记的阵列足够大,内层循环的执行可将缓存行从早期的标记阵列元素中提取出来,进而满足随后的外层循环迭代需求。此行为将会导致循环的串行和并行版本的缓存命中率降低。

通过循环裂变,内部循环迭代可以分裂成块,一旦其被使用,便能更好地适应缓存,并可重新使用缓存行。在这种情况下若要完成分裂,则需要加入另一个循环来控制内部循环执行范围。
 

for (k = 0; k < N; k += CHUNK_SIZE)
  for (i = 0; i < list_len; i++) {
    start = f(prime[i], k);
    end = g(prime[i], k);
    for (j = start; j < end; j += prime[i])
      marked[j] = 1;
  }

对于上述代码中最外层循环的每个迭代,i 循环中的全套迭代都将执行。从主阵列中所选择的元素,标记阵列块内的起始和结束指数(受外层循环控制)一定会被发现。这些计算已被封装在f()g() 例程之内。因此,同一标志块将会在下一个处理之前进行处理。并且,鉴于每个块的处理过程完全独立于其他块,因而外层迭代也可并行运行。

合并嵌入式循环增加迭代计数为另一优化,可高效辅助循环迭代并行化。例如,考虑一下左边代码带有两个嵌入式循环,其迭代计数分布为 23 和 1000。鉴于 23 为质数,因而无法平均划分外层迭代;同样,1000 迭代可能无法充分削减仅处理内层循环的线程费用。另一方面,借助 23,000 迭代(可在右面看得到),循环可能被融合成一个单一循环,通过并行原始代码,上述问题将会得到缓解。
 

#define N 23
#define M 1000
. . .
for (k = 0; k < N; k++)
  for (j = 0; j < M; j++)
    wn[k][j] = Work(w[k][j], k, j);
#define N 23
#define M 1000
. . .
for (kj = 0; kj < N*M; kj++) {
  k = kj / M;
  j = kj % M;
  wn [k][j] = Work(w[k][j], k, j);
}

然而,如果迭代变量在循环体中均被使用,新的循环计数必须被转换成相应的组件值,因此造成了原始算法没有的额外开销。

具有相似指数的融合(或合并)循环将改善粒度和数据本地化,而且在并行化时最大限度地减少费用支出。左边示例代码中的前两个循环可以很容易地合并:
 

  for (j = 0; j < N; j++)
    a[j] = b[j] + c[j];

  for (j = 0; j < N; j++)
    d[j] = e[j] + f[j];

  for (j = 5; j < N - 5; j++)
    g[j] = d[j+1] + a[j+1];
  for (j = 0; j < N; j++)
  {
    a[j] = b[j] + c[j];
    d[j] = e[j] + f[j];
  }

  for (j = 5; j < N - 5; j++)
    g[j] = d[j+1] + a[j+1];

合并这些循环增加了每次迭代的工作量(即粒度),并减少了循环开销。因为第三个循环的迭代计数不同,因而其不易被合并。然而,更重要的是,第三个循环和前两个循环之间存在数据独立性。

如果子句选择基于运行时间信息的串行和并行执行,这时可使用 OpenMP。有时一个循环内的迭代数量在运行时间期之前无法被确定。如果执行一个采用多线程(例如,迭代数量较少)的 OpenMP 并行区域会带来消极性能,那么指定一个最低临界值将有助于保持性能,如下面的例子所示:
 

#pragma omp parallel for if(N >= threshold)
  for (i = 0; i < N; i++) { ... }

对于本示例代码,如果迭代次数超过了程序规定的临界值,那么循环将仅并行执行。

鉴于英特尔® TBB 中没有相同项,为确定并行和串行执行代码是否完成,需要进行明确条件测试。或者说,一个并行算法可调度,英特尔® TBB 任务调度得到自由发挥,从而确定单一线程使用于足够低的 N 值。最后的选型可能需要一些开销。
 

其他资源

现代代码社区

OpenMP* 规范

英特尔® 线程构建模块

面向开放源代码的英特尔线程构建模块

James Reinders, 英特尔线程构建模块: 针对多核处理器并行机制配置 C++. O'Reilly Media, Inc. Sebastopol, CA, 2007.

有关编译器优化的更完整信息,请参阅优化通知