¿Por qué la división es mucho más compleja que otras operaciones aritméticas?

39

Recientemente encontré un caso en el que necesitaba una operación de división de enteros en un chip que carecía de uno (ARM Cortex-A8). Mientras intentaba investigar por qué debía ser eso, descubrí que, en general, la división lleva muchos más ciclos que la suma, la resta o la multiplicación en casi cualquier arquitectura entera (o de punto fijo). ¿Por qué es este el caso? ¿No es representable con una lógica AND-OR de dos capas como todo lo demás?

Phonon
fuente

Respuestas:

34

La división es un algoritmo iterativo en el que el resultado del cociente debe desplazarse al resto utilizando una medida euclidiana, ver 2 ; mientras que la multiplicación puede reducirse a una serie (fija) de trucos de manipulación de bits.

aterrel
fuente
2
Solía ​​ser que tanto la multiplicación como la división eran operaciones lentas. Hoy en día la multiplicación es un poco más rápida (pero un poco más lenta que la suma / resta), pero la división aún es más lenta que las demás. Creo que Newton-Raphson todavía es utilizado internamente por la mayoría para corresponder un número.
JM
12
(Fuera del tema: "Las operaciones inversas suelen ser difíciles. Solo mire la integración versus la diferenciación" - depende de si lo que está haciendo es simbólico o numérico. La diferenciación es simbólicamente fácil, pero numéricamente difícil; la integración es simbólicamente difícil, pero numéricamente fácil.)
JM
1
De acuerdo, me libraré diciendo que la cubicación es una lata diferente de gusanos; pero al menos en el caso unidimensional, la cuadratura es más fácil que la diferenciación.
JM
1
En cualquier caso, los inversos siempre vienen en pares. ¿Por qué llamarías a uno la "operación" y al otro el "inverso"?
David Ketcheson el
2
Ni la iteración ni la inversa lo hacen más difícil. La dureza de la división proviene del hecho de que tiene que cambiar el resultado del cociente al resto utilizando una medida euclidiana. Ver el teorema del algoritmo de división .
20

Si bien todas las CPU actuales parecen usar un enfoque iterativo como sugiere aterrel , se ha realizado algún trabajo en enfoques no iterativos. La división de punto flotante de precisión variable y la raíz cuadrada hablan de una implementación no iterativa de la división de punto flotante y la raíz cuadrada en un FPGA , utilizando tablas de búsqueda y expansión de la serie taylor.

Sospecho que las mismas técnicas pueden hacer posible que estas operaciones se reduzcan a un solo ciclo (rendimiento, si no latencia), pero es probable que necesite grandes tablas de búsqueda y, por lo tanto, áreas inusualmente grandes de bienes raíces de silicio para hacerlo. .

¿Por qué no sería factible?

Al diseñar CPU, hay muchas compensaciones que hacer. La funcionalidad, la complejidad (número de transistores), la velocidad y el consumo de energía están interrelacionados y las decisiones tomadas durante el diseño pueden tener un gran impacto en el rendimiento.

Un procesador moderno probablemente podría tener una unidad de punto flotante principal que dedique suficientes transistores en el silicio para realizar una división de punto flotante en un solo ciclo , pero es poco probable que sea un uso eficiente de esos transistores.

El punto flotante multiplicado hizo esta transición de iterativo a no iterativo hace una década. En estos días, la multiplicación de ciclo único e incluso la acumulación múltiple son comunes, incluso en procesadores móviles.

Antes de convertirse en un uso eficiente del presupuesto de transistores, la multiplicación, como la división, a menudo se realizaba mediante un método iterativo. En aquel entonces, los procesadores DSP dedicados podían dedicar la mayor parte de su silicio a una sola unidad de acumulación múltiple (MAC) rápida . Una CPU Core2duo tiene una latencia múltiple de coma flotante de 3 (el valor sale de la tubería 3 ciclos después de entrar), pero puede tener 3 multiplicaciones en vuelo a la vez, lo que resulta en un rendimiento de ciclo único, mientras que su unidad SSE2 puede bombea múltiples multiplicaciones de FP en un solo ciclo.

En lugar de dedicar grandes áreas de silicio a una unidad de división de ciclo único, las CPU modernas tienen múltiples unidades, cada una de las cuales puede realizar operaciones en paralelo, pero están optimizadas para sus propias situaciones específicas. De hecho, una vez que tenga en cuenta las instrucciones SIMD como SSE o los gráficos integrados de CPU del Sandy Bridge o CPU posteriores, puede haber muchas unidades de división de punto flotante en su CPU.

Si la división genérica de punto flotante fuera más importante para las CPU modernas, entonces podría tener sentido dedicar suficiente área de silicio para hacer un solo ciclo, sin embargo, la mayoría de los fabricantes de chips obviamente han decidido que pueden hacer un mejor uso de ese silicio al usar esas compuertas para otras cosas . Por lo tanto, una operación es más lenta, pero en general (para escenarios de uso típicos) la CPU es más rápida y / o consume menos energía.

Mark Booth
fuente
Que yo sepa, ningún chip tiene latencias de división de ciclo único para coma flotante. Por ejemplo, las tablas de instrucciones de Agner Fog para las CPU Intel, AMD y VIA enumeran DIVPS (división de punto flotante empaquetado con SSE) como 10-14 ciclos. No puedo encontrar ningún hardware con instrucciones de división de ciclo único, pero estaría dispuesto a demostrar que estoy equivocado. No es común por lo que puedo decir.
Bill Barth
@ Bill - Gracias, tienes razón. Estoy seguro de que he visto operaciones de división de ciclo único en chips DSP antes, así que asumí que habría llegado al escritorio, tal como lo hizo la multiplicación de ciclo único, pero ahora no puedo encontrar ninguna referencia. Sin embargo, actualicé mi respuesta y agregué información relevante sobre métodos no iterativos que podrían permitirlo en el futuro. Es sorprendente pensar que la división no es más eficiente por ciclo ahora que cuando estaba usando computadoras.
Mark Booth
1
Creo que los DSP hacen eso limitando el rango en el que son precisos. Esta es la misma estrategia utilizada para la búsqueda + interpolación para raíz cuadrada.
Matt Knepley
1
Sin embargo, no estoy seguro de cuál sería la latencia de tal división. A 4 GHz, hacer un viaje de ida y vuelta a la tabla de búsqueda dentro de N ciclos limita severamente el tamaño potencial de dicha tabla (por ejemplo, los cachés L1 se han estancado en 32K cada uno). Pasar a 3D ayudaría a aumentar esto (pero es un desafío para el enfriamiento de wrt). ¿Tiene alguna idea de qué latencia se podría alcanzar para las CPU modernas de 4GHz / 5GHz?
Matthieu M.
1
Para los números de latencia y rendimiento de divps / divpd vs. mulps / mulpd, vea División de punto flotante versus multiplicación de punto flotante . Tomé datos de las tablas de instrucciones de Agner Fog y los formateé en un resumen a través de uarches de rendimiento y latencia div y mul, para simple versus doble y para diferentes anchos de vector SIMD. (Los chips Intel generalmente tienen un divisor SIMD que es solo la mitad del ancho de las otras ALU de vector).
Peter Cordes