En informática , el sumador de Kogge-Stone ( KSA o KS ) es un sumador de avance de forma de prefijo paralelo . Otros sumadores de prefijos paralelos (PPA) incluyen el sumador de Brent-Kung (BKA), [1] el sumador de Han-Carlson (HCA), [2] [3] y la variación más rápida conocida, el sumador de árbol de expansión de Lynch-Swartzlander (STA ). [4] [5]
El sumador Kogge-Stone requiere más área para implementar que el sumador Brent-Kung, pero tiene un abanico menor en cada etapa, lo que aumenta el rendimiento de los nodos de proceso CMOS típicos. Sin embargo, la congestión del cableado suele ser un problema para los sumadores de Kogge-Stone. El diseño de Lynch-Swartzlander es más pequeño, tiene un abanico más bajo y no sufre de congestión en el cableado; sin embargo, para ser utilizado, el nodo de proceso debe admitir implementaciones de cadena de transporte de Manchester . El problema general de optimizar sumadores de prefijos paralelos es idéntico al problema de optimización de sumadores de acarreo y salto de tamaño de bloque variable, multinivel, cuya solución se encuentra en la tesis de Thomas Lynch de 1996. [5]
En el diagrama se muestra un ejemplo de un sumador Kogge-Stone de 4 bits. Cada etapa vertical produce un bit de "propagación" y un bit de "generación", como se muestra. Los bits de generación culminantes (los acarreos ) se producen en la última etapa (verticalmente), y estos bits son XOR 'd con la propagación inicial después de la entrada (las cajas rojas) para producir los bits de suma. Por ejemplo, el primer bit de suma (el menos significativo) se calcula aplicando un XOR al propagado en el cuadro rojo más a la derecha (un "1") con el arrastre (un "0"), produciendo un "1". El segundo bit se calcula XORing la propagación en el segundo cuadro desde la derecha (un "0") con C0 (un "0"), produciendo un "0".
El concepto de sumador de Kogge-Stone fue desarrollado por Peter M. Kogge y Harold S. Stone , quienes lo publicaron en un artículo seminal de 1973 titulado A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations . [6]
Mejoras
Las mejoras a la implementación original incluyen el aumento de la base y la dispersión del sumador. La base del sumador se refiere a cuántos resultados del nivel de cálculo anterior se utilizan para generar el siguiente. La implementación original usa radix-2, aunque es posible crear radix-4 y superior. Hacerlo aumenta la potencia y el retraso de cada etapa, pero reduce el número de etapas requeridas. En el llamado sumador disperso de Kogge-Stone ( SKA ), la escasez del sumador se refiere a la cantidad de bits de acarreo generados por el árbol de acarreo. La generación de cada bit de acarreo se llama sparsity-1, mientras que la generación de todos los demás es sparsity-2 y cada cuarto es sparsity-4. Los acarreos resultantes se utilizan luego como entradas de acarreo para sumadores de acarreo de ondulación mucho más cortos o algún otro diseño de sumador, que genera los bits de suma final. El aumento de la dispersión reduce el cálculo total necesario y puede reducir la cantidad de congestión de enrutamiento.
Arriba hay un ejemplo de una sumadora de Kogge-Stone con escasez-4. Los elementos eliminados por escasez se muestran marcados con transparencia. Como se muestra, la potencia y el área de la generación de acarreo se mejoran significativamente y la congestión del enrutamiento se reduce sustancialmente. Cada acarreo generado alimenta un multiplexor para un sumador de acarreo de selección o el acarreo de un sumador de acarreo de ondulación.
Expansión
Este ejemplo es un avance: en un sumador de 4 bits como el que se muestra en la imagen introductoria de este artículo, hay 5 salidas. A continuación se muestra la expansión:
S0 = (A0 XOR B0) XOR CinS1 = (A1 XOR B1) XOR ((A0 Y B0) O ((A0 XOR B0) Y Cin))S2 = (A2 XOR B2) XOR ((A1 Y B1) O ((A1 XOR B1) Y (A0 Y B0)) O ((A1 XOR B1) Y (A0 XOR B0) Y Cin))S3 = (A3 XOR B3) XOR ((A2 Y B2) O ((A2 XOR B2) Y (A1 Y B1)) O ((A2 XOR B2) Y (A1 XOR B1) Y (A0 Y B0)) O ((A2 XOR B2) Y (A1 XOR B1) Y (A0 XOR B0) Y Cin))Cout = (A3 Y B3) O ((A3 XOR B3) Y (A2 Y B2)) O ((A3 XOR B3) Y (A2 XOR B2) Y (A1 Y B1)) O ((A3 XOR B3) Y (A2 XOR B2) Y (A1 XOR B1) Y (A0 Y B0)) O ((A3 XOR B3) Y (A2 XOR B2) Y (A1 XOR B1) Y (A0 XOR B0) Y Cin)
Referencias
- ^ Brent, Richard Peirce ; Kung, Hsiang Te (marzo de 1982). "Un diseño regular para sumadores paralelos" . Transacciones IEEE en computadoras . C-31 (3): 260–264. doi : 10.1109 / TC.1982.1675982 . ISSN 0018-9340 .
- ^ Han, Tackdon; Carlson, David A .; Levitan, Steven P. (octubre de 1982). "Diseño VLSI de circuitos de adición de área baja y alta velocidad" . Proceedings 1981 IEEE International Conference on Computer Design: VLSI in Computers & Processors . IEEE : 418–422. ISBN 0-81860802-1.
- ^ Han, Tackdon; Carlson, David A. (octubre de 1987). "Sumadores VLSI rápidos de área eficiente". Actas del 8º Simposio de Aritmética Informática . IEEE : 49–56.
- ^ Lynch, Thomas Walker; Swartzlander, Jr., Earl E. (agosto de 1992). "Un árbol de expansión lleva una víbora anticipada". Transacciones IEEE en computadoras . 41 (8): 931–939. doi : 10.1109 / 12.156535 .
- ^ a b Lynch, Thomas Walker (mayo de 1996). "Sumadores binarios" (Tesis). Universidad de Texas . Archivado (PDF) desde el original el 14 de abril de 2018 . Consultado el 14 de abril de 2018 .
- ^ Kogge, Peter Michael ; Stone, Harold S. (agosto de 1973). "Un algoritmo paralelo para la solución eficiente de una clase general de ecuaciones de recurrencia". Transacciones IEEE en computadoras . C-22 (8): 786–793. doi : 10.1109 / TC.1973.5009159 .
Otras lecturas
- Zeydel, Bart R. (2006). "Características de retardo de energía de sumadores CMOS". En Oklobdzija, Vojin G .; Krishnamurth, Ram K. (eds.). Diseño de microprocesador de alto rendimiento energéticamente eficiente . Serie sobre circuitos y sistemas integrados. Dordrecht, Holanda: Springer . págs. 147-169. doi : 10.1007 / 978-0-387-34047-0_6 . ISBN 0-387-28594-6.