Как оптимизировать C-код с помощью SSE-intrinsics для упакованных 32x32 => 64-битных умножений и распаковывать половинки этих результатов для (поля Галуа) - PullRequest
Новая
       17

Как оптимизировать C-код с помощью SSE-intrinsics для упакованных 32x32 => 64-битных умножений и распаковывать половинки этих результатов для (поля Галуа)

8 голосов
/ 22 октября 2011

Я некоторое время боролся с производительностью сетевого кодирования в разрабатываемом приложении (см. Оптимизация SSE-кода , Повышение производительности сетевого кодирования-кодирования и дистрибутив OpenCL ). Теперь я довольно близок к достижению приемлемой производительности. Это текущее состояние самого внутреннего цикла (где тратится> 99% времени выполнения): 

while(elementIterations-- >0)
{   
    unsigned int firstMessageField = *(currentMessageGaloisFieldsArray++);
    unsigned int secondMessageField = *(currentMessageGaloisFieldsArray++);
    __m128i valuesToMultiply = _mm_set_epi32(0, secondMessageField, 0, firstMessageField);
    __m128i mulitpliedHalves = _mm_mul_epu32(valuesToMultiply, fragmentCoefficentVector);
}

Есть ли у вас какие-либо предложения по дальнейшей оптимизации? Я понимаю, что без контекста трудно обойтись, но любая помощь приветствуется!

Ответы [ 2 ]

9 голосов
/ 25 октября 2011

Теперь, когда я не сплю, вот мой ответ:

В вашем исходном коде узкое место почти наверняка _mm_set_epi32.Эта единственная внутренняя сущность компилируется в этот беспорядок в вашей сборке: 

633415EC  xor         edi,edi  
633415EE  movd        xmm3,edi  
...
633415F6  xor         ebx,ebx  
633415F8  movd        xmm4,edi  
633415FC  movd        xmm5,ebx  
63341600  movd        xmm0,esi  
...
6334160B  punpckldq   xmm5,xmm3  
6334160F  punpckldq   xmm0,xmm4 
...
63341618  punpckldq   xmm0,xmm5

Что это?9 инструкций?!?!?! Чистые накладные расходы ...

Еще одно странное место в том, что компилятор не объединяет добавления и загрузки: 

movdqa      xmm3,xmmword ptr [ecx-10h]
paddq       xmm0,xmm3

были объединены в: 

paddq       xmm0,xmmword ptr [ecx-10h]

Я не уверен, что компилятор потерял сознание или у него действительно была законная причина сделать это ... В любом случае, это мелочь по сравнению с_mm_set_epi32.

Отказ от ответственности: Код, который я представлю здесь, нарушает строгие псевдонимы.Но для достижения максимальной производительности часто требуются нестандартные совместимые методы.

Решение 1: нет векторизации

В этом решении предполагается, что allZero действительно все нули.

Цикл на самом деле проще, чем кажется.Поскольку арифметики немного, может быть лучше просто не векторизовать: 

//  Test Data
unsigned __int32 fragmentCoefficentVector = 1000000000;

__declspec(align(16)) int currentMessageGaloisFieldsArray_[8] = {10,11,12,13,14,15,16,17};
int *currentMessageGaloisFieldsArray = currentMessageGaloisFieldsArray_;

__m128i currentUnModdedGaloisFieldFragments_[8];
__m128i *currentUnModdedGaloisFieldFragments = currentUnModdedGaloisFieldFragments_;
memset(currentUnModdedGaloisFieldFragments,0,8 * sizeof(__m128i));


int elementIterations = 4;

//  The Loop
while (elementIterations > 0){
    elementIterations -= 1;

    //  Default 32 x 32 -> 64-bit multiply code
    unsigned __int64 r0 = currentMessageGaloisFieldsArray[0] * (unsigned __int64)fragmentCoefficentVector;
    unsigned __int64 r1 = currentMessageGaloisFieldsArray[1] * (unsigned __int64)fragmentCoefficentVector;

    //  Use this for Visual Studio. VS doesn't know how to optimize 32 x 32 -> 64-bit multiply
//    unsigned __int64 r0 = __emulu(currentMessageGaloisFieldsArray[0], fragmentCoefficentVector);
//    unsigned __int64 r1 = __emulu(currentMessageGaloisFieldsArray[1], fragmentCoefficentVector);

    ((__int64*)currentUnModdedGaloisFieldFragments)[0] += r0 & 0x00000000ffffffff;
    ((__int64*)currentUnModdedGaloisFieldFragments)[1] += r0 >> 32;
    ((__int64*)currentUnModdedGaloisFieldFragments)[2] += r1 & 0x00000000ffffffff;
    ((__int64*)currentUnModdedGaloisFieldFragments)[3] += r1 >> 32;

    currentMessageGaloisFieldsArray     += 2;
    currentUnModdedGaloisFieldFragments += 2;
}

, которая компилируется в x64: 

$LL4@main:
mov ecx, DWORD PTR [rbx]
mov rax, r11
add r9, 32                  ; 00000020H
add rbx, 8
mul rcx
mov ecx, DWORD PTR [rbx-4]
mov r8, rax
mov rax, r11
mul rcx
mov ecx, r8d
shr r8, 32                  ; 00000020H
add QWORD PTR [r9-48], rcx
add QWORD PTR [r9-40], r8
mov ecx, eax
shr rax, 32                 ; 00000020H
add QWORD PTR [r9-24], rax
add QWORD PTR [r9-32], rcx
dec r10
jne SHORT $LL4@main

и в x86: 

$LL4@main:
mov eax, DWORD PTR [esi]
mul DWORD PTR _fragmentCoefficentVector$[esp+224]
mov ebx, eax
mov eax, DWORD PTR [esi+4]
mov DWORD PTR _r0$31463[esp+228], edx
mul DWORD PTR _fragmentCoefficentVector$[esp+224]
add DWORD PTR [ecx-16], ebx
mov ebx, DWORD PTR _r0$31463[esp+228]
adc DWORD PTR [ecx-12], edi
add DWORD PTR [ecx-8], ebx
adc DWORD PTR [ecx-4], edi
add DWORD PTR [ecx], eax
adc DWORD PTR [ecx+4], edi
add DWORD PTR [ecx+8], edx
adc DWORD PTR [ecx+12], edi
add esi, 8
add ecx, 32                 ; 00000020H
dec DWORD PTR tv150[esp+224]
jne SHORT $LL4@main

Возможно, оба они уже работают быстрее, чем ваш исходный (SSE) код ... На x64, развертывание сделает его еще лучше.

Решение 2: SSE2 Integer Shuffle

Это решение разворачивает цикл в 2 итерации: 

//  Test Data
__m128i allZero = _mm_setzero_si128();
__m128i fragmentCoefficentVector = _mm_set1_epi32(1000000000);

__declspec(align(16)) int currentMessageGaloisFieldsArray_[8] = {10,11,12,13,14,15,16,17};
int *currentMessageGaloisFieldsArray = currentMessageGaloisFieldsArray_;

__m128i currentUnModdedGaloisFieldFragments_[8];
__m128i *currentUnModdedGaloisFieldFragments = currentUnModdedGaloisFieldFragments_;
memset(currentUnModdedGaloisFieldFragments,0,8 * sizeof(__m128i));


int elementIterations = 4;

//  The Loop
while(elementIterations > 1){   
    elementIterations -= 2;

    //  Load 4 elements. If needed use unaligned load instead.
    //      messageField = {a, b, c, d}
    __m128i messageField = _mm_load_si128((__m128i*)currentMessageGaloisFieldsArray);

    //  Get into this form:
    //      values0 = {a, x, b, x}
    //      values1 = {c, x, d, x}
    __m128i values0 = _mm_shuffle_epi32(messageField,216);
    __m128i values1 = _mm_shuffle_epi32(messageField,114);

    //  Multiply by "fragmentCoefficentVector"
    values0 = _mm_mul_epu32(values0, fragmentCoefficentVector);
    values1 = _mm_mul_epu32(values1, fragmentCoefficentVector);

    __m128i halves0 = _mm_unpacklo_epi32(values0, allZero);
    __m128i halves1 = _mm_unpackhi_epi32(values0, allZero);
    __m128i halves2 = _mm_unpacklo_epi32(values1, allZero);
    __m128i halves3 = _mm_unpackhi_epi32(values1, allZero);


    halves0 = _mm_add_epi64(halves0, currentUnModdedGaloisFieldFragments[0]);
    halves1 = _mm_add_epi64(halves1, currentUnModdedGaloisFieldFragments[1]);
    halves2 = _mm_add_epi64(halves2, currentUnModdedGaloisFieldFragments[2]);
    halves3 = _mm_add_epi64(halves3, currentUnModdedGaloisFieldFragments[3]);

    currentUnModdedGaloisFieldFragments[0] = halves0;
    currentUnModdedGaloisFieldFragments[1] = halves1;
    currentUnModdedGaloisFieldFragments[2] = halves2;
    currentUnModdedGaloisFieldFragments[3] = halves3;

    currentMessageGaloisFieldsArray     += 4;
    currentUnModdedGaloisFieldFragments += 4;
}

, который компилируется в это (x86): (x64 не слишком отличается) 

$LL4@main:
movdqa    xmm1, XMMWORD PTR [esi]
pshufd    xmm0, xmm1, 216               ; 000000d8H
pmuludq   xmm0, xmm3
movdqa    xmm4, xmm0
punpckhdq xmm0, xmm2
paddq     xmm0, XMMWORD PTR [eax-16]
pshufd    xmm1, xmm1, 114               ; 00000072H
movdqa    XMMWORD PTR [eax-16], xmm0
pmuludq   xmm1, xmm3
movdqa    xmm0, xmm1
punpckldq xmm4, xmm2
paddq     xmm4, XMMWORD PTR [eax-32]
punpckldq xmm0, xmm2
paddq     xmm0, XMMWORD PTR [eax]
punpckhdq xmm1, xmm2
paddq     xmm1, XMMWORD PTR [eax+16]
movdqa    XMMWORD PTR [eax-32], xmm4
movdqa    XMMWORD PTR [eax], xmm0
movdqa    XMMWORD PTR [eax+16], xmm1
add       esi, 16                   ; 00000010H
add       eax, 64                   ; 00000040H
dec       ecx
jne       SHORT $LL4@main

Только немного длиннее, чем не векторизованная версия для двух итераций.Здесь используется очень мало регистров, поэтому вы можете развернуть его даже на x86.

Пояснения:

  • Как упомянул Пол Р., развернув до двухИтерации позволяют объединить начальную загрузку в одну загрузку SSE.Это также имеет то преимущество, что ваши данные попадают в регистры SSE.
  • Поскольку данные начинаются в регистрах SSE, _mm_set_epi32 (который компилируется в ~ 9 инструкций в вашем исходном коде) можно заменитьс одной _mm_shuffle_epi32.
5 голосов
/ 24 октября 2011

Я предлагаю вам развернуть цикл с коэффициентом 2, чтобы вы могли загрузить 4 значения messageField, используя одно _mm_load_XXX, а затем распаковать эти четыре значения в две пары векторов и обработать их в соответствии с текущим циклом.Таким образом, компилятор не будет генерировать много грязного кода для _mm_set_epi32, и все ваши загрузки и хранилища будут 128-битными загрузками / хранилищами SSE.Это также даст компилятору больше возможностей для оптимального планирования инструкций в цикле.

...