时间戳

首页 > 解决方案 > 如何使用 SIMD 计算找到 4 个不同 Vector128 之间的最大值

c# - 如何使用 SIMD 计算找到 4 个不同 Vector128 之间的最大值

问题描述

我正在尝试用 SIMD 计算做一些事情。我的问题已经走了很远，然后我被卡住了，想知道如何做到这一点。

我认为最简单的方法是一步一步地描述我所做的事情：

我使用Vector128<byte>它，然后一次处理 16 个字节

  1. 我创建了一个二维数组（array2D），每列有 9 列和 16 行。我将数字按以下顺序排列：0 和 2。这意味着例如 Row: 0 只有 0。行：1 只有 2s 等。

  2. 现在我Avx.LoadVector128为每个列/维度给出： 9Vector128<byte>我输入：dimensionLIST

  3. 现在的任务是计算有多少数字：0 and 2可以在每一行找到。（我们有 16 行）。这些信息最终存储在：counts[0]

  4. 看中的结果counts[0]。MessageBox如下图所示： MessageBox.Show(counts[0]);

（代表 16 行）
[0,9,0,9,0,9,0,9,0,9,0,9,0,9,0,9]

9, 2 每隔一行找到。


现在的目标是计算在[0,9,0,9,0,9,0,9,0,9,0,9,0,9,0,9]中找到了多少个“9”是 8。

所以不知何故，我们希望整数 8 在这里以某种方式作为标量？

    public unsafe static void SIMDfunction()
    {
        //Create dummy values
        byte[,] array2D = new byte[9, 16]; byte num = 0;
        for (int i = 0; i < 9; i++)
        {
            for (int i2 = 0; i2 < 16; i2++)
            {
                array2D[i, i2] = num;
                if (num == 0) { num = 2; } else { num = 0; }
            }
        }


        /*----------------------------------------------------------------------------------------*/
        unsafe
        {
            //Below starts SIMD calculations!
            fixed (byte* ptr = array2D)
            {
                //Add all 9 dimensions as Vector128
                List<Vector128<byte>> dimensionLIST = new List<Vector128<byte>>();
                for (int i = 0; i < 9; i++)
                {
                    byte* featuredimension = &*((byte*)(ptr + i * 16)); //This gives the first dimension with start: 0
                    dimensionLIST.Add(Avx.LoadVector128(&featuredimension[0])); //add "featuredimension" as a vector of the 16 next numbers: [0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3]
                }


                //Now count how many of: 0,1,2,3 are found in total in all "dimensionLIST" together?
                Span<Vector128<byte>> counts = stackalloc Vector128<byte>[1];
                Span<Vector128<UInt64>> sum64 = stackalloc Vector128<UInt64>[1];
                byte nr2 = 2; byte nr3 = 9; 
                for (int i = 0; i < dimensionLIST.Count; i++) //Each column
                {
                    //Compare: dimensionLIST[i] with Vector128 val to find out how many matches of 2 in this loop
                    //[0,2,0,2,0,2,0,2,0,2,0,2,0,2,0,2], [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]
                    var match = Avx.CompareEqual(dimensionLIST[i], Vector128.Create(nr2)); //Create Vector128 for numbers: 2
                    counts[0] = Avx.Subtract(counts[0], match);
                }
                //STEP1: Show result on how many 2s are found == 9 occurences of "2"!
                var result = Avx.CompareEqual(Vector128.Create(nr3), counts[0]); //counts[0]: [0,9,0,9,0,9,0,9,0,9,0,9,0,9,0,9] (In total 9 2s are found on those indexes)


                //result:[0,255,0,255,0,255,0,255,0,255,0,255,0,255,0,255] Puts - 1 where integer == 9
                MessageBox.Show(result.ToString());

                //Now the goal is to count how many "9" that were found in: [0,9,0,9,0,9,0,9,0,9,0,9,0,9,0,9] which is 8.
                //So somehow we want the the integer 8 as Scalar somehow here?
            }
        }
    }

标签： c#arraysssesimdavx

解决方案

对已编辑问题的回答：为一个向量水平计数匹配项

这似乎过于简单，就像在实践中你不会知道那9是你正在寻找的价值。但是由于您在源代码中对其进行了硬编码，也许这就是您想要的。

pcmpeqb您正在寻找与您正在寻找的元素完全匹配的正确轨道。然后你只需要对这些匹配进行水平求和：

// This is C, sorry I don't know C#
#include <immintrin.h>

// input: a vector like {0,9,0,9,...} and a value like 9 or 0
int count_matches(__m128i v, int val)
{
    __m128i matches = _mm_cmpeq_epi8(v, _mm_set1_epi8(val));  // 0 or -1
    matches = _mm_sub_epi8(_mm_setzero_si128(), matches);     // 0 or +1
    __m128i hsums = _mm_sad_epu8(matches, _mm_setzero_si128());  // psadbw against 0 = hsum of each qword half = count ones
    __m128i high = _mm_unpackhi_epi64(hsums, hsums);      // punpckhqdq to extract high half
    hsums = _mm_add_epi32(hsums, high);                // paddd or paddw would be fine
    unsigned sum = _mm_cvtsi128_si32(hsums);           // movd to extract the low 32-bit scalar

    return sum;
}

（Godbolt - 有趣的事实：clang10 从内存“优化” sub 到，即使wherepand与.silly 编译器具有相同的性能。）set1_epi8(1)-march=skylakevpsubbvpand

即只是水平总和结果中“真实”元素的数量pcmpeqb。

如果我们刚刚水平添加了 0 或 255 个元素，那么之前用psubb(或pand用 set1(1))psadbw求反比我想出的任何方法都更有效。sum*255sum

-(int8_t)sum或(int8_t)-sum编译为movsx eax, al/neg eax这是 2 条指令（假设我们需要将结果作为 32 位整数），比vpsubb针对已经存在的零向量更糟糕。如果没有 AVX，它可能会更好，或者如果您在后端 SIMD 执行端口而不是前端遇到瓶颈。

sum/255显然会很糟糕，编译器没有足够的信息来优化它，这就是我的答案不使用它的原因。另一种选择是(sum + 16) >> 8，它恰好为从到的所有i*255值给出正确的答案。但是 Intel CPU 上的转换在端口 0 或 6 上运行，而不是任何ALU 端口，所以这可能比 neg/movsx 更糟糕。 并且可以在任何 ALU 端口上运行，因此在避免/不应对来自周围代码的后端 ALU 压力方面最为灵活。0*25516*255negmovsx

vpsubb在 Intel Skylake 及更高版本的 p0、p1、p5 中的任何一个上运行，但在早期 CPU 上不太灵活。如果没有 AVX，它可能需要一个movdqa寄存器副本，或者重做一个异或归零来为psadbw.

回答原始/标题问题，找出每个垂直 SIMD 元素中最大值来自 4 个向量中的哪一个

在计数[0..3] 之后，如果计数顶部有备用位，则左移 2 和 OR 与 0..3 标签号（以记录它的来源），以便您可以pmaxub使用选择最大的计数，并带上标签。

SIMD MAX 操作将作用于整体(counts[i] << 2) | i，因此计数部分是整数值的最高有效部分，但标记部分是整数 MAX 操作的一部分。

“标签”将充当决胜局，偏向较高i（即3在您的情况下）。如果您需要将相等的计数视为 vector 0，则与 3 或其他东西进行异3或或倒数，以便标签位具有您想要的平局顺序中的整数值。

// kind of pseudo-code, I don't know C# so this is more like C with intrinsics
for (int i=0 ; i<4 ; i++){
    counts[i] <<= 2;   // emulate non-existent psllb somehow; 2x paddb or psllw / pand
    counts[i] |= set1(i);  // low 2 bits = tag
}
__m128i m0 = _mm_max_epu8(counts[0], counts[1]);
__m128i m1 = _mm_max_epu8(counts[2], counts[3]);
__m128i max = _mm_max_epu8(m0, m1);
max = _mm_and_si128(max, _mm_set1_epi8(3));  // discard high 6 bits, keep low 2 = tag

或者，如果您在不丢失重要位的情况下没有左移空间，请使用( )解压缩set1(i)并使用2x max -> 1x max 的树，分别用于高/低半部分。所以每个整数都是。_mm_max_epu16pmaxuw(count<<8) | i

然后你必须重新打包到低字节（标签），可能需要你屏蔽掉_mm_packs_epi16（packsswb）之前的值字节。punpcklbw/没有真正的逆punpckhbw；打包指令做有符号饱和而不是截断。

然而，最后的掩码 + 打包步骤只是 2x PAND，set1_epi16(0x00FF)输入为馈送一个packsswb，并不太复杂。

您可以首先通过对大型数组或列表的 4 桶直方图进行微优化来加速计算计数 -从（循环结束时的 3 个 SIMD 减法，每次迭代保存比较/子）推断。counts[3]set1(total/16) - counts[0..2]

推荐阅读