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

Intel ISN

0/5 (0投票)

2010年4月1日

CPOL

7分钟阅读

22334

在数据并行应用程序中，相同的独立操作会针对不同数据重复执行。循环通常是数据并行应用程序中最耗费计算的部分，因此循环优化直接影响性能。

摘要

在数据并行应用程序中，相同的独立操作会针对不同数据重复执行。循环通常是数据并行应用程序中最耗费计算的部分，因此循环优化直接影响性能。当遇到嵌套循环时，分配给线程的计算的粒度将直接影响性能。循环转换，例如拆分（循环分离）和合并（循环融合）嵌套循环，可以使并行化更容易和更有效。

本文是大型系列“Intel 多线程应用程序开发指南”的一部分，该系列为 Intel® 平台上的高效多线程应用程序开发提供了指导方针。

背景

循环优化为提高数据并行应用程序的性能提供了良好的机会。这些优化，如循环融合、循环交换和循环展开，通常以改进粒度、负载平衡和数据局部性为目标，同时最大限度地减少同步和其他并行开销。经验法则通常是，具有高迭代次数的循环是并行化的最佳候选者，尤其是当使用相对较少数量的线程时。更高的迭代次数由于可用于线程分发的任务数量更多，可以实现更好的负载平衡。尽管如此，还应考虑每次迭代的工作量。除非另有说明，本节的讨论假定循环的每次迭代的计算量（大致）等于同一循环中的其他每次迭代。

考虑一个使用 OpenMP* for 工作共享构造的循环场景，如下面的示例代码所示。在这种情况下，低迭代次数会导致在将循环迭代分配给四个线程时出现负载不平衡。如果单次迭代仅需要几微秒，这种不平衡可能不会造成重大影响。但是，如果每次迭代需要一个小时，那么三个线程将保持空闲 60 分钟，而第四个线程则完成。将此与具有 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]);
}

如果使用的线程数不是五，那么并行化外层循环将导致负载不平衡和线程空闲。如果数组维度 imx、jmx 和 kmx 非常大，这种低效率会尤其严重。在这种情况下，并行化内层循环是更好的选择。

在安全的情况下，避免在工作共享构造结束时产生的隐式屏障。所有 OpenMP 工作共享构造（for、sections、single）在结构化块的末尾都有一个隐式屏障。在执行可以继续之前，所有线程都必须在此屏障处会合。有时这些屏障是不必要的，并且会对性能产生负面影响。使用 OpenMP nowait 子句来禁用此屏障，如下面的示例所示。

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];
  });

由于最内层循环中的计算都是独立的，因此没有理由让线程在进入下一个 k 迭代之前在隐式屏障处等待。如果每次迭代的工作量不相等，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 元素赋值的完成。因此，如上所示，该循环无法并行化。

通过将循环拆分为两个独立的运算，这两个运算都可以并行执行。例如，Intel® Threading Building Blocks (Intel® 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 调用在第二个调用执行之前返回，确保对 a 数组的所有更新都已完成，然后才开始对 b 数组的更新。

循环分离的另一个用途是提高数据局部性。考虑以下类似筛子的代码。

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

外层循环从素数数组中选择内层循环的起始索引和步长。然后，内层循环遍历标记数组的长度，将“1”值存入选定的元素中。如果标记数组足够大，内层循环的执行可能会将 marked 早期元素的缓存行逐出，这些缓存行将在外层循环的后续迭代中需要。这种行为将导致循环的串行和并行版本中的缓存命中率都很低。

通过循环分离，可以将内层循环的迭代次数分解成更适合放入缓存的块，并在将缓存行引入后重新使用它们。为了在此处实现分离，添加了另一个循环来控制最内层循环执行的范围。

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 循环的完整集合。从选定的素数数组元素开始，必须找到 marked 数组块中的开始和结束索引（由外层循环控制）。这些计算已封装在 f() 和 g() 例程中。因此，在处理下一个块之前，将处理 marked 的同一块。并且，由于每个块的处理与其他块的处理无关，因此外层循环的迭代可以并行运行。

合并嵌套循环以增加迭代次数是另一种可能有助于有效并行化循环迭代的优化。例如，考虑左侧的代码，其中有两个嵌套循环，迭代次数分别为 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 if 子句，根据运行时信息选择串行或并行执行。有时循环的迭代次数要到运行时才能确定。如果使用多线程执行 OpenMP 并行区域会产生负面性能影响（例如，迭代次数少），指定最小阈值将有助于保持性能，如下面的示例所示。

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

对于此示例代码，仅当迭代次数超过程序员指定的阈值时，该循环才会在并行中执行。

由于 Intel TBB 中没有等效的机制，因此可以进行显式条件测试来确定代码应以串行还是并行方式执行。或者，可以调用并行算法，并让 Intel TBB 任务调度器自由决定当 N 值足够低时应使用单个线程。这种最后的选项需要一些开销。

额外资源

Intel® 软件网络并行编程社区
OpenMP* 规范
Intel® Threading Building Blocks
Intel Threading Building Blocks 开源版
James Reinders, *Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism*. O’Reilly Media, Inc. Sebastopol, CA, 2007.