Bloques Aritméticos - Multiplicadores La multiplicación es una operación cara (en términos de recursos) y lenta Este hecho ha motivado la integración de unidades completas de multiplicación en los DSPs y µPs Los multiplicadores son en la práctica matrices complejas de sumadores

DCSE 2010-11

1/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Bloques Aritméticos - Multiplicadores Consideramos dos números binarios sin signo X e Y, de M y N bits respectivamente: X=

M −1

∑ i =0

Y=

X i 2i

N −1

j Y 2 ∑ j j =0

X i , Y j ∈ {0,1}

Definición de la operación de multiplicación: Z = X×Y =

M + N −1

∑

k =0

Z k 2k =

N −1   M −1  i j   ∑ Xi 2   ∑ Yj 2  =  i =0   j =0  DCSE 2010-11

2/34

N −1

 M −1 i+ j  ∑  ∑ X iY j 2  j =0  i =0 

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Multiplicadores – Desplazamiento y Suma X= ∑X2 N −1 M −1  i+ j  M −1

Y=

i

i

i =0 N −1

∑Y 2 j =0

Z = X×Y =

j

∑∑ XY 2 j =0

j

 i =0

i

j

 

La multiplicación requiere M ciclos utilizando un sumador de N bits. Se realiza la suma de N productos parciales, que se generan multiplicando un bit del multiplicador por el valor del multiplicando (operación AND) y desplazando el resultado según la posición del bit del multiplicador. DCSE 2010-11

3/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Multiplicador matricial: ejemplo 1 0 1 0 1 0

Multiplicando

1 0 1 1

Multiplicador

×

1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 +

1 0 1 0 1 0 1 1 1 0 0 1 1 1 0

DCSE 2010-11

Productos parciales

4/34

Resultado

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Multiplicador matricial 1 0 1 0 1 0

×

1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0

+

Los productos parciales se generan en paralelo y se organizan en una matriz

1 0 1 0 1 0 1 1 1 0 0 1 1 1 0

Un sumador multioperando calcula el producto final

En hardware, la estructura del multiplicador matricial combina las funciones: generación de productos parciales, acumulación de productos parciales y suma final DCSE 2010-11

5/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Generación de productos parciales X7

X6

X5

X4

X3

X2

X1

X0

Yj

PP7

PP6

PP5

PP4

PP3

PP2

PP1

PP0

Los productos parciales (PP) resultan de aplicar la operación lógica AND al multiplicando X y a un bit del multiplicador Yj Cada fila de la matriz de PP es una copia del multiplicando o una fila de ceros Optimizar la generación de los PP para reducir los retardos y el área ocupada en hardware (recodificación Booth) DCSE 2010-11

6/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Algoritmo de Booth Ejemplo: Un multiplicador de 8 bits: 01111110 produce 6 filas de productos parciales distintos de cero Este número se puede re-codificar para poder reducir (sustancialmente) el número de filas distintas de cero: − El número 10000010 representa el mismo − número, si 1 es una anotación abreviada para designar el valor -1 DCSE 2010-11

7/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Algoritmo de Booth Ejemplo (cont.): − Utilizando esta representación ( 10000010), basta con sumar dos productos parciales, aunque el sumador tiene que ser capaz de realizar restas. Reducir el número de productos parciales es equivalente a reducir el número de sumas, lo que permite acelerar la operación y reducir el área ocupada. DCSE 2010-11

8/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Re-codificación de Booth modificado No resulta demasiado práctico para el diseño de multiplicadores disponer de una matriz de productos parciales de tamaño variable. Por eso, normalmente se utiliza el esquema de re-codificación de Booth modificado, en lugar del esquema original. El multiplicador se divide en grupos de 3 bits, solapados por un bit. Cada grupo de 3 se recodifica según la tabla siguiente: DCSE 2010-11

9/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Re-codificación de Booth modificado Tabla de re-codificación Booth Bits del multiplicador

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

DCSE 2010-11

0 1 0 1 0 1 0 1

Ejemplos: 01110110(0) → 011 110 011 100

recodificados

00 01 01 02 -02 -01 -01 00 10/34

↓ 02 -01 02 -02 00100111(0)→ 001 100 011 110 ↓ 01 -02 02 -01 10111010(0)→ 101 111 101 100 ↓ -01 00 -01 -02

-01: complemento a 2 02: desplazamiento (multiplicar por 2) -02: complemento a 2 y desplazamiento Diseño de circuitos y sistemas digitales / Bloques aritméticos

Re-codificación de Booth modificado Tabla de re-codificación Booth

1

0

1

5

0

1

1

1

7

0

0

0

1

0

0

0

0

0

1

1

1×5 2×5

1

4×5 0×5

th oo

+

1

0

B ión ac

0

1

ic dif co re-

×

0

Bits del multiplicador

re-codificados

0

0

0

00

0

0

1

01

0

1

0

01

0

1

1

02

1

0

0

-02

1

0

1

-01

1

1

0

-01

1

1

1

00

0 1 1 1 → 0 1 1 1 (0) → 011 110

↓ 0

0

1

DCSE 2010-11

0

0

0

1

11/34

1

35

02 -01

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Re-codificación de Booth modificado Tabla de re-codificación Booth

×

0

0

1

1

1 0

0

0 1

5

0

2

0 -1

7= 2×22 + (-1)×20

1

0

1

1

2×22×5

1

0

-1×5

0

1

1

35

th oo

0

1

1

B ión ac

+

1

0

ic dif co re-

1

Bits del multiplicador

re-codificados

0

0

0

00

0

0

1

01

0

1

0

01

0

1

1

02

1

0

0

-02

1

0

1

-01

1

1

0

-01

1

1

1

00

0 1 1 1 → 0 1 1 1 (0) → 011 110

↓ 02 -01

0 1 0 1 (compl. 2): 1 0 1 0 + 0 0 0 1 = 1 0 1 1 y en 8 bits: 1 1 1 1 1 0 1 1 DCSE 2010-11

12/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Multiplicador matricial Topológicamente muy similar al procedimiento manual de multiplicación

Z7

X3

X2

X1

X0 Y1 Z0

X3

X2

X1

X0

HA

FA

FA

HA

X3

X2

X1

X0

FA

FA

FA

HA

X3

X2

X1

X0

FA

FA

FA

HA

Z6

Z5

Z4

Y3

Y2

Y0

Z1

Z2

Z3

Multiplicador matricial de 4× ×4 bits para números sin signo DCSE 2010-11

13/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Multiplicador matricial

La generación de N PPs requiere N×M puertas AND de 2 bits La mayor parte del área del multiplicador está dedicada a la suma de los N PPs, que requiere N-1 sumadores de M bits Desplazamiento: conectar apropiadamente las pistas de interconexión, sin necesidad de lógica especial ¡Estructura compacta! Se puede implementar de forma rectangular (opt. layout) DCSE 2010-11

14/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Multiplicador matricial ¿Cómo calcular el retardo de propagación de este circuito?

Identificar camino crítico de temporización ¡(no trivial)! Se pueden identificar varios caminos con una longitud prácticamente idéntica

DCSE 2010-11

15/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Multiplicador matricial

Hay N-1 sumadores de M bits

tmult ≈ tAND + (N-1)·tsum + [(M-1) + (N-2)]·tcarry (para el camino crítico 2) DCSE 2010-11

16/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Multiplicador matricial Hay dependencias verticales y horizontales en todos los niveles Todos los caminos críticos se tienen que acelerar al mismo tiempo (acelerar solo uno de ellos sustituyendo un sumador por otro más rápido, como por ejemplo un sumador CarrySelect, no tiene mucho sentido)

tmult ≈ tAND + (N-1)·tsum + [(M-1) + (N-2)]·tcarry De la ecuación anterior, se observa que la minimización de tmult requiere la minimización tanto de tcarry como de tsum Se puede utilizar un sumador Carry-Save DCSE 2010-11

17/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Multiplicador Carry-Save Observamos que el resultado de la multiplicación no varía cuando los bits de salida del acarreo se transmiten diagonalmente hacia abajo en lugar de solo hacia la derecha ¡Este es el principio del CSA que hemos visto en la clase anterior! Para generar el resultado final se incluye en el diseño un sumador adicional, denominado sumador de combinación de vectores DCSE 2010-11

18/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Multiplicador Carry-Save

La propagación de señales se realiza hacia la siguiente etapa y no entre elementos de una misma etapa DCSE 2010-11

19/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Multiplicador Carry-Save - ejemplo

compresor 3-2

DCSE 2010-11

20/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Multiplicador Carry-Save La propagación de señales se realiza hacia la siguiente etapa y no entre elementos de una misma etapa

Retardo de un FA por cada fila superior

tmult ≈ tAND + (N-1)·tcarry + tfinalsum Retardo de un sumador de N bits DCSE 2010-11

21/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Disposición rectangular de un CSM

y se combinan Se utilizanmediante 6 sumadores operaciones AND antes de completos las sumas

FA y 6 semi-sumadores HA

DCSE 2010-11

22/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Árbol de retardos balanceado La cadena vertical de FA en un CSM es una cadena serie. Se puede reducir el retardo de dicha cadena empleando árboles binarios

DCSE 2010-11

23/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Multiplicador en árbol Empleando sumadores para las sumas parciales en estructura de árbol, se pueden reducir tanto el camino crítico (retardo) como el núm. de celdas sumadoras necesarias (área) Para un multiplicador de 4×4 bits, se puede observar que solo la columna 3 de la matriz de sumadores tiene que sumar 4 bits. Todas las demás columnas son algo menos complejas.

DCSE 2010-11

24/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Árbol de Wallace para un multiplicador de 4×4 bits

Para conseguir una implementación mínima, recubrimos de manera iterativa el árbol con FA y HA comenzando por la parte más densa. En un primer paso introducimos HA en las columnas 4 y 3

DCSE 2010-11

25/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Árbol de Wallace para un multiplicador de 4×4 bits

Este es el árbol reducido, y en esta estructura introducimos en una segunda iteración 3 FA y un HA. DCSE 2010-11

26/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Árbol de Wallace para un multiplicador de 4×4 bits

Después de esta segunda iteración de reducciones hemos creado un árbol de profundidad 2, para alimentar el sumador final de dos entradas, para el cual se puede utilizar cualquier tipo de sumador DCSE 2010-11

27/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Árbol de Wallace para un multiplicador de 4×4 bits

Solo se utilizan 3 sumadores completos FA y 3 semi-sumadores HA para el proceso de reducción DCSE 2010-11

28/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Implementación del multiplicador en árbol de Wallace

El multiplicador el árbol permite conseguir un ahorro sustancial de hardware para multiplicadores de gran tamaño. También se reduce el retardo de propagación, que es: O(log3/2(N)). Desventaja: el multiplicador Wallace es muy irregular, lo que complica la tarea de obtener un layout eficiente. HA

DCSE 2010-11

29/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Suma final La velocidad del sumador final tiene gran importancia La elección del estilo de sumador dependerá de la estructura de la matriz de acumulación. Se puede preferir un CLA si todos los bits de entrada al sumador llegan al mismo tiempo (es el sumador con el más pequeño retardo posible) Este es el caso, por ejemplo, si se utiliza una etapa de registro justo antes de la suma final. El procesamiento en cadena mediante la inclusión de registros es una técnica frecuentemente utilizada en los multiplicadores de altas prestaciones DCSE 2010-11

30/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Suma final En los multiplicadores que no están basados en una estructura de procesamiento en cadena, el perfil de instantes de llegada de las entradas al sumador final es bastante poco equilibrado, debido a las profundidades lógicas variables del árbol del multiplicador En estas circunstancias, otras topologías de sumador, como las de carry-select, suelen proporcionar prestaciones similares a las del CLA, pero con un coste en términos de hardware sustancialmente menor

DCSE 2010-11

31/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Problemas

DCSE 2010-11

32/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Problema 1. Examen junio 2003 Se desea realizar un bloque combinacional que realice la siguiente operación: Z = 4·A + 7·B + 3·C siendo A, B y C números enteros positivos de 4 bits. a) Determine los valores máximo y mínimo de la salida Z. ¿Cuántos bits son necesarios para poder representarla? b) Utilizando únicamente sumadores completos de un bit, construya el bloque combinacional. Si lo considera oportuno siga la estructura de un multiplicador en array. c) Sabiendo que los retardos de propagación del sumador completo de un bit son: tsuma=tcarry=1 ns, señale en la estructura anterior los caminos con retardo máximo y mínimo e indique sus valores. DCSE 2010-11

33/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos

Problema 2. Examen febrero 2002 Se desea realizar un bloque sumador de 8+8 bits y salida de 8 bits más acarreo. En este problema se estudiarán diferentes alternativas de implementación. Considere que deberá almacenar los datos de entrada en dos registros de 8 bits y que el resultado deberá escribirse en otro registro de 9 bits. Los componentes disponibles son los siguientes: Sumadores de 1 bit (full-adder): Area normalizada = 1; Retardo = 1 ns. Puertas lógicas (cualesquiera): Area normalizada = 0,5; Retardo = 0,5 ns. Multiplexores (2 a 1): Area normalizada = 0,25; Retardo = 0,25 ns. Multiplexores (8 a 1): Area normalizada = 1,75; Retardo = 0,75 ns. Flip-flops tipo D: Area normalizada = 0,75; tprop = 0,75 ns.; tsetup = 0,25 ns. a) Dibuje de forma detallada una arquitectura con un sumador del tipo carry-bypass de 8 bits con grupos de 3 bits. b) Comente la diferencia entre los dos tipos de sumadores carry-select y seleccione uno de ellos para diseñar un sumador carry-select de 8 bits donde el grupo que contiene el bit menos significativo sea de 2 bits. Dibuje de forma detallada la arquitectura resultante. c) En el caso de disponer un único sumador de 1 bit, dibuje el datapath de una arquitectura que permita realizar la suma completa en secuencia. d) Calcule el área y el tiempo total (periodo mínimo × número de ciclos de reloj) de cada una de las implementaciones realizadas. Compare estos resultados y comente de forma razonada cuál(es) de las alternativas realizadas considera más eficiente. DCSE 2010-11

34/34

Diseño de circuitos y sistemas digitales / Bloques aritméticos