c++ - SIMD 减少 4 个 vector 而没有 hadd

Question

我正在尝试优化一些代码，但我处于有 4 个 vector 的状态 __m256d我想将它们的总和存储在另一个 __m256d 中.
所以基本上result = [sum(a), sum(b), sum(c), sum(d)] .我知道有一种方法可以使用 2 hadds 混合和置换来做到这一点，但我意识到 hadd 太贵了。

所以我想知道是否有一个内在可以更快地做到这一点。

Answer 1

三个选项:

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

好:概念上简单，使用普遍有用的算法(矩阵转置)，可移植代码

不好:代码大小、延迟、吞吐量

2 使用 vhaddpd高效

好:小代码(适合 Icache)，英特尔 uArchs 上的良好延迟和吞吐量

不好:需要特定于架构的代码，在某些 uArch 上有问题

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

好:良好的延迟，良好的吞吐量

坏:不如 vhaddpd 小-code，不像全矩阵转置那么容易理解

矩阵转置，垂直和

让您的编译器为您优化它。与 gcc vector 扩展*，对转置矩阵求和的代码可能如下所示:

#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

Agner Fog 的表格说:

vunpck[h/l]pd :1 个周期延迟，每个周期 1 个吞吐量，1 个 uOP 端口 5。

vinsertf128 :3 个周期延迟，每个周期 1 个吞吐量，1 个 uOP 端口 5。

vperm2f128 :3 个周期延迟，每个周期 1 个吞吐量，1 个 uOP 端口 5。

vaddpd :4 个周期延迟，每个周期 2 个吞吐量，1 个 uOP port01。

总之，有

4 [解包] + 2 [插入] + 2 [置换] = 8 个 port5 uOP。

3 [添加] = 3 个 port01 uOP。

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

水平总和

代码(明智地)使用 vhadd通过 gcc vector 扩展不容易获得，因此代码需要特定于英特尔的内在函数:

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 port01 + 2*port5。

总之，有

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 个 port5 uOP。

3 [添加] = 3 个 port01 uOP。

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

如果您想提高吞吐量，则必须将工作从端口 5 转移出去。不幸的是，几乎所有置换/插入/混洗指令都需要端口 5，而跨车道指令(此处需要)至少有 3 个周期的延迟。一个几乎有帮助的有趣指令是 vblendpd ，它有 3 个/周期的吞吐量，1 个周期的延迟，并且可以在端口 015 上执行，但是使用它来替换置换/插入/混洗之一需要 vector 的 128 位 channel 的 64 位移位，即由 vpsrldq/vpslldq 实现，你猜对了它需要一个 port5 uOP(所以这将有助于 32 位 vector float，因为 vpsllq/vpsrlq 不需要 port5)。这里没有免费的午餐。

* gcc vector 扩展快速描述:

代码使用 gcc vector 扩展，允许在 vector 上使用基本运算符( +-*/=><>><< 等)，按元素操作。它们还包括一些 __builtin_*函数，特别是 __builtin_shuffle() ，它具有 3 操作数形式，其中前两个是相同类型 T 的两个(相同长度 N) vector ，它们(逻辑上)连接到该类型 T 的双倍长度 (2N) vector ，第三个是与原始 vector 类型具有相同宽度和长度 (N) 的整数类型 (IT) vector 。结果是原始 vector 的相同类型 T 和宽度 N 的 vector ，元素由整数类型 vector 中的索引选择。

本来，我的回答是关于 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];
}

由 gcc-9.2.1 生成的翻译在 skylake-avx2 上可能看起来像这样:

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 vector 扩展。

根据 Agner Fog 的 Skylake 指令表，

vpunpck[h/l]qdq :1 个周期延迟，每个周期 1 个吞吐量，端口 5。

vperm2i128 :3 个周期延迟，每个周期 1 个吞吐量，端口 5。

vpaddq :1 个周期延迟，每个周期 3 个吞吐量，端口 015。

因此转置需要 10 个周期(4 个用于解包，4 个吞吐量 + 2 个用于置换的延迟)。在三个添加中，只有两个可以并行执行，因此需要 2 个周期，总共 12 个周期。