11

int compare_16bytes(__m128i lhs, __m128i rhs)SSE 命令を使用して 2 つの 16 バイトの数値を比較する関数を作成しました。この関数は、比較の実行後に等しいバイト数を返します。

ここで、上記の関数を使用して、任意の長さの 2 つのバイト配列を比較したいと思います。長さが 16 バイトの倍数ではない可能性があるため、この問題に対処する必要があります。以下の関数の実装を完了するにはどうすればよいですか? 以下の機能を改善するにはどうすればよいですか？

int fast_compare(const char* s, const char* t, int length)
{
    int result = 0;

    const char* sPtr = s;
    const char* tPtr = t;

    while(...)
    {
        const __m128i* lhs = (const __m128i*)sPtr;
        const __m128i* rhs = (const __m128i*)tPtr;

        // compare the next 16 bytes of s and t
        result += compare_16bytes(*lhs,*rhs);

        sPtr += 16;
        tPtr += 16;
    }

    return result;
}
4

4 に答える 4

5

@Mysticial が上記のコメントで述べているように、垂直方向に比較と合計を行い、メイン ループの最後で水平方向に合計します。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <emmintrin.h>

// reference implementation
int fast_compare_ref(const char *s, const char *t, int length)
{
    int result = 0;
    int i;

    for (i = 0; i < length; ++i)
    {
        if (s[i] == t[i])
            result++;
    }
    return result;
}

// optimised implementation
int fast_compare(const char *s, const char *t, int length)
{
    int result = 0;
    int i;

    __m128i vsum = _mm_set1_epi32(0);
    for (i = 0; i < length - 15; i += 16)
    {
        __m128i vs, vt, v, vh, vl, vtemp;

        vs = _mm_loadu_si128((__m128i *)&s[i]); // load 16 chars from input
        vt = _mm_loadu_si128((__m128i *)&t[i]);
        v = _mm_cmpeq_epi8(vs, vt);             // compare
        vh = _mm_unpackhi_epi8(v, v);           // unpack compare result into 2 x 8 x 16 bit vectors
        vl = _mm_unpacklo_epi8(v, v);
        vtemp = _mm_madd_epi16(vh, vh);         // accumulate 16 bit vectors into 4 x 32 bit partial sums
        vsum = _mm_add_epi32(vsum, vtemp);
        vtemp = _mm_madd_epi16(vl, vl);
        vsum = _mm_add_epi32(vsum, vtemp);
    }

    // get sum of 4 x 32 bit partial sums
    vsum = _mm_add_epi32(vsum, _mm_srli_si128(vsum, 8));
    vsum = _mm_add_epi32(vsum, _mm_srli_si128(vsum, 4));
    result = _mm_cvtsi128_si32(vsum);

    // handle any residual bytes ( < 16)
    if (i < length)
    {
        result += fast_compare_ref(&s[i], &t[i], length - i);
    }

    return result;
}

// test harness
int main(void)
{
    const int n = 1000000;
    char *s = malloc(n);
    char *t = malloc(n);
    int i, result_ref, result;

    srand(time(NULL));

    for (i = 0; i < n; ++i)
    {
        s[i] = rand();
        t[i] = rand();
    }

    result_ref = fast_compare_ref(s, t, n);
    result = fast_compare(s, t, n);

    printf("result_ref = %d, result = %d\n", result_ref, result);;

    return 0;
}

上記のテスト ハーネスをコンパイルして実行します。

$ gcc -Wall -O3 -msse3 fast_compare.c -o fast_compare
$ ./fast_compare
result_ref = 3955, result = 3955
$ ./fast_compare
result_ref = 3947, result = 3947
$ ./fast_compare
result_ref = 3945, result = 3945

上記の SSE コードには、 16 ビット/値を 32 ビット部分和_mm_madd_epi16にアンパックして累積するために使用する、自明ではないトリックが 1 つあります。私たちは(そしてもちろん)という事実を利用しています - ここでは実際に乗算を行っているのではなく、1 つの命令でアンパックして合計するだけです。0-1-1*-1 = 10*0 = 0

更新: 以下のコメントに記載されているように、このソリューションは最適ではありません。かなり最適な 16 ビット ソリューションを採用し、8 ビットから 16 ビットへのアンパッキングを追加して、8 ビット データで機能するようにしました。psadbwただし、8 ビット データの場合は、 /_mm_sad_epu8を使用するなど、より効率的な方法があります。この回答は、後世のためにここに残します。また、16ビットデータでこの種のことをしたい人のために残しますが、実際には、入力データのアンパックを必要としない他の回答の1つが受け入れられるはずです。

于 2013-03-09T21:50:20.340 に答える
3

16 x uint8 要素で部分和を使用すると、パフォーマンスがさらに向上する場合があります。
ループを内側のループと外側のループに分けました。
内側のループは uint8 要素を合計します (各 uint8 要素は最大 255 個の "1" を合計できます)。
ちょっとしたトリック: _mm_cmpeq_epi8 は等しい要素を 0xFF に設定し、(char)0xFF = -1 にすることで、合計から結果を引くことができます (1 を足すには -1 を引きます)。

fast_compare 用に最適化されたバージョンは次のとおりです。 

int fast_compare2(const char *s, const char *t, int length)
{
    int result = 0;
    int inner_length = length;
    int i;
    int j = 0;

    //Points beginning of 4080 elements block.
    const char *s0 = s;
    const char *t0 = t;


    __m128i vsum = _mm_setzero_si128();

    //Outer loop sum result of 4080 sums.
    for (i = 0; i < length; i += 4080)
    {
        __m128i vsum_uint8 = _mm_setzero_si128(); //16 uint8 sum elements (each uint8 element can sum up to 255).
        __m128i vh, vl, vhl, vhl_lo, vhl_hi;

        //Points beginning of 4080 elements block.
        s0 = s + i;
        t0 = t + i;

        if (i + 4080 <= length)
        {
            inner_length = 4080;
        }
        else
        {
            inner_length = length - i;
        }

        //Inner loop - sum up to 4080 (compared) results.
        //Each uint8 element can sum up to 255. 16 uint8 elements can sum up to 255*16 = 4080 (compared) results.
        //////////////////////////////////////////////////////////////////////////
        for (j = 0; j < inner_length-15; j += 16)
        {
              __m128i vs, vt, v;

              vs = _mm_loadu_si128((__m128i *)&s0[j]); // load 16 chars from input
              vt = _mm_loadu_si128((__m128i *)&t0[j]);
              v = _mm_cmpeq_epi8(vs, vt);             // compare - set to 0xFF where equal, and 0 otherwise.

              //Consider this: (char)0xFF = (-1)
              vsum_uint8 = _mm_sub_epi8(vsum_uint8, v); //Subtract the comparison result - subtract (-1) where equal.
        }
        //////////////////////////////////////////////////////////////////////////

        vh = _mm_unpackhi_epi8(vsum_uint8, _mm_setzero_si128());        // unpack result into 2 x 8 x 16 bit vectors
        vl = _mm_unpacklo_epi8(vsum_uint8, _mm_setzero_si128());
        vhl = _mm_add_epi16(vh, vl);    //Sum high and low as uint16 elements.

        vhl_hi = _mm_unpackhi_epi16(vhl, _mm_setzero_si128());   //unpack sum of vh an vl into 2 x 4 x 32 bit vectors
        vhl_lo = _mm_unpacklo_epi16(vhl, _mm_setzero_si128());   //unpack sum of vh an vl into 2 x 4 x 32 bit vectors

        vsum = _mm_add_epi32(vsum, vhl_hi);
        vsum = _mm_add_epi32(vsum, vhl_lo);
    }

    // get sum of 4 x 32 bit partial sums
    vsum = _mm_add_epi32(vsum, _mm_srli_si128(vsum, 8));
    vsum = _mm_add_epi32(vsum, _mm_srli_si128(vsum, 4));
    result = _mm_cvtsi128_si32(vsum);

    // handle any residual bytes ( < 16)
    if (j < inner_length)
    {
        result += fast_compare_ref(&s0[j], &t0[j], inner_length - j);
    }

    return result;
}
于 2016-06-20T22:15:54.003 に答える
1

SSE の整数比較では、すべてゼロまたはすべて 1 のバイトが生成されます。カウントする場合は、最初に比較結果を 7 だけ右シフト (算術ではなく) してから、結果ベクトルに追加する必要があります。最後に、要素を合計して結果ベクトルを減らす必要があります。この削減は、スカラー コードで行うか、一連の加算/シフトを使用して行う必要があります。通常、この部分は気にする価値はありません。

于 2013-03-09T17:59:29.607 に答える