Най-бързият начин за хоризонтална векторна сума на SSE (или друга редукция)

По принцип за всякакъв вид векторно хоризонтално намаляване, извличане/разбъркване на висока половина към ниска, след това вертикално добавяне (или мин./макс./или/и/xor/умножение/каквото и да е); повтаряйте, докато остане един елемент. Ако започнете с вектори, по-широки от 128 бита, стеснете наполовина, докато стигнете до 128 (тогава можете да използвате една от функциите в този отговор за този вектор). Освен ако не се нуждаете от излъчване на резултата към всички елементи в края, можете да помислите за разбъркване на цялата ширина докрай.

Свързани въпроси и отговори за по-широки вектори и цели числа и FP

• __m128 и __m128d Този отговор (вижте по-долу)

• __m256d с анализ на ефективността за Ryzen 1 срещу Intel (показва защо vextractf128 е много по-добър от vperm2f128) Получаване на сбор от стойности, съхранени в __m256d с SSE/AVX

• __m256 Как да сумирам __m256 хоризонтално?

• Intel AVX: 256-битова версия на точков продукт за променливи с плаваща запетая с двойна точност на единични вектори.

• Точково произведение на масиви (не само един вектор от 3 или 4 елемента): направете вертикално mul/add или FMA в множество акумулатори и hsum в края. Пълен пример за точков продукт на масив AVX+FMA, включително ефективен hsum след цикъла. (За проста сума или друго редуциране на масив, използвайте този модел, но без частта за умножение, напр. add вместо fma). Не правете хоризонталната работа отделно за всеки SIMD вектор; направете го веднъж накрая.

  Как да преброим срещанията на знаци с помощта на SIMD като цяло число пример за преброяване _mm256_cmpeq_epi8 съвпадения, отново върху цял масив, само hsumming в края. (Заслужава да се спомене специално за извършване на 8-битово натрупване, след което разширяване на 8 -› 64-бита, за да се избегне препълване, без да се прави пълна hsum в този момент.)

Цяло число

• __m128i 32-битови елементи: този отговор (вижте по-долу). 64-битовите елементи трябва да са очевидни: само една стъпка pshufd/paddq.

• __m128i 8-битови неподписани елементи: psadbw срещу _mm_setzero_si128(), след това hsum двете половини на qword (или 4 или 8 за по-широки вектори). Най-бързият начин за хоризонтално сумиране на SSE неподписан байт вектор показва 128-битов с SSE2. Сумиране на 8-битови цели числа в __m512i с AVX intrinsics има пример за AVX512. Как да преброите срещанията на знаци с помощта на SIMD има пример за AVX2 __m256i.

  (За байтове със знак можете да XOR set1(0x80), за да обърнете към unsigned преди SAD, след което да извадите отклонението от крайната hsum).

• _mm_madd_epi16 с set1(1) като единичен uop разширяващ се хоризонтален градивен блок за добавяне на тесни цели числа: SIMD: Натрупване на съседни Двойки

• __m256i и __m512i с 32-битови елементи. Най-бързият метод за изчисляване на сумата от всички пакетирани 32-битови цели числа с помощта на AVX512 или AVX2. За AVX512 Intel добави куп вградени функции за намаляване (не хардуерни инструкции), които правят това вместо вас, като _mm512_reduce_add_ps (и pd, epi32 и epi64). Също така намали_мин/макс/мул/и/или. Правенето му ръчно води до основно същото asm.

• хоризонтален макс (вместо добавяне): Получаване на макс. стойност във вектор __m128i със SSE?

SSE1 (известен още като SSE):

Ето някои версии, настроени на базата на ръководството за микроарки на Agner Fog и таблиците с инструкции за микроархите. Вижте също x86 tag wiki. Те трябва да са ефективни на всеки процесор, без големи затруднения. (напр. избягвах неща, които биха помогнали малко на един uarch, но биха били бавни на друг uarch). Размерът на кода също е сведен до минимум.

Общата SSE3 / SSSE3 2x hadd идиома е добра само за размер на кода, а не за скорост на съществуващи процесори. Има случаи на употреба за него (като транспониране и добавяне, вижте по-долу), но единичен вектор не е един от тях.

Включих и AVX версия. Всеки вид хоризонтално редуциране с AVX / AVX2 трябва да започва с vextractf128 и вертикална операция за редуциране до един XMM (__m128) вектор. Като цяло за широките вектори най-добрият ви залог е да стеснявате наполовина многократно, докато стигнете до 128-битов вектор, независимо от типа на елемента. (С изключение на 8-битово цяло число, тогава vpsadbw като първа стъпка, ако искате да hsum без препълване към по-широки елементи.)

Има компромиси, които трябва да имате предвид:

Когато хоризонталното добавяне е рядко:

• Размер на uop-кеша: Често по-ценен от L1 I$. 4 single-uop инструкции могат да заемат по-малко място от 2 haddps, така че това е много подходящо тук.
• латентност: Понякога уместно
• пропускателна способност (back-end портове): обикновено без значение, хоризонталните суми не трябва да са единственото нещо в най-вътрешния цикъл. Налягането на порта има значение само като част от целия контур, който съдържа това.
• пропускателна способност (общо uops на предния слят домейн): Ако заобикалящият код не пречи на същия порт, който използва hsum, това е прокси за въздействието на hsum върху пропускателната способност на цялото нещо.
• movhlps (Merom: 1uop) е значително по-бърз от shufps (Merom: 3uops). На Pentium-M, по-евтино от movaps. Също така, той работи в FP домейна на Core2, като избягва закъсненията за байпас от други разбърквания.

Процесорите без uop-cache може да предпочитат 2x haddps, ако се използва много рядко: Бавно е, когато работи, но това не е често. Това, че има само 2 инструкции, минимизира въздействието върху околния код (размер I$).

Процесорите с uop-cache вероятно ще предпочетат нещо, което отнема по-малко uops, дори ако това е повече инструкции/по-голям размер на x86 кода. Общо използваните кеш-редове на uops е това, което искаме да минимизираме, което не е толкова просто като минимизирането на общия брой uops (взетите разклонения и 32B граници винаги започват нов uop кеш ред).

Както и да е, с това казано, хоризонталните суми се появяват много, така че ето моят опит внимателно да изработя някои версии, които да се компилират добре. Не е сравнен с реален хардуер или дори внимателно тестван. Може да има грешки в константите за разбъркване или нещо подобно.

Ако правите резервна/базова версия на вашия код, не забравяйте, че само стари процесори ще го изпълняват; по-новите процесори ще работят с вашата AVX версия или SSE4.1 или каквото и да е друго.

Старите процесори като K8 и Core2(merom) и по-стари имат само 64-битови модули за разбъркване. Core2 има 128-битови изпълнителни единици за повечето инструкции, но не и за разбъркване. (Pentium M и K8 обработват всички 128b векторни инструкции като две 64-битови половини).

Разбърквания като movhlps, които преместват данни в 64-битови части (без разбъркване в рамките на 64-битови половини), също са бързи.

Свързани: разбъркване на нови процесори и трикове за избягване на пропускателна способност на разбъркване на 1/clock на Haswell и по-нови: Дават ли 128-битовите операции в AVX512 по-добра производителност?

На стари процесори с бавно разбъркване:

shufps на Core2 (включително Penryn) въвежда данни в целочисления домейн, причинявайки забавяне на байпаса, за да ги върне обратно към FP изпълнителните единици за addps, но movhlps е изцяло в FP домейна. shufpd също работи в float домейна.

• unpcklpd е по-бърз от unpcklps.
• pshufd е бавен, pshuflw/pshufhw са бързи (защото разбъркват само 64-битова половина)
• pshufb mm0 (MMX) е бърз, pshufb xmm0 е бавен.
• haddps е много бавен (6uops на Merom и Pentium M)
• movshdup (Merom: 1uop) е интересен: Това е единственият 1uop insn, който се разбърква в рамките на 64b елемента.
• Открих, че те са приблизително със същата скорост като двойната __m256d (но не съм измервал твърде внимателно).

movshdup работи в целочислен домейн, но е само един uop.

AMD K10, Intel Core2 (Penryn/Wolfdale) и всички по-нови процесори изпълняват всички xmm разбърквания като един uop. (Но имайте предвид забавянето на байпаса с shufps на Penryn, избегнато с movhlps)

Без AVX избягването на пропилени movaps/movdqa инструкции изисква внимателен избор на разбъркване. Само няколко разбърквания работят като копиране и разбъркване, вместо да променят дестинацията. Разбърквания, които комбинират данни от два входа (като unpck* или movhlps), могат да се използват с tmp променлива, която вече не е необходима вместо _mm_movehl_ps(same,same).

Някои от тях могат да бъдат направени по-бързи (освен MOVAPS), но по-грозни/по-малко чисти, като се вземе фиктивен аргумент за използване като дестинация за първоначално разбъркване. Например:

Съобщих за кланг грешка за песимизиране на разбъркванията. Той има собствено вътрешно представяне за разбъркване и го превръща обратно в разбъркване. gcc по-често използва инструкциите, които директно съответстват на вътрешния, който сте използвали.

// Use dummy = a recently-dead variable that vec depends on,
//  so it doesn't introduce a false dependency,
//  and the compiler probably still has it in a register
__m128d highhalf_pd(__m128d dummy, __m128d vec) {
#ifdef __AVX__
    // With 3-operand AVX instructions, don't create an extra dependency on something we don't need anymore.
    (void)dummy;
    return _mm_unpackhi_pd(vec, vec);
#else
    // Without AVX, we can save a MOVAPS with MOVHLPS into a dead register
    __m128 tmp = _mm_castpd_ps(dummy);
    __m128d high = _mm_castps_pd(_mm_movehl_ps(tmp, _mm_castpd_ps(vec)));
    return high;
#endif
}

SSE3

float hsum_ps_sse1(__m128 v) {                                  // v = [ D C | B A ]
    __m128 shuf   = _mm_shuffle_ps(v, v, _MM_SHUFFLE(2, 3, 0, 1));  // [ C D | A B ]
    __m128 sums   = _mm_add_ps(v, shuf);      // sums = [ D+C C+D | B+A A+B ]
    shuf          = _mm_movehl_ps(shuf, sums);      //  [   C   D | D+C C+D ]  // let the compiler avoid a mov by reusing shuf
    sums          = _mm_add_ss(sums, shuf);
    return    _mm_cvtss_f32(sums);
}
    # gcc 5.3 -O3:  looks optimal
    movaps  xmm1, xmm0     # I think one movaps is unavoidable, unless we have a 2nd register with known-safe floats in the upper 2 elements
    shufps  xmm1, xmm0, 177
    addps   xmm0, xmm1
    movhlps xmm1, xmm0     # note the reuse of shuf, avoiding a movaps
    addss   xmm0, xmm1

    # clang 3.7.1 -O3:  
    movaps  xmm1, xmm0
    shufps  xmm1, xmm1, 177
    addps   xmm1, xmm0
    movaps  xmm0, xmm1
    shufpd  xmm0, xmm0, 1
    addss   xmm0, xmm1

Често clang се справя по-добре от gcc, в код, където изборът на инструкции не е ръчно настроен, или константното разпространение може да опрости нещата, дори когато присъщите са оптимални за непостоянния случай. Като цяло е хубаво, че компилаторите работят като правилен компилатор за вътрешни елементи, а не просто като асемблер. Компилаторите често могат да генерират добър asm от скаларен C, който дори не се опитва да работи по начина, по който добрият asm би го направил. В крайна сметка компилаторите ще третират intrinsics като просто още един C оператор като вход за оптимизатора.

Това има няколко предимства:

SSE3 оптимизиране за размер на кода

float hsum_ps_sse3(__m128 v) {
    __m128 shuf = _mm_movehdup_ps(v);        // broadcast elements 3,1 to 2,0
    __m128 sums = _mm_add_ps(v, shuf);
    shuf        = _mm_movehl_ps(shuf, sums); // high half -> low half
    sums        = _mm_add_ss(sums, shuf);
    return        _mm_cvtss_f32(sums);
}

    # gcc 5.3 -O3: perfectly optimal code
    movshdup    xmm1, xmm0
    addps       xmm0, xmm1
    movhlps     xmm1, xmm0
    addss       xmm0, xmm1

не изисква никакви movaps копия, за да заобиколи разрушителните разбърквания (без AVX): дестинацията на movshdup xmm1, xmm2 е само за запис, така че създава tmp от мъртъв регистър за нас. Ето защо използвах movehl_ps(tmp, sums) вместо movehl_ps(sums, sums).

• малък размер на кода. Инструкциите за разбъркване са малки: movhlps е 3 байта, movshdup е 4 байта (същото като shufps). Не се изисква непосредствен байт, така че с AVX vshufps е 5 байта, но vmovhlps и vmovshdup са 4.

• Мога да спестя още един байт с addps вместо addss. Тъй като това няма да се използва във вътрешни вериги, допълнителната енергия за превключване на допълнителните транзистори вероятно е незначителна. Изключенията на FP от горните 3 елемента не представляват риск, тъй като всички елементи съдържат валидни FP данни. Въпреки това, clang/LLVM всъщност разбира векторните размествания и излъчва по-добър код, ако знае, че само ниският елемент има значение.

Подобно на версията SSE1, добавянето на странни елементи към себе си може да причини FP изключения (като препълване), които не биха се случили иначе, но това не би трябвало да е проблем. Денормалните са бавни, но IIRC, произвеждащ +Inf резултат, не е на повечето uarch.

Ако размерът на кода е основната ви грижа, две инструкции haddps (_mm_hadd_ps) ще свършат работа (отговорът на Paul R). Това е и най-лесното за въвеждане и запомняне. Въпреки това не е бърз. Дори Intel Skylake все още декодира всеки haddps до 3 uops, с латентност от 6 цикъла. Така че, въпреки че спестява байтове на машинен код (L1 I-кеш), той заема повече място в по-ценния uop-кеш. Реални случаи на употреба за haddps: a проблем с транспониране и сумиране или извършване на известно мащабиране на междинна стъпка в тази реализация на SSE atoi().

AVX:

Тази версия запазва кодов байт спрямо отговора на Марат на въпроса за AVX .

Двойна точност:

Съхраняването в паметта и обратно избягва ALU uop. Това е добре, ако налягането на порта за разбъркване или ALU uops като цяло са пречка. (Имайте предвид, че не е необходимо да sub rsp, 8 или нещо подобно, защото x86-64 SysV ABI осигурява червена зона, върху която обработващите сигнали няма да стъпят.)

#ifdef __AVX__
float hsum256_ps_avx(__m256 v) {
    __m128 vlow  = _mm256_castps256_ps128(v);
    __m128 vhigh = _mm256_extractf128_ps(v, 1); // high 128
           vlow  = _mm_add_ps(vlow, vhigh);     // add the low 128
    return hsum_ps_sse3(vlow);         // and inline the sse3 version, which is optimal for AVX
    // (no wasted instructions, and all of them are the 4B minimum)
}
#endif

 vmovaps xmm1,xmm0               # huh, what the heck gcc?  Just extract to xmm1
 vextractf128 xmm0,ymm0,0x1
 vaddps xmm0,xmm1,xmm0
 vmovshdup xmm1,xmm0
 vaddps xmm0,xmm1,xmm0
 vmovhlps xmm1,xmm1,xmm0
 vaddss xmm0,xmm0,xmm1
 vzeroupper 
 ret

Цяло число:

double hsum_pd_sse2(__m128d vd) {                      // v = [ B | A ]
    __m128 undef  = _mm_undefined_ps();                       // don't worry, we only use addSD, never touching the garbage bits with an FP add
    __m128 shuftmp= _mm_movehl_ps(undef, _mm_castpd_ps(vd));  // there is no movhlpd
    __m128d shuf  = _mm_castps_pd(shuftmp);
    return  _mm_cvtsd_f64(_mm_add_sd(vd, shuf));
}

# gcc 5.3.0 -O3
    pxor    xmm1, xmm1          # hopefully when inlined, gcc could pick a register it knew wouldn't cause a false dep problem, and avoid the zeroing
    movhlps xmm1, xmm0
    addsd   xmm0, xmm1


# clang 3.7.1 -O3 again doesn't use movhlps:
    xorpd   xmm2, xmm2          # with  #define _mm_undefined_ps _mm_setzero_ps
    movapd  xmm1, xmm0
    unpckhpd        xmm1, xmm2
    addsd   xmm1, xmm0
    movapd  xmm0, xmm1    # another clang bug: wrong choice of operand order


// This doesn't compile the way it's written
double hsum_pd_scalar_sse2(__m128d vd) {
    double tmp;
    _mm_storeh_pd(&tmp, vd);       // store the high half
    double lo = _mm_cvtsd_f64(vd); // cast the low half
    return lo+tmp;
}

    # gcc 5.3 -O3
    haddpd  xmm0, xmm0   # Lower latency but less throughput than storing to memory

    # ICC13
    movhpd    QWORD PTR [-8+rsp], xmm0    # only needs the store port, not the shuffle unit
    addsd     xmm0, QWORD PTR [-8+rsp]

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

pshufd е удобно копиране и разбъркване. Разместванията на битове и байтове за съжаление са на място и punpckhqdq поставя горната половина на дестинацията в ниската половина на резултата, обратно на начина, по който movhlps може да извлече високата половина в различен регистър.

размер на кода: по-малък е по-добър поради причини за L1 I-кеша и за извличане на код от диск (по-малки двоични файлове). Общият двоичен размер има значение най-вече за решенията на компилатора, които се правят многократно в цялата програма. Ако си правите труда да кодирате ръчно нещо с вътрешни елементи, струва си да похарчите няколко байта код, ако това дава някакво ускоряване за цялата програма (внимавайте с микробенчмарковете, които правят разгръщането да изглежда добре).

Използването на movhlps за първата стъпка може да е добро за някои процесори, но само ако имаме рег. за надраскване. pshufd е безопасен избор и бърз на всичко след Merom.

На някои процесори е безопасно да използвате FP разбъркване върху целочислени данни. Не направих това, тъй като на модерни процесори, които ще спестят най-много 1 или 2 кодови байта, без увеличаване на скоростта (освен ефектите на размера на кода/подравняването).

int hsum_epi32_sse2(__m128i x) {
#ifdef __AVX__
    __m128i hi64  = _mm_unpackhi_epi64(x, x);           // 3-operand non-destructive AVX lets us save a byte without needing a mov
#else
    __m128i hi64  = _mm_shuffle_epi32(x, _MM_SHUFFLE(1, 0, 3, 2));
#endif
    __m128i sum64 = _mm_add_epi32(hi64, x);
    __m128i hi32  = _mm_shufflelo_epi16(sum64, _MM_SHUFFLE(1, 0, 3, 2));    // Swap the low two elements
    __m128i sum32 = _mm_add_epi32(sum64, hi32);
    return _mm_cvtsi128_si32(sum32);       // SSE2 movd
    //return _mm_extract_epi32(hl, 0);     // SSE4, even though it compiles to movd instead of a literal pextrd r32,xmm,0
}

    # gcc 5.3 -O3
    pshufd xmm1,xmm0,0x4e
    paddd  xmm0,xmm1
    pshuflw xmm1,xmm0,0x4e
    paddd  xmm0,xmm1
    movd   eax,xmm0

int hsum_epi32_ssse3_slow_smallcode(__m128i x){
    x = _mm_hadd_epi32(x, x);
    x = _mm_hadd_epi32(x, x);
    return _mm_cvtsi128_si32(x);
}

Основен отговор на този въпрос: предимно float и __m128

И четирите:

Можете да го направите в две

const __m128 t = _mm_add_ps(v, _mm_movehl_ps(v, v));
const __m128 sum = _mm_add_ss(t, _mm_shuffle_ps(t, t, 1));

инструкции в SSE3:

const __m128 t = _mm_add_ps(v, _mm_movehl_ps(v, v));
const __m128 sum = _mm_add_ss(t, _mm_shuffle_ps(t, t, 1));

r1+r2+r3:

const __m128 t1 = _mm_movehl_ps(v, v);
const __m128 t2 = _mm_add_ps(v, t1);
const __m128 sum = _mm_add_ss(t1, _mm_shuffle_ps(t2, t2, 1));

SSE2

Това поставя сумата във всички елементи.

v = _mm_hadd_ps(v, v);
v = _mm_hadd_ps(v, v);

Определено бих пробвал SSE 4.2. Ако правите това няколко пъти (предполагам, че сте, ако производителността е проблем), можете предварително да заредите регистър с (1,1,1,1) и след това да направите няколко dot4(my_vec(s), one_vec) върху него. Да, прави излишно умножение, но те са сравнително евтини в наши дни и подобна операция вероятно ще бъде доминирана от хоризонталните зависимости, които може да са по-оптимизирани в новата функция за точков продукт на SSE. Трябва да тествате, за да видите дали превъзхожда двойната хоризонтална добавка, публикувана от Paul R.

Също така предлагам да го сравните с директен скаларен (или скаларен SSE) код - колкото и да е странно, той често е по-бърз (обикновено защото вътрешно е сериализиран, но тясно конвейеризиран чрез байпас на регистъра, където специалните хоризонтални инструкции може да не са бързи (все още)), освен ако не изпълнявате код, подобен на SIMT, което звучи сякаш не сте (в противен случай бихте направили произведения с четири точки).

Ако хоризонталните добавяния са критични за производителността за вас, тогава може да подхождате към SIMD кодирането по не толкова оптимален начин - публикувайте код, който показва как и къде трябва да направите това.