通过英特尔 Cilk Plus 数组符号实现外层循环向量化

面向 MIC Compi 的英特尔® Composer XE

面向英特尔® MIC 架构的编译器方法

向量化要素,通过英特尔® Cilk™ Plus 数组符号实现外层循环向量化

概述

外层循环向量化是一种用于增强性能的技术。默认情况下,编译器会对嵌套循环结构中最内层的循环进行向量化处理。但在某些情况下,最内层循环中的迭代数量较小。此时,对最内层循环进行向量化有些得不偿失。但是,如果外层循环中具有更多的工作,则可以使用 C++ 数组符号来模拟外层循环向量化。C++ 数组符号是英特尔® Cilk™ Plus(英特尔® C++ Composer XE 的一种特性)的一部分。

主题

下面展示了通过数组符号实现的外层循环向量化示例。

C++ 数组符号可以通过模拟外层循环向量化来阻止循环(对外层循环进行向量化处理,同时保留内层循环的结构)。下面的示例基于德布洛特集合的计算:

串行代码:

void serial_mandel(
   float c_re[SIZE], float c_im[SIZE],
   unsigned int max_recurrences,
   char output[SIZE])
{
   for (int i = 0; i < SIZE; i++) {
     unsigned int iter = 0;
     float z_re = c_re[i];
     float z_im = c_im[i];

     // If the loop reaches max_recurrences, c is an element of
     // the Mandelbrot set.
     while (iter < max_recurrences) {
       if (z_re * z_re + z_im * z_im > 4.0) {
         break; // escape from a circle of radius 2
       }  

       float new_z_re = c_re[i] + z_re*z_re – z_im*z_im;
       float new_z_im = c_im[i] + 2.*z_re*z_im;
       iter++;
     }

     // Scale the number of iterations to the range of an 8-bpp image
     output = static_cast<unsigned char>(static_cast<float>(iter) /
     max_recurrences * 255);
   }
}

该代码具有两个循环。外层循环通过输入集中的所有点进行迭代,这些点代表复平面中的坐标。对于每个点来说,内层循环使用坐标作为初始条件来计算一个循环,并记下达到饱和状态需要执行多少次迭代。

内层循环并不是理想的向量化对象,因为它是一个不知道具体迭代数量的迭代总和。但是另一方面,外层循环可能运行良好,因为可针对每个点单独计算循环。

由于外层循环中存在代码,编译器不能自动进行循环交换(编译器倾向于不带中介代码的“完美”循环嵌套)。

我们可以使用数组符号来模拟外层循环向量化:

void mandel_v(
  double c_re[SIZE], double c_im[SIZE],
  int max_recur,
  char output[SIZE])
{
  float count[VLEN];
  for (int i = 0; i < size; i += VLEN) {
    double z_re[VLEN], z_im[VLEN], new_z_re[VLEN], new_z_im[VLEN];
    int test[VLEN];
    z_re[:] = c_re[i:VLEN];
    z_im[:] = c_im[i:VLEN];
    int iter;

    // Count how many times you can multiply z by itself
     // until it is greater than 4. count[:] is the result.
    count[:] = 0;
      for (iter=0; iter<max_recur; iter++) {
        test[:] = (z_re[:] * z_re[:] + z_im[:] * z_im[:]) <= 4.;
         if (__sec_reduce_all_zero(test[:])) {
          break;>
        }
        count[:] += test[:];

        // add 1 or 0 depending on whether z[:] is <= 4
        new_z_re[:] = c_re[:] + z_re[:]*z_re[:] - z_im[:]*z_im[:];
        new_z_im[:] = c_im[:] + 2.*z_re[:]*z_im[:];
        z_re[:] = new_z_re[:];
        z_im[:] = new_z_im[:];
      }
      output[i:VLEN] = (char)((float)count[:] / max_recur*255);
    }
}

该代码使用 加宽数组段的标量参数的基本技术来增加 VLEN 的大小。我们不希望加宽至整个数组长度,因为这可能会使体积过大,较大的数组段操作可能不利于生成最优的代码。因此,我们不会完全删除外层循环;我们通过 VLEN 块中的点进行迭代操作。

该转换的一个有趣的特性是如何在原始代码中处理 while 循环。在原始代码中,我们在每个点上运行循环,直到其达到饱和状态才停止。在并行处理 VLEN 点时,我们必须在每个点达到饱和时停止迭代,并仍然针对每个点使用相同的代码(SIMD 语义)。我们通过对点进行并行测试以达到饱和状态来实现这一点,默认情况下会生成 1 或 0。我们向计数向量添加 1 或 0:1 代表该点未饱和,0 代表饱和。当一个点达到饱和时,向量计数器递增会变成该向量元素的 no-op。我们使用 __sec_reduce_all_zero() 内联(intrinsic)来测试所有点是否达到饱和状态并打破循环,因此我们可以顺利执行 no-op 添加直到达到 max_recur。

向量加速取决于生成的 no-op 添加的数量,而后者又取决于指定 VLEN 的结果的一致性。如果所有点中只有一个点达到饱和状态,那么该点将继续进行迭代直至达到最大值,我们会在成熟点上浪费一次计算。因此,执行小于机器大小(smaller-than-machine-size)的 VLEN 可能效果更好;用户必须进行尝试。此外,__sec_reduce_all_zero() 还添加了部分开销;如果计数器结果总是接近某些输入集的 max_recur;可以将其忽略。

该技术可以达到与外层循环向量化相同的结果,但是无须执行向量化操作(我们帮助编译器阻止 VLEN 块中的外层循环并创建基于这些块的向量操作 — 每个数组符号语句都是一个较短的单语句内存循环)。

下面的文章提供了关于外层循环向量化的更多示例。

ISCA 2012 论文:《传统编程是否能缩小并行计算应用的 Ninja 性能差距?》(2012 年 6 月)

要点

默认情况下,编译器会对嵌套循环结构中最内层的循环进行向量化处理。如果该最内层循环中没有足够的迭代数,那么对于编译器来说,执行向量化操作有些得不偿失。但是,如果外层循环上具有更多的迭代,那么在外层执行向量化会带来更好的效果。要实现这一点,可以使用 C++ 数组符号来模拟外层循环向量化。C++ 数组符号是英特尔® Cilk™ Plus(英特尔® C++ Composer XE 的一种特性)的一部分。

要在英特尔® 至强 融核™ 架构上成功调试您的应用,请务必通读此指南,并点击文中的超链接查看相关内容。本指南提供了实现最佳应用性能所要执行的步骤。

返回到主章节“向量化要素”。

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