c - 高效的手动循环展开

Question

我有这个 C 代码：

for (k = 0; k < n_n; k++) {
    if (k == i || k == j) continue;
    dd=q2_vect[k]-q1_vect;
    d2=dd*dd;
    if (d2<0) {
        a=1;
        break;
    }       
}

出于编译器优化的原因（在 Cell 处理器的 SPE 上），我需要手动解循环，所以我尝试了：

dd=q2_vect[0]-q1_vect;
d2=dd*dd;
if (d2<0)goto done;

dd=q2_vect[1]-q1_vect;
d2=dd*dd;
if (d2<0)goto done;

dd=q2_vect[2]-q1_vect;
d2=dd*dd;
if (d2<0)goto done;

.....
.....

// end
goto notdone;

done: 
ok=0;

notdone:
.....

但我不知道如何处理

if (k == i || k == j) continue;

并且事实上lopp取决于“n_n”上的每次运行，并且我应该手动编写代码多次，因为最大值“n_n”会得到。

你认为它可以如何修复？

score 3 · Accepted Answer

你确定写的代码是正确的吗？当前代码具有未定义的行为 ifdd是有符号整数类型，并且 if 中的条件永远不会满足 ifd2是无符号或 ifdd和d2是浮点类型。看起来您正在对第一个索引进行错误的搜索，而不是k平方表达式溢出的位置。ijq2_vect[ k]-q1_vect

至于有效地跳过iandj迭代，我只会查看展开的“循环”停止的位置，然后在k+1ifk等于ior处重新启动它j。这是假设您的循环中的代码没有副作用/运行总数，这在编写时是正确的，但我希望您可能打算让代码执行其他操作（例如对平方求和）。

最后，当您似乎没有工作代码开始时，我对您手动展开循环的愿望高度怀疑。任何优秀的编译器都可以为您展开循环，但您想要执行的循环展开类型通常会使性能更差而不是更好。我认为你最好先让你的代码正常工作，然后测量（并查看编译器生成的 asm），然后在确定存在问题后才尝试改进它。

score 1 · Accepted Answer

编写的这段代码非常不适合 SPE，因为它的分支繁重。此外，有关所涉及变量类型的信息也会有所帮助；编写的测试似乎相当模糊（即使有>0修复），但代码看起来可能是 C++，它使用某种矢量类，重载operator -意味着矢量减法和operator *两个矢量来计算点积。

在 SPE 上处理这种简单循环的第一件事是让它们无分支（至少是内部循环；即展开几次，每 N 次迭代只检查是否提前退出）并使用 SIMD 指令：SPE只有 SIMD指令，因此不在循环中使用 SIMD 处理会立即浪费 75% 的可用寄存器空间和计算能力。同样，SPE 一次只能加载对齐的 qwords（16 字节），使用较小的数据类型需要额外的工作来打乱寄存器的内容，以便您尝试加载的值最终位于“首选插槽”中。

if (k == i || k == j)通过使用以下无分支形式重写循环的第一部分来摆脱

dd = q2_vect[k] - q1_vect;
d2 = dd * dd;
d2 &= ~(cmp_equal(k, i) | cmp_equal(k, j));

在这里，cmp_equal对应于各自的 SPE 内在函数（语义：）cmp_equal(a,b) == (a == b) ? ~0u : 0。这在或时强制d2为零。k == ik == j

要避免if (d2 > 0)内部循环中的分支，请执行以下操作：

a |= cmp_greater(d2, 0);

并且只检查a每几次循环迭代是否为非零（提前退出）。如果计算出的所有值d2都是非负数（如果您的类型是整数、浮点数或实值向量类，则会出现这种情况），您可以进一步简化这一点。做就是了：

a |= d2;

最后，a仅当所有单个项都非零时，才会非零。但要小心整数溢出（如果您使用整数）和 NaN（如果您使用浮点数）。如果您必须处理这些情况，上述简化将破坏代码。

score 0 · Accepted Answer

对于第一个问题，您不需要在满足条件时“执行”循环体。对于这个特定问题，您可以将该条件的逻辑否定放在if语句的条件中。

通常展开是一个因素；展开的代码仍然存在于循环中（除非已知循环边界非常小）。此外，您需要在循环之外完成工作的“剩余部分”（对应于问题大小除以展开因子的剩余部分）。

因此，循环展开的示例：

for (i = 0; i < n; ++i) do_something(i);

可以展开 2 倍至：

for (i = 0; i < n-1; i += 2) { do_something(i); do_something(i+1); }
for (; i < n; ++i) do_something(i);

其中第二个循环执行“剩余”（它也设置i为与展开循环相同的内容，但如果i在此之后不需要，则整行仅if (i < n) etc适用于这种情况）。

score 0 · Accepted Answer

假设 n_n 是一个编译时常量，循环可能会像这样简单展开：

do
{ 
  k=0
  if (k == i || k == j) 
    ;
  else
  {
    dd=q2_vect[ k]-q1_vect;
    d2=dd*dd;
    if (d2<0)
    {
      a=1;
      break;
    }
  }

  k=1
  if (k == i || k == j) 
    ;
  else
  {
    dd=q2_vect[ k]-q1_vect;
    d2=dd*dd;
    if (d2<0)
    {
      a=1;
      break;
    }
  }

  /* and so on, n_n times */

  k= n_n-1
  if (k == i || k == j) 
    ;
  else
  {
    dd=q2_vect[ k]-q1_vect;
    d2=dd*dd;
    if (d2<0)
    {
      a=1;
      break;
    }
  }

} while (0);

本质上， continue 之后的所有内容都进入elseif 语句的部分

编辑：由于n_n不是编译时间常数，您仍然可以通过在循环中多次运行来展开循环，然后使用 switch-case 语句完成。事实上，你可以像这样组合它们，这就是所谓的达夫装置。

#define LOOP_BODY              \
do{                            \  
  if (k == i || k == j)        \
    ;                          \
  else                         \
  {                            \
    dd=q2_vect[ k]-q1_vect;    \
    d2=dd*dd;                  \
    if (d2<0)                  \
    {                          \
      a=1;                     \
      break;                   \
    }                          \
  } while (0)          


k = 0;
switch(n_n % 8)
{
  case 0: for (; k < n_n; k++) { LOOP_BODY; k++; 
  case 7:                        LOOP_BODY; k++;
  case 6:                        LOOP_BODY; k++;
  case 5:                        LOOP_BODY; k++;
  case 4:                        LOOP_BODY; k++;
  case 3:                        LOOP_BODY; k++;
  case 2:                        LOOP_BODY; k++;    
  case 1:                        LOOP_BODY; k++;}
}

score 0 · Accepted Answer

通常循环展开意味着使循环包含一些迭代，从而减少运行次数。例如，

for(i=0;i<count;i++) {
    printf("%d", i);
}

可以展开到

i=0;
if(count%2==1) {
    printf("%d", i);
    i=1;
}
while(i<count) {
    printf("%d", i);
    printf("%d", i+1);
    i+=2;
}

score 0 · Accepted Answer

展开这个循环在这里没有多大帮助。内环软件展开有助于指令的软件流水线化，以在运行时实现更高的 IPC。在这里，它可能会通过展开来破坏逻辑。

c - 高效的手动循环展开

6 回答 6

Related

Reference