在AVX寄存器内旋转字节的有效方法

总结/ tl; dr：有没有办法按位旋转YMM寄存器中的一个字节(使用AVX),而不是进行2x移位并将结果混合在一起？

对于YMM寄存器中的每8个字节,我需要在其中左旋7个字节.每个字节需要比前者更向左旋转一个位.因此,1字节应旋转0位,第7字节旋转6位.

目前,我做了一个实现,通过[我在这里使用1位旋转作为示例]将寄存器1位向左移位,并将7向右移位.然后我使用混合操作(内部操作_mm256_blend_epi16)从第一个和第二个临时结果中选择正确的位以获得我的最终旋转字节.
每个字节总共需要2个移位操作和1个混合操作,并且需要旋转6个字节,因此每个字节有18个操作(移位和混合具有几乎相同的性能).

必须有一种更快的方法来做到这一点,而不是使用18个操作来旋转单个字节！

此外,我需要在新寄存器中组装所有字节.我通过将带有“set”指令的7个掩码加载到寄存器中来完成此操作,因此我可以从每个寄存器中提取正确的字节.我和这些掩码与寄存器一起从中提取正确的字节.然后,我将单字节寄存器一起异或,以获得具有所有字节的新寄存器.
这需要总共7 7 6个操作,因此另外20个操作(每个寄存器).

我可以使用提取内在函数(_mm256_extract_epi8)来获取单个字节,然后使用_mm256_set_epi8来组合新的寄存器,但我还不知道是否会更快. (英特尔内在指南中没有列出这些功能的性能,所以也许我在这里误解了一些内容.)

这给每个寄存器总共38次操作,这似乎不是在寄存器内以不同方式旋转6个字节的最佳值.

我希望有更多精通AVX / SIMD的人可以在这里指导我 – 无论我是以错误的方式解决这个问题 – 因为我觉得我现在可能正在这样做.

解决方法

XOP instruction set确实提供了 _mm_rot_epi8()(这不是特定于Microsoft的;它也可以在4.4或更早版本的GCC中使用,并且也应该在最近的clang中提供).它可用于以128位为单位执行所需任务.不幸的是,我没有支持XOP的cpu,所以我无法测试.

在AVX2上,将256位寄存器分成两半,一个包含偶数字节,另一个奇数字节右移8位,允许16位向量乘法.给定常量(使用GCC 64位组件数组格式)

static const __m256i epi16_highbyte = { 0xFF00FF00FF00FF00ULL,0xFF00FF00FF00FF00ULL,0xFF00FF00FF00FF00ULL };
static const __m256i epi16_lowbyte  = { 0x00FF00FF00FF00FFULL,0x00FF00FF00FF00FFULL,0x00FF00FF00FF00FFULL };
static const __m256i epi16_oddmuls  = { 0x4040101004040101ULL,0x4040101004040101ULL,0x4040101004040101ULL };
static const __m256i epi16_evenmuls = { 0x8080202008080202ULL,0x8080202008080202ULL,0x8080202008080202ULL };

旋转操作可以写成

__m256i byteshift(__m256i value)
{
    return _mm256_or_si256(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value,epi16_lowbyte),epi16_oddmuls),8),_mm256_and_si256(_mm256_mullo_epi16(_mm256_and_si256(_mm256_srai_epi16(value,epi16_evenmuls),epi16_highbyte));
}

已经过验证,使用GCC-4.8.4可以在Intel Core i5-4200U上产生正确的结果.例如,输入向量(作为单个256位十六进制数)

88 87 86 85 84 83 82 81 38 37 36 35 34 33 32 31 28 27 26 25 24 23 22 21 FF FE FD FC FB FA F9 F8

旋转进去

44 E1 D0 58 24 0E 05 81 1C CD C6 53 A1 CC 64 31 14 C9 C4 52 21 8C 44 21 FF BF BF CF DF EB F3 F8

最左边的八位字节向左旋转7位,接下来的6位,依此类推;第七个八位字节不变,第八个八位字节旋转7位,依此类推,所有32个八位字节.

我不确定上面的函数定义是否编译成最佳的机器代码 – 这取决于编译器 – 但我对它的性能肯定很满意.

由于您可能不喜欢上述简洁的函数格式,因此它采用程序化的扩展形式：

static __m256i byteshift(__m256i value)
{
    __m256i low,high;
    high = _mm256_srai_epi16(value,8);
    low = _mm256_and_si256(value,epi16_lowbyte);
    high = _mm256_and_si256(high,epi16_lowbyte);
    low = _mm256_mullo_epi16(low,epi16_lowmuls);
    high = _mm256_mullo_epi16(high,epi16_highmuls);
    low = _mm256_srli_epi16(low,8);
    high = _mm256_and_si256(high,epi16_highbyte);
    return _mm256_or_si256(low,high);
}

在评论中,Peter Cordes建议更换srai和srli,可能是最终和/或者使用blendv.前者很有意义,因为它纯粹是一种优化,但后者可能不是(但是,在当前的Intel cpu上！)实际上更快.

我尝试了一些微基准测试,但无法获得可靠的结果.我通常在x86-64上使用TSC,并使用存储到阵列的输入和输出来获取几十万个测试的中值.

我认为如果我只是在这里列出变体是最有用的,所以任何需要这样的功能的用户都可以在他们的实际工作负载上做一些基准测试,并测试是否存在任何可衡量的差异.

我也同意他建议使用奇数和偶数而不是高和低,但请注意,因为向量中的第一个元素编号为元素0,所以第一个元素是偶数,第二个元素是偶数,依此类推.

#include <immintrin.h>

static const __m256i epi16_oddmask  = { 0xFF00FF00FF00FF00ULL,0xFF00FF00FF00FF00ULL };
static const __m256i epi16_evenmask = { 0x00FF00FF00FF00FFULL,0x00FF00FF00FF00FFULL };
static const __m256i epi16_evenmuls = { 0x4040101004040101ULL,0x4040101004040101ULL };
static const __m256i epi16_oddmuls  = { 0x8080202008080202ULL,0x8080202008080202ULL };

/* Original version suggested by Nominal Animal. */
__m256i original(__m256i value)
{
    return _mm256_or_si256(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value,epi16_evenmask),epi16_oddmask));
}

/* Optimized as suggested by Peter Cordes,without blendv */
__m256i no_blendv(__m256i value)
{
    return _mm256_or_si256(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value,_mm256_and_si256(_mm256_mullo_epi16(_mm256_srli_epi16(value,with blendv.
 * This is the recommended version. */
__m256i optimized(__m256i value)
{
    return _mm256_blendv_epi8(_mm256_srli_epi16(_mm256_mullo_epi16(_mm256_and_si256(value,_mm256_mullo_epi16(_mm256_srli_epi16(value,epi16_oddmask);
}

以下是以显示各个操作的方式编写的相同功能.虽然它根本不影响理智编译器,但我已经标记了函数参数和每个临时值const,因此很明显如何将每个插入到后续表达式中,以简化上述简洁形式的函数.

__m256i original_verbose(const __m256i value)
{
    const __m256i odd1  = _mm256_srai_epi16(value,8);
    const __m256i even1 = _mm256_and_si256(value,epi16_evenmask);
    const __m256i odd2  = _mm256_and_si256(odd1,epi16_evenmask);
    const __m256i even2 = _mm256_mullo_epi16(even1,epi16_evenmuls);
    const __m256i odd3  = _mm256_mullo_epi16(odd3,epi16_oddmuls);
    const __m256i even3 = _mm256_srli_epi16(even3,8);
    const __m256i odd4  = _mm256_and_si256(odd3,epi16_oddmask);
    return _mm256_or_si256(even3,odd4);
}

__m256i no_blendv_verbose(const __m256i value)
{
    const __m256i even1 = _mm256_and_si256(value,epi16_evenmask);
    const __m256i odd1  = _mm256_srli_epi16(value,8);
    const __m256i even2 = _mm256_mullo_epi16(even1,epi16_evenmuls);
    const __m256i odd2  = _mm256_mullo_epi16(odd1,epi16_oddmuls);
    const __m256i even3 = _mm256_srli_epi16(even2,8);
    const __m256i odd3  = _mm256_and_si256(odd2,odd3);
}

__m256i optimized_verbose(const __m256i value)
{
    const __m256i even1 = _mm256_and_si256(value,8);
    return _mm256_blendv_epi8(even3,odd2,epi16_oddmask);
}

我个人最初以上面的详细形式编写我的测试函数,因为形成简洁版本是一组简单的复制粘贴.但是,我测试两个版本以验证是否存在任何错误,并保持可访问的详细版本(作为注释等),因为简洁版本基本上是只写的.编辑详细版本,然后将其简化为简洁形式要比编辑简洁版本容易得多.

在AVX寄存器内旋转字节的有效方法

解决方法

相关文章