Por que a divisão de hardware demora tanto mais que a multiplicação em um microcontrolador? Por exemplo, em um dsPIC, uma divisão leva 19 ciclos, enquanto a multiplicação leva apenas um ciclo de relógio.
Passei por alguns tutoriais, incluindo o algoritmo de divisão e o algoritmo de multiplicação na Wikipedia. Aqui está o meu raciocínio.
Um algoritmo de divisão, como um método de divisão lenta com restauração na Wikipedia, é um algoritmo recursivo. Isso significa que os resultados (intermediários) da etapa k
são usados como entradas para a etapa k+1
, o que significa que esses algoritmos não podem ser paralelizados. Portanto, são necessários pelo menos n
ciclos para concluir a divisão, enquanto n
há um número de bits em um dividendo. Para dividendos de 16 bits, isso é igual a pelo menos 16 ciclos.
Um algoritmo de multiplicação não precisa ser recursivo, o que significa que é possível paralelizá-lo. No entanto, existem muitos algoritmos de multiplicação diferentes, e eu não tenho idéia de qual deles pode ser usado pelos microcontroladores. Como a multiplicação funciona em um hardware / microcontrolador?
Encontrei um algoritmo multiplicador Dadda , que deveria levar apenas um ciclo de clock para terminar. No entanto, o que não entendi aqui é que o algoritmo de Dadda prossegue em três etapas, enquanto os resultados da etapa 1 são usados na etapa 2, etc. De acordo com isso, isso levaria pelo menos três ciclos de clock para ser concluído.
fonte
Respostas:
Um divisor mapeia com muito menos elegância o hardware típico. Veja os FPGAs Lattice ICE40 como exemplos.
Vamos comparar dois casos: esse multiplicador de 8x8 a 16 bits:
e esse divisor que reduz os operandos de 8 e 8 bits para o resultado de 8 bits:
(Sim, eu sei, o relógio não faz nada)
Uma visão geral do esquema gerado ao mapear o multiplicador para um ICE40 FPGA pode ser encontrada aqui e o divisor aqui .
As estatísticas de síntese da Yosys são:
multiplicar
dividir
Vale a pena notar que o tamanho do verilog gerado para um multiplicador de largura total e um divisor de divisão máxima não são tão extremos. No entanto, se você olhar as figuras abaixo, notará que o multiplicador tem talvez uma profundidade de 15, enquanto o divisor parece mais ou menos 50; o caminho crítico (ou seja, o caminho mais longo que pode ocorrer durante a operação) é o que define a velocidade!
De qualquer maneira, você não poderá ler isso para obter uma impressão visual. Eu acho que as diferenças de complexidade são possíveis de detectar. Estes são multiplicadores / divisores de ciclo único!
Multiplicar
Multiplique em um ICE40 (aviso: ~ 100 imagens Mpixel)
Dividir
( Divida em um ICE40 ) (aviso: ~ 100 imagens Mpixel)
fonte
A divisão lenta é inerentemente iterativa, por isso tende a demorar mais tempo. Existem algoritmos de divisão lenta um pouco mais rápidos que os simples, usando tabelas de pesquisa. O algoritmo SRT produz dois bits por ciclo. Um erro nessa tabela foi a causa do infame bug do Pentium FDIV (ca. 1994). Depois, existem os chamados algoritmos de divisão rápida.
Obviamente, em princípio, você poderia simplesmente usar uma enorme tabela de pesquisa para calcular o produto ou quociente de dois números e, assim, obter resultados em um único ciclo, mas isso tende a se tornar rapidamente impraticável à medida que o número de bits por número aumenta.
fonte
Podemos ter várias camadas de lógica por ciclo de clock, mas há um limite, exatamente quantas camadas de lógica podemos ter e quão complexas essas camadas podem ser dependerão da velocidade do relógio e do processo de semicondutores.
A maioria das multiplicações em computadores usa uma variante da multiplicação longa binária. A multiplicação binária longa envolve
Então, vamos dar uma olhada na implementação disso no hardware.
Então, vamos avaliar quantos estágios lógicos precisamos para um multiplicador 8x8 com resultados de 16 bits. Para simplificar, vamos supor que não tentamos otimizar, pois nem todos os resultados intermediários têm bits em todas as posições.
Vamos supor que um somador completo seja implementado em dois "estágios do portão".
Portanto, cerca de 46 estágios lógicos no total. A maioria é gasta somando os dois últimos resultados intermediários.
Isso pode ser aprimorado ainda mais, explorando o fato de que nem todos os resultados intermediários têm todos os bits presentes (é basicamente o que o multiplicador dado), usando um somador carry lookahead na etapa final. Adicionando 7 números para produzir 3 em vez de três para produzir dois (reduzindo o número de estágios ao preço de mais portões e portões mais largos) etc.
Esses são todos os pequenos detalhes, porém, o ponto importante é que o número de estágios necessários para multiplicar dois números de n bits e produzir um resultado de 2n bits é aproximadamente proporcional a n.
Por outro lado, se olharmos para os algoritmos de divisão, descobrimos que todos eles têm um processo iterativo onde.
Portanto, o número de estágios lógicos necessários para implementar a divisão é aproximadamente proporcional a n ao quadrado.
fonte
Um algoritmo de divisão (de fato qualquer algoritmo) pode ser criado em um ciclo de clock. Se você estiver disposto a pagar pelos transistores extras e diminuir a taxa de clock permitida.
Suponha que você tenha um conjunto de portas que implementa um ciclo de clock de um algoritmo de divisão multiciclo existente. Para tornar o algoritmo um ciclo único, use vários estágios de hardware (semelhantes aos usados em um estágio do algoritmo de vários ciclos), com a saída de um estágio alimentando o estágio seguinte.
Obviamente, o motivo para não fazer dessa maneira é que ele usa muitos transistores. Por exemplo, para uma divisão de 16 bits, pode usar quase 16 vezes mais transistores. Também ter mais estágios de portas reduz a freqüência de clock máxima permitida (porque há mais estágios de atraso de propagação).
fonte
Os algoritmos de divisão prática são todos baseados em conjuntos numéricos que convergem para o quociente.
Existem métodos aditivos, como não restauração ou SRT, que funcionam adicionando ou removendo 2 ^ N ao quociente e, correspondentemente, adicionam ou removem o divisor 2 ^ N * ao restante parcial até que ele converta para zero.
Existem métodos multiplicativos, como Newton-Raphson ou Goldshmidth, que são métodos de localização de raízes em que a divisão é calculada como o inverso da multiplicação.
Os métodos aditivos fornecem um ou alguns bits por ciclo. Os métodos multiplicativos dobram o número de bits para cada ciclo, mas precisam de alguma aproximação inicial, geralmente obtida com uma tabela constante.
As denominações "lenta" e "rápida" são enganosas, pois a velocidade real depende do número de bits, quanto hardware é dedicado à função (e um multiplicador rápido é muito grande) ...
A divisão é mais lenta que a multiplicação, porque não existe um método paralelo direto para calculá-lo: existe uma iteração ou o hardware é copiado para implementar a iteração como blocos em cascata (ou em pipeline).
fonte
Esta não é uma questão de eletrônica. Na melhor das hipóteses, é uma questão de computador, mais bem endereçada ao Stack Overflow.
Veja, por exemplo, aqui: A multiplicação é mais rápida que a divisão de flutuação?
Na realidade, é uma pergunta da vida real: por que a divisão demora muito mais que a multiplicação?
Qual você prefere calcular no papel?
ou
A divisão leva mais tempo que a multiplicação porque é mais difícil de fazer .
fonte