gpt4 book ai didi

sse - SIMD:位包有符号整数

转载 作者:行者123 更新时间:2023-12-04 15:00:13 33 4
gpt4 key购买 nike

可以使用“位打包”技术压缩无符号整数:在一个无符号整数 block 中,只存储有效位,当一个 block 中的所有整数都“小”时,会导致数据压缩。该方法称为 FOR (引用框架)。

有SIMD libraries可以非常有效地做到这一点。

现在我想使用类似 FOR 的技术来编码有符号整数,例如来自未排序的无符号整数的差分序列。每个有符号整数的符号需要存储在某处,有两种选择:

  1. 将标志存储在单独的数据 block 中。这会增加开销。
  2. 将符号与每个有符号整数的绝对值一起存储。

我现在正在走路径 2。 2-s 补码在 msb(最高有效位)中有符号位,因此这不适用于位打包 à la FOR。一种可能性是将符号存储在 lsb(最低有效位)中。以这种方式存储有符号整数是非常不寻常的,据我所知,没有任何指令支持这种方式。现在的问题是:能否使用 SIMD 指令有效地编码/解码这些 lsb 符号整数?

我认为 AVX-512 _mm_testn_epi32_mask 可用于从每个 uint32 中提取 lsb,然后是移位,然后是某种类型的两个 mask_extract?相当复杂。

最佳答案

未经测试ZigZag C 中使用 SSE2 处理 64 位整数的示例:

(注意:SSE2 缺少一些 64 位指令...)

#include <emmintrin.h>


// from comment by Peter-Cordes
__m128i zigzag_encode_epi64(__m128i v) {
__m128i signmask = _mm_shuffle_epi32(v, _MM_SHUFFLE(3,3,1,1));
signmask = _mm_srai_epi32(signmask, 31);
return _mm_xor_si128(_mm_add_epi64(v, v), signmask);
}


__m128i zigzag_decode_epi64 (__m128i v) {
__m128i signmask = _mm_and_si128(_mm_set_epi32(0, 1, 0, 1), v);
signmask = _mm_sub_epi64(_mm_setzero_si128(), signmask);
return _mm_xor_si128(_mm_srli_epi64(v, 1), signmask);
}


// no constant
__m128i zigzag_decodev3_epi64 (__m128i v) {
__m128i t = _mm_srli_epi64(v, 1);
__m128i signmask = _mm_sub_epi64(_mm_slli_epi64(t, 1), v);
return _mm_xor_si128(t, signmask);
}

Zigzag 适用于按位 varint。但是,字节组 varint 可能希望“从可变位宽进行符号扩展”。


32 位示例

我更喜欢比较而不是算术移位。我假设 - 当展开时 - 比较将有 1 个周期的低延迟。

__m128i zigzag_encode_epi32 (__m128i v) {
__m128i signmask =_mm_cmpgt_epi32(_mm_setzero_si128(), v);
return _mm_xor_si128(_mm_add_epi32(v, v), signmask);
}


__m128i zigzag_decode_epi32 (__m128i v) {
const __m128i m = _mm_set1_epi32(1);
__m128i signmask =_mm_cmpeq_epi32(_mm_and_si128(m, v), m);
return _mm_xor_si128(_mm_srli_epi32(v, 1), signmask);
}


__m128i delta_encode_epi32 (__m128i v, __m128i prev) {
return _mm_sub_epi32(v, _mm_alignr_epi8(v, prev, 12));
}


// prefix sum (see many of answers around stackoverflow...)
__m128i delta_decode_epi32 (__m128i v, __m128i prev) {
prev = _mm_shuffle_epi32(prev, _MM_SHUFFLE(3,3,3,3)); // [P P P P]
v = _mm_add_epi32(v, _mm_slli_si128(v, 4)); // [A AB BC CD]
prev = _mm_add_epi32(prev, v); // [PA PAB PBC PCD]
v = _mm_slli_si128(v, 8); // [0 0 A AB]
return _mm_add_epi32(prev, v); // [PA PAB PABC PABCD]
}


__m128i delta_zigzag_encode_epi32 (__m128i v, __m128i prev) {
return zigzag_encode_epi32(delta_encode_epi32(v, prev));
}


__m128i delta_zigzag_decode_epi32 (__m128i v, __m128i prev) {
return delta_decode_epi32(zigzag_decode_epi32(v), prev);
}

注意:Delta 编码会更快(往返/解码),以便在编码时转置元素然后在解码期间再次转置它们;水平前缀和真的很慢。然而,确定每个批处理中要转置的元素的最佳数量似乎是一个难题。

关于sse - SIMD:位包有符号整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/67088336/

33 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com