Найти все позиции совпадений в SIMD Avx.CompareEqual или для всего массива при подсчете совпадений - PullRequest
Новая
       107

Найти все позиции совпадений в SIMD Avx.CompareEqual или для всего массива при подсчете совпадений

0 голосов
/ 16 апреля 2020

У меня есть вопрос, возможно ли это вообще с использованием инструкций SIMD или может быть какое-то гибридное решение SIMD / Normal C# кодовое решение того, что я есть пытаясь сделать или, если это невозможно, и принесет много пользы SIMD-инструкциям, чтобы это было интересно.

Мой код считает, сколько 0,1,2,3 существует в: inputArray ( Микрооптимизация гистограммы с 4 сегментами большого массива или списка ). Результат показан в: countArray
Правильный ответ на этот вопрос: 3,9,1,3.

Мой вопрос сейчас таков:
Как видно, мы также прошли: indexArray к функции. Если мы возьмем 0 из inputArray в качестве примера, где у нас есть 3 вхождения. В indexArray мы видим, что эти вхождения имеют индексы: 9,43,5

Интересно, возможно ли добавить / собрать эту информацию, например, в 4 контейнерах для каждого возможных значений элемента (0,1,2,3) в inputArray?

В приведенной ниже части кода мы видим, где находятся индексы, например: val = 1: 0,9,10

Я не знаю, можно ли как-то поймать эти индексы, которые могли бы map/get индексы из indexArray?

Основная цель, например: ´0´ в конце получить массив следующим образом:
int[] indexes0 = new int[3]; //But we dont know that it will be 3 beforehand indexes0[0] = 9; indexes0[1] = 43; indexes0[2] = 5;

[1,0,0,0,0,0,0,0,0,1,1,0 , 0,0,0,0] 

// accumulate match counts into 4 vectors of 8-bit counters, one for each val
var v = Avx.LoadVector128(&fixedInput[0]);
for (byte val = 0; val < 4; val++)
{
   //[1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0] -CompareEqual to: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
   var match = Avx.CompareEqual(v, Vector128.Create(val)); 
   counts[val] = Avx.Subtract(counts[val], match);   // count -= 0 or -1
}

(Обратите внимание: у меня есть процессор Piledriver, который не может запустить AVX2)

Полный код (упрощено для массива это только одна ширина вектора): 

using System.Runtime.Intrinsics;
using System.Runtime.Intrinsics.X86;
private void button3_Click(object sender, EventArgs e)
{
    //Create 16 indexes with numbers between: 0-3. The goal is to count how many of those occurences we have for the numbers: 0-3
    byte[] v1 = new byte[16]; int[] v2 = new int[16];

    v1[0] = 0; v2[0] = 9;
    v1[1] = 1; v2[1] = 12;
    v1[2] = 2; v2[2] = 55;
    v1[3] = 3; v2[3] = 23;
    v1[4] = 1; v2[4] = 568;
    v1[5] = 1; v2[5] = 4;
    v1[6] = 1; v2[6] = 6;
    v1[7] = 1; v2[7] = 1008;
    v1[8] = 1; v2[8] = 188800;
    v1[9] = 0; v2[9] = 43;
    v1[10] = 0; v2[10] = 5;
    v1[11] = 3; v2[11] = 2;
    v1[12] = 1; v2[12] = 1;
    v1[13] = 1; v2[13] = 58;
    v1[14] = 1; v2[14] = 8;
    v1[15] = 3; v2[15] = 15;
    /*---------------*/

    ReadOnlySpan<byte> inputArray = v1;
    ReadOnlySpan<int> indexArray = v2;

    //Call function
    countElements(inputArray, indexArray);
}

// simplified for inputArray.Count == 16 exactly, no looping or cleanup
// shows counts, doesn't find positions at all
private unsafe static void countElements(ReadOnlySpan<byte> inputArray, ReadOnlySpan<int> indexArray)
{
    int[,] indexes0123 = new int[,] { }; //Store arrays for indexes found for the numbers: 0,1,2,3 in the "indexArray"


    //Below starts the SIMD calculations!
    int[] countArray = new int[4];
    Span<Vector128<byte>> counts = stackalloc Vector128<byte>[4];
    Span<Vector128<UInt64>> sum64 = stackalloc Vector128<UInt64>[4];
    unsafe
    {
        fixed (byte* fixedInput = inputArray)
        {
            var v = Avx.LoadVector128(&fixedInput[0]);
            for (byte val = 0; val < 4; val++)
            {
                //[1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0] -CompareEqual to: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
                var match = Avx.CompareEqual(v, Vector128.Create(val)); 
                counts[val] = Avx.Subtract(counts[val], match); 
            }

            //Here SumAbsoluteDifferences
            for (int i3 = 0; i3 < 4; i3++)
            {
                sum64[i3] = Sse2.Add(sum64[i3], Sse2.SumAbsoluteDifferences(counts[i3], Vector128<byte>.Zero).AsUInt64()); //sum64: <2,0,0,0,3,0,0,0>
            }

            //UnpackHigh and get the lower element from the Vector128<UInt64>
            for (int i3 = 0; i3 < 4; i3++)
            {
                Vector128<UInt64> upper = Sse2.UnpackHigh(sum64[i3], sum64[i3]).AsUInt64(); //3
                countArray[i3] += Sse2.Add(sum64[i3], upper).ToScalar();
            }


            //We now know how many 0,1,2,3 we have of each: (But we also need to collect which indexes from "indexlist" each of these 4 buckets has)
            //3,9,1,3
            MessageBox.Show(countArray[0] + "," + countArray[1] + "," + countArray[2] + "," + countArray[3]); 
        }
    }
}
...