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

37

¿Por qué la división de hardware tarda tanto más que la multiplicación en un microcontrolador? Por ejemplo, en un dsPIC, una división toma 19 ciclos, mientras que la multiplicación toma solo un ciclo de reloj.

Revisé algunos tutoriales, incluidos el algoritmo de división y el algoritmo de multiplicación en Wikipedia. Aquí está mi razonamiento.

Un algoritmo de división, como un método de división lenta con restauración en Wikipedia, es un algoritmo recursivo. Esto significa que los resultados (intermedios) del paso kse utilizan como entradas para el paso k+1, lo que significa que estos algoritmos no se pueden paralelizar. Por lo tanto, se necesitan al menos nciclos para completar la división, mientras que nhay una cantidad de bits en un dividendo. Para dividendos de 16 bits, esto equivale a al menos 16 ciclos.

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

Encontré un algoritmo multiplicador Dadda , que se supone que toma solo un ciclo de reloj para terminar. Sin embargo, lo que no entiendo aquí es que el algoritmo de Dadda procede en tres pasos, mientras que los resultados del paso 1 se usan en el paso 2, etc. De acuerdo con esto, esto tomaría al menos tres ciclos de reloj para terminar.

Marko Gulin
fuente
2
El algoritmo no define realmente el número de ciclos de reloj. Su CPU específica podría tener un multiplicador / divisor de hardware trabajando en un ciclo o 20 ciclos, independientemente de la implementación interna.
Eugene Sh.
1
OP, ¿puede proporcionar un enlace que brinde más información sobre los ciclos 19 vs 1 del que habla? Algo específico sobre tu DSP.
Vladimir Cravero
1
Gracias por las respuestas Aquí hay una hoja de datos para mi microcontrolador: ww1.microchip.com/downloads/en/DeviceDoc/70005127c.pdf . Consulte Descripción general del conjunto de instrucciones, comenzando en la página 292. Dice que todas las instrucciones DIV toman 18 ciclos, mientras que todas las instrucciones MUL toman solo 1 ciclo. Pero no es común solo para este MCU, lo he visto en muchos otros MCU.
Marko Gulin
2
@Curd, bueno, son casi lo mismo, ¿no? Son para mi No creo que eso lo ilustre tan bien como te puedas imaginar.
TonyM
1
El otro factor es la economía y los patrones de uso. La mayoría de los usos invocan multiplicar con mucha más frecuencia que dividir. Dedicar una gran área de silicio a una función de división de hardware más rápida que se utilizará con poca frecuencia es una economía pobre. Es mejor hacer un chip más pequeño y más barato, o usar la lógica adicional de una manera más productiva. Por cierto, cuando comencé con las minicomputadoras, dividir no siempre fue una instrucción. En algunas máquinas era una llamada a la biblioteca de software, como la raíz cuadrada.
nigel222

Respuestas:

34

Un divisor se asigna mucho menos elegantemente al hardware típico. Tome los FPGA Lattice ICE40 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 a un 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 una descripción general del esquema generado al asignar el multiplicador a un FPGA ICE40 aquí y el divisor aquí .

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

multiplicar

  • Número de cables: 155
  • Número de puntas de alambre: 214
  • Número de cables públicos: 4
  • Número de bits de cable público: 33
  • Cantidad de recuerdos: 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 cables: 145
  • Número de puntas de alambre: 320
  • Número de cables públicos: 4
  • Número de bits de cable público: 25
  • Cantidad de recuerdos: 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 de división máxima no son tan extremos. 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 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 todos modos, no podrá leer esto para obtener una impresión visual. Creo que las diferencias en complejidad son posibles de detectar. ¡Estos son multiplicadores / divisores de ciclo único!

Multiplicar

Multiplique en un ICE40 (advertencia: ~ 100 imágenes de Mpixel)

Imagen a escala del multiplicador

Dividir

( Dividir en un ICE40 ) (advertencia: ~ imagen de 100 Mpixel)

Imagen a escala del divisor

Marcus Müller
fuente
44
no, puedes implementarlos de forma no iterativa. Pero simplemente tomará bastante tiempo hasta que el resultado válido "ondule" a través de la lógica. Las implementaciones anteriores no son iterativas.
Marcus Müller
99
Quiero un póster de pared del divisor.
Ian Howson
55
Hay un PDF ahora en la esencia de multiplicación . Es 3378 × 3177 mm, así que por favor hable con su pareja antes de poner esto en el techo de la habitación.
Marcus Müller
2
Sus imágenes de 100 megapíxeles son impresionantes, pero son excesivas para el punto que está tratando de hacer, y causan grandes problemas a cualquiera que intente ver esta página en un dispositivo con memoria limitada, como un teléfono o tableta. Si desea mostrar las imágenes en línea, busque la manera de producir una vista previa de menor resolución.
Dave Tweed
44
¡Yo, esos gráficos Graphviz están descolgados, yo!
Spencer Williams el
8

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 usan tablas de búsqueda. El algoritmo SRT produce dos bits por ciclo. Un error en dicha tabla fue la causa del infame error Pentium FDIV (ca. 1994). Luego están los llamados algoritmos de división rápida.

Por supuesto, en principio, podría simplemente usar una gran 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 rápidamente a medida que aumenta el número de bits por número.

Spehro Pefhany
fuente
Pero la conclusión es que los algoritmos de división no pueden ser paralelos, a diferencia de los algoritmos de multiplicación, y es por eso que son mucho más lentos.
Marko Gulin
2
@MarkoGulin "no puede" es una afirmación muy fuerte. Ciertamente no es sencillo.
Spehro Pefhany
2
Creo que podría debilitarlo de "los algoritmos de división no pueden ser paralelizados" a "las formas en que hemos encontrado que la división en paralelo es más difícil para el hardware que implementa la división que la multiplicación en paralelo". Sphero da un ejemplo de cómo hacer una división de ciclo único usando compuertas O (2 ^ n) para multiplicar números de n bits ... pero eso no es práctico.
Cort Ammon
1
La división larga puede explotar el paralelismo en cualquier grado deseado al calcular un recíproco aproximado que, cuando se multiplica por el divisor, produce un resultado de la forma 1000 ... xxxx, cuando se trabaja con un divisor de tal forma con N ceros iniciales, es fácil para calcular N bits del resultado con cada paso.
supercat
8

Podemos tener múltiples capas de lógica por ciclo de reloj, pero hay un límite, exactamente cuántas capas de lógica podemos tener y cuán complejas pueden ser 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 utilizado por los microcontroladores.

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

  • Cambio de un operando por varias cantidades diferentes
  • Enmascarar los números desplazados en función del 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.
  • El enmascaramiento requiere Y 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 de transporte. Afortunadamente hay un truco que podemos usar. Para la mayoría de las etapas de suma, en lugar de sumar dos números para producir uno, podemos sumar tres números para producir dos.

Así que vamos a calcular cuántas etapas lógicas necesitamos para un multiplicador 8x8 con resultados de 16 bits. Para simplificar, supongamos que no intentamos optimizar por el hecho de que no todos los resultados intermedios tienen bits en todas las posiciones.

Supongamos que se implementa un sumador completo 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.

Entonces, 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 dada), mediante el uso de un sumador anticipado de acarreo para el paso final. Al agregar 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.

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


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

  1. Lo que se hace en una iteración depende enormemente 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.

Peter Green
fuente
Gracias por su respuesta. Leí en Wiki que el algoritmo de Dadda es muy eficiente cuando se trata de la cantidad requerida de puertas para implementar este algoritmo en el hardware. A pesar de eso, ¿la mayoría del hardware usa "multiplicación larga binaria"?
Marko Gulin
1
Parece que el algotihm de papá es una versión optimizada de la multiplicación larga binaria.
Peter Green
Quemo 8 ciclos para hacer una división 1 / x. Luego lo uso contra una multiplicación de 8 ciclos por un costo fijo de 16 ciclos.
b degnan
Esto demuestra que la multiplicación no es mucho peor que la suma después de todo.
Hagen von Eitzen
1
Una iteración requiere una resta que se puede hacer en etapas O (lgN) usando hardware O (NlgN) u etapas O (sqrt (N)) usando hardware O (N). Sin embargo, el punto esencial es que la multiplicación requiere etapas O (lgN), mientras que la división requiere etapas O (NlgN). No O (N * N) sino mayor que la multiplicación por un factor de O (N) a menos que uno comience tomando un recíproco aproximado para permitir más trabajo por paso.
supercat
4

Se puede hacer un algoritmo de división (de hecho, cualquier algoritmo) en un ciclo de reloj. Si está dispuesto a pagar los transistores adicionales y la tasa de reloj más baja permitida.

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

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

usuario4574
fuente
4

Los algoritmos prácticos de división se basan en conjuntos numéricos que convergen al cociente.

  • Existen métodos aditivos, como la no restauración o SRT, que funciona agregando o eliminando 2 ^ N al cociente y, en consecuencia, agregue o elimine el divisor 2 ^ N * al resto parcial hasta que haya convergido a cero.

  • Existen métodos multiplicativos, como Newton-Raphson o 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, cuánto hardware 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 existe un método directo y paralelo para calcularla: o hay una iteración, o se copia el hardware para implementar la iteración como bloques en cascada (o canalizados).

TEMLIB
fuente
0

¿Por qué la división de hardware tarda tanto más 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 a Stack Overflow.

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

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

¿Cuál preferirías 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 .

Nick Gammon
fuente