Por que a latência da instrução sqrtsd muda com base na entrada? Processadores Intel

9

Bem no guia intrínseco Intel , afirma-se que a instrução chamada "sqrtsd" possui uma latência de 18 ciclos.

Eu testei com meu próprio programa e está correto se, por exemplo, usarmos 0,15 como entrada. Mas quando usamos o número 256 (ou qualquer 2 ^ x), a latência é apenas 13. Por que isso?

Uma teoria que tive é que, como 13 é a latência de "sqrtss", que é a mesma que "sqrtsd", mas feita em pontos flutuantes de 32 bits, talvez o processador tenha sido inteligente o suficiente para entender que 256 podem caber em 32 bits e, portanto, usar essa versão enquanto 0,15 precisa de 64 bits completos, pois não é representável de maneira finita.

Estou fazendo isso usando assembly embutido, aqui está a parte do releante compilada com gcc -O3 e -fno-tree-vectorize.

static double sqrtsd (double x) {
    double r;
    __asm__ ("sqrtsd %1, %0" : "=x" (r) : "x" (x));
    return r;
}
Tommy95
fonte
3
Mostre-nos o código do teste. Eu posso imaginar a implementação onde a otimização feita pelo compilador e não pelo processador.
Robert Navado 12/03
Os processadores não são inteligentes: eles executam as instruções fornecidas.
Cata-vento
Isso responde sua pergunta? Por que o SSE escalar sqrt (x) é mais lento que rsqrt (x) * x?
Tarek Dakhran 12/03
2
Você não está imaginando coisas: o instlatx64 para skylake também lista 18 (pior caso) e 13 (valores simples)
harold
1
Seu asm inline não faz sentido e não será compilado: godbolt.org/z/rJA6nS . "i"especifica é um imediato e não pode ser uma restrição de saída. sqrtsdaceita apenas uma entrada reg / mem, não imediata, portanto não seria montada, mesmo que fosse compilada. Além disso, o uso imediato imediato de tempo de compilação não permite testar a latência, apenas a taxa de transferência. Mas seus números parecem sãos, então o que você realmente fez provavelmente testou a latência do sqrtsd.
Peter Cordes

Respostas:

10

SQRT * e DIV * são as únicas duas instruções ALU "simples" (uop único, ramificação / loop não microcodificado) que possuem taxa de transferência ou latência dependente de dados nas modernas CPUs Intel / AMD. (O microcódigo não contado ajuda a valores FP anormais anormais aka em adicionar / multiplicar / fma). Todo o resto é praticamente consertado, de modo que o mecanismo de programação de UOP avariado não precisa esperar pela confirmação de que um resultado ficou pronto em algum ciclo, apenas sabe que será.

Como sempre, o guia intrínseco da Intel fornece uma imagem simplificada do desempenho. A latência real não é de 18 ciclos fixos para precisão dupla no Skylake. (Com base nos números que você escolheu para citar, presumo que você tenha um Skylake.)

div / sqrt são difíceis de implementar; mesmo em hardware, o melhor que podemos fazer é um processo de refinamento iterativo. O refinamento de mais bits de uma vez (divisor radix-1024 desde Broadwell) acelera (consulte as perguntas e respostas sobre o hardware ). Mas ainda é lento o suficiente para que um early-out seja usado para acelerar casos simples (ou talvez o mecanismo de aceleração esteja apenas pulando uma etapa de configuração para mantissas totalmente nulas em CPUs modernas com unidades div / sqrt parcialmente pipelines. = latência para FP div / sqrt; essa unidade de execução é mais difícil de pipeline.)


https://www.uops.info/html-instr/VSQRTSD_XMM_XMM_XMM.html mostra que o Skylake SQRTSD pode variar de 13 a 19 latências de ciclo. Os números SKL (cliente) mostram apenas latência de 13 ciclos, mas podemos ver na página detalhada SKL vsqrtsd que eles testaram apenas com entrada = 0. Os números SKX (servidor) mostram latência de 13 a 19 ciclos. ( Esta página possui a análise detalhada do código de teste que eles usaram, incluindo os padrões de bits binários para os testes.) Testes semelhantes (com apenas 0 para núcleos de clientes) foram feitos na página não VEXsqrtsd xmm, xmm . : /

Os resultados do InstLatx64 mostram latências de melhor / pior caso, de 13 a 18 ciclos no Skylake-X (que usa o mesmo núcleo que o Skylake-client, mas com o AVX512 ativado).

As tabelas de instruções da Agner Fog mostram latência de 15 a 16 ciclos no Skylake. (Agner normalmente testa com um intervalo de diferentes valores de entrada.) Seus testes são menos automatizados e às vezes não correspondem exatamente a outros resultados.

O que torna alguns casos rápidos?

Observe que a maioria dos ISAs (incluindo x86) usa ponto flutuante binário :
os bits representam valores como um significando linear (também conhecido como mantissa) vezes 2 exp e um bit de sinal.

Parece que pode haver apenas duas velocidades na Intel moderna (desde Haswell, pelo menos) (veja a discussão com @harold nos comentários.) Por exemplo, mesmo potências de 2 são todas rápidas, como 0,25, 1, 4 e 16. Elas possuem recursos triviais. mantissa = 0x0 representando 1.0. https://www.h-schmidt.net/FloatConverter/IEEE754.html possui um bom conversor de padrão de bits decimal interativo <-> para precisão única, com caixas de seleção para os bits definidos e anotações do que a mantissa e o expoente representam.

No Skylake, os únicos casos rápidos que encontrei em uma verificação rápida são mesmo potências de 2 como 4,0, mas não de 2,0. Esses números têm um resultado exato do sqrt com entrada e saída com uma mantissa 1.0 (apenas o conjunto de 1 bit implícito). 9.0não é rápido, mesmo que seja exatamente representável e o 3.0resultado também. 3.0 possui mantissa = 1.5 com apenas o bit mais significativo definido na representação binária. A mantissa de 9.0 é 1,125 (0b00100 ...). Portanto, os bits diferentes de zero estão muito próximos do topo, mas aparentemente isso é suficiente para desqualificá-lo.

( +-Infe NaNsão rápidos também. O mesmo acontece com os números negativos comuns: result = -NaN . Medo a latência de 13 ciclos para eles no i7-6700k, o mesmo que para a 4.0latência vs. 18 ciclos no caso lento.)

x = sqrt(x)é definitivamente rápido com x = 1.0(mantissa totalmente zero, exceto o 1 bit implícito à esquerda). Tem uma entrada simples e uma saída simples.

Com 2.0, a entrada também é simples (mantissa zero e expoente 1 maior), mas a saída não é um número redondo. O sqrt (2) é irracional e, portanto, possui infinitos bits diferentes de zero em qualquer base. Aparentemente, isso torna o Skylake lento.

As tabelas de instruções de Agner Fog dizem que o divdesempenho inteiro das instruções do AMD K10 depende do número de bits significativos no dividendo (entrada), não no quociente, mas a pesquisa nas tabelas de microarquitetura e pdf de microarquitetura da Agner não encontrou notas de rodapé ou informações sobre como o sqrt é especificamente dependente de dados.

Em CPUs mais antigas com sqrt FP ainda mais lento, pode haver mais espaço para uma variedade de velocidades. Eu acho que o número de bits significativos na mantissa da entrada provavelmente será relevante. Menos bits significativos (mais zeros à direita no significando) o tornam mais rápido, se isso estiver correto. Mas, novamente, em Haswell / Skylake, os únicos casos rápidos parecem ter poderes de 2.


Você pode testar isso com algo que acopla a saída de volta à entrada sem interromper a dependência de dados, por exemplo, andps xmm0, xmm1/ orps xmm0, xmm2para definir um valor fixo em xmm0 que depende da saída sqrtsd.

Ou uma maneira mais simples de testar a latência é tirar "vantagem" da dependência de saída falsasqrtsd xmm0, xmm1 - e sqrtssdeixar os 64/32 bits (respectivamente) superiores do destino inalterados, assim o registro de saída também é uma entrada para essa mesclagem. Suponho que foi assim que sua ingênua tentativa inline-asm acabou com gargalos na latência, em vez de na taxa de transferência, com o compilador escolhendo um registro diferente para a saída, para que ele pudesse reler a mesma entrada em um loop. O asm inline que você adicionou à sua pergunta está totalmente quebrado e nem será compilado, mas talvez o seu código real tenha usado "x"(registro xmm) restrições de entrada e saída em vez de "i"(imediato)?

Essa fonte NASM para um loop de teste executável estático (a ser executado sob perf stat) usa essa dependência falsa com a codificação não-VEX de sqrtsd.

Esta verruga de design ISA é graças à otimização da Intel a curto prazo com o SSE1 no Pentium III. O P3 manipulou registros de 128 bits internamente como duas metades de 64 bits. Deixando a metade superior sem modificação, as instruções escalares decodificam para um único uop. (Mas isso ainda dá à PIII sqrtssuma falsa dependência). Finalmente, o AVX nos permite evitar isso com vsqrtsd dst, src,srcpelo menos para fontes de registro e da mesma forma vcvtsi2sd dst, cold_reg, eaxpara as instruções de conversão de intar escalar projetadas de modo semelhante à míope. (GCC perdeu-otimização relatórios: 80586 , 89071 , 80571 ).


Em muitas CPUs anteriores, a taxa de transferência era variável, mas a Skylake aumentou os divisores o suficiente para que o planejador sempre saiba que pode iniciar um novo div / sqrt em 3 ciclos após a última entrada de precisão única.

Mesmo o rendimento de dupla precisão da Skylake é variável: 4 a 6 ciclos após a última entrada de precisão dupla, se as tabelas de instruções de Agner Fog estiverem corretas. https://uops.info/ mostra uma taxa de transferência 6c recíproca plana. (Ou duas vezes tanto tempo para vectores de 256 bits; 128 bits e escalar pode usar metades separadas das divisórias SIMD largas para mais o rendimento, mas o mesmo latência). Ver também de flutuação divisão ponto vs flutuante multiplicação ponto de alguns números de rendimento / latência extraídos das tabelas de instruções de Agner Fog.

Peter Cordes
fonte
A propósito, e as latências entre os dois extremos? Eles acontecem? Eu não poderia fazer isso acontecer no meu Haswell, mas isso não é conclusivo
harold
@harold: IDK, eu acho que se fosse possível, isso aconteceria com um número menor de zeros à direita na mantissa. Mas talvez exista apenas um detector especial para os casos mais simples. O divisor de menor raio de Haswell deve torná-lo mais lucrativo para uma busca antecipada mais cedo, mas talvez seja uma questão de a estimativa inicial (da mesma tabela que o rsqrt usa) ser exata ou não, e se não for, precisa de refinamento iterativo. caminho até o fim.
Peter Cordes
rsqrtembora não seja exato para potências de dois (em Haswell, de qualquer maneira), mas potências de zero e duas são, até agora, as únicas entradas que encontrei onde a raiz quadrada é rápida; as rsqrtinstruções parecem fazer mais do que apenas uma pesquisa quanto tempo sua latência realmente é
harold
@harold: rsqrtpode não ser a saída bruta do LUT (sim, como você editou, a alta latência pode ser um pouco de trabalho). Ou talvez leve à resposta exata para entradas simples (mantissa zero). Ou talvez a mantissa totalmente zero possa ignorar a pesquisa LUT antes de iniciar o refinamento. Eu não sei o suficiente sobre divisores de HW para descartar qualquer uma dessas suposições. : /
Peter Cordes
1
É sqrtsdrápido para potências de dois com expoentes ímpares? Ou apenas para potências de dois com expoentes pares? Isto é interessante.
fuz 13/03