Por que a divisão de hardware demora muito mais que a multiplicação?

37

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 ksã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 nciclos para concluir a divisão, enquanto nhá 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.

Marko Gulin
fonte
2
O algoritmo não está realmente definindo o número de ciclos de clock. Sua CPU específica pode ter um multiplicador / divisor de hardware trabalhando em um ciclo ou 20 ciclos, independentemente da implementação interna.
Eugene Sh.
11
OP, você pode fornecer um link que forneça mais informações sobre os ciclos 19 vs 1 de que você fala? Algo específico sobre o seu DSP.
Vladimir Cravero
11
Obrigado pelas respostas. Aqui está uma folha de dados para o meu microcontrolador: ww1.microchip.com/downloads/en/DeviceDoc/70005127c.pdf . Consulte Visão geral do conjunto de instruções, começando na página 292. Diz que todas as instruções DIV levam 18 ciclos, enquanto todas as instruções MUL levam apenas 1 ciclo. Mas não é comum apenas para este MCU, já vi isso em muitos outros MCUs.
Marko Gulin
2
@ Curd, bem, eles são iguais, não são? São para mim. Eu não acho que isso ilustra tão bem quanto você pode imaginar.
TonyM
11
O outro fator é a economia e os padrões de uso. A maioria dos usos invocados se multiplicam muito mais frequentemente do que dividem. Dedicar uma grande área de silício a uma função de divisão de hardware mais rápida que será usada com pouca frequência é uma economia pobre. Melhor fazer um chip menor e mais barato, ou usar a lógica extra de uma maneira mais produtiva. Aliás, quando comecei com minicomputadores, dividir nem sempre era uma instrução. Em algumas máquinas, era uma chamada de biblioteca de software, como raiz quadrada.
precisa saber é o seguinte

Respostas:

34

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:

module multiply (clk, a, b, result);
   input clk;
   input [7:0]a;
   input [7:0]b;
   output [15:0]result;
   always @(posedge clk)
     result = a * b;
endmodule // multiply

e esse divisor que reduz os operandos de 8 e 8 bits para o resultado de 8 bits:

module divide(clk, a, b, result);
   input clk;
   input [7:0] a;
   input [7:0] b;
   output [7:0] result;
   always @(posedge clk)
     result = a / b;
endmodule // divide

(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

  • Número de fios: 155
  • Número de bits de fio: 214
  • Número de fios públicos: 4
  • Número de bits de fio público: 33
  • Número de memórias: 0
  • Número de bits de memória: 0
  • Número de processos: 0
  • Número de células: 191
    • SB_CARRY 10
    • SB_DFF 16
    • SB_LUT4 165

dividir

  • Número de fios: 145
  • Número de bits de fio: 320
  • Número de fios públicos: 4
  • Número de bits de fio público: 25
  • Número de memórias: 0
  • Número de bits de memória: 0
  • Número de processos: 0
  • Número de células: 219
    • SB_CARRY 85
    • SB_DFF 8
    • SB_LUT4 126

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)

Imagem em escala do multiplicador

Dividir

( Divida em um ICE40 ) (aviso: ~ 100 imagens Mpixel)

Imagem em escala do divisor

Marcus Müller
fonte
4
não, você pode implementá-los de forma não iterativa. Mas isso levará algum tempo até que o resultado válido "ondule" pela lógica. As implementações acima são não iterativas.
Marcus Müller
9
Quero um pôster na parede do divisor.
precisa saber é o seguinte
5
Agora há um PDF na multiplicação . Tem 3378 × 3177 mm, portanto, converse com seu parceiro antes de colocá-lo no teto do quarto.
Marcus Müller
2
Suas imagens de 100 megapixels são impressionantes, mas são um exagero para o ponto que você está tentando expressar, e causam enormes problemas para quem tenta visualizar esta página em um dispositivo com memória limitada, como um telefone ou tablet. Se você deseja exibir as imagens em linha, encontre uma maneira de produzir uma visualização com resolução mais baixa.
Dave Tweed
4
Ei, esses gráficos graphiz estão fora do gancho, ei!
Spencer Williams
8

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.

Spehro Pefhany
fonte
Mas o ponto principal é que os algoritmos de divisão não podem ser paralelos, diferentemente dos algoritmos de multiplicação, e é por isso que eles são muito mais lentos?
Marko Gulin
2
O @MarkoGulin "não pode" é uma afirmação muito forte. Certamente não é simples.
Spehro Pefhany
2
Eu acho que você pode enfraquecê-lo de "algoritmos de divisão não podem ser paralelizados" para "as maneiras que descobrimos para paralelizar a divisão são mais difíceis para o hardware que implementa a divisão do que a multiplicação paralela". Sphero dá um exemplo de como fazer a divisão de ciclo único usando portas O (2 ^ n) para multiplicar números de n bits ... mas isso não é prático.
precisa saber é o seguinte
11
A divisão longa pode explorar o paralelismo em qualquer grau desejado, calculando um valor recíproco aproximado que, quando multiplicado pelo divisor, produz um resultado da forma 1000 ... xxxx. Ao trabalhar com um divisor dessa forma com N zeros à esquerda, é fácil para calcular N bits do resultado a cada etapa.
Supercat
8

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.

No entanto, existem muitos algoritmos de multiplicação diferentes, e eu não tenho idéia de qual deles pode ser usado pelos microcontroladores

A maioria das multiplicações em computadores usa uma variante da multiplicação longa binária. A multiplicação binária longa envolve

  • Mudando um operando por várias quantidades diferentes
  • Mascarar os números deslocados com base no segundo operando
  • Adicionando os resultados da máscara juntos.

Então, vamos dar uma olhada na implementação disso no hardware.

  • Mudar é apenas uma questão de como ligamos as coisas, por isso é de graça.
  • O mascaramento requer AND portões. Isso significa uma camada de lógica, portanto, do ponto de vista do tempo, é barato.
  • A adição é relativamente cara devido à necessidade de uma cadeia de transporte. Felizmente, há um truque que podemos usar. Para a maioria dos estágios de adição, em vez de adicionar dois números para produzir um, podemos adicionar três números para produzir dois.

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".

  • 1 para mascarar para produzir 8 resultados intermediários.
  • 2 para adicionar grupos de três números para reduzir os 8 resultados intermediários para 6
  • 2 para adicionar grupos de três números para reduzir os 6 resultados intermediários para 4
  • 2 para adicionar um grupo de três números para reduzir os 4 resultados intermediários para 3
  • 2 para adicionar um grupo de três números para reduzir os 3 resultados intermediários para 2
  • 32 para somar os dois resultados finais.

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.

  1. O que é feito em uma iteração depende muito dos resultados da iteração anterior.
  2. o número de estágios lógicos necessários para implementar uma iteração é aproximadamente proporcional a n (subtração e comparação são muito semelhantes em complexidade à adição)
  3. o número de iterações também é aproximadamente proporcional a n.

Portanto, o número de estágios lógicos necessários para implementar a divisão é aproximadamente proporcional a n ao quadrado.

Peter Green
fonte
Obrigado pela sua resposta. Eu li no Wiki que o algoritmo do Dadda é muito eficiente quando se trata do número necessário de portas para implementar esse algoritmo no hardware. Apesar disso, a maioria dos hardwares usa "multiplicação binária longa"?
Marko Gulin
11
Parece que o algotihm de dada é uma versão otimizada da multiplicação binária longa.
Peter Green
Eu queimo 8 ciclos para fazer uma divisão 1 / x. Eu então uso isso contra uma multiplicação de 8 ciclos por um custo fixo de 16 ciclos.
precisa saber é o seguinte
Isso demonstra muito bem que a multiplicação não é muito pior do que a adição, afinal.
Hagen von Eitzen
11
Uma iteração requer uma subtração que pode ser feita nos estágios O (lgN) usando o hardware O (NlgN) ou O (sqrt (N)) usando o hardware O (N). O ponto essencial, porém, é que a multiplicação requer estágios O (lgN), enquanto a divisão requer estágios O (NlgN). Não O (N * N), mas maior que a multiplicação por um fator de O (N), a menos que se comece tomando um recíproco aproximado, de modo a permitir que mais trabalho seja feito por etapa.
Supercat
4

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

user4574
fonte
4

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

TEMLIB
fonte
0

Por que a divisão de hardware demora tanto mais que a multiplicação em um microcontrolador?

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?

51 * 82

ou

4182 / 51

A divisão leva mais tempo que a multiplicação porque é mais difícil de fazer .

Nick Gammon
fonte