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

Un divisor se asigna de forma mucho menos elegante al hardware típico. Tome Lattice ICE40 FPGAs como ejemplos.

Comparemos dos casos: este multiplicador de 8x8 bits 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

y este divisor que reduce los operandos de 8 y 8 bits al 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

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

Puede encontrar un resumen del esquema generado al asignar multiplicador a un FPGA ICE40 aquí y el divisor aquí .

Las estadísticas de síntesis de Yosys son:

multiplica

• Número de cables: 155
• Número de bits de cable: 214
• Número de cables públicos: 4
• Número de bits de cable públicos: 33
• Cantidad 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

divide

• Número de cables: 145
• Número de bits de cable: 320
• Número de cables públicos: 4
• Número de bits de cable públicos: 25
• Cantidad 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 del verilog generado para un multiplicador de ancho completo y un divisor que se divide al máximo no es tan extremo. Sin embargo, si observa las imágenes a continuación, notará que el multiplicador tiene quizás una profundidad de 15, mientras que el divisor se parece más o menos a 50; La ruta crítica (es decir, la ruta más larga que puede ocurrir durante la operación) es lo que define la velocidad.

De todas formas, no podrás leer esto para obtener una impresión visual. Creo que las diferencias en la complejidad son posibles de detectar. ¡Estos son multiplicadores / divisores de ciclo único!

Multiplica

Multiplica en un ICE40 (advertencia: ~ 100 Mpixel image)

Divide

(

La división lenta es inherentemente iterativa por lo que tiende a tomar más tiempo. Hay algoritmos de división lenta algo más rápidos que los simples, que utilizan tablas de búsqueda. El algoritmo SRT produce dos bits por ciclo. Un error en dicha tabla fue la causa del infame error de Pentium FDIV (ca. 1994). Luego están los llamados algoritmos de división rápida.

Por supuesto, en principio, simplemente podría usar una enorme tabla de búsqueda para calcular el producto o el cociente de dos números, y así obtener resultados en un solo ciclo, pero eso tiende a volverse poco práctico como el número de bits por número. aumenta

Podemos tener múltiples capas de lógica por ciclo de reloj, pero hay un límite, la cantidad exacta de capas de lógica que podamos tener y la complejidad de esas capas dependerá de nuestra velocidad de reloj y nuestro proceso de semiconductores.

  

Sin embargo, hay muchos algoritmos de multiplicación diferentes, y no tengo ni idea de cuál puede ser usado por los microcontroladores

La mayoría de las multiplicaciones de Afaict en computadoras usa una variante de la multiplicación larga binaria. La multiplicación larga binaria implica

• Desplazando un operando por varias cantidades diferentes
• Enmascarar los números desplazados según el segundo operando
• Agregar los resultados del enmascaramiento juntos.

Así que echemos un vistazo a la implementación de esto en hardware.

• El cambio es solo una cuestión de cómo conectamos las cosas, por lo que es gratis.
• Enmascaramiento requiere AND puertas. Eso significa una capa de lógica, por lo que desde el punto de vista del tiempo es barato.
• La adición es relativamente costosa debido a la necesidad de una cadena portadora. Afortunadamente hay un truco que podemos usar. Para la mayoría de las etapas de adición, en lugar de agregar dos números para producir uno, podemos agregar tres números para producir dos.

Entonces, veamos cuántas etapas lógicas necesitamos para un multiplicador de 8x8 con resultados de 16 bits. Para simplificar, supongamos que no intentamos y optimizamos porque no todos los resultados intermedios tienen bits en todas las posiciones.

Supongamos que un sumador completo se implementa en dos "etapas de puerta".

• 1 para enmascarar para producir 8 resultados intermedios.
• 2 para agregar grupos de tres números para reducir los 8 resultados intermedios a 6
• 2 para agregar grupos de tres números para reducir los 6 resultados intermedios a 4
• 2 para agregar un grupo de tres números para reducir los 4 resultados intermedios a 3
• 2 para agregar un grupo de tres números para reducir los 3 resultados intermedios a 2
• 32 para sumar los dos resultados finales.

Así que alrededor de 46 etapas lógicas en total. La mayoría de los cuales se gastan sumando los dos últimos resultados intermedios.

Esto podría mejorarse aún más explotando el hecho de que no todos los resultados intermedios tienen todos los bits presentes (eso es básicamente lo que hace el multiplicador dado), mediante el uso de un sumador de acarreo anticipado para el paso final. Sumando 7 números para producir 3 en lugar de tres para producir dos (reduciendo el número de etapas al precio de más puertas y puertas más anchas) etc.

Aunque todos los detalles son menores, el punto importante es que el número de etapas necesarias para multiplicar dos números de n bits y producir un resultado de 2 n bits es aproximadamente proporcional a n.

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

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

Entonces, el número de etapas lógicas requeridas para implementar la división es aproximadamente proporcional a n al cuadrado.

Un algoritmo de división (de hecho, cualquier algoritmo) se puede hacer en un ciclo de reloj. Si está dispuesto a pagar por los transistores adicionales y la menor tasa de reloj permitida.

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

Por supuesto, la razón para no hacerlo de esta manera es que usa muchos transistores. Por ejemplo, para una división de 16 bits puede usar casi 16 X más transistores. Además, al tener más etapas de puertas, se reduce la frecuencia de reloj máxima permitida (porque hay más etapas de retardo de propagación).

Los algoritmos de división práctica están basados en conjuntos numéricos que convergen al cociente.

• Hay métodos aditivos, como non-restore o SRT, que funcionan agregando o eliminando 2 ^ N al cociente y agregando o eliminando correspondientemente el divisor 2 ^ N * al resto parcial hasta que haya convergido a cero .

• Hay métodos multiplicativos, como Newton-Raphson u Goldshmidth, que son métodos de búsqueda de raíces donde la división se calcula como la inversa de la multiplicación.

Los métodos aditivos dan uno o unos pocos bits por ciclo. Los métodos multiplicativos duplican el número de bits para cada ciclo, pero necesitan una aproximación inicial, a menudo obtenida con una tabla constante.

Las denominaciones "lenta" y "rápida" son engañosas, ya que la velocidad real depende de la cantidad de bits, la cantidad de hardware que se dedica a la función (y un multiplicador rápido es muy grande) ...

La división es más lenta que la multiplicación porque no hay un método directo y paralelo para calcularla: existe una iteración o se copia el hardware para implementar la iteración como bloques en cascada (o segmentados).

  

¿Por qué la división de hardware toma mucho más tiempo que la multiplicación en un microcontrolador?

Esta no es una pregunta electrónica. En el mejor de los casos, es una pregunta de computadora, mejor dirigida al desbordamiento de pila.

Vea, por ejemplo, aquí: ¿La multiplicación es más rápida que la división flotante?

En realidad, es una pregunta de la vida real: ¿Por qué la división lleva mucho más tiempo que la multiplicación?

¿Qué prefieres calcular en papel?

51 * 82

o

4182 / 51

La división lleva más tiempo que la multiplicación porque es más difícil de hacer .