Algum processador implementou uma instrução de raiz quadrada inteira?

 (retrocomputing.stackexchange.com)
1 pontos por GN⁺ 2024-04-08 | 1 comentários | Compartilhar no WhatsApp
  • A questão não é a instrução comum de sqrt de ponto flutuante, mas se houve casos em que a raiz quadrada inteira foi oferecida como instrução de CPU ou recurso de hardware; o divider/square-rooter do Nintendo DS é semelhante, mas não é uma instrução nativa
  • O RTX 2000 Forth CPU da Harris e o RTX 2010 de grau militar são citados como exemplos que forneciam uma instrução de square root em múltiplas etapas; no RTX 2000, o resultado era obtido com uma execução de setup e 15 execuções de step
  • Um caso mais antigo, o ENIAC, em 1946, usava uma unidade divider/square-rooter para controlar acumuladores de inteiros decimais e realizava até 40 divisões ou 3 operações de raiz quadrada por segundo
  • A raiz quadrada inteira exigia um multiplicador inteiro rápido e precisão suficiente, o que era pesado para CPUs históricas; também há abordagens como frsqrte/frsqrts do ARMv8, que separam estimativa e iteração para ajustar precisão e velocidade
  • A inverse square root ao estilo Quake já não tem, em hardware moderno, uma vantagem geral de desempenho; lookup em tabela, interpolação, iterações da família de Halley e divisão e conquista em ponto fixo variam conforme o ambiente de implementação

Escopo da pergunta e o caso do Nintendo DS

  • A pergunta trata de saber se algum processador realmente implementou uma instrução de raiz quadrada inteira
  • Instruções de square root em ponto flutuante são comuns, mas o ponto de partida é que o autor da pergunta nunca viu uma instrução de square root dedicada a inteiros
  • O Nintendo DS tinha um integer divider/square rooter mapeado em memória
    • Como o processador ARM não tinha FPU nem divisor em hardware, isso ajudava em cálculos 3D
    • Porém, o principal detalhe da pergunta é que ele não era uma instrução nativa do processador

Harris RTX 2000 e RTX 2010

  • O RTX 2000 Forth CPU da Harris é mencionado como um caso que oferecia uma instrução de square root em múltiplas etapas
  • Seu sibling de grau militar, o RTX 2010, também oferecia recursos da mesma família
  • Como material relacionado, é citado Stack Computers: RTX 2000
  • Segundo o RTX2000 Family Programmer’s Reference Manual, esse recurso é mais próximo de uma square root iterativa: executa-se 1 instrução de setup e 15 instruções de step para obter o valor final
  • “A Fast Method for Finding an Integer Square Root”, de Ken Lyons, também é mencionado como material que trata da implementação em hardware e de exemplos de programação da família RTX2000

Unidade divider/square-rooter do ENIAC

  • O ENIAC de 1946 também se enquadra como exemplo de hardware para raiz quadrada inteira
  • Segundo a descrição citada, o ENIAC controlava 4 acumuladores por meio de uma unidade multiplier especial e realizava até 385 multiplicações por segundo
  • 5 acumuladores eram controlados por uma unidade especial divider/square-rooter, capaz de processar até 40 divisões por segundo ou 3 operações de raiz quadrada por segundo
  • Os acumuladores do ENIAC operavam com inteiros decimais

Por que implementar raiz quadrada inteira é difícil

  • Uma resposta explica como método eficiente para calcular square root a abordagem de obter a raiz quadrada inversa via iteração de Newton-Raphson e depois multiplicar pelo valor original
  • Essa abordagem é conhecida como “método Quake” e há casos em CPUs e GPUs modernas em que ela foi generalizada com instruções de estimativa inicial e instruções de iteração
  • A principal limitação dessa abordagem é a necessidade de um multiplicador rápido
    • Para sqrt de ponto flutuante, é preciso um multiplicador FP rápido, e a FPU já o possui
    • Para sqrt inteira, é preciso um multiplicador inteiro rápido, mas historicamente a maioria das CPUs não tinha esse hardware, segundo a explicação
    • Para obter precisão suficiente, também é necessário um multiplicador rápido com largura duas vezes maior que a largura da entrada
  • Como os requisitos de precisão nem sempre são os mesmos, separar estimativa e iteração, como em frsqrte e frsqrts, permite ajustar o número de iterações de acordo com o trade-off entre velocidade e precisão desejado

Técnica do Quake e debate sobre implementações modernas de sqrt

  • Outra resposta contesta a afirmação de que o truque do Quake seria o mais eficiente, dizendo que isso deixou de ser verdade há muito tempo e só se aplica quando se quer um resultado float de baixa qualidade em hardware específico
  • Em chips modernos, instruções nativas de sqrt são muito mais rápidas, muitas vezes na casa de alguns ciclos de clock, segundo a explicação
  • Como método mais rápido, é sugerido armazenar uma tabela de valores em intervalos não uniformes, buscar rapidamente dois valores e interpolá-los, deslocar o expoente base 2 e, se necessário, aplicar uma iteração melhor que Newton-Raphson
  • A família Halley e vários métodos iterativos podem convergir mais rapidamente que Newton-Raphson, mas a velocidade real depende do custo de cada operação
  • Para faixas apenas de inteiros, por exemplo 2^32, a mesma ideia pode ser aplicada em ponto fixo
    • Como método simples para hardware, é sugerida a divisão e conquista
    • Cada 8 bits pode ser mapeado para uma tabela de 256 valores em ponto fixo, consultado em paralelo e, em seguida, 2 de 3 multiplicações podem ser realizadas em paralelo para obter um valor de 32 bits e truncá-lo
  • Pesquisas sobre otimização de sqrt continuam, e o material INRIA HAL é citado como exemplo

Leituras relacionadas

1 comentários

 
GN⁺ 2024-04-08
Opiniões no Hacker News

  • O AArch64 NEON tem a instrução URSQRTE, então ela chega mais perto da pergunta original do que parece à primeira vista
    Se você encarar um valor de 32 bits como um inteiro de ponto fixo com 32 bits fracionários, o intervalo representável vai de 0 até 1-ε, com espaçamento uniforme, e ε=2^-32
    A URSQRTE calcula uma raiz quadrada inversa aproximada, depois divide por dois e limita o resultado ao intervalo de 0 a 1-ε
    Um inteiro de ponto fixo não é exatamente um inteiro, e uma raiz quadrada inversa aproximada também não é uma raiz quadrada, mas dá para chegar bem perto
    A FRSQRTE relacionada é uma instrução bem mais geral, que fornece uma raiz quadrada inversa aproximada para ponto flutuante de 32 bits

    • Fico curioso para saber que tipo de tarefa se beneficia tanto de uma instrução complexa dessas, a ponto de ela entrar no AArch64, mesmo podendo ser facilmente decomposta em instruções mais simples

  • Se a pergunta é se dá em um único ciclo de clock, dá, se houver uma tabela de consulta enorme
    Dependendo de quantas portas lógicas seriais você consegue executar dentro de um ciclo de clock, talvez dê para reduzir o tamanho
    Por exemplo, a raiz quadrada binária de 10000 é bem parecida com a raiz quadrada de 100; dá para pensar que só muda a quantidade de zeros

    • Instruções de estimativa de raiz quadrada inversa em ponto flutuante (frsqrte) normalmente são implementadas com uma consulta a tabela desse tipo, indexada por alguns bits da mantissa e pelo bit menos significativo do expoente
      A precisão costuma ficar mais ou menos no nível de bf16 (ARM, RISC-V) ou fp16 (x86), então, se você precisar de mais precisão, faz algumas iterações de Newton-Raphson depois
    • Quando o número de bits da entrada é n, a raiz quadrada inteira pode ser calculada com n/2 iterações usando apenas shifts e somas
      Em cada etapa, calcula-se se é preciso definir um novo bit no resultado n_old com n2_new = (n_old + (1 << bit))^2 = n2_old + (n_old << (bit + 1)) + (1 << (bit*2))
      Depois se compara com o operando original e, se for menor ou igual, 1) define-se o bit no resultado e 2) atualiza-se n2_old para n2_new
      Com um conjunto adequado de instruções de microcódigo e uma ALU, dá para fazer em n/2, ou talvez n, ciclos de clock; com mais otimização, dá para reduzir n até o índice do bit 1 mais à esquerda no operando
    • Pode ser uma pergunta boba, mas uma consulta a uma tabela grande realmente termina em um único ciclo de clock na prática?
      Se a tabela de consulta for grande, ela teria de ser buscada na memória; aí não haveria latência de cache e da hierarquia de memória?
    • Vendo por esse lado, parece que qualquer algoritmo do mundo poderia ser executado em 1 ciclo de clock
    • Raiz quadrada inteira não é tão ruim quanto parece: basta armazenar N^0,5 entradas na tabela de consulta maior/menor
      Seria algo como armazenar N^2 para cada resposta N
      Para inteiros de 16 bits é viável, para 32 bits talvez também, mas para 64 bits não dá

  • Se ampliarmos a definição de “processador” para incluir dispositivos eletromecânicos, a Friden SRQ conseguia calcular raízes quadradas usando apenas soma e shift, sem nenhum componente eletrônico além do motor
    Era preciso ajustar manualmente a posição da vírgula decimal, então tecnicamente também dá para chamar isso de operação inteira
    Vídeo: https://youtu.be/o44a1ao5h8w

  • Usando a sequência 1 + 3 + 5 + ... + 2k + 1, não dá para encontrar a raiz quadrada inteira de qualquer inteiro?
    Basicamente, seria procurar o k do termo mais próximo dessa sequência que seja menor ou igual ao meu número

    • Você pode explicar a ideia?
      Por definição, é um algoritmo, mas, implementado de forma ingênua, é muito lento até para números de 32 bits
      Nesse ponto, é muito mais rápido simplesmente fazer uma busca binária
    • Um método melhor talvez seja usar a expansão (x+y)^2=x^2+2xy+y^2 junto com a observação de que, em qualquer base, a raiz quadrada de um número com 2n dígitos tem no máximo n dígitos
      É o mesmo método comum de calcular raiz quadrada à mão com papel e caneta
      Se você processar isso de 8 em 8 bits, só precisa de uma tabela de consulta para a raiz quadrada de números de 8 bits
    • Se a ideia é iterar por essa sequência inteira, isso leva tempo exponencial em relação ao comprimento em bits da entrada
    • Esse é um daqueles trabalhos clássicos embaraçosamente fáceis de paralelizar

  • Achei engraçada esta parte de uma resposta mais abaixo:

    My implementation of square root using binary search, that doesn't depend on a multiplier. Only basic ALU instructions are used. It is vigorously undocumented. I have no idea what I wrote but it seems to work.
    É um bom reminder de que, se você escreve código inteligente demais, há uma boa chance de depois não lembrar como ele funciona

  • É preciso descer um pouco na leitura, mas é muito engraçado que a resposta seja ENIAC

    • Muita gente acha que tudo que existia antes de ela entrar na escola era primitivo e mal funcionava :)
      Basta ler um pouco para ver que era exatamente o contrário
      A maioria das ideias inteligentes de hoje já era usada em computadores das décadas de 1940 a 1960 e está sendo reaproveitada em novos chips semicondutores
      Pipelining, execução fora de ordem e múltiplos núcleos são exemplos disso
      O hardware antigo podia ser um pouco “tosco”, mas as arquiteturas usavam técnicas muito engenhosas

  • 2 ^ (1/2 * Log2(X)) = sqrt(X)
    Se você trocar Log2(x) por contagem de zeros à esquerda, dá para obter uma aproximação bem grosseira
    Aproximando melhor Log(2), dá para chegar mais perto da resposta

  • Se a ideia não é obter a resposta exata até o inteiro mais próximo, mas sim uma aproximação muito grosseira, basta fazer um shift para a direita pela metade da posição do primeiro bit 1
    Quase todo processador tem instruções de shift, e instruções como FLO (Find Leading One) ou FFS (Find First Set) parecem tão comuns que nem sei dizer quantos não as têm
    Em alguns usos, uma aproximação bem grosseira assim pode ser tão útil quanto a resposta exata
    Por exemplo, quando você só precisa de um valor inicial razoável para uma iteração de Newton-Raphson posterior
    Claro, o truque do shift para a direita também funciona bem como valor inicial para um cálculo mais preciso de raiz quadrada :P

    • É aqui que entra a história do DOOM?
      Hoje já é uma história bem famosa da internet, com Carmack e um número mágico de 32 bits
    • Curiosidade: FFS e sua generalização, FNS, existem em CUDA: https://docs.nvidia.com/cuda/cuda-math-api/index.html#group_...
      Outra função intrínseca de hardware da CUDA de que gosto pessoalmente é log2

  • Se me lembro bem, a maioria, talvez todos os DSPs de ponto fixo, tem uma instrução de raiz quadrada ou alguma instrução auxiliar

  • Uma análise exaustiva de algoritmos de raiz quadrada meio relacionada e que pode interessar aos fãs do 6502: https://github.com/TobyLobster/sqrt_test