stringtranslate.com

Víbora de piedra de Kogge

Gráfico del generador de acarreo de un sumador Kogge-Stone de 4 bits con acarreo de entrada cero, base 2, valencia 2.

En informática , el sumador Kogge-Stone ( KSA o KS ) es una forma de prefijo paralelo del sumador de acarreo anticipado . Otros sumadores de prefijo paralelo (PPA) incluyen el sumador Sklansky (SA), [1] el sumador Brent-Kung (BKA), [2] el sumador Han-Carlson (HCA), [3] [4] la variación más rápida conocida, el sumador de árbol de expansión Lynch-Swartzlander (STA), [5] [6] el sumador Knowles (KNA) [7] y el sumador Beaumont-Smith (BSA) (como el sumador Sklansky (SA), de base 4). [8]

El sumador Kogge-Stone requiere más área para implementarse que el sumador Brent-Kung, pero tiene un menor abanico de salida 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 Kogge-Stone. El diseño Lynch-Swartzlander es más pequeño, tiene un abanico de salida menor y no sufre de congestión del cableado; sin embargo, para poder usarse, el nodo de proceso debe admitir implementaciones de cadena de acarreo Manchester . El problema general de optimizar los sumadores de prefijo paralelo es idéntico al problema de optimización de sumadores de acarreo-salto de múltiples niveles y tamaño de bloque variable , una solución del cual se encuentra en la tesis de Thomas Lynch de 1996. [6]

Diseño

Al igual que todos los sumadores de acarreo con anticipación, el sumador Kogge-Stone realiza un seguimiento interno de los bits de "generación" y "propagación" para intervalos de bits. Comenzamos con intervalos de 1 bit, donde una sola columna en la suma genera un bit de acarreo si ambas entradas son 1 ( AND lógico ) y propaga un bit de acarreo si exactamente una entrada es 1 ( XOR lógico ). Luego, los intervalos adyacentes se fusionan para producir bits de generación y propagación para intervalos más amplios.

La fusión continúa hasta que se conocen los bits de generación para todos los intervalos que terminan en el bit menos significativo, momento en el cual estos pueden usarse como entradas de acarreo para calcular todos los bits de suma en paralelo.

La diferencia entre los distintos diseños de sumadores con acarreo anticipado radica en cómo se lleva a cabo la fusión de tramos. La mayoría de los diseños utilizan etapas de log 2 n , duplicando el ancho de los tramos fusionados en cada etapa, pero difieren en cómo se dividen en subtramos los tramos que no son una potencia de dos en tamaño. El diseño de Kogge-Stone trunca los tramos menos significativos y siempre utiliza tramos más significativos de ancho completo.

Comenzando con los intervalos de 1 bit, todos los intervalos adyacentes se fusionan para producir intervalos de 2 bits. El intervalo menos significativo se trata de manera especial: se fusiona con el acarreo en la adición y solo produce un bit de generación, ya que no es posible la propagación. En la siguiente etapa, cada intervalo de 2 bits de ancho se fusiona con el intervalo de 2 bits anterior para producir un intervalo de 4 bits. Esto es con la excepción de los tres intervalos menos significativos. El intervalo menos significativo ya se ha calculado, mientras que los dos siguientes se fusionan con el acarreo y el intervalo menos significativo calculado anteriormente respectivamente, produciendo bits de generación para intervalos de 3 y 4 bits, incluido el acarreo.

Este proceso se repite, duplicando los anchos de los tramos en cada etapa y con un cálculo simplificado de los tramos menos significativos, hasta que se conocen todos los bits de generación deseados.

Dado que cada tramo se fusiona con, como máximo, otros dos tramos en la siguiente etapa (uno más significativo y uno menos significativo), la distribución en abanico es mínima. Sin embargo, hay una congestión de cableado significativa; en la segunda última etapa de un sumador de 64 bits, la mitad más significativa de los tramos que se fusionarán requiere señales de generación y propagación independientes de tramos a 16 bits de distancia, lo que requiere 32 cables horizontales a través del sumador. La etapa final es similar; aunque solo se necesitan bits de generación, se requieren 32 de ellos para cruzar el sumador.

Ejemplos

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 se combinan con el bit de propagación inicial después de la entrada (los cuadros rojos) para producir los bits de suma. Por ejemplo, el primer bit de suma (el menos significativo) se calcula combinando el bit de propagación en el cuadro rojo más a la derecha (un "1") con el acarreo de entrada (un "0"), lo que produce un "1". El segundo bit se calcula combinando el bit de propagación en el segundo cuadro desde la derecha (un "0") con C0 (un "0"), lo que produce un "0".

Binario, base 2, 4 bits

Sumador Kogge-Stone de 4 bits, base 2, sin Cin en Borland Turbo Basic 1.1 :

'--- Paso=0 --------------------------------------------P00 = A0 XOR B0 '1dt, dt - tiempo de retardoG00 = A0 Y B0 '1dtP01 = A1 O B1 '1dtG01 = A1 Y B1 '1dtP02 = A2 O B2 '1dtG02 = A2 Y B2 '1dtP03 = A3 O B3 '1dtG03 = A3 Y B3 '1dt'--- Paso=1, Valencia-2, Distancia=Radix^(Paso-1)=2^0G10 = G00 '1dtG11 = G01 O (P01 Y G00) '3dt Distancia=2^0=1P12 = P02 Y P01 '2dt Distancia=2^0=1G12 = G02 O (P02 Y G01) '3dt Distancia=2^0=1' 1 día 1 día 1 díaP13 = P03 Y P02 '2dt Distancia=2^0=1G13 = G03 O (P03 Y G02) '3dt Distancia=2^0=1' 1 día 1 día 1 día'--- Paso=2, Valencia-2, Distancia=Radix^(Paso-1)=2^1=2G20 = G10 '1dt, C1G21 = G11 '3dt, C2G22 = G12 O (P12 Y G10) '4dt, C3 Distancia=2^1=2' 3dt 2dt 1dtG23 = G13 O (P13 Y G11) '5dt, C4 Distancia=2^1=2' 3dt 2dt 3dt'--- Suma ------------------------------S0 = P00 '1dtS1 = P01 O G20 '2dtS2 = P02 O G21 '4dtS3 = P03 XOR G22 ' 5dt
S4 = G23 ' 5dt . S4=C4=Cout [9]

Binario, base 2, 4 bits, con Cin

Sumador Kogge-Stone de 4 bits, base 2, con Cin:

'--- Paso Pre -------------------G0a = A0 Y Cin '1dtG0b = B0 Y Cin '1dtG0c = A0 Y B0 '1dt'--- Paso 0 ---------------------P00 = A0 O B0 '1dtG00 = G0a O G0b O G0c '2dtP01 = A1 O B1 '1dtG01 = A1 Y B1 '1dtP02 = A2 O B2 '1dtG02 = A2 Y B2 '1dtP03 = A3 O B3 '1dtG03 = A3 Y B3 '1dt'--- Paso 1 ---------------------G10 = G00 '2dtG11 = G01 O P01 Y G00 '4dtP12 = P02 Y P01 '2dtG12 = G02 O P02 Y G01 '3dtP13 = P03 Y P02 '2dtG13 = G03 O P03 Y G02 '3dt'--- Paso 2 -------------------------G20 = G10 '2dt, C1G21 = G11 '4dt, C2G22 = G12 O P12 Y G00 '5dt, C3G23 = G13 O P13 Y G11 '6dt, C4'--- Suma ------------------------S0 = P00 XOR Cin '2dtS1 = P01 O G20 '3dtS2 = P02 O G21 '5dtS3 = P03 XOR G22 ' 6dt
S4 = G23 ' 6dt , S4=C4=Cout

Binario, base 2, 8 bits

Sumador Kogge-Stone de 8 bits, base 2, valencia 2:

'---Paso 0 ---------------------P00 = A0 O B0 '1dtG00 = A0 Y B0 '1dtP01 = A1 O B1 '1dtG01 = A1 Y B1 '1dtP02 = A2 O B2 '1dtG02 = A2 Y B2 '1dtP03 = A3 O B3 '1dtG03 = A3 Y B3 '1dtP04 = A4 O B4 '1dtG04 = A4 Y B4 '1dtP05 = A5 O B5 '1dtG05 = A5 Y B5 '1dtP06 = A6 O B6 '1dtG06 = A6 Y B6 '1dtP07 = A7 O B7 '1dtG07 = A7 Y B7 '1dt'--- Paso 1, Distancia=2^0=1 --------G10 = G00 '1dtG11 = G01 O (P01 Y G00) '3dtP12 = P02 Y P01 '2dtG12 = G02 O (P02 Y G01) '3dtP13 = P03 Y P02 '2dtG13 = G03 O (P03 Y G02) '3dtP14 = P04 Y P03 '2dtG14 = G04 O (P04 Y G03) '3dtP15 = P05 Y P04 '2dtG15 = G05 O (P05 Y G04) '3dtP16 = P06 Y P05 '2dtG16 = G06 O (P06 Y G05) '3dtP17 = P07 Y P06 '2dtG17 = G07 O (P07 Y G06) '3dt'--- Paso 2, Distancia=2^1=2 ----G20 = G10 '1dtG21 = G11 '3dtG22 = G12 O (P12 Y G10) '4dt' 3dt 2dt 1dtG23 = G13 O (P13 Y G11) '5dt' 3dt 2dt 3dtP24 = P14 Y P12 '3dtG24 = G14 O (P14 Y G12) '5dt' 3dt 2dt 3dtP25 = P15 Y P13 '3dtG25 = G15 O (P15 Y G13) '5dt' 3dt 2dt 3dtP26 = P16 Y P14 '3dtG26 = G16 O (P16 Y G14) '5dt' 3dt 2dt 3dtP27 = P17 Y P15 '3dtG27 = G17 O (P17 Y G15) '5dt' 3dt 2dt 3dt'--- Paso 3, Distancia=2^2=4 --------G30 = G20 '1dt, C1G31 = G21 '3dt, C2G32 = G22 '4dt, C3G33 = G23 '5dt, C4G34 = G24 O (P24 Y G20) '6dt, C5' 5dt 3dt 1dtG35 = G25 O (P25 Y G21) '6dt, C6' 5dt 3dt 3dtG36 = G26 O (P26 Y G22) '6dt, C7' 5dt 3dt 4dtG37 = G27 O (P27 Y G23) '7dt, C8' 5dt 3dt 5dt'---Suma ------------------------S0 = P00 '1dtS1 = P01 O G30 ​​'2dtS2 = P02 O G31 '4dtS3 = P03 O G32 '5dtS4 = P04 O G33 '6dtS5 = P05 O G34 '7dtS6 = P06 O G35 '7dtS7 = P07 XOR G36 ' 7dt
S8 = G37 ' 7dt , S8=C8=Cout [10]

Binario, base 4, 4 bits

Sumador PPA de 4 bits de base 4 (valencia 2,3,4) (es un sumador CLA de 4 bits de base 4 (valencia 2,3,4) y un sumador Sklansky de 4 bits de base 4 (valencia 2,3,4) y un sumador Kogge-Stone de 4 bits de base 4 (valencia 2,3,4) y un sumador Beaumont-Smith de 4 bits de base 4 (valencia 2,3,4)):

'--- Paso 0 ----------P00 = A0 O B0 '1dtG00 = A0 Y B0 '1dtP01 = A1 O B1 '1dtG01 = A1 Y B1 '1dtP02 = A2 O B2 '1dtG02 = A2 Y B2 '1dtP03 = A3 O B3 '1dtG03 = A3 Y B3 '1dt'--- Paso 1 --------------------------------------------------------G10 = G00 '1dt, C1, valencia-1, distancia-0G11 = G01 O_ P01 Y G00 '3dt, C2, valencia-2, distancia-0,1G12 = G02 O_ P02 Y G01 O_ P02 Y P01 Y G00 '3dt, C3, valencia-3, distancia-0,1,2G13 = G03 O_ P03 Y G02 O_ P03 Y P02 Y G01 O_ P03 Y P02 Y P01 Y G00 '3dt, C4, valencia-4, distancia-0,1,2,3'--- Suma ------------------------------------S0 = P00 '1dtS1 = P01 O G10 '2dtS2 = P02 O G11 '4dtS3 = P03 XOR G12 ' 4dt
S4 = G13 ' 3dt , S4=C4=Cout [11]

Binario, base 4, 8 bits

Sumador Kogge-Stone de 8 bits, base 4, valencia 2,3,4:

'--- Paso 0 -----------P00 = A0 O B0 '1dtG00 = A0 Y B0 '1dtP01 = A1 O B1 '1dtG01 = A1 Y B1 '1dtP02 = A2 O B2 '1dtG02 = A2 Y B2 '1dtP03 = A3 O B3 '1dtG03 = A3 Y B3 '1dtP04 = A4 O B4 '1dtG04 = A4 Y B4 '1dtP05 = A5 O B5 '1dtG05 = A5 Y B5 '1dtP06 = A6 O B6 '1dtG06 = A6 Y B6 '1dtP07 = A7 O B7 '1dtG07 = A7 Y B7 '1dt'--- Paso 1 ---------------------------G10 = G00 '1dtG11 = G01 O_ P01 Y G00 '3dtG12 = G02 O_ P02 Y G01 O_ P02 Y P01 Y G00 '3dtG13 = G03 O_ P03 Y G02 O_ P03 Y P02 Y G01 O_ P03 Y P02 Y P01 Y G00 '3dtP14 = P04 Y P03 Y P02 Y P01 '2dtG14 = G04 O_ P04 Y G03 O_ P04 Y P03 Y G02 O_ P04 Y P03 Y P02 Y G01 '3dtP15 = P05 Y P04 Y P03 Y P02 '2dtG15 = G05 O_ P05 Y G04 O_ P05 Y P04 Y G03 O_ P05 Y P04 Y P03 Y G02 '3dtP16 = P06 Y P05 Y P04 Y P03 '2dtG16 = G06 O_ P06 Y G05 O_ P06 Y P05 Y G04 O_ P06 Y P05 Y P04 Y G03 '3dtP17 = P07 Y P06 Y P05 Y P04 '2dtG17 = G07 O_ P07 Y G06 O_ P07 Y P06 Y G05 O_ P07 Y P06 Y P05 Y G04 '3dt'--- Paso 2 -----------------------G20 = G10 '1dt, C1G21 = G11 '3dt, C2G22 = G12 '3dt, C3G23 = G13 '3dt, C4G24 = G14 O (P14 Y G10) '4dt, C5G25 = G15 O (P15 Y G11) '4dt, C6G26 = G16 O (P16 Y G12) '4dt, C7G27 = G17 O (P17 Y G13) '5dt, C8'--- Suma --------------------------S0 = P00 '1dtS1 = P01 O G20 '2dtS2 = P02 O G21 '4dtS3 = P03 O G22 '4dtS4 = P04 O G23 '4dtS5 = P05 O G24 '5dtS6 = P06 O G25 '5dtS7 = P07 XOR G26 ' 5dt
S8 = G27 ' 5dt , S8=C8=Cout [12]

Binario, base 8, 8 bits

Sumador PPA de valencia 2,3,4,5,6,7,8 de 8 bits con base 8 (es un sumador CLA de valencia 2,3,4,5,6,7,8 de 8 bits y un sumador Sklansky de valencia 2,3,4,5,6,7,8 de 8 bits y un sumador Kogge-Stone de valencia 2,3,4,5,6,7,8 de 8 bits):

'--- Paso 0 ---------------------------P00 = A0 O B0 '1dtG00 = A0 Y B0 '1dtP01 = A1 O B1 '1dtG01 = A1 Y B1 '1dtP02 = A2 O B2 '1dtG02 = A2 Y B2 '1dtP03 = A3 O B3 '1dtG03 = A3 Y B3 '1dtP04 = A4 O B4 '1dtG04 = A4 Y B4 '1dtP05 = A5 O B5 '1dtG05 = A5 Y B5 '1dtP06 = A6 O B6 '1dtG06 = A6 Y B6 '1dtP07 = A7 O B7 '1dtG07 = A7 Y B7 '1dt'--- Paso 1 ---------------------------G10 = G00 '1dtG11 = G01 O P01 Y G00 '3dt, C2, valencia-2, distancia-1G12 = G02 OR_ '3dt, C3, valencia-3, distancia-1,2 P02 Y G01 O_ P02 Y P01 Y G00 '3-in YG13 = G03 OR_ '3dt, C4, valencia-4, distancia-1,2,3 P03 Y G02 O_ P03 Y P02 Y G01 O_ P03 Y P02 Y P01 Y G00 '4-in YG14 = G04 OR_ '3dt, C5, valencia-5, distancia-1,2,3,4 P04 Y G03 O_ P04 Y P03 Y G02 O_ P04 Y P03 Y P02 Y G01 O_ P04 Y P03 Y P02 Y P01 Y G00 '5-in YG15 = G05 OR_ '3dt, C6, valencia-6, distancia-1,2,3,4,5 P05 Y G04 O_ P05 Y P04 Y G03 O_ P05 Y P04 Y P03 Y G02 O_ P05 Y P04 Y P03 Y P02 Y G01 O_ P05 Y P04 Y P03 Y P02 Y P01 Y G00 '6-in YG16 = G06 OR_ '3dt, C7, valencia-7, distancia-1,2,3,4,5,6 P06 Y G05 O_ P06 Y P05 Y G04 O_ P06 Y P05 Y P04 Y G03 O_ P06 Y P05 Y P04 Y P03 Y G02 O_ P06 Y P05 Y P04 Y P03 Y P02 Y G01 O_ P06 Y P05 Y P04 Y P03 Y P02 Y P01 Y G00 '7-in YG17 = G07 OR_ '3dt, C8, valencia-8, distancia-1,2,3,4,5,6,7 P07 Y G06 O_ P07 Y P06 Y G05 O_ P07 Y P06 Y P05 Y G04 O_ P07 Y P06 Y P05 Y P04 Y G03 O_ P07 Y P06 Y P05 Y P04 Y P03 Y G02 O_ P07 Y P06 Y P05 Y P04 Y P03 Y P02 Y G01 O_ P07 Y P06 Y P05 Y P04 Y P03 Y P02 Y P01 Y G00 '8-in Y'--- Suma --------------S0 = P00 '1dtS1 = P01 O G10 '2dtS2 = P02 O G11 '4dtS3 = P03 O G12 '4dtS4 = P04 O G13 '4dtS5 = P05 O G14 '4dtS6 = P06 O G15 '4dtS7 = P07 XOR G16 ' 4dt
S8 = G17 ' 3dt , S8=C8=Cout [13]

Binario, radix-16 16 bits, radix-32 32 bits, radix-64 64 bits,...

'--- Paso 0 -----------------------------------------------------------PARA I=0 A N 'N=15 (31 para base 32 de 32 bits, 63 para base 64 de 64 bits,...) P0[I] = A[I] XOR B[I] '1dt G0[I] = A[I] Y B[I] '1dtSIGUIENTE I'--- Paso 1 ----------------------------------------------------------PARA I=0 A N 'G1[I] G1[I] = 0 PARA J=0 A I 'Cadena J SALIDA1[J] = 1 PARA K=I A IJ PASO -1 'Número de hasta 16 pulgadas Y SI K<>IJ ENTONCES OUT1[J] = OUT1[J] Y P0[K] 'AND'ing, 2dt DEMÁS OUT1[J] = OUT1[J] Y G0[K] 'AND'ing, 2dt FIN SI SIGUIENTE K SI J=0 ENTONCES G1[I] = OUT1[J] DE LO CONTRARIO G1[I] = G1[I] O OUT1[J] Operación 'OR', 3dt 'G1[15]=S[16]=C[16]=Cout, 3dt SIGUIENTE JSIGUIENTE I'--- Suma -----------------------------PARA I=0 A N 'Desplazamiento a la izquierda 1 bit G1[N+1-I] = G1[NI]SIGUIENTE IG1[0] = 0P0[N+1] = 0PARA I=0 A N+1 S[I] = P0[I] XOR G1[I] 'XOR', 4dt (Kogge-Stone, binario, base 2, 64 bits - 14dt )SIGUIENTE I[14]

Velocidad de los sumadores Kogge-Stone con operadores paralelos G

Número de bits n=2 n=4 n=8 n=16 n=32 n=64Base-2Número de pasos s=1 s=2 s=3 s=4 s=5 s=6Añadiendo tiempo 4dt 6dt 8dt 10dt 12dt 14dt Base-4Número de pasos s=1 s=2 s=2 s=3 s=3 Añadiendo tiempo 4dt 6dt 6dt 8dt 8dtBase-8 Número de pasos s=1 s=2 s=2 s=2Añadiendo tiempo 4dt 6dt 6dt 6dtBase-16Número de pasos s=1 s=2 s=2Añadiendo tiempo 4dt 6dt 6dtBase-32Número de pasos s=1 s=2Añadiendo tiempo 4dt 6dtBase-64Número de pasos s=1Añadiendo tiempo 4dt

Velocidad de los sumadores Kogge-Stone en puertas CMOS inversoras

Número de bits n=2 n=4 n=8 n=16 n=32 n=64Base-2Número de pasos s=1 s=2 s=3 s=4 s=5 s=6Añadiendo tiempo 5dt 6dt 7dt 8dt 9dt 10dt Base-4Número de pasos s=1 s=2 s=2 s=3 s=3 Añadiendo tiempo 5dt 6dt 6dt 7dt 7dtBase-8 Número de pasos s=1 s=2 s=2 s=2Añadiendo tiempo 5dt 6dt 6dt 6dtBase-16Número de pasos s=1 s=2 s=2Añadiendo tiempo 5dt 6dt 6dtBase-32Número de pasos s=1 s=2Añadiendo tiempo 5dt 6dtBase-64Número de pasos s=1Añadiendo tiempo 5dt

Velocidad de los sumadores Kogge-Stone en puertas CMOS inversoras con bits de entrada en parafase

Número de bits n=2 n=4 n=8 n=16 n=32 n=64Base-2Número de pasos s=1 s=2 s=3 s=4 s=5 s=6Añadiendo tiempo 4dt 5dt 6dt 7dt 8dt 9dt Base-4Número de pasos s=1 s=2 s=2 s=3 s=3 Añadiendo tiempo 4dt 5dt 5dt 6dt 6dtBase-8 Número de pasos s=1 s=2 s=2 s=2Añadiendo tiempo 4dt 5dt 5dt 5dtBase-16Número de pasos s=1 s=2 s=2Añadiendo tiempo 4dt 5dt 5dt Base-32Número de pasos s=1 s=2Añadiendo tiempo 4dt 5dtBase-64Número de pasos s=1Añadiendo tiempo 4dt

Velocidad de los sumadores Kogge-Stone en puertas de clave no inversora

Número de bits n=2 n=4 n=8 n=16 n=32 n=64Base-2Número de pasos s=1 s=2 s=3 s=4 s=5 s=6Añadiendo tiempo 3dt 4dt 5dt 6dt 7dt 8dtBase-4Número de pasos s=1 s=2 s=2 s=3 s=3 Añadiendo tiempo 3dt 4dt 4dt 5dt 5dtBase-8 Número de pasos s=1 s=2 s=2 s=2Añadiendo tiempo 3dt 4dt 4dt 4dtBase-16Número de pasos s=1 s=2 s=2Añadiendo tiempo 3dt 4dt 4dtBase-32Número de pasos s=1 s=2Añadiendo tiempo 3dt 4dtBase-64Número de pasos s=1Añadiendo tiempo 3dt

El concepto de sumador Kogge-Stone fue desarrollado por Peter M. Kogge y Harold S. Stone , quienes lo publicaron en un artículo seminal de 1973 titulado Un algoritmo paralelo para la solución eficiente de una clase general de ecuaciones de recurrencia . [15]

Mejoras

Las mejoras de la implementación original incluyen el aumento del radix y la escasez del sumador. El radix del sumador se refiere a cuántos resultados del nivel anterior de cómputo se utilizan para generar el siguiente. La implementación original utiliza radix-2, aunque es posible crear radix-4 y superiores. Hacerlo aumenta la potencia y el retraso de cada etapa, pero reduce la cantidad de etapas requeridas. En el llamado sumador Kogge-Stone disperso ( SKA ), la escasez del sumador se refiere a cuántos bits de acarreo son generados por el árbol de acarreo. La generación de cada bit de acarreo se llama escasez-1, mientras que la generación de cada otro es escasez-2 y cada cuarto es escasez-4. Los acarreos resultantes se utilizan luego como entradas de acarreo para sumadores de acarreo de ondulación mucho más corta o algún otro diseño de sumador, que genera los bits de suma final. Aumentar la escasez reduce el cálculo total necesario y puede reducir la cantidad de congestión de enrutamiento.

Sumador de Kogge-Stone de escasez-4. Ejemplo de un sumador de Kogge-Stone con escasez-4. Los elementos eliminados por escasez se muestran marcados con transparencia.

Arriba se muestra un ejemplo de un sumador 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 de enrutamiento se reduce sustancialmente. Cada acarreo generado alimenta un multiplexor para un sumador de selección de acarreo o el acarreo de entrada de un sumador de acarreo de ondulación.

Sumador Kogge-Stone de 16 bits con valencia 2 sin Cin:

P00 = A0 XOR B0 '1dt, S0, dt - tiempo de retardo de tipo G00 = A0 Y B0 '1dt, C0 P10 = A1 O B1 '1dt  G10 = A1 Y B1 '1dt P20 = A2 O B2 '1dt G20 = A2 Y B2 '1dt  P30 = A3 O B3 '1dt G30 = A3 Y B3 '1dt P40 = A4 O B4 '1dt G40 = A4 Y B4 '1dt P50 = A5 O B5 '1dt  G50 = A5 Y B5 '1dt P60 = A6 O B6 '1dt G60 = A6 Y B6 '1dt P70 = A7 XOR B7 '1dt G70 = A7 Y B7 '1dt P80 = A8 O B8 '1dt G80 = A8 Y B8 '1dt  P90 = A9 O B9 '1dt  G90 = A9 Y B9 '1dtP100 = A10 O B10 '1dtG100 = A10 Y B10 '1dtP110 = A11 O B11 '1dtG110 = A11 Y B11 '1dt P120 = A12 O B12 '1dtG120 = A12 Y B12 '1dtP130 = A13 O B13 '1dtG130 = A13 Y B13 '1dtP140 = A14 O B14 '1dt G140 = A14 Y B14 '1dtP150 = A15 O B15 '1dtG150 = A15 Y B15 '1dtG11 = G10 O P10 Y G00 '3dt, C1P21 = P20 Y P10 '2dtG21 = G20 O P20 Y G10 '3dtP31 = P30 Y P20 '2dtG31 = G30 O P30 Y G20 '3dtP41 = P40 Y P30 '2dtG41 = G40 O P40 Y G30 '3dtP51 = P50 Y P40 '2dtG51 = G50 O P50 Y G40 '3dtP61 = P60 Y P50 '2dtG61 = G60 O P60 Y G50 '3dtP71 = P70 Y P60 '2dtG71 = G70 O P70 Y G60 '3dtP81 = P80 Y P70 '2dt G81 = G80 O P80 Y G70 '3dtP91 = P90 Y P80 '2dtG91 = G90 O P90 Y G80 '3dtP101 = P100 Y P90 '2dtG101 = G100 O P100 Y G90 '3dtP111 = P110 Y P100 '2dt G111 = G110 O P110 Y G100 '3dtP121 = P120 Y P110 '2dtG121 = G120 O P120 Y G110 '3dtP131 = P130 Y P120 '2dtG131 = G130 O P130 Y G120 '3dtP141 = P140 Y P130 '2dtG141 = G140 O P140 Y G130 '3dtP151 = P150 Y P140 '2dtG151 = G150 O P150 Y G140 '3dtG22 = G21 O P21 Y G00 '4dt, C2G32 = G31 O P31 Y G11 '5dt, C3P42 = P41 Y P21 '3dtG42 = G41 O P41 Y G21 '5dtP52 = P51 Y P31 '3dtG52 = G51 O P51 Y G31 '5dtP62 = P61 Y P41 '3dtG62 = G61 O P61 Y G41 '5dtP72 = P71 Y P51 '3dtG72 = G71 O P71 Y G51 '5dtP82 = P81 Y P61 '3dtG82 = G81 O P81 Y G61 '5dtP92 = P91 Y P71 '3dtG92 = G91 O P91 Y G71 '5dtP102 = P101 Y P81 '3dtG102 = G101 O P101 Y G81 '5dtP112 = P111 Y P91 '3dt G112 = G111 O P111 Y G91 '5dtP122 = P121 Y P101 '3dtG122 = G121 O P121 Y G101 '5dtP132 = P131 Y P111 '3dtG132 = G131 O P131 Y G111 '5dtP142 = P141 Y P121 '3dtG142 = G141 O P141 Y G121 '5dtP152 = P151 Y P131 '3dtG152 = G151 O P151 Y G131 '5dtG43 = G42 O P42 Y G00 '6dt, C4G53 = G52 O P52 Y G11 '6dt, C5G63 = G62 O P62 Y G22 '6dt, C6G73 = G72 O P72 Y G32 '7dt, C7P83 = P82 Y P42 '4dtG83 = G82 O P82 Y G42 '7dtP93 = P92 Y P52 '4dtG93 = G92 O P92 Y G52 '7dtP103 = P102 Y P62 '4dtG103 = G102 O P102 Y G62 '7dtP113 = P112 Y P72 '4dtG113 = G112 O P112 Y G72 '7dtP123 = P122 Y P82 '4dt G123 = G122 O P122 Y G82 '7dtP133 = P132 Y P92 '4dtG133 = G132 O P132 Y G92 '7dtP143 = P142 Y P102 '4dtG143 = G142 O P142 Y G102 '7dtP153 = P152 Y P112 '4dtG153 = G152 O P152 Y G112 '7dtG84 = G83 O P83 Y G00 '8dt, C8G94 = G93 O P93 Y G11 '8dt, C9G104 = G103 O P103 Y G22 '8dt, C10G114 = G113 O P113 Y G32 '8dt, C11G124 = G123 O P123 Y G43 '8dt, C12G134 = G133 O P133 Y G53 '8dt, C13G144 = G143 O P143 Y G63 '8dt, C14G154 = G153 O P153 Y G73 '9dt, C15S0 = P00 '1dtS1 = P10 O G00 '2dtS2 = P20 O G11 '4dtS3 = P30 O G22 '5dtS4 = P40 O G32 '6dtS5 = P50 O G43 '7dtS6 = P60 O G53 '7dtS7 = P70 O G63 '7dtS8 = P80 O G73 '8dtS9 = P90 O G84 '9dtS10 = P100 O G94 '9dtS11 = P110 O G104 '9dtS12 = P120 O G114 '9dtS13 = P130 O G124 '9dtS14 = P140 O G134 '9dtS15 = P150 O G144 '9dt

Referencias

  1. ^ Lógica de adición de suma condicional. Sklansky J. IRE Transaction on Electronic Computer. 1960. p.226.
  2. ^ Brent, Richard Peirce ; Kung, Hsiang Te (marzo de 1982). "Un diseño regular para sumadores paralelos" (PDF) . IEEE Transactions on Computers . C-31 (3): 260–264. doi :10.1109/TC.1982.1675982. ISSN  0018-9340. S2CID  17348212. Archivado desde el original el 24 de septiembre de 2017.
  3. ^ Han, Tackdon; Carlson, David A.; Levitan, Steven P. (octubre de 1982). "Diseño VLSI de circuitos de adición de área reducida y alta velocidad". Actas de la Conferencia Internacional IEEE de 1981 sobre Diseño de Computadoras: VLSI en Computadoras y Procesadores . IEEE : 418–422. ISBN 0-81860802-1.
  4. ^ Han, Tackdon; Carlson, David A. (octubre de 1987). "Sumadores VLSI rápidos y eficientes en el área". Actas del 8º Simposio sobre Aritmética Informática . IEEE : 49–56.
  5. ^ Lynch, Thomas Walker; Swartzlander, Jr., Earl E. (agosto de 1992). "Un sumador de búsqueda anticipada de acarreo de árbol de expansión". IEEE Transactions on Computers . 41 (8): 931–939. doi :10.1109/12.156535.
  6. ^ ab 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 .
  7. ^ Una familia de víboras. Simon Knowles. Elemento 14, Aztec Centre, Bristol, Reino Unido.
  8. ^ Diseño de sumador de prefijo paralelo. Beaumont-Smith A., Cheng-Chew L. Departamento de Ingeniería Eléctrica y Electrónica, Universidad de Adelaida, Australia. 2001
  9. ^ https://andserkul.narod.ru/R2KS4.bas [ URL desnuda ]
  10. ^ https://andserkul.narod.ru/R2KS8.bas [ URL desnuda ]
  11. ^ https://andserkul.narod.ru/R4KS4F.bas [ URL desnuda ]
  12. ^ https://andserkul.narod.ru/R4KS8F.bas [ URL desnuda ]
  13. ^ https://andserkul.narod.ru/R8KS8F.bas [ URL desnuda ]
  14. ^ https://andserkul.narod.ru/R16KSFM.bas [ URL desnuda ]
  15. ^ 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". IEEE Transactions on Computers . C-22 (8): 786–793. doi :10.1109/TC.1973.5009159. S2CID  206619926.

Lectura adicional