1

我需要从原始比特流中提取所有 10 位字,其构建为ABACABACABAC...

它已经适用于天真的 C 实现,例如

for(uint8_t *ptr = in_packet; ptr < max; ptr += 5){
    const uint64_t val =
        (((uint64_t)(*(ptr + 4))) << 32) |
        (((uint64_t)(*(ptr + 3))) << 24) |
        (((uint64_t)(*(ptr + 2))) << 16) |
        (((uint64_t)(*(ptr + 1))) <<  8) |
        (((uint64_t)(*(ptr + 0))) <<  0) ;

    *a_ptr++ = (val >>  0);
    *b_ptr++ = (val >> 10);
    *a_ptr++ = (val >> 20);
    *c_ptr++ = (val >> 30);
}

但是性能对于我的应用程序来说是不够的,所以我想使用一些 AVX2 优化来改进它。

我访问了网站https://software.intel.com/sites/landingpage/IntrinsicsGuide/#以找到任何可以提供帮助的功能,但似乎没有什么可用于 10 位字,只有 8 位或 16 位。这似乎是合乎逻辑的,因为 10 位不是处理器原生的,但这对我来说很困难。

有没有办法使用AVX2来解决这个问题?

4

1 回答 1

7

您的标量循环无法有效编译。编译器将其作为 5 个单独的字节加载来完成。您可以用 C++ 表示未对齐的 8 字节负载memcpy

#include <stdint.h>
#include <string.h>

// do an 8-byte load that spans the 5 bytes we want
// clang auto-vectorizes using an AVX2 gather for 4 qwords.  Looks pretty clunky but not terrible
void extract_10bit_fields_v2calar(const uint8_t *__restrict src, 
   uint16_t *__restrict a_ptr, uint16_t *__restrict b_ptr, uint16_t *__restrict c_ptr,
   const uint8_t *max)
{
    for(const uint8_t *ptr = src; ptr < max; ptr += 5){
        uint64_t val;
        memcpy(&val, ptr, sizeof(val));

        const unsigned mask = (1U<<10) - 1; // unused in original source!?!
        *a_ptr++ = (val >>  0) & mask;
        *b_ptr++ = (val >> 10) & mask;
        *a_ptr++ = (val >> 20) & mask;
        *c_ptr++ = (val >> 30) & mask;
    }
}

ICC 和 clang 自动矢量化您的 1 字节版本,但做得非常糟糕(大量插入/提取单个字节)。这是您在 Godbolt 上的原始功能和此功能(使用 gcc 和 clang -O3 -march=skylake

这 3 个编译器都没有真正接近我们可以手动执行的操作。


手动矢量化

我当前的 AVX2 版本的这个答案忘记了一个细节:只有 3 种字段 ABAC,而不是像 10 位 RGBA 像素的 ABCD。所以我有一个版本,它可以解压缩到 4 个单独的输出流(如果我为 ABAC 交错添加专用版本,我将保留它,因为打包的 RGBA 用例)。

现有版本可以vpunpcklwd用来交错两个 A 部分而不是单独存储vmovq应该适用于您的情况。可能有更有效的东西,IDK。

顺便说一句,我发现更容易记住和键入指令助记符,而不是固有名称。英特尔的在线内在函数指南可通过指令助记符进行搜索。


关于您的布局的意见:

每个字段跨越一个字节边界,从不跨越两个,因此可以在包含 4 个完整字段的 qword 中组装任意 4 对字节。

或者使用字节洗牌,创建 2 字节的单词,每个单词在某个偏移量处都有一个完整的字段。(例如,对于AVX512BWvpsrlvw或对于 AVX2 2x vpsrld+ word-blend。)像 AVX512vpermw这样的单词混洗是不够的:一些单独的字节需要与一个字段的开头和另一个字段的结尾重复。即源位置并不是所有对齐的单词,尤其是当您在向量的同一 16 字节“通道”内有 2x 5 个字节时。

00-07|08-15|16-23|24-31|32-39     byte boundaries  (8-bit)
00...09|10..19|20...29|30..39     field boundaries (10-bit)

幸运的是 8 和 10 的 GCD 为 2,即 >= 10-8=2。8*5 = 4*10 所以我们没有得到所有可能的起始位置,例如,从来没有一个字段从 1 个字节的最后一位开始,跨越另一个字节,并且包括第 3 个字节的第一个位。

可能的 AVX2 策略:未对齐的 32 字节负载,在低通道顶部留下 2x 5 字节,在高通道底部留下 2x 5 字节。 然后vpshufb在车道内洗牌以设置 2 次vpsrlvd可变计数换档和混合。

一个我还没有扩展的新想法的快速总结。

给定xxx a0B0A0C0 a1B1A1C1 | a2B2A2C2 a3B3A3C3来自我们未对齐负载的输入,我们可以得到
a0 A0 a1 A1 B0 B1 C0 C1 | a2 A2 a3 A3 B2 B3 C2 C3正确选择vpshufb控制的结果。
然后 avpermd可以将所有这些 32 位组按正确的顺序排列,所有A元素都在高半部分(准备 avextracti128到内存),而 B 和 C 在低半部分(准备vmovq/vmovhps存储)。

对相邻对使用不同vpermd的 shuffle,以便我们可以vpblendd将它们合并为 128 位BC存储。


旧版本,可能比 unaligned load + vpshufb 差

使用 AVX2,一种选择是将包含的 64 位元素广播到向量中的所有位置,然后使用可变计数右移将位移到 dword 元素的底部。

您可能希望为每个组执行单独的 64 位广播加载(因此与前一个组部分重叠),而不是尝试分离 a__m256i连续位。(广播负载很便宜,洗牌很贵。)

之后_mm256_srlvd_epi64,然后与以隔离每个 qword 中的低 10 位。

对 4 个输入向量重复该操作 4 次,然后用于_mm256_packus_epi32将通道内打包到 32 位和 16 位元素。


那是简单的版本。交织的优化是可能的,例如通过使用左移或右移来设置,vpblendd而不是像vpackusdw或的 2 输入随机播放vshufps_mm256_blend_epi32在现有 CPU 上非常高效,可在任何端口上运行。

这也允许将 AND 延迟到第一个打包步骤之后,因为我们不需要避免高垃圾导致的饱和。

设计说明:

shown as 32-bit chunks after variable-count shifts
[0 d0 0 c0 | 0 b0 0 a0]      # after an AND mask
[0 d1 0 c1 | 0 b1 0 a1]

[0 d1 0 c1 0 d0 0 c0 | 0 b1 0 a1 0 b0 0 a0]   # vpackusdw
shown as 16-bit elements but actually the same as what vshufps can do

---------

[X d0 X c0 | X b0 X a0]    even the top element is only garbage right shifted by 30, not quite zero
[X d1 X c1 | X b1 X a1]

[d1 c1 d0 c0 | b1 a1 b0 a0 ]   vshufps  (can't do d1 d0 c1 c0 unfortunately)

---------

[X  d0  X c0 |  X b0  X a0]   variable-count >>  qword
[d1 X  c1  X | b1  X a1  0]   variable-count <<  qword

[d1 d0 c1 c0 | b1 b0 a1 a0]   vpblendd

最后一个技巧延伸到vpblendw,允许我们用交错混合来做所有事情,根本没有洗牌指令,导致我们想要连续的输出,并且在 a 的 qwords 中以正确的顺序输出__m256i

x86 SIMD 变量计数只能对所有元素进行左移或右移,因此我们需要确保所有数据都在所需位置的左侧或右侧,而不是同一向量中的每个数据。我们可以使用立即计数移位来为此进行设置,但更好的是只调整我们加载的字节地址。对于第一个之后的加载,我们知道在我们想要的第一个位域之前加载一些字节是安全的(不接触未映射的页面)。

# as 16-bit elements
[X X X d0  X X X c0 | ...]    variable-count >> qword
[X X d1 X  X X c1 X | ...]    variable-count >> qword from an offset load that started with the 5 bytes we want all to the left of these positions

[X d2 X X  X c2 X X | ...]    variable-count << qword
[d3 X X X  c3 X X X | ...]    variable-count << qword

[X d2 X d0  X c2 X c0 | ...]   vpblendd
[d3 X d1 X  c3 X c1 X | ...]   vpblendd

[d3 d2 d1 d0   c3 c2 c1 c0 | ...] vpblendw  (Same behaviour in both high and low lane)

Then mask off the high garbage inside each 16-bit word

注意:这有 4 个单独的输出,例如 ABCD 或 RGBA->planar,而不是 ABAC

// potentially unaligned 64-bit broadcast-load, hopefully vpbroadcastq. (clang: yes, gcc: no)
// defeats gcc/clang folding it into an AVX512 broadcast memory source
// but vpsllvq's ymm/mem operand is the shift count, not data
static inline
__m256i bcast_load64(const uint8_t *p) {
    // hopefully safe with strict-aliasing since the deref is inside an intrinsic?
    __m256i bcast = _mm256_castpd_si256( _mm256_broadcast_sd( (const double*)p ) );
    return bcast;
}

// UNTESTED
// unpack 10-bit fields from 4x 40-bit chunks into 16-bit dst arrays
// overreads past the end of the last chunk by 1 byte
// for ABCD repeating, not ABAC, e.g. packed 10-bit RGBA
void extract_10bit_fields_4output(const uint8_t *__restrict src, 
   uint16_t *__restrict da, uint16_t *__restrict db, uint16_t *__restrict dc, uint16_t *__restrict dd,
   const uint8_t *max)
{
  // FIXME: cleanup loop for non-whole-vectors at the end    
  while( src<max ){
    __m256i bcast = bcast_load64(src);  // data we want is from bits [0 to 39], last starting at 30
    __m256i ext0 = _mm256_srlv_epi64(bcast, _mm256_set_epi64x(30, 20, 10, 0));  // place at bottome of each qword

    bcast = bcast_load64(src+5-2);        // data we want is from bits [16 to 55], last starting at 30+16 = 46
    __m256i ext1 = _mm256_srlv_epi64(bcast, _mm256_set_epi64x(30, 20, 10, 0));   // place it at bit 16 in each qword element

    bcast = bcast_load64(src+10);        // data we want is from bits [0 to 39]
    __m256i ext2 = _mm256_sllv_epi64(bcast, _mm256_set_epi64x(2, 12, 22, 32));   // place it at bit 32 in each qword element

    bcast = bcast_load64(src+15-2);        // data we want is from bits [16 to 55], last field starting at 46
    __m256i ext3 = _mm256_sllv_epi64(bcast, _mm256_set_epi64x(2, 12, 22, 32));   // place it at bit 48 in each qword element

    __m256i blend20 = _mm256_blend_epi32(ext0, ext2, 0b10101010);   // X d2 X d0  X c2 X c0 | X b2 ...
    __m256i blend31 = _mm256_blend_epi32(ext1, ext3, 0b10101010);   // d3 X d1 X  c3 X c1 X | b3 X ...

    __m256i blend3210 = _mm256_blend_epi16(blend20, blend31, 0b10101010);  // d3 d2 d1 d0   c3 c2 c1 c0 
    __m256i res = _mm256_and_si256(blend3210, _mm256_set1_epi16((1U<<10) - 1) );

    __m128i lo = _mm256_castsi256_si128(res);
    __m128i hi = _mm256_extracti128_si256(res, 1);
    _mm_storel_epi64((__m128i*)da, lo);     // movq store of the lowest 64 bits
    _mm_storeh_pi((__m64*)db, _mm_castsi128_ps(lo));       // movhps store of the high half of the low 128.  Efficient: no shuffle uop needed on Intel CPUs

    _mm_storel_epi64((__m128i*)dc, hi);
    _mm_storeh_pi((__m64*)dd, _mm_castsi128_ps(hi));       // clang pessmizes this to vpextrq :(
    da += 4;
    db += 4;
    dc += 4;
    dd += 4;
    src += 4*5;
  }
}

这在每 4 组 4 个字段的循环中编译(Godbolt)到大约 21 个前端微指令(在 Skylake 上)。(包括有一个无用的寄存器副本,_mm256_castsi256_si128而不仅仅是使用 ymm0 = xmm0 的低半部分)。这在 Skylake 上会非常好。不同端口的微指令平衡良好,SKL 上的 p0 或 p1 的可变计数移位为 1 微指令(与以前更昂贵相比)。瓶颈可能只是每个时钟 4 个融合域微指令的前端限制。

由于未对齐的负载有时会跨越 64 字节的缓存行边界,因此会发生缓存行拆分加载的重播。但这只是在后端,由于前端瓶颈,我们在端口 2 和 3 上有几个空闲周期(每组结果 4​​ 个加载和 4 个存储,索引存储因此不能使用端口 7 )。如果依赖的 ALU 微指令也必须得到重放,我们可能会开始看到后端瓶颈。

尽管有索引寻址模式,但不会出现分层,因为 Haswell 和更高版本可以保持索引存储微融合,并且广播负载无论如何都是单个纯 uop,而不是微融合 ALU+负载。

在 Skylake 上,如果内存带宽不是瓶颈,它可能会接近每 5 个时钟周期 4 个 40 位组。(例如,具有良好的缓存阻塞。)一旦考虑到开销和缓存行拆分负载的成本会导致偶尔的停顿,那么每 40 位输入可能需要 1.5 个周期,即在 Skylake 上每 20 字节输入需要 6 个周期。

在其他 CPU(Haswell 和 Ryzen)上,变量计数变化将成为瓶颈,但您对此无能为力。我不认为有什么更好的。在 HSW 上是 3 微指令:p5 + 2p0。在 Ryzen 上它只有 1 uop,但它每 2 个时钟的吞吐量只有 1 个(对于 128 位版本),或者每 4 个时钟的 256 位版本需要 2 uop。

当心clang pessmizes _mm_storeh_pistore vpextrq [mem], xmm, 1:2 uops,shuffle + store。(而不是vmovhps:英特尔上的纯存储,没有 ALU)。GCC 将其编译为书面形式。


_mm256_broadcast_sd即使我真的想要,我也使用vpbroadcastq了,因为有一个内部函数需要一个指针操作数而不是__m256i(因为使用 AVX1,只存在内存源版本。但使用 AVX2,存在所有广播指令的寄存器源版本)。要使用_mm256_set1_epi64,我必须编写不违反严格别名(例如使用 memcpy)的纯 C 来执行未对齐的uint64_t加载。不过,我认为在当前 CPU 上使用 FP 广播负载不会损害性能。

我希望_mm256_broadcast_sd允许它的源操作数在没有 C++ 严格别名未定义行为的情况下对任何东西进行别名,同样的方式_mm256_loadu_ps。无论哪种方式,如果它不内联到存储到的函数中,它*src甚至可以在实践中工作。所以也许 memcpy 未对齐的负载会更有意义!

过去,我在让编译器pmovzxdw xmm0, [mem]从代码中发出类似的代码时得到了不好的结果_mm_cvtepu16_epi32( _mm_loadu_si64(ptr) );你经常得到一个实际的movq负载 + reg-reg pmovzx。这就是我没有尝试的原因_mm256_broadcastq_epi64(__m128i)


老想法;如果我们已经需要一个字节洗牌,我们不妨使用纯字移位而不是 vpmultishift。

使用 AVX512VBMI (IceLake, CannonLake),您可能需要vpmultishiftqb. 我们可以在首先将正确的字节放在正确的位置之后,为整个组向量完成所有工作,而不是一次广播/移动一个组。

您仍然需要/想要一个带有一些 AVX512 但不是 AVX512VBMI 的 CPU 版本(例如 Skylake-avx512)。可能vpermd+vpshufb可以将我们需要的字节放入我们想要的 128 位通道。

我认为我们不能只使用 dword 粒度移位来允许合并屏蔽而不是 qword 移位后的 dword 混合。我们也许可以合并屏蔽一个vpblendw,保存一个vpblendd

IceLake 有 1/clockvpermwvpermb, single-uop。(它在另一个端口上有一个第二个洗牌单元,可以处理一些洗牌微指令)。所以我们可以加载一个包含 4 或 8 组 4 个元素的完整向量,并有效地将每个字节打乱到位。我认为每个 CPUvpermb都有它的单 uop。(但这只是 Ice Lake 和限量发行的 Cannon Lake)。

vpermt2w(将 2 个向量中的 16 位元素组合成任意顺序)是每 2 个时钟吞吐量一个。(IceLake-Y 的 InstLatx64),所以不幸的是它不如单向量洗牌效率高。

无论如何,您可以像这样使用它:

  • 64 字节/512 位加载(包括最后从 8x 8 字节组而不是 8x 5 字节组的一些过度读取。可选地使用零掩码加载以使其在数组末尾附近安全,这要归功于故障抑制)
  • vpermb将包含每个字段的 2 个字节放入所需的最终目标位置。
  • vpsrlvw+vpandq将每个 10 位字段提取为 16 位字

这大约是 4 微秒,不包括商店。

您可能想要包含A连续元素的高半部分vextracti64x4和包含 B 和 C 元素的低半部分vmovdquvextracti128存储。

或者为 2xvpblenddd设置 256 位存储。(使用 2 个不同的vpermb向量来创建 2 个不同的布局。)

对于更广泛的商店,您不需要vpermt2wvpermt2d组合相邻的向量。

如果没有 AVX512VBMI,可能vpermd+vpshufb可以将所有必要的字节放入每个 128 位块而不是vpermb. 其余的只需要 Skylake-X 拥有的 AVX512BW。

于 2019-08-22T20:32:31.107 回答