¿Por qué división de hardware de tomar mucho más de la multiplicación?

Question

¿Por qué división de hardware de tomar mucho más tiempo que la multiplicación por un microcontrolador? E. g., en un dsPIC, una división lleva 19 ciclos, mientras que la multiplicación se lleva sólo un ciclo de reloj.

Me fui a través de algunos tutoriales, incluyendo el algoritmo de la División y el algoritmo de la Multiplicación en la Wikipedia. Aquí está mi razonamiento.

Un algoritmo de la división, como un lento método de la división con restauración en la Wikipedia, es un algoritmo recursivo. Esto significa que (intermedio) los resultados del paso k se utilizan como entradas a paso k+1, lo que significa que estos algoritmos no puede ser paralelizado. Por lo tanto, se necesitan al menos n ciclos para completar la división, mientras que n es un número de bits en el pago de un dividendo. Para la 16 bits de dividendos, esto es igual a por lo menos 16 ciclos.

Un algoritmo de la multiplicación no necesita ser recursivo, lo que significa que es posible paralelizar. Sin embargo, hay muchos tipos diferentes de algoritmos de la multiplicación, y no tengo ni idea que puede ser usado por los microcontroladores. ¿Cómo multiplicación de trabajar en un hardware/microcontrolador?

He encontrado un Dadda multiplicador de algoritmo, que se supone tendrá sólo un ciclo de reloj para terminar. Sin embargo, lo que no entiendo aquí es que Dadda del algoritmo procede en tres pasos, mientras que los resultados del paso 1 se utiliza en el paso 2, etc. De acuerdo a esto, esto requeriría por lo menos tres ciclos de reloj para terminar.

Answer 1

Un divisor de mapas y mucho menos elegante típico de hardware. Tomar Celosía ICE40 FPGAs como ejemplos.

Vamos a comparar dos casos: este 8x8 bits a 16 bits del multiplicador:

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

y este divisor que reduce el 8 y 8 bits de los operandos de 8 bits de resultado:

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

(Sí, lo sé, el reloj no hacer nada)

Una visión general de los generados esquemático a la hora de asignar el multiplicador a un ICE40 FPGA se pueden encontrar aquí y el divisor de aquí.

La síntesis de las estadísticas de Yosys son:

multiplicar

• Número de hilos: 155
• Número de hilos de bits: 214
• Número de público cables: 4
• Número de público alambre de bits: 33
• Número de memorias: 0
• Número de bits de memoria: 0
• Número de procesos: 0
• Número de celdas: 191
  • SB_CARRY 10
  • SB_DFF 16
  • SB_LUT4 165

dividir

• Número de hilos: 145
• Número de hilos de bits: 320
• Número de público cables: 4
• Número de público alambre de bits: 25
• Número de memorias: 0
• Número de bits de memoria: 0
• Número de procesos: 0
• Número de celdas: 219
  • SB_CARRY 85
  • SB_DFF 8
  • SB_LUT4 126

---

Vale la pena señalar que el tamaño de los generados verilog para un ancho completo multiplicador y un máximo-división el divisor no son tan extremas. Sin embargo, si usted mira las fotos de abajo, te darás cuenta de que el multiplicador tiene quizás una profundidad de 15, mientras que el divisor se parece más a 50 o así; la ruta crítica (es decir, el camino más largo que pueden ocurrir durante la operación) es lo que define la velocidad!

---

Usted no será capaz de leer esto, de todos modos, para obtener una impresión visual. Creo que las diferencias en complejidad son posibles de detectar. Estos son solo ciclo multiplicador/divisores!

Multiplicar

Multiplicar en un ICE40 (advertencia: ~100 Megapíxeles de imagen)

Dividir

(Se dividen en un ICE40) (advertencia: ~100 Megapíxeles de imagen)

Answer 2

Podemos tener múltiples capas de lógica en cada ciclo de reloj, pero hay un límite, exactamente cuántas capas de lógica podemos tener lo complejo de las capas puede ser dependerá de la velocidad de reloj y nuestro proceso de semiconductores.

Sin embargo, hay muchos tipos diferentes de algoritmos de la multiplicación, y no tengo ni idea que puede ser usado por los microcontroladores

Afaict la mayoría de la multiplicación en los equipos que utiliza una variante de binario largo de la multiplicación. Binario multiplicación larga implica

• Cambio de un operando por diferentes cantidades
• El enmascaramiento de los cambió de números basados en el segundo operando
• La adición de los resultados de la enmascaramiento juntos.

Así que echemos un vistazo a la aplicación de esta en el hardware.

• El cambio es sólo una cuestión de cómo nos alambre de cosas, así que le sale gratis.
• Enmascaramiento requiere Y puertas. Eso significa que una capa de la lógica, por lo que desde un punto de vista del tiempo es barato.
• Además es relativamente costoso debido a la necesidad de llevar a la cadena. Afortunadamente, hay un truco que podemos utilizar. Para la mayoría de la adición etapas en lugar de la adición de dos números para producir uno le puede agregar tres números para producir dos.

Así que deja de béisbol cuántas etapas lógicas que necesitamos para un 8x8 multiplicador con un 16 bits resultados. Por simplicidad vamos a suponer no tratamos de optimizar por el hecho de que no todos los resultados intermedios han bits en todas las posiciones.

Supongamos que una serpiente llena se implementa en dos "puerta de las etapas".

• 1 para enmascarar para producir 8 resultados intermedios.
• 2 para agregar grupos de tres números para reducir el 8 resultados intermedios para 6
• 2 para agregar grupos de tres números para reducir el 6 resultados intermedios para 4
• 2 para añadir un grupo de tres números para reducir la 4 resultados intermedios a 3
• 2 para añadir un grupo de tres números para reducir el 3 resultados intermedios para 2
• 32 para agregar los dos últimos resultados.

Por lo que alrededor de 46 etapas lógicas en total. La mayoría de los cuales se pasó de sumar los dos últimos resultados intermedios.

Esto podría ser mejorado aún más por explotar el hecho de que no todos los resultados intermedios, tiene todos los bits presentes (que es básicamente lo que la dada multiplicador), mediante un acarreo de la serpiente de lookahead para el paso final. Mediante la adición de los números 7 a producir 3 en lugar de tres, para producir dos (reducción del número de etapas en el precio de más puertas y más amplias puertas) etc.

Que es todos los detalles de menor importancia, sin embargo, el punto importante es que el número de etapas necesarias para multiplicar dos números de n bits y producir un 2n bits resultado es aproximadamente proporcional a n.

---

Por otro lado, si nos fijamos en la división de los algoritmos encontramos todos ellos tienen un proceso iterativo donde.

1. Lo que se hace en una iteración depende heavilly en los resultados de la iteración anterior.
2. el número de etapas lógicas necesarias para implementar una iteración es de aproximadamente proporitional a n (resta y comparación son muy similares en complejidad a la adición)
3. el número de iteraciones es aproximadamente proporcional a n.

Por lo que el número de etapas lógicas necesarias para implementar la división es aproximadamente proporcional a n al cuadrado.

Answer 3

Lento división es inherentemente iterativo, por lo que tiende a tomar más tiempo. Hay algo más rápido lento de la división de los algoritmos de los simples, el uso de tablas de búsqueda. El SRT algoritmo produce dos bits por ciclo. Un error en un cuadro de este fue la causa de la infame Pentium FDIV error (ca. 1994). Luego están los llamados fast división de algoritmos.

Por supuesto, en principio, podría simplemente utilizar una enorme tabla de búsqueda para calcular el producto o el cociente de dos números, y así obtener los resultados en un único ciclo, pero que tiende a obtener rápidamente práctico como el número de bits por número aumenta.

Answer 4

División de prácticas de algoritmos se basan en numérico suites que convergen para el cociente.

• Hay métodos aditivos, como no-de la restauración o el SRT que funciona mediante la adición o eliminación de 2^N el cociente y, en consecuencia, agregar o quitar los 2^N * Divisor para el parcial resto hasta que se ha aproximado a cero.

• Hay multiplicativo métodos, como el de Newton-Raphson o Goldshmidth, que son la raíz de encontrar métodos donde la división se calcula como la inversa de la multiplicación.

Métodos aditivos le da a uno o unos pocos bits por ciclo. Multiplicativa de los métodos de duplicar el número de bits para cada ciclo, pero necesitan algún aproximación inicial, a menudo se obtiene con una mesa constante.

El "lento" y "rápido" denominaciones son engañosas, como la velocidad real depende del número de bits, cuánto hardware está dedicado a la función (y un rápido multiplicador es muy grande)...

La división es más lento que el de la multiplicación porque no hay ningún daño directo, paralelo método de cálculo es : no es una iteración, o de hardware es copiado a implementar la iteración como en cascada (o canalizado) bloques.

Answer 5

Un algoritmo de la división (de hecho, cualquier algoritmo) puede hacerse en un solo ciclo de reloj. Si usted está dispuesto a pagar extra para el transistores inferiores y permitió que la frecuencia de reloj.

Suponga que tiene un conjunto de puertas que implementa un ciclo de reloj de un multi-ciclo del algoritmo de la división. Para hacer que el algoritmo de ciclo único, el uso de múltiples etapas de hardware (similar a la utilizada en una etapa de la multi-algoritmo de ciclo), con la salida de una etapa de alimentación de la etapa siguiente.

Por supuesto, la razón de no hacerlo de esa manera es que se utiliza una gran cantidad de transistores. Por ejemplo, para un joven de 16 bits de la división que se puede utilizar casi 16 X más transistores. También tener más etapas de puertas reduce el máximo permitido frecuencia de reloj (porque no hay más etapas de retardo de propagación).