- En 1993, el Pentium de Intel incluía un circuito dedicado de ×3 para generar valores triplicados y acelerar la multiplicación de punto flotante, y este pequeño circuito por sí solo usaba miles de transistores
- El Pentium usa multiplicación radix-8 para reducir de 64 a 22 los términos a sumar en una multiplicación de 64 bits, pero este método requiere generar rápidamente múltiplos de ×3
- El cálculo de ×3 en sí es una suma
x + 2x, pero como el resto de las etapas de multiplicación esperan ese resultado, se necesitan técnicas de sumadores rápidos como carry lookahead y Kogge-Stone - El circuito tiene una estructura jerárquica que combina 8 bloques de 8 bits con un lookahead superior, y por overflow y redondeo la salida real se amplía a 69 bits
- Que un solo circuito de ×3 use unos 9000 transistores muestra hasta qué punto se aplicaban complejas optimizaciones de hardware para rendimiento en la generación Pentium
Por qué el Pentium tenía un circuito ×3 aparte
- El multiplicador de punto flotante del Pentium multiplica dos números de 64 bits con un esquema radix-8
- En la multiplicación binaria normal, por cada bit se suma 0 o el multiplicando, así que en una multiplicación de 64 bits se necesitan 64 términos
- El esquema radix-8 agrupa el multiplicador de 3 bits en 3 bits y multiplica por uno de los valores de 0 a 7, reduciendo los términos a sumar a 22
- Algunos de los múltiplos de 0 a 7 se pueden generar de forma relativamente simple en hardware
- ×2 se resuelve con un desplazamiento a la izquierda de 1 bit
- ×4 se resuelve con un desplazamiento a la izquierda de 2 bits
- ×6 y ×7 pueden resolverse combinando el +1 del siguiente dígito radix-8 con la resta del dígito actual mediante el algoritmo de multiplicación de Booth
- ×5 puede obtenerse restando ×3 de ×8
- Al final, el múltiplo complicado es ×3, y el Pentium lo resolvía con un circuito dedicado dentro del multiplicador de punto flotante
El punto donde una suma simple se vuelve cuello de botella
- El valor triplicado puede generarse sumando el valor de entrada y ese mismo valor desplazado un bit a la izquierda
- Estructuralmente, es la suma
x + 2x
- Estructuralmente, es la suma
- El cuello de botella aparece en la propagación de carry durante la suma
- En un sumador ripple-carry, el carry generado en los bits bajos debe propagarse secuencialmente hasta los bits altos
- Hasta que el resultado de ×3 esté listo, el resto del proceso de multiplicación no puede comenzar, así que hay que reducir la latencia
- El Pentium usa un carry-lookahead adder para calcular el carry en paralelo en vez de propagarlo secuencialmente
- En cada bit se generan señales de carry generate y carry propagate
- generate indica que esa posición produce un carry
- propagate indica que un carry entrante se transmite hacia afuera
- Si el carry se calcula en paralelo, los bits de suma también pueden calcularse en paralelo
Kogge-Stone y carry lookahead de 2 etapas
- Si el carry lookahead se implementa de forma directa y simple, la carga de circuito y cableado crece a medida que aumenta el número de bits
- La lógica se vuelve más compleja en posiciones de bit más altas
- Las compuertas con muchas entradas se vuelven lentas por razones eléctricas
- El Pentium usa un sumador de prefijo paralelo Kogge-Stone en unidades de 8 bits
- Kogge-Stone calcula el carry en paralelo combinando señales propagate/generate por rangos
- Reutiliza resultados intermedios para controlar la latencia y el tamaño del circuito
- En vez de procesar los 64 bits completos con un solo Kogge-Stone, los divide en una estructura jerárquica de 2 etapas
- La capa inferior calcula el carry dentro de cada bloque con 8 circuitos Kogge-Stone de 8 bits
- La capa superior trata cada bloque de 8 bits como una unidad y calcula el carry entre bloques
- Al combinar ambas capas, se obtiene rápidamente el carry necesario para la suma de 64 bits
- Puede verse como un circuito de 64 bits, pero en realidad genera una salida de 69 bits al incluir bits extra para evitar overflow y para redondeo
Cómo carry-select reduce el tiempo de espera
- Cada bloque de 8 bits incluye un carry-select adder
- Calcula por adelantado tanto la suma para carry-in = 0 como para carry-in = 1
- Cuando el circuito lookahead superior informa el carry-in real, un multiplexor selecciona el resultado correcto
- Este enfoque ahorra tiempo a cambio de usar más hardware
- Se necesitan dos sumadores y un multiplexor para seleccionar el resultado
- La superposición entre el cálculo de la suma y el del carry reduce la latencia total
- El bloque de 8 bits más bajo no necesita circuito carry-select porque no tiene carry-in
- Los bits de salida de este bloque se calculan con compuertas XNOR
Qué ocurre dentro de un bloque de 8 bits
- Cada bloque de 8 bits del circuito ×3 divide la línea de entrada entre el sumador izquierdo y la ruta derecha
- Esta estructura de bifurcación implementa ×3 al sumar el valor de entrada y ese valor desplazado un bit a la izquierda
- La parte superior del bloque está formada por el circuito que genera las señales propagate/generate
- Estas señales entran al circuito lookahead Kogge-Stone de 8 bits
- La parte Kogge-Stone no se ve como un bloque repetitivo y uniforme, sino irregular, porque la complejidad cambia según la posición del bit
- La parte inferior del bloque es el área del carry-select adder
- Calcula dos sumas por adelantado y el multiplexor elige según el carry-in
- Los bloques carry-select adder se colocan más angostos que el circuito circundante para dejar espacio a parte del circuito Kogge-Stone superior
- Cada bloque refuerza sus bits de salida con un circuito driver antes de enviarlos al siguiente circuito del multiplicador
Compuertas XNOR e implementación a nivel transistor
- Las compuertas XNOR de la zona de bits bajos están implementadas en el Pentium como multiplexores
- El Intel 386 implementaba XOR con compuertas AND-NOR, y el Z-80 usaba transistores de paso, pero el enfoque del Pentium era distinto
- Ese circuito XNOR está compuesto por cuatro inversores y un multiplexor con transistores de paso
- La entrada B selecciona en el multiplexor ya sea la entrada A o la A invertida
- Como resultado se obtiene la función XNOR
- En el análisis de las fotos del chip se retiraron las dos capas metálicas superiores para observar la capa metálica inferior M1 y las regiones de silicio dopado
- Los puntos donde las líneas de polisilicio cruzan el silicio dopado forman las compuertas de los transistores
- Los circuitos CMOS están compuestos por transistores NMOS en la parte superior y PMOS en la inferior
Drivers de salida BiCMOS
- La salida del circuito ×3 requiere alta corriente
- Cada señal de ×3 puede llegar a manejar hasta 22 términos dentro del multiplicador de punto flotante
- El circuito de destino puede estar lejos del circuito ×3
- El cableado largo y la gran cantidad de compuertas de transistores aumentan la capacitancia, y para cambiar la señal rápidamente se necesita mucha corriente
- El Pentium usaba un proceso BiCMOS que combinaba transistores bipolares y CMOS en el mismo chip
- El Pentium usó ampliamente circuitos BiCMOS para reducir hasta un 35% el retraso de señal
- Intel también usó BiCMOS en Pentium Pro, Pentium II, Pentium III y Xeon
- A medida que bajó el voltaje del chip, las ventajas de los transistores bipolares disminuyeron y BiCMOS terminó dejando de usarse
- El driver del circuito ×3 tiene una estructura en la que un driver BiCMOS vuelve a manejar un segundo driver BiCMOS
- Las compuertas de los transistores del inversor de alta corriente son grandes, por lo que se necesita una etapa intermedia para manejarlas
- Amplificar una señal pequeña en varias etapas puede reducir la latencia total
- El transistor NPN del driver BiCMOS se ve como una gran caja, a diferencia de un transistor MOS normal
- El inversor usa la estructura CMOS estándar, elevando la salida con PMOS y bajándola con NMOS
- Algunos inversores están diseñados con características de corriente asimétricas para producir una salida fuertemente alta o fuertemente baja
La complejidad creciente que muestra el hardware de multiplicación
- La historia del hardware de multiplicación en computadoras se remonta a la década de 1950
- La técnica de multiplicación de Booth fue descrita en 1951
- Los multiplicadores paralelos fueron propuestos a mediados de la década de 1960 por Wallace y Dadda
- Los primeros microprocesadores tenían soporte de multiplicación por hardware limitado
- Procesadores como el 6502 no tenían hardware de multiplicación, así que el usuario debía implementarla por software con desplazamientos y sumas
- El Intel 8086 ejecutaba un lento bucle shift-and-add mediante microcódigo
- El 386 incluía una unidad de multiplicación, pero la instrucción de multiplicación podía tardar hasta 41 ciclos de reloj
- Para la época del Pentium, ya se podían integrar millones de transistores y eso permitió optimizaciones de rendimiento mucho más complejas
- La multiplicación de punto flotante del Pentium tarda 3 ciclos de reloj, y el circuito de multiplicación se usa durante 2 de esos ciclos
- La multiplicación entera
MULes mucho más lenta, con 11 ciclos - La microarquitectura Nehalem de 2008 redujo la multiplicación de punto flotante a 1 ciclo
- El multiplicador ×3 del Pentium incluye alrededor de 9000 transistores
- Eso es un poco más que todo el microprocesador Z80 de 1976
- El circuito ×3 es solo una pequeña parte del multiplicador de punto flotante dentro de la unidad de punto flotante del Pentium
1 comentarios
Opiniones de Hacker News
Es una tangente, pero hace mucho, mientras trabajaba en una emulación de computadora ternaria, usé un truco simpático para encontrar una transformación de forma cerrada que convierte la división por potencias de 3 en una serie de corrimientos de bits y sumas.
Primero basta con ver que
1/3 - 1/2 = 2/6 - 3/6, es decir,1/3 = 1/2 - 1/2 (1/3).Si sustituyes esta expresión infinitamente en el lado derecho, aparece una forma
1/3 = -(-1/2)^N, conNen el rango1..inf.Se puede hacer algo parecido no solo con pares de potencias de 2 y 3, sino también en otras bases.
Lo que significa es que, para valores cercanos a potencias de 2, se pueden construir con bastante facilidad circuitos de división constante en tiempo fijo usando solo sumadores y restadores.
El procesador de los juegos arcade de Cinematronics tiene dos acumuladores de 12 bits.
La instrucción de multiplicación desplaza ambos a la derecha como si fueran un único valor de 24 bits, y si sale un 1 en el bit menos significativo, suma el contenido de memoria.
Así que se limpia la mitad superior, se carga un valor en la mitad inferior y, aunque ya no recuerdo cómo se configuraba la dirección de memoria del otro operando, se ejecuta la multiplicación de 1 bit varias veces seguidas.
De esta forma se puede obtener un producto de 24 bits, pero la mayoría del código que vi encadenaba 8 multiplicaciones, y el uso más común era la multiplicación de matrices 2x2 para rotar coordenadas de objetos del juego.
Estaba hecho con componentes 7400 estándar de mediados de los años 70, y su rendimiento máximo era de 5 MIPS.
En los últimos 20 años tuve que hacer operaciones de punto fijo algunas veces, y mi respeto por los programadores de generaciones anteriores aumentó.
En relación con la parte de que quizá hayas oído hablar de técnicas como
carry lookaheadyKogge-Stone addition, aquí Kogge es Peter Kogge.Hizo su doctorado en Stanford, trabajó en temas relacionados con el transbordador espacial, es IBM Fellow y es la persona que inventó el primer CPU multinúcleo.
“CPU multinúcleo” en sí, estrictamente hablando, es más una idea que una invención. En cierto punto de la historia de los semiconductores, además, es una idea bastante obvia y trivial.
Hacer que un CPU multinúcleo funcione en la práctica no es trivial, pero eso tampoco es una sola invención; para ese momento los equipos de desarrollo ya eran tan grandes que decir que una sola persona resolvió todos los problemas por su cuenta resulta más bien insultante.
Puede que Kogge haya liderado el desarrollo del primer CPU multinúcleo, y puede que haya sido un pionero que lo impulsó antes de que otros lo vieran posible, pero en cualquier caso no lo inventó él solo.
Este enfoque es intelectualmente bastante convincente. Si mover los datos al cómputo central tiene latencia o costo, tiene sentido; en nuestro caso, como eran sensores espaciales, se podía construir ese argumento.
Sin embargo, hasta donde sé, este tipo de procesamiento nunca se adoptó de forma sistemática en sistemas de procesamiento espaciales, aunque muchos sistemas, como los de radar, sí hacen reducciones de datos ad hoc en hardware cercano al sensor.
Gracias por señalar esa conexión.
Soy el autor. Si tienen preguntas, las respondo.
x4dex7para obtenerx3?Creo que falta algo.
Si ×2 es tan fácil de calcular como para poder usar 6x = 8x - 2x, y ×4 también es fácil de calcular como 4x = 4x, no entiendo por qué calcular 3x como la suma de 2x + 1x, o como la diferencia 4x - 1x, sería más difícil que eso.
También me pregunto: si ×6 se puede calcular fácilmente de alguna manera, ¿por qué no desplazar ese valor a la derecha para obtener ×3? Sería un paso adicional, pero ese paso adicional es un corrimiento.
Cada término debe ser trivial de calcular, así que para obtener un término puedes desplazar o invertir el signo, pero no puedes hacer otra suma.
La clave es que, si calculas ×3 una vez de antemano, después puedes insertarlo donde haga falta entre los 22 términos.
No puedes construir ×3 dentro de un término poniendo ×2 y ×1. Para eso necesitarías otro sumador en cada término.
En otras palabras, lo que quieres es un solo circuito que calcule ×3, no 22 circuitos.
Sobre la pregunta de ×6, ese valor se calcula poniendo un ×2 negativo en el término y, conceptualmente, sumando 1 al siguiente dígito para obtener ×8. Ese ×8 forma parte de un término completamente distinto, así que no se puede desplazar a la derecha.
Con tantos números y sumas yendo de un lado a otro se vuelve complicado, pero visto así debería tener sentido.
La multiplicación por 3 en realidad es una operación común, especialmente en el cálculo de direcciones, donde muchas veces se multiplica un índice por 3 usando desplazamientos y sumas
Si se implementa de forma ingenua, la latencia aumenta bastante. Pero con este circuito, la instrucción LEA (Load Effective Address) puede procesarse en un ciclo, así que gastar ese presupuesto de transistores ahí era una decisión bastante buena
LEA es simplemente una instrucción que pone la dirección calculada por el modo de direccionamiento en el operando de salida, en vez de mover datos desde esa dirección, y todos los cálculos de dirección que puede hacer LEA también los puede hacer la instrucción MOV
En x86, el direccionamiento con índice que usan MOV o LEA no admite un factor de escala 3; solo admite potencias de 2 como 1, 2, 4 y 8. Así que no hay dónde usar una multiplicación por 3 en la generación de direcciones
El artículo deja claro que el multiplicador por 3 es parte del multiplicador de punto flotante
“Este multiplicador ×3 contiene aproximadamente 9000 transistores, un poco más que todo el microprocesador Z80 (1976). Hay que recordar que el multiplicador ×3 es una pequeña parte del multiplicador de punto flotante dentro de la unidad de punto flotante del Pentium. Es decir, una pequeña pieza de una función es más compleja que un microprocesador completo de 17 años antes, lo que muestra cuánto aumentó enormemente la complejidad de los procesadores.”
Este ritmo de crecimiento del rendimiento dio origen a la hinchazón del software actual. Porque las mejoras de rendimiento del año siguiente podían tapar en gran medida el pecado de no pensar críticamente en los algoritmos y en el contexto y la localidad del flujo de datos
Hoy, por lo que he leído, ya llegamos a los límites prácticos de lo que se puede hacer razonablemente con la tecnología de semiconductores de silicio y la comprensión actual de la física. Ahora el péndulo tiene que moverse en sentido contrario, y las computadoras deben trabajar más inteligentemente, no con más fuerza
Aunque creo que la hinchazón del software está creciendo todavía más rápido
goto/jmp→ búsqueda en vtable → hash y búsqueda en un diccionario → ejecutar un modelo de lenguaje grande“En lugar de multiplicar por 7, se suma 8 veces el número y luego se resta el número para obtener 7 veces. Podría parecer que hacen falta dos pasos, pero se obtiene el coeficiente 8 sin un paso adicional mediante el truco de multiplicar por 1 más en la posición de la izquierda.”
¿Esto significa que hay un sumador que agrega 1 a la “siguiente posición” antes de poner el número en la parte principal del multiplicador? Eso en sí también se parece a un circuito de predicción de acarreo
También me hace pensar en cuándo se necesita esto:
7 = 8-1,6 = 8-2,5 = 8-3,4 = 8-4En el último caso, aunque el artículo no dice que lo haga, si se usa el bit más significativo del valor de 3 bits para decidir si hay que sumar 1 a la siguiente posición, parece que se podrían ahorrar unas cuantas compuertas
Es interesante que hayan elegido un multiplicador Booth de radix 8 que necesita el circuito ×3. Parece un compromiso de área/rendimiento para subir la frecuencia máxima, y como lo mismo podría haberse logrado con más pipeline, parece que había una restricción en los ciclos de latencia
El pipeline es complicado, porque no hay un buen punto donde dividir en dos el arreglo de multiplicación
https://github.com/EI2030/Low-power-E-Paper-OS/blob/master/P...
8086: 29,000
386: 275,000
486: 1.2 millones
Pentium: 3.1 millones
Por lo que recuerdo, la NSA entró en este juego en algún momento después del año 2000