Maneira mais rápida de fazer a sum vetorial do flutuador horizontal no x86

Você tem um vetor de três (ou quatro) carros alegóricos. Qual é o caminho mais rápido para resumi-los?

O SSE (movaps, shuffle, add, movd) é sempre mais rápido que x87? As instruções de adição horizontal no SSE4.2 valem a pena? Qual é o custo para mudar para o FPU, então faddp, faddp? Qual é a sequência de instruções específica mais rápida?

“Tente organizar as coisas para que você possa sumr quatro vetores de cada vez” não será aceito como resposta. 🙂

Aqui estão algumas versões ajustadas com base no guia de microarcas e nas tabelas de instruções do microarch guide do Agner Fog . Veja também o wiki da tag x86 . Eles devem ser eficientes em qualquer CPU, sem grandes gargalos. (por exemplo, evitei coisas que ajudariam um uaré um pouco, mas seriam lentas em outro uaré). O tamanho do código também é minimizado.

O idioma hadd 2x comum é bom apenas para o tamanho do código, não para a velocidade de qualquer CPU existente. Existem casos de uso para isso (veja abaixo), mas este não é um deles.

Eu também incluí uma versão do AVX. Qualquer tipo de redução horizontal com AVX / AVX2 deve começar com um vextractf128 e uma operação “vertical” para reduzir para um vetor XMM ( __m128 ).

Veja a saída do asm de todo este código no Godbolt Compiler Explorer . Veja também minhas melhorias nas funções horizontal_add Biblioteca de Classes C ++ Vector da Agner Fog . ( thread do quadro de mensagens e código no github ). Eu usei macros CPP para selecionar embaralhamentos ideais para tamanho de código para SSE2, SSE4 e AVX, e para evitar o movdqa quando o AVX não está disponível.


Existem compensações a serem consideradas:

  • tamanho do código: menor é melhor para motivos de cache I da L1 e para busca de código do disco (binários menores). O tamanho binário total é importante principalmente para as decisões do compilador feitas repetidamente em todo o programa. Se você estiver incomodando a codificar manualmente algo com intrínsecos, vale a pena gastar alguns bytes de código se isso der alguma aceleração para todo o programa (cuidado com os microbenchmarks que tornam o desenrolar com bom aspecto).
  • Tamanho do cache uop: Frequentemente mais precioso que L1 I $. 4 instruções single-uop podem ocupar menos espaço do que 2 haddps , portanto, isso é altamente relevante aqui.
  • latência: por vezes relevante
  • taxa de transferência: geralmente irrelevante, as sums horizontais não devem estar no loop mais interno.
  • uops total do domínio fundido: Se o código circundante não se afunilar na mesma porta que o hsum usa, isso é um proxy para o impacto do hsum na taxa de transferência da coisa toda.

Quando um acréscimo horizontal é pouco frequente :

CPUs sem cache uop podem favorecer 2x haddps : é lento quando executado, mas não é frequente. Sendo apenas 2 instruções minimiza o impacto sobre o código circundante (tamanho I $).

UCPs com um cache uop provavelmente favorecerão algo que leve menos uops, mesmo que seja mais instruções / mais x86 de tamanho de código. O total de linhas de cache de uops usadas é o que queremos minimizar, o que não é tão simples quanto minimizar o total de uops (as ramificações tomadas e os limites de 32B sempre iniciam uma nova linha de cache do uop).

De qualquer forma, com isso dito, as sums horizontais crescem muito , então aqui está minha tentativa de criar cuidadosamente algumas versões que compilam bem. Não avaliado em qualquer hardware real ou mesmo cuidadosamente testado. Pode haver bugs nas constantes de shuffle ou algo assim.


Se você está fazendo uma versão de reserva / baseline do seu código, lembre-se de que apenas CPUs antigas irão rodá-lo ; CPUs mais recentes irão rodar sua versão AVX, ou SSE4.1 ou qualquer outra coisa.

CPUs antigas como K8 e Core2 (merom) e anteriores possuem apenas unidades de shuffle de 64 bits . O Core2 tem unidades de execução de 128 bits para a maioria das instruções, mas não para shuffles. (O Pentium M e o K8 lidam com todas as instruções do vetor 128b como duas metades de 64 bits).

Shuffles como movhlps que movem dados em blocos de 64 bits (sem embaralhar dentro de metades de 64 bits) também são rápidos.

Em CPUs antigas com shuffles lentos :

  • movhlps (Merom: 1uop) é significativamente mais rápido que shufps (Merom: 3uops). No Pentium-M, mais barato que os movaps . Além disso, ele é executado no domínio FP no Core2, evitando os atrasos de desvio de outros shuffles.
  • unpcklpd é mais rápido que o unpcklps .
  • pshufd é lento, pshuflw / pshufhw são rápidos (porque eles apenas embaralham uma metade de 64 bits)
  • pshufb mm0 (MMX) é rápido, pshufb xmm0 é lento.
  • haddps é muito lento (6uops em Merom e Pentium M)
  • movshdup (Merom: 1uop) é interessante : é o único inson 1uop que embaralha dentro dos elementos 64b.

shufps no Core2 (incluindo Penryn) traz dados para o domínio inteiro, causando um atraso de retorno para recuperá-lo para as unidades de execução FP para addps , mas movhlps é inteiramente no domínio FP. shufpd também é executado no domínio float.

movshdup é executado no domínio inteiro, mas é apenas um uop.

AMD K10, Intel Core2 (Penryn / Wolfdale) e todas as CPUs posteriores, executam todos os shuffles xmm como um único uop. (Mas observe o atraso de bypass com shufps no Penryn, evitado com movhlps )


Sem o AVX, evitar instruções de movdqa / movaps desperdiçadas requer uma escolha cuidadosa de embaralhamentos . Apenas alguns shuffles funcionam como cópia e reprodução, em vez de modificar o destino. Aleatórios que combinam dados de duas inputs (como unpck* ou movhlps ) podem ser usados ​​com uma variável tmp que não é mais necessária em vez de _mm_movehl_ps(same,same) .

Algumas delas podem ser feitas mais rapidamente (exceto MOVAPS), mas mais feias / menos “limpas”, pegando um “dummy arg” para usar como destino para um shuffle inicial. Por exemplo:

 // 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 (também conhecido como 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 

Eu relatei um bug clang sobre pessimizing os embaralhamentos . Ele tem sua própria representação interna para embaralhar e transforma isso de volta em shuffles. O gcc usa com mais frequência as instruções que correspondem diretamente ao intrínseco usado.

Frequentemente o clang é melhor que o gcc, em código onde a escolha da instrução não é ajustada manualmente, ou a propagação constante pode simplificar as coisas mesmo quando os intrínsecos são ótimos para o caso não constante. No geral, é bom que os compiladores funcionem como um compilador adequado para intrínsecos, não apenas para um montador. Compiladores muitas vezes podem gerar um bom asm a partir do escalar C, que nem sequer tenta funcionar da maneira como seria bom. Eventualmente compiladores tratarão intrínsecos como apenas outro operador C como input para o otimizador.


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 

Isso tem várias vantagens:

  • não requer nenhuma cópia movaps para contornar movaps destrutivos (sem AVX): movshdup xmm1, xmm2 o destino de movshdup xmm1, xmm2 é somente para gravação, então criamos tmp de um registro morto para nós. É também por isso que usei movehl_ps(tmp, sums) vez de movehl_ps(sums, sums) .

  • pequeno tamanho de código. As instruções de embaralhamento são pequenas: movhlps é de 3 bytes, movshdup é de 4 bytes (o mesmo que shufps ). Nenhum byte imediato é necessário, portanto, com o AVX, o vshufps tem 5 bytes, mas o vmovhlps e o vmovshdup são ambos 4.

Eu poderia salvar outro byte com addps vez de addss . Como isso não será usado dentro de loops internos, a energia extra para trocar os transistores extras é provavelmente insignificante. As exceções de FP dos 3 elementos superiores não são um risco, porque todos os elementos contêm dados FP válidos. No entanto, clang / LLVM realmente “entende” shuffles de vetores e emite um código melhor se souber que apenas o elemento low é importante.

Como a versão SSE1, adicionar os elementos ímpares a eles mesmos pode causar exceções FP (como estouro) que não aconteceriam de outra forma, mas isso não deveria ser um problema. Denormals são lentos, mas o IIRC produzindo um resultado + Inf não é na maioria dos uarches.


SSE3 otimizando para tamanho de código

Se o tamanho do código for sua principal preocupação, duas haddps ( _mm_hadd_ps ) farão o truque (a resposta de Paul R). Este também é o mais fácil de digitar e lembrar. Não é rápido , no entanto. Até a Intel Skylake ainda decodifica cada haddps para 3 uops, com 6 ciclos de latência. Assim, apesar de salvar bytes de código de máquina (L1 I-cache), ele ocupa mais espaço no uop-cache mais valioso. Casos de uso reais para haddps : um problema de transposição e sum , ou fazer algum dimensionamento em uma etapa intermediária nessa implementação de atoi() SSE .


AVX:

Esta versão salva um byte de código versus a resposta de Marat à questão do 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 

Dupla precisão:

 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] 

Armazenar na memory e voltar evita um UUP da ULA. Isso é bom se a pressão da porta embaralhada, ou UUU em geral, for um gargalo. (Observe que não é necessário sub rsp, 8 ou qualquer coisa, porque o x86-64 SysV ABI fornece uma zona vermelha na qual os manipuladores de sinal não vão pisar.)

Algumas pessoas armazenam em uma matriz e summ todos os elementos, mas os compiladores geralmente não percebem que o elemento baixo da matriz ainda está lá em um registro anterior à loja.


Inteiro:

pshufd é um prático copy-shuffle. Infelizmente, os turnos de bits e bytes estão no local, e punpckhqdq coloca a metade alta do destino na metade inferior do resultado, o oposto da maneira pela qual os movhlps podem extrair a metade alta para um registro diferente.

Usar movhlps para o primeiro passo pode ser bom em algumas CPUs, mas apenas se tivermos um scratch reg. pshufd é uma escolha segura e rápida em tudo depois do 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); } 

Em algumas CPUs, é seguro usar FP shuffles em dados inteiros. Eu não fiz isso, já que em CPUs modernas que economizarão no máximo 1 ou 2 bytes de código, sem ganhos de velocidade (além do tamanho do código / efeitos de alinhamento).

SSE2

Todos os quatro:

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

Eu encontrei estes para ser sobre a mesma velocidade que o dobro HADDPS (mas eu não tenho medido muito de perto).

Você pode fazer isso em duas instruções do HADDPS no SSE3:

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

Isso coloca a sum em todos os elementos.

Eu definitivamente daria uma chance ao SSE 4.2. Se você está fazendo isso várias vezes (eu suponho que você esteja se o desempenho é um problema), você pode pré-carregar um registrador com (1,1,1,1), e então fazer vários dot4 (my_vec (s), one_vec) nele. Sim, ele faz uma multiplicação supérflua, mas esses são bastante baratos hoje em dia e tal operação provavelmente será dominada pelas dependencies horizontais, que podem ser mais otimizadas na nova function de produto de ponto SSE. Você deve testar para ver se ele supera o double horizontal add Paul R postado.

Eu também sugiro compará-lo com código scalar (ou escalar SSE) – estranhamente, ele é mais rápido (geralmente porque é serializado, mas firmemente pipeline usando bypass de registradores, onde instruções horizontais especiais podem não ter um caminho rápido (ainda)) a menos que você está executando código similar ao SIMT, o que parece que você não é (caso contrário, você faria quatro produtos de ponto).