¿Las computadoras realmente usan sumadores de anticipación?

12

Hay muchos detalles sobre los cargadores de anticipación como Kogge-Stone, Lander-Fischer, etc. en los cursos universitarios de CS. Se describen como "comunes en la industria". Sin embargo, no puedo encontrar ninguna evidencia (aparte de quizás la cadena de transporte de Manchester) de los últimos tiempos de que realmente se usen en cualquier lugar específicamente. Una búsqueda en Google solo devuelve páginas de revistas e investigaciones académicas. A lo sumo, se dan implementaciones hipotéticas.

Mi pregunta es, ¿hay lugares / implementaciones específicas que se utilizan sumadores de anticipación? ¿O son irrelevantes para el mundo real?

qwr
fuente
1
El tiempo de ciclo de los procesadores de alto rendimiento y su ciclo único agregan latencia sin duda apunta a que no usan Ripple-carry (pero esto permitiría la selección de acarreo). Incluso para el proceso de 22nm de Intel, la ondulación a través de 64 bits en menos de 300ps podría ser improbable.
Paul A. Clayton el
@ PaulA.Clayton Tengo la impresión de mirar a través de algunas hojas de datos que se utilizan los adders de selección de portador o decodificador.
qwr

Respuestas:

16

Esta es una pregunta sencilla con una respuesta muy compleja.

En primer lugar, algunos antecedentes.

El diseño VLSI del mundo real es un campo extremadamente técnico que presenta un equilibrio de compensaciones en constante cambio. El tiempo que toma un circuito para calcular una respuesta rara vez es el único factor importante. También hay consumo de energía y área física, además de un montón de factores que revelan que los circuitos que está diseñando son en realidad analógicos (por ejemplo, resistencia de cables, capacitancia parásita). Todos estos son importantes en un circuito real y pueden afectar el diseño elegido.

En segundo lugar, debe considerar todo el ciclo de vida de un proyecto. Un sumador que sea apropiado para una realización VLSI puede no ser apropiado para una realización FPGA. Si el diseño va a pasar por una fase que se está probando en un FPGA ... obtendrá la imagen.

En tercer lugar, no todos los sumadores son iguales. En una CPU típica, hay muchos sumadores que realizan tareas diferentes; Probablemente hay varias ALU enteras, un sumador de mantisa de coma flotante, un sumador que hace el cálculo de dirección, un sumador que calcula los objetivos de las ramas, y así sucesivamente. Eso no cuenta los sumadores carry-save que encuentras en las unidades de multiplicación modernas. Cada uno tiene sus propias peculiaridades y limitaciones.

El cálculo del objetivo de la rama, por ejemplo, generalmente implica agregar una pequeña constante a una palabra completa, lo que sugiere un diseño de sumador diferente de uno que agrega dos palabras completas juntas. Del mismo modo, la adición de punto flotante requiere un paso de redondeo posterior a la adición que puede tomar menos de un ciclo, por lo que no hay razón por la que no pueda robar el resto del ciclo para finalizar la adición.

Por último, y quizás lo más importante, los grandes jugadores (por ejemplo, Intel, AMD, NVIDIA) son bastante discretos sobre los detalles de implementación de bajo nivel por razones obvias, a menos que piensen que pueden obtener un documento y / o una patente. Incluso entonces, a menudo no puede estar seguro de lo que realmente hicieron sin ingeniería inversa.

Dicho esto, hay algunas cosas que sabemos.

La clave que debe tener en cuenta es que los métodos de anticipación son elementos básicos y no necesariamente métodos en sí mismos. Una analogía podría estar en orden aquí.

Si piensa en las clases de algoritmos, probablemente haya aprendido un montón de algoritmos de ordenación, como la ordenación rápida, la fusión, la inserción, etc. En el mundo real, si la clasificación es un cuello de botella en el rendimiento, cualquier ingeniero decente pensaría en estos como bloques de construcción primitivos a partir de los cuales se puede construir una clasificación "real".

El algoritmo de ordenamiento de la biblioteca estándar GNU C ++, por ejemplo, usa ordenamiento rápido, usando ordenamiento por inserción cuando los intervalos se vuelven lo suficientemente pequeños. Sin embargo, si después de algunos pases parece que la partición de clasificación rápida ha afectado el comportamiento patológico, vuelve a la clasificación de montón. Son tres algoritmos de clasificación diferentes para hacer una clasificación de fuerza industrial.

Lo mismo se aplica a los circuitos sumadores. Se sabe, por ejemplo, que la unidad entera Pentium 4 usaba un sumador Han-Carlson, que es una mezcla de Kogge-Stone y Brent-Kung. (Han-Carlson es especialmente interesante, porque es un "punto óptimo" en la compensación entre el retraso de propagación y el área de la matriz, que también es bastante eficiente en términos de energía). A menudo vale la pena usar una combinación de varios métodos.

Los sumadores "puros" de búsqueda anticipada siguen siendo la norma en los circuitos sintetizados (p. Ej., Si suministra un operador Verilog "+" a Cadence o Synopsys), cuando se trata de diseño manual, CPU modernas de alta gama con su superescalar- Los motores de ejecución de orden parecen moverse hacia un diseño ligeramente diferente para sus unidades enteras.

Los sumadores especulativos son circuitos que tienen un retardo de propagación extremadamente bajo, pero solo funcionan correctamente algunas veces (el 95% del tiempo es típico), y es posible decir con muy poca lógica si el sumador especulativo devuelve el resultado correcto o no. Entonces, la idea es hacer una adición especulativa y la mitad de una adición de anticipación en paralelo, en un ciclo. Si el sumador especulativo devolvió la respuesta correcta, la instrucción está hecha. De lo contrario, detenga la tubería y realice la otra mitad de la adición precisa.

Debido a que sabe que el camino lento tomará dos ciclos, los diseñadores podrían usar un método más eficiente en términos de espacio y energía incluso si fuera demasiado lento para el uso general.

Seudónimo
fuente
6

Sí, muchas computadoras usan sumadores de anticipación. Realicé ingeniería inversa de algunos microprocesadores antiguos y puedo dar algunos ejemplos.

La ALU en el Intel 8008 (su primer procesador de 8 bits) incluía un gran circuito de anticipación implementado con lógica dinámica. Este circuito ocupaba casi tanto espacio de matriz como la propia ALU. Carry lookahead se muestra en la hoja de datos 8008 , figura 3. No he visto ningún otro procesador de 1970 con carry-lookahead para la ALU, por lo que el 8008 es un poco inusual en este sentido.

El 6502 utiliza el primitivo carry-lookahead para el contador del programa (PC). Detecta si habrá una transferencia desde el byte inferior de la PC y la utiliza para incrementar el byte superior. Esto reduce el transporte de ondas de potencialmente 16 bits a 8 bits. La ALU del 6502 usa el transporte de ondulación, aunque la lógica de transporte se invierte para bits alternos, lo que corta un inversor del camino y lo hace un poco más rápido.

El Z-80 tiene un incrementador / decrementador de 16 bits utilizado para actualizaciones de PC, instrucciones de inc / dec, y un contador de bucle. Utiliza una estructura carry-skip, por lo que los carry se calculan para grupos de dos bits. Además, utiliza algo de anticipación para generar el acarreo de los bits 0-7, 7-11 y 12-14. Otros transportes se calculan con Ripple carry ( detalles ). La ALU del Z-80, sorprendentemente, es de 4 bits, por lo que cada operación de 8 bits hace dos pasadas a través de la ALU.

El 8085, por otro lado, utiliza el transporte de ondulación para su incrementador / decrementador de 16 bits. Pero como el 6502, se acelera un poco al invertir la lógica de transporte en bits alternos.

El ARM-1 tiene una ALU de 32 bits sin adelanto de transporte, solo transporte de ondulación. También utiliza el truco de invertir el carry en bits alternos.

En el mundo de las minicomputadoras, muchos procesadores se construyeron a partir del conocido chip ALU de 4 bits 74181, que tenía un control interno interno. Los ejemplos incluyen el Data General Nova, el Xerox Alto, el VAX-11/780 y el TI-990. (Vea la lista más larga de Wikipedia ). Algunos de estos utilizan el ripple carry entre cada chip de 4 bits y algunos usan el 74182 carry lookahead chip para el lookahead completo.

Para resumir, los diferentes microprocesadores utilizan una variedad de técnicas de transporte según sus objetivos de rendimiento y qué operaciones se encuentran en la ruta crítica. La ALU puede usar un look-lookahead completo (como el 8008) o incluso puede ser de tamaño medio (como el Z-80). El incrementador puede ser un problema de rendimiento porque generalmente es de 16 bits en un procesador de 8 bits, lo que resulta en el doble del retraso de ondulación. El incrementador puede tener transporte de ondulación (8085), una carga anticipada (6502) o varias etapas de anticipación (Z-80).

Ken Shirriff
fuente