Tivemos a oportunidade de realizar um exercício tático pequeno, mas extremamente interessante
No processo de pesquisa de um novo MK de uma empresa conhecida, baseada na arquitetura Cortex-M4 (eu definitivamente escreverei sobre isso mais tarde), surgiu a questão de quão rapidamente a operação de divisão inteira na implementação de hardware pode funcionar. O experimento em grande escala deu um resultado um tanto inesperado: a divisão de um número de 32 bits em um número de 32 bits é realizada em 3 ciclos de clock da frequência do processador - bem, não importa a rapidez. Aconteceu que isso ocorre apenas com certos operandos, mas estudos posteriores mostraram que o tempo necessário para concluir uma divisão nunca excede 7 medidas. Os resultados obtidos causaram uma leve correria ("e esta não é uma figura de linguagem específica, que não sabe o que significa, mas um verbo muito específico" - Divov, como sempre, é incomparável).
Bem, você não pode simplesmente pegar e dividir rapidamente números tão longos, é estranho assim, mas os fatos são uma coisa teimosa. Imaginei a imagem que o Presidente da Federação Russa me chama para ele amanhã e coloca diante de mim a tarefa de tornar o MK não pior do que o da ARM (eu concordo que a imagem é ilusória, mas não acontece no mundo), mas olho para ele confusa e entendo que Não poderei fazer essa divisão desses números em um período tão longo e não cumprirei as expectativas que me são impostas (bem, na verdade, sempre posso comprar uma licença da ARM em silêncio e fingir que inventei tudo sozinha, muitas fazem isso, mas O PIB está esperando algo completamente diferente de mim, e então - eu posso enganá-lo, mas é improvável).
Fiquei triste por os caras do ARM serem muito mais espertos do que eu, e fiquei olhando ansiosamente a Internet para ver como eles fazem isso. Não encontrei nenhuma informação sobre o tempo de execução no site da ARM; em um dos materiais do STM32, foi indicado que a divisão leva de 2 a 7 ciclos de relógio, o que corresponde às observações, mas não há informações sobre como isso é feito.
Em geral, a onipotente Internet não ajudou muito, há truques com divisão por constante, escrevi sobre eles em uma das postagens, mas temos uma situação diferente, existe o algoritmo de Newton e sua versão acelerada, mas esse claramente não é o caso, existe um algoritmo baseado em Transformada de Fourier, mas isso é para números muito grandes e é improvável que seja concluída em 7 ciclos, mesmo na arquitetura ARM. Eu mesmo tive que criar uma solução e foi encontrada uma solução, tão simples e óbvia que se torna um pouco embaraçosa pelo fato de isso não ter sido feito imediatamente após a formulação da tarefa.
Antes de analisar minha decisão, sugiro que você encontre a sua e compare com a minha. Se elas diferirem, estou esperando por você nos comentários.
Então, como dividimos rapidamente (em não mais de 7 ciclos) dois números de 32 bits para obter um resultado de 32 bits.
Para começar, lembramos como a divisão na aritmética binária é geralmente realizada em
forma clássica. O algoritmo é bastante simples e direto - subtraímos o divisor do dividendo. Se o resultado for não negativo (dividimos os números não assinados), faça o próximo dígito do resultado igual a um e considere o resultado como o próximo dividendo, caso contrário, o próximo bit do resultado será 0. Antes da próxima medida, reduzimos o divisor pela metade (mova-o para a direita ou desloque o dividendo para a esquerda) e reduza o peso do bit em 2 vezes (em turnos semelhantes). Assim, obtemos um pouco do resultado em um ciclo de clock e toda a operação durará 32 ciclos de clock. Ainda existe uma mudança inicial nesse processo, mas isso não afeta a avaliação da situação como um todo. Vamos acelerar, mas como?
Observamos que o algoritmo resultante se assemelha fortemente à operação de um ADC com uma aproximação sequencial e lembramos que existem outros métodos de conversão, conversão paralela muito mais rápida. E se ...
Subtrairemos do divisor não apenas o dividendo, mas também o dividendo * 2 e o dividendo * 3 (ao mesmo tempo, em três somadores); em seguida, obteremos três bits (sinais de resultados) da informação, que recebem 4 valores diferentes, para que você possa extrair 2 bits ao mesmo tempo. resultado. Em seguida, extrapolamos uma abordagem semelhante para 3,4,5 bits do resultado.
Para obter 5 bits de informação por ciclo, precisamos de 31 somadores, em cada um dos quais será executada a operação Dividend-Divisor * n (1-31), os sinais do resultado serão passados pelo codificador e receberemos imediatamente 5 bits do resultado. Em seguida, deslocamos o dividendo em 5 dígitos para a esquerda e repetimos até estar pronto. Então precisamos de 32/5 = 6.4 => 7 medidas para concluir a operação.
Para o trabalho, precisamos de 31 + x somadores, parece ser muito, mas já os temos, porque temos uma operação de multiplicação 32 * 32 por ciclo e, para implementá-lo, não podemos prescindir de 32 somadores (bem, acho que sim ... ), para que já tenhamos o equipamento necessário, a única questão é construir um circuito de controle e um monte de multiplexadores para realizar uma mudança rápida, mas isso é completamente solucionável.
Portanto, a tarefa de dividir em 7 etapas é resolvida, a questão permanece - como esse tempo pode ser reduzido, porque no MK estudado é menor que 7. A solução óbvia é determinar o número do dígito mais significativo do dividendo (H) e do divisor (3) na fase de preparação do algoritmo ficará imediatamente claro quantos bits altos do quociente são iguais a zero, para que possamos pular a primeira ou várias fases do algoritmo. Por exemplo, se C <3, o resultado é imediatamente zero e concluímos a operação, com certeza você pode derivar uma fórmula para o número de medidas, mas eu já estava entediado.
Curiosamente, a operação udiv fornece apenas o quociente, embora o restante obviamente permaneça em algum lugar dentro. Em princípio, não é difícil obtê-lo em duas etapas, o que foi feito no fragmento estudado do código de máquina executando o pseudo-código Divisible-Private * Divider, mas isso é para duas etapas, por que não divulgá-lo imediatamente no par de registradores - não sei a resposta para isso uma pergunta
Em geral, conheça o PIB, diga a ele que definitivamente faremos a divisão em MK, se isso ainda for interessante para ele.
PS: A propósito, quando eu estava procurando por KDPV (como você notou, não o encontrei), notei uma com a inscrição francamente incorreta "Você não deve dividir por zero". Devo dizer com certeza que é possível dividir por zero, não pode ser dividido. Mas, falando sério, em diferentes arquiteturas, elas se dividem por zero de maneira diferente; em x86, obtemos uma exceção (este é um erro inesquecível 200); em algumas, obtemos um dividendo ou zero, mas nunca vi o número máximo máximo. No ARM n / 0 = 0/0, verifica-se 0.