SIMD减少4个向量，无hadd

Question

我正在尝试优化一些代码，我的状态是有4个向量，我想将它们的总和存储在另一个向量中。所以基本上，结果=[求和（a），求和（b），求和（c），求和（d）]。我知道有一种方法可以做到这一点，使用2个hadd a混合和置换，但我意识到hadd太贵了。

所以我想知道是否有一种内在的机制可以让我们更快地做到这一点。

Answer 1

三个选项：

• 1矩阵转置，然后垂直和

好：概念简单，使用通用算法（矩阵转置），可移植代码

错误：代码大小、延迟、吞吐量

• 2有效使用vhaddpd

好：代码小（适用于Icache），在Intel UARCH上具有良好的延迟和吞吐量

坏：需要架构特定的代码，在一些uArch上有问题

• 3部分转置，求和，部分转置，求和

好：延迟好，吞吐量好

错误：没有vhaddpd代码那么小，没有完整的矩阵转置那么容易理解

让您的编译器为此进行优化。使用gcc向量扩展*，在转置矩阵上求和的代码可能如下所示：

#include <stdint.h>

typedef uint64_t v4u64 __attribute__((vector_size(32)));
typedef double v4f64  __attribute__((vector_size(32)));

v4f64 dfoo(v4f64 sv0, v4f64 sv1, v4f64 sv2, v4f64 sv3)
{
  v4f64 tv[4];
  tv[0] = __builtin_shuffle(sv0, sv1, (v4u64){0,4,2,6});
  tv[1] = __builtin_shuffle(sv0, sv1, (v4u64){1,5,3,7});
  tv[2] = __builtin_shuffle(sv2, sv3, (v4u64){0,4,2,6});
  tv[3] = __builtin_shuffle(sv2, sv3, (v4u64){1,5,3,7});
  v4f64 fv[4];
  fv[0] = __builtin_shuffle(tv[0], tv[2], (v4u64){0,1,4,5});
  fv[1] = __builtin_shuffle(tv[0], tv[2], (v4u64){2,3,6,7});
  fv[2] = __builtin_shuffle(tv[1], tv[3], (v4u64){0,1,4,5});
  fv[3] = __builtin_shuffle(tv[1], tv[3], (v4u64){2,3,6,7});
  return fv[0]+fv[1]+fv[2]+fv[3];
}

gcc-9.2.1生成以下程序集：

dfoo:
    vunpcklpd   %ymm3, %ymm2, %ymm5
    vunpcklpd   %ymm1, %ymm0, %ymm4
    vunpckhpd   %ymm1, %ymm0, %ymm0
    vinsertf128 $1, %xmm5, %ymm4, %ymm1
    vperm2f128  $49, %ymm5, %ymm4, %ymm4
    vunpckhpd   %ymm3, %ymm2, %ymm2
    vaddpd  %ymm4, %ymm1, %ymm1
    vinsertf128 $1, %xmm2, %ymm0, %ymm3
    vperm2f128  $49, %ymm2, %ymm0, %ymm0
    vaddpd  %ymm3, %ymm1, %ymm1
    vaddpd  %ymm0, %ymm1, %ymm0
    ret

艾格纳·福格的表格上写着：

• vunpck[小时/小时]pd：1个周期延迟，1个周期吞吐量，1个uOP端口5
• vinsertf128：3个周期延迟，1个周期吞吐量，1个uOP端口5
• vperm2f128：3个周期延迟，1个周期吞吐量，1个uOP端口5
• vaddpd：4个周期延迟，2个周期吞吐量，1个uOP端口01

在所有，有

• 4[解包]2[插入]2[排列]=8个端口5个UOP

port5上的吞吐量会出现瓶颈。大约18个周期的延迟非常糟糕。代码大小约为60字节。

通过gcc向量扩展，使用vhadd的代码（合理地）不容易获取，因此代码需要特定于英特尔的内部函数：

v4f64 dfoo_hadd(v4f64 sv0, v4f64 sv1, v4f64 sv2, v4f64 sv3)
{
  v4f64 hv[2];
  hv[0] = __builtin_ia32_haddpd256(sv0, sv1); //[00+01, 10+11, 02+03, 12+13]
  hv[1] = __builtin_ia32_haddpd256(sv2, sv3); //[20+21, 30+31, 22+23, 32+33]
  v4f64 fv[2];
  fv[0] = __builtin_shuffle(hv[0], hv[1], (v4u64){0, 1, 4, 5}); //[00+01, 10+11, 20+21, 30+31]
  fv[1] = __builtin_shuffle(hv[0], hv[1], (v4u64){2, 3, 6, 7}); //[02+03, 12+13, 22+23, 32+33]
  return fv[0] + fv[1]; //[00+01+02+03, 10+11+12+13, 20+21+22+23, 30+31+32+33]
}

这将生成以下组件：

dfoo_hadd:
    vhaddpd %ymm3, %ymm2, %ymm2
    vhaddpd %ymm1, %ymm0, %ymm0
    vinsertf128 $1, %xmm2, %ymm0, %ymm1
    vperm2f128  $49, %ymm2, %ymm0, %ymm0
    vaddpd  %ymm0, %ymm1, %ymm0
    ret

根据Agner Fog的说明书，

• vhaddpd：6个周期的延迟，0.5个周期的吞吐量，3个uOPS端口01 2*端口5

在所有，有

• 4[hadd] 2[插入/永久]=6 uOPs port5。
• 3[hadd/add]=3 uOPs port01。

吞吐量也受到port5的限制，这比转置代码有更多的吞吐量。延迟应该大约为16个周期，也比转置代码快。代码大小约为25字节。

实施@PeterCordes评论：

v4f64 dfoo_PC(v4f64 sv0, v4f64 sv1, v4f64 sv2, v4f64 sv3)
{
  v4f64 tv[4];
  v4f64 av[2];
  tv[0] = __builtin_shuffle(sv0, sv1, (v4u64){0,4,2,6});//[00, 10, 02, 12]
  tv[1] = __builtin_shuffle(sv0, sv1, (v4u64){1,5,3,7});//[01, 11, 03, 13]
  av[0] = tv[0] + tv[1];//[00+01, 10+11, 02+03, 12+13]
  tv[2] = __builtin_shuffle(sv2, sv3, (v4u64){0,4,2,6});//[20, 30, 22, 32]
  tv[3] = __builtin_shuffle(sv2, sv3, (v4u64){1,5,3,7});//[21, 31, 23, 33]
  av[1] = tv[2] + tv[3];//[20+21, 30+31, 22+23, 32+33]
  v4f64 fv[2];
  fv[0] = __builtin_shuffle(av[0], av[1], (v4u64){0,1,4,5});//[00+01, 10+11, 20+21, 30+31]
  fv[1] = __builtin_shuffle(av[0], av[1], (v4u64){2,3,6,7});//[02+03, 12+13, 22+23, 32+33]
  return fv[0]+fv[1];//[00+01+02+03, 10+11+12+13, 20+21+22+23, 30+31+32+33]
}

这会产生：

dfoo_PC:
    vunpcklpd   %ymm1, %ymm0, %ymm4
    vunpckhpd   %ymm1, %ymm0, %ymm1
    vunpcklpd   %ymm3, %ymm2, %ymm0
    vunpckhpd   %ymm3, %ymm2, %ymm2
    vaddpd  %ymm1, %ymm4, %ymm1
    vaddpd  %ymm2, %ymm0, %ymm2
    vinsertf128 $1, %xmm2, %ymm1, %ymm0
    vperm2f128  $49, %ymm2, %ymm1, %ymm1
    vaddpd  %ymm1, %ymm0, %ymm0
    ret

在所有，有

• 4[拆包]2[插入/置换]=6个端口5个计量单位

这与hadd-code获得相同数量的port5 uOP。代码在port5上仍然存在瓶颈，延迟约为16个周期。代码大小约为41字节。

如果您想增加吞吐量，您必须将工作从port5转移。不幸的是，几乎所有permute/插入/随机指令都需要port5，而车道交叉指令（此处需要）至少有3个周期延迟。一个几乎有帮助的有趣指令是vblendpd，它具有3/周期吞吐量，1周期延迟，并且可以在port015上执行，但使用它来替换permute/插入/shuffles之一需要对向量的128位通道进行64位移位，由vpsrldq/vpslldq实现，您猜对了-需要port5 uOP（因此这将有助于32位浮动的向量，因为vpsllq/vpsrlq不需要port5）。这里没有免费的午餐。

*gcc矢量扩展快速描述：

代码使用gcc向量扩展，允许使用基本运算符（-*/=

最初，我的答案是关于uint64\t的，保留在这里作为上下文：

 #include <stdint.h>

typedef uint64_t v4u64 __attribute__((vector_size(32)));

v4u64 foo(v4u64 sv0, v4u64 sv1, v4u64 sv2, v4u64 sv3)
{
  v4u64 tv[4];
  tv[0] = __builtin_shuffle(sv0, sv1, (v4u64){0,4,2,6});
  tv[1] = __builtin_shuffle(sv0, sv1, (v4u64){1,5,3,7});
  tv[2] = __builtin_shuffle(sv2, sv3, (v4u64){0,4,2,6});
  tv[3] = __builtin_shuffle(sv2, sv3, (v4u64){1,5,3,7});
  v4u64 fv[4];
  fv[0] = __builtin_shuffle(tv[0], tv[2], (v4u64){0,1,4,5});
  fv[1] = __builtin_shuffle(tv[0], tv[2], (v4u64){2,3,6,7});
  fv[2] = __builtin_shuffle(tv[1], tv[3], (v4u64){0,1,4,5});
  fv[3] = __builtin_shuffle(tv[1], tv[3], (v4u64){2,3,6,7});
  return fv[0]+fv[1]+fv[2]+fv[3];
}

skylake-avx2上gcc-9.2.1生成的翻译如下：

foo:
    vpunpcklqdq %ymm3, %ymm2, %ymm5
    vpunpcklqdq %ymm1, %ymm0, %ymm4
    vpunpckhqdq %ymm3, %ymm2, %ymm2
    vpunpckhqdq %ymm1, %ymm0, %ymm0
    vperm2i128  $32, %ymm2, %ymm0, %ymm3
    vperm2i128  $32, %ymm5, %ymm4, %ymm1
    vperm2i128  $49, %ymm2, %ymm0, %ymm0
    vperm2i128  $49, %ymm5, %ymm4, %ymm4
    vpaddq  %ymm4, %ymm1, %ymm1
    vpaddq  %ymm0, %ymm3, %ymm0
    vpaddq  %ymm0, %ymm1, %ymm0
    ret

请注意，程序集具有与gcc向量扩展对应的几乎行。

根据Agner Fog为Skylake提供的指令表，

• vPunpck[h/l]qdq：1个周期延迟，每个周期吞吐量1，端口5。
• vperm2i128：3个周期延迟，每个周期吞吐量1个，端口5。
• vpaddq：1个周期延迟，3个周期吞吐量，ports015。

因此，转置需要10个周期（4个周期用于解包，4个周期用于吞吐量，2个周期用于置换）。在三个加法中，只有两个可以并行执行，因此总共需要2个周期，共12个周期。