Sumador Brent-Kung

El sumador Brent-Kung ( BKA o BK ), propuesto en 1982, ^[1] es un diseño de sumador binario avanzado , que tiene una profundidad de nivel de puerta de . ${\ Displaystyle O (\ log _ {2} (n))}$

Introducción

El sumador Brent-Kung es una forma de sumador de prefijo paralelo (PPA) de sumador de anticipación (CLA). Propuesto por Richard Peirce Brent y Hsiang Te Kung en 1982, introdujo una mayor regularidad en la estructura del sumador y tiene menos congestión de cableado, lo que conduce a un mejor rendimiento y menos área de chip necesaria para implementar en comparación con el sumador Kogge-Stone (KSA). También es mucho más rápido que los sumadores de acarreo ondulado (RCA).

Los sumadores de acarreo de ondulación fueron los sumadores multibit iniciales que se desarrollaron en los primeros días y obtuvieron su nombre del efecto dominó que producía el acarreo mientras se propagaba de derecha a izquierda. El tiempo necesario para la adición fue directamente proporcional a la longitud del bit que se agregó. Esto es lo contrario en los sumadores Brent-Kung, donde el carry se calcula en paralelo, lo que reduce drásticamente el tiempo de suma. Se ha trabajado más en sumadores Brent-Kung y otros sumadores paralelos para reducir el consumo de energía y el área del chip, así como para aumentar la velocidad, haciéndolos adecuados para diseños de baja potencia.

Un sumador Brent-Kung es un sumador paralelo fabricado con un diseño regular con el objetivo de minimizar el área del chip y facilitar la fabricación. La suma de un número de n bits se puede realizar en el tiempo con un tamaño de área de chip, lo que lo convierte en un sumador de buena elección con restricciones de área y maximización del rendimiento. Su simetría y estructura de construcción regular reducen los costos de producción de manera efectiva y permiten su uso en arquitecturas de tuberías. En los sumadores paralelos, la ruta crítica se decide mediante el cálculo del acarreo desde el sumador del bit menos significativo (LSB) al sumador del bit más significativo (MSB); por lo tanto, los esfuerzos se centran en reducir la ruta crítica para que el acarreo llegue al MSB. ${\ Displaystyle O (\ log _ {2} n)}$ $O(n\log _ {2}n),$

Esquema del modelo básico

En general, la mayoría de los sumadores utilizan el acarreo y los bits correspondientes de dos números (A y B) para obtener el bit de suma correspondiente y el acarreo, y los sumadores de acarreo ondulado toman tiempo para que el acarreo alcance MSB. $O(n)$

Considerando que A = a _n a _n-1 … a ₁ y B = b _n b _n-1 … b ₁ son números binarios de n bits.
Siendo la suma S = s _n+1 s _n … s ₁ y el acarreo generado en cada etapa C = c _n … c ₀ se trasladará a las siguientes etapas.

Para RCA, c ₀ = 0 , y i el bit de suma y el bit de acarreo generados son
c _i = g _i ∨ (a _i ∧ c _i-1 ) ∨ (b _i ∧ c _i-1 ),
s _i = a _i ⊕ b _i ⊕ c _i-1 para i = 1, 2, … n
s _n+1 = c _n respectivamente.
Es posible transformar el acarreo de ondulación anterior en acarreo anticipado (CLA) definiendo el bit de acarreo i como
c ₀ = 0,
c _i = g _i ∨ (p _i ∧ c _i-1 ) donde
g _i = a _i ∧ b _i ,
p _i = a _i ⊕ b _i , y
s _i = p _i ⊕ c _i-1 para i = 1, 2,… n.
p y g se conocen como acarreo propagado y acarreo generado. Esto corresponde al hecho de que el acarreo ci _es generado por a _i y b _i o se propaga desde el acarreo anterior ci _-1 .

Brent y Kung transformaron aún más la generación y propagación del acarreo al definir un operador asociativo ○ que define la generación y propagación del acarreo en un rango de bits como
(g ₁ , p ₁ ) ○ (g ₂ , p ₂ ) = (g ₁ ∨ ( pag ₁ ∧ gramo ₂ ), pag ₁ ∧ pag ₂ ) .

También definieron los valores Gi _y Pi _como los bits de generación y propagación para los bits de i a 1, es decir
(G1 _, P1 ₎ = (g1 _, p1 ₎ para i = 1;
de lo contrario (G _i , P _i ) = (g _i , p _i ) ○ (G _i-1 , P _i-1 ) para i = 2, 3,… n.
Se puede derivar que G _i en la función es equivalente a c _i . Además (G _n , P _n ) se puede escribir de forma no recursiva como = (g _n , p _n ) ○ (g _n-1 , p _n-1 ) ○ … ○ (g ₁ , p ₁ ) .

Aprovechando la asociatividad del operador ○ , (G _n , P _n ) se puede calcular en forma de árbol.

El diseño de los nodos blancos es obvio ya que solo almacenan en búfer los g _i y p _i , y los nodos negros realizan la operación definida por el operador ○ , que es similar a un sumador de un bit.

Esta propagación del acarreo similar a un árbol reduce su camino crítico al de la altura del árbol. Como la altura del árbol de acarreo puede ser máxima de , la ruta crítica del sumador paralelo Brent-Kung también es , que es mejor que el rendimiento del sumador normal de . El diseño basado en árbol también reduce el área del chip y el cableado redundante requerido en los sumadores generales basados en CLA. $O(log_{2}(n))$ $O(log_{2}(n))$ $O(n)$

Etapa de procesamiento final

Utilizando la transformación de propagación y generación de acarreo para calcular la suma y el acarreo utilizada por Brent y Kung, el rendimiento del sumador aumenta considerablemente y también conduce a un aumento en la regularidad. La suma final se puede calcular de la siguiente manera: s _i = p _i ⊕ G _i-1 , ya que p _i = a _i ⊕ b _i y G _i-1 = c _i-1 .

Sumador de baja potencia

El aumento en el rendimiento de los sumadores Brent-Kung se atribuye a su estructura de árbol de propagación de acarreo, que también conduce a un menor consumo de energía, ya que la señal de acarreo ahora tiene que viajar a través de menos etapas, lo que lleva a una menor conmutación de transistores. Además, la disminución en la cantidad de cableado y distribución también contribuye en gran medida a su menor consumo de energía que los sumadores CLA. También se puede utilizar un sumador Brent-Kung en forma de tubería, lo que puede reducir aún más el consumo de energía al reducir la profundidad de la lógica combinatoria y la estabilización de fallas. ^[1] El gráfico muestra un sumador Brent-Kung de baja potencia. ^[2]

Comparación con la sumadora de Kogge-Stone

Ventajas

Debido a que este tipo de sumador requiere menos módulos para implementar que el sumador Kogge-Stone , el sumador Brent-Kung es mucho más sencillo de construir. También contiene muchas menos conexiones a otros módulos, lo que también contribuye a su simplicidad. ^[3]

Desventajas

Este tipo de sumador tiene un mayor retraso y ^requiere 2 $log 2 n - 2$ niveles de lógica para calcular todos los bits de acarreo. (Kogge-Stone requiere $log 2 n$ .)

Ecuaciones

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

P00 = A0 XOR B0 '1dt, S0G00 = A0 Y B0 '1dt, C0P10 = A1 XOR B1 '1dt G10 = A1 Y B1 '1dtP20 = A2 XOR B2 '1dtG20 = A2 Y B2 '1dtP30 = A3 XOR B3 '1dtG30 = A3 Y B3 '1dtP40 = A4 XOR B4 '1dtG40 = A4 Y B4 '1dtP50 = A5 XOR B5 '1dtG50 = A5 Y B5 '1dt P60 = A6 XOR B6 '1dtG60 = A6 Y B6 '1dtP70 = A7 XOR B7 '1dtG70 = A7 Y B7 '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 '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 '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, C7, CoutS0 = P00 '1dtS1 = P10 XOR G00 '2dtS2 = P20 XOR G11 '4dtS3 = P30 XOR G22 '5dtS4 = P40 XOR G32 '6dtS5 = P50 XOR G43 '7dtS6 = P60 XOR G53 '7dtS7 = P70 XOR G63 '7dt

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

P00 = A0 XOR B0 '1dt, S0G00 = A0 Y B0 '1dt, C0P10 = A1 XOR B1 '1dtG10 = A1 Y B1 '1dtP20 = A2 XOR B2 '1dtG20 = A2 Y B2 '1dtP30 = A3 XOR B3 '1dtG30 = A3 Y B3 '1dtP40 = A4 XOR B4 '1dtG40 = A4 Y B4 '1dtP50 = A5 XOR B5 '1dtG50 = A5 Y B5 '1dtP60 = A6 XOR B6 '1dtG60 = A6 Y B6 '1dtP70 = A7 XOR B7 '1dtG70 = A7 Y B7 '1dtG11 = G10 O P10 Y G00 '3dt, distancia=2^0=1, valencia-2, C1P21 = P20 Y P10 '2dtG21 = G20 O P20 Y G10 '3dt, distancia=2^0=1, valencia-2P31 = P30 Y P20 '2dtG31 = G30 O P30 Y G20 '3dt, distancia=2^0=1, valencia-2P41 = P40 Y P30 '2dtG41 = G40 O P40 Y G30 '3dt, distancia=2^0=1, valencia-2P51 = P50 Y P40 '2dtG51 = G50 O P50 Y G40 '3dt, distancia=2^0=1, valencia-2P61 = P60 Y P50 '2dtG61 = G60 O P60 Y G50 '3dt, distancia=2^0=1, valencia-2P71 = P70 Y P60 '2dtG71 = G70 O P70 Y G60 '3dt, distancia=2^0=1, valencia-2G22 = G20 O_ P20 Y G10 O_ P20 Y P10 Y G00 '3dt, distancia=2^1=2, valencia-3, C2G32 = G30 O_ P30 Y G20 O_ P30 Y P20 Y G10 O_ P30 Y P20 Y P10 Y G00 '3dt, distancia=2^1=2, valencia-4, C3P42 = P41 Y P21 '3dt, distancia=2^1=2G42 = G40 O_ P40 Y G30 O_ P40 Y P30 Y G20 O_ P40 Y P30 Y P20 Y G10 '3dt, distancia=2^1=2, valencia-4P52 = P51 Y P31 '3dt, distancia=2^1=2G52 = G50 O_ P50 Y G40 O_ P50 Y P40 Y G30 O_ P50 Y P40 Y P30 Y G20 '3dt, distancia=2^1=2, valencia-4P62 = P61 Y P41 '3dt, distancia=2^1=2G62 = G60 O_ P60 Y G50 O_ P60 Y P50 Y G40 O_ P60 Y P50 Y P40 Y G30 '3dt, distancia=2^1=2, valencia-4P72 = P71 Y P51G72 = G70 O_ P70 Y G60 O_ P70 Y P60 Y G50 O_ P70 Y P60 Y P50 Y G40 '3dt, distancia=2^1=2, valencia-4G43 = G42 O P42 Y G00 '5dt, distancia=2^2=4, valencia-2, C4G53 = G52 O P52 Y G11 '5dt, distancia=2^2=4, valencia-2, C5G63 = G62 O P62 Y G22 '5dt, distancia=2^2=4, valencia-2, C6G73 = G72 O P72 Y G32 '5dt, distancia=2^2=4, valencia-2, C7S0 = P00 '1dtS1 = P10 XOR G00 '2dtS2 = P20 XOR G11 '4dtS3 = P30 XOR G22 '4dtS4 = P40 XOR G32 '6dtS5 = P50 XOR G43 '6dtS6 = P60 XOR G53 '6dtS7 = P70 XOR G63 '6dt

Sumador Brent-Kung de 8 bits, valencia-2:

P00 = A0 XOR B0 '1dt, S0G00 = A0 Y B0 '1dt, C0P10 = A1 XOR B1 '1dtG10 = A1 Y B1 '1dtP20 = A2 XOR B2 '1dtG20 = A2 Y B2 '1dtP30 = A3 XOR B3 '1dtG30 = A3 Y B3 '1dtP40 = A4 XOR B4 '1dtG40 = A4 Y B4 '1dtP50 = A5 XOR B5 '1dtG50 = A5 Y B5 '1dtP60 = A6 XOR B6 '1dtG60 = A6 Y B6 '1dtP70 = A7 XOR B7 '1dtG70 = A7 Y B7 '1dtG11 = G10 O P10 Y G00 '3dt, C1G21 = G20 O P20 Y G11 '3dt, C2P31 = P30 Y P20 '2dtG31 = G30 O P30 Y G20 '3dtP51 = P50 Y P40 '2dt G51 = G50 O P50 Y G40 '3dtP71 = P70 Y P60 '2dt G71 = G70 O P70 Y G60 '3dtG32 = G31 O P31 Y G11 '5dt, C3P72 = P71 Y P51 '3dtG72 = G71 O P71 Y G51 '5dt G53 = G51 O P51 Y G32 '7dt, C5G73 = G72 O P72 Y G32 '7dt, C7, CoutG44 = G40 O P40 Y G32 '7dt, C4G64 = G60 O P60 Y G53 '9dt, C6S0 = P00 '1dt S1 = P10 XOR G00 '2dtS2 = P20 XOR G11 '4dtS3 = P30 XOR G21 '4dtS4 = P40 XOR G32 '6dtS5 = P50 XOR G44 '8dtS6 = P60 XOR G53 '8dtS7 = P70 XOR G64 '10dt

Referencias

^ ab Brent, Richard Peirce ; Kung, Hsiang Te (marzo de 1982) [junio de 1979]. "Un diseño regular para sumadores paralelos". Transacciones IEEE en computadoras . C-31 (3). Departamento de Ciencias de la Computación, Universidad Carnegie-Mellon, EE. UU.: 260–264. doi :10.1109/TC.1982.1675982. ISSN 0018-9340. S2CID 17348212. CMS-CS-79-131. Archivado desde el original el 24 de septiembre de 2017.
^ Alejandro, Jonathan (2004). "Consejos de diseño VHDL y técnicas de diseño de bajo consumo" . Consultado el 21 de abril de 2018 .
^ ab Pointer, Robey (14 de noviembre de 2012). "Cómo sumar números (parte 2)". robey.lag.net . Archivado desde el original el 21 de abril de 2018 . Consultado el 21 de abril de 2018 .

Otras lecturas

Reynders, Nele; Dehaene, Wim (2015). Diseño de voltaje ultrabajo de circuitos digitales energéticamente eficientes . Circuitos analógicos y procesamiento de señales (ACSP) (1 ed.). Cham, Suiza: Springer International Publishing AG Suiza . doi :10.1007/978-3-319-16136-5. ISBN 978-3-319-16135-8. ISSN 1872-082X. LCCN 2015935431.

enlaces externos

Archivado el 4 de febrero de 2020 en Wayback Machine.