Самый быстрый способ сделать горизонтальную векторную сумму float на x86

Вот несколько версий, настроенных на основе руководства и таблиц микроархива руководства микроорганизма Agner Fog . См. Также вики-tags x86 . Они должны быть эффективными на любом процессоре, без каких-либо серьезных узких мест. (например, я избегал вещей, которые могли бы помочь одному уарху немного, но медленно на другом уархе). Размер кода также минимизируется.

Общая hadd 2x-идиома хороша только для размера кода, а не для любых существующих процессоров. Для него есть прецеденты (см. Ниже), но это не один из них.

Я также включил версию AVX. Любой вид горизонтальной редукции с AVX / AVX2 должен начинаться с vextractf128 и «вертикальной» операции, чтобы уменьшить до одного вектора XMM ( __m128 ).

См. Вывод asm из всего этого кода в проводнике компилятора Godbolt . См. Также мои улучшения в функциях horizontal_add библиотеки C ++ Vector Class Library для Agner Fog . ( stream сообщений и код на github ). Я использовал macros CPP для выбора оптимальных перетасовки для размера кода для SSE2, SSE4 и AVX и для предотвращения movdqa когда AVX недоступен.

---

Есть компромиссы:

• размер кода: меньше для причин I1 кеша L1 и для извлечения кода с диска (меньшие двоичные файлы). Общий двоичный размер в основном имеет значение для решений компилятора, которые неоднократно повторяются во всей программе. Если вы пытаетесь скомпоновать что-то с внутренними функциями, стоит потратить несколько байтов кода, если он дает какое-либо ускорение для всей программы (будьте осторожны с микрообъектами, которые делают разворачивание хорошо выглядеть).
• uop-cache size: Часто более ценный, чем L1 I $. 4 инструкций с одним-уходом могут занимать меньше места, чем 2-х haddps , поэтому здесь очень важно.
• задержка: иногда
• пропускная способность: обычно не имеет значения, горизонтальные суммы не должны быть в самом внутреннем цикле.
• Total fused-domain uops: Если окружающий код не является узким местом на том же порту, что и hsum, это прокси-сервер для воздействия hsum на пропускную способность всего.

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

Процессоры без кэша haddps могут использовать 2x haddps : он медленный, когда он запускается, но это не так часто. Только 2 инструкции минимизируют влияние на окружающий код (размер I $).

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

Во всяком случае, с учетом сказанного, горизонтальные суммы приходят много , так что вот моя попытка тщательно разработать некоторые версии, которые компилируются красиво. Не тестируется на каком-либо реальном оборудовании или даже тщательно проверяется. Могут быть ошибки в константах тасования или что-то в этом роде.

---

Если вы делаете резервную / базовую версию своего кода, помните, что будут запускать только старые процессоры ; более новые процессоры будут запускать вашу версию AVX или SSE4.1 или что-то еще.

Старые процессоры, такие как K8 и Core2 (merom) и ранее, имеют только 64-битные блоки перетасовки . Core2 имеет 128 бит исполнения для большинства инструкций, но не для перетасовки. (Pentium M и K8 управляют всеми 128b векторными инструкциями как две 64-битные половинки).

Перемешиваются, как movhlps которые перемещают данные в 64-битных кусках (без перетасовки в пределах 64-битных половинок) тоже быстры.

На старых процессорах с медленными тасованиями :

• movhlps (Merom: 1uop) значительно быстрее, чем shufps (Merom: 3uops). На Pentium-M, дешевле, чем movaps . Кроме того, он работает в домене FP на Core2, избегая задержек при переходе из других тасов.
• unpcklpd быстрее, чем unpcklps .
• pshufd медленный, pshuflw / pshufhw быстр (потому что они только перетасовывают 64-битную половину)
• pshufb mm0 (MMX) работает быстро, pshufb xmm0 медленный.
• haddps очень медленный (6 футов на Merom и Pentium M)
• movshdup (Merom: 1uop) интересен : это единственный 1uop insn, который перемещается в пределах 64b элементов.

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

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

AMD K10, Intel Core2 (Penryn / Wolfdale) и все более поздние процессоры, запускают все xmm shuffles как один uop. (Но обратите внимание на задержку байпаса с помощью shufps на Penryn, избежать с помощью movhlps )

---

Без AVX, избегая movdqa инструкций movdqa / movdqa требуется тщательный выбор тасований . Только несколько перетасовки работают как копирование и перетасовка, а не изменение назначения. Перемешивания, которые объединяют данные с двух входов (например, unpck* или movhlps ), могут использоваться с переменной tmp, которая больше не нужна, а не _mm_movehl_ps(same,same) .

Некоторые из них могут быть сделаны быстрее (за исключением MOVAPS), но более уродливые / менее «чистые», взяв фиктивный аргумент для использования в качестве места назначения для первоначального тасования. Например:

 // 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 } 

---

SSE1 (aka SSE):

 float hsum_ps_sse1(__m128 v) { // v = [ DC | BA ] __m128 shuf = _mm_shuffle_ps(v, v, _MM_SHUFFLE(2, 3, 0, 1)); // [ CD | AB ] __m128 sums = _mm_add_ps(v, shuf); // sums = [ D+C C+D | B+A A+B ] shuf = _mm_movehl_ps(shuf, sums); // [ CD | 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 

Я доложил о том, как пессимизировать перетасовку . Он имеет собственное внутреннее представление для перетасовки и превращается в тасование. gcc чаще всего использует инструкции, которые непосредственно соответствуют встроенной вами функции.

Часто clang делает лучше, чем gcc, в коде, где выбор команды не настроен вручную, или постоянное распространение может упростить ситуацию, даже если intrinsics являются оптимальными для непостоянного случая. В целом, хорошо, что компиляторы работают как правильный компилятор для intrinsics, а не только для ассемблера. Компиляторы часто генерируют хороший asm из скаляра C, который даже не пытается работать так, как было бы хорошо. В конце концов компиляторы будут рассматривать 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 

Это имеет ряд преимуществ:

• не требует каких-либо копий копий для работы с деструктивными перетасовками (без AVX): movshdup xmm1, xmm2 назначение movshdup xmm1, xmm2 – только для записи, поэтому оно создает tmp из мертвого регистра для нас. Вот почему я использовал movehl_ps(tmp, sums) вместо movehl_ps(sums, sums) .

• маленький размер кода. movhlps перетасовки малы: movhlps – 3 байта, movshdup – 4 байта (то же, что и shufps ). Не требуется немедленный байт, поэтому с AVX vshufps составляет 5 байт, но vmovhlps и vmovshdup оба равны 4.

Я могу сохранить еще один байт с addps вместо addss . Поскольку это не будет использоваться внутри внутренних петель, дополнительная энергия для переключения дополнительных транзисторов, вероятно, незначительна. Исключения FP из трех верхних элементов не являются риском, поскольку все элементы содержат достоверные данные FP. Тем не менее, clang / LLVM фактически «понимает» перетасовку векторов и испускает лучший код, если знает, что имеет значение только низкий элемент.

Как и версия SSE1, добавление нечетных элементов к себе может привести к тому, что исключения FP (например, переполнение) не произойдут иначе, но это не должно быть проблемой. Денормалы медленные, но IIRC, производящий результат + Inf, не на большинстве урчей.

---

SSE3, оптимизирующий размер кода

Если размер кода является вашей главной проблемой, две haddps ( _mm_hadd_ps ) будут делать трюк (ответ Paul R). Это также самый легкий тип и запоминание. Однако это не быстро . Даже Intel Skylake по-прежнему расшифровывает каждый haddps до 3-х часов, с задержкой 6 циклов. Таким образом, хотя он сохраняет байты машинного кода (I-кеш L1), он занимает больше места в более ценном uop-кеше. Реальные прецеденты для haddps : haddps с транспозицией и суммой или некоторое масштабирование на промежуточном этапе в реализации SSE atoi() .

---

AVX:

Эта версия сохраняет байты кода и ответ Марата на вопрос AVX .

 #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] 

Хранение памяти и обратно позволяет избежать ALU uop. Это хорошо, если давление в шунтировании портов или ALU-шумы в общем случае являются узким местом. (Обратите внимание, что ему не требуется sub rsp, 8 или что-либо, потому что x86-64 SysV ABI обеспечивает красную зону, в которой обработчики сигналов не будут наступать.)

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

---

Integer:

pshufd – удобная копия и перетасовка. Бит и байтовые сдвиги, к сожалению, на месте, а punpckhqdq помещает большую половину места назначения в низкую половину результата, противоположную тому, как movhlps может извлечь movhlps половину в другой регистр.

Использование movhlps для первого шага может быть хорошим для некоторых процессоров, но только если у нас есть коррекция нуля. pshufd – это безопасный выбор, и быстро все после Merom.

 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); } 

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

SSE2

Все четыре:

 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)); 

Я обнаружил, что они имеют одинаковую скорость, как двойной HADDPS (но я не слишком тщательно измерял).

Вы можете сделать это в двух инструкциях HADDPS в SSE3:

 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 dot. Вы должны проверить, будет ли он превосходить двойную горизонтальную добавку Paul R.

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