ESTRUCTURA Y TECNOLOGÍA DE COMPUTADORES · que se traduce en dos desplazamientos (de 3 y 4 lugares respectivamente) y dos sumas ... derecha para el multiplicador. •Un sumador de

Universidad

Rey Juan Carlos

ESTRUCTURA Y TECNOLOGESTRUCTURA Y TECNOLOGÍÍA DE A DE COMPUTADORESCOMPUTADORES

Circuitos para multiplicación y

división de números en coma fija

Luis Rincón CórcolesLicesio J. Rodríguez-Aragón

Circuitos para multiplicación y división de números en coma fija

2

Programa

Bibliografía.

1. Multiplicación binaria en coma fija.

2. Multiplicación por una constante.

3. Multiplicación por suma - desplazamiento.

4. Multiplicación por grupos solapados.

5. Circuitos para multiplicación rápida.

6. División binaria en coma fija.

7. División por una constante.

8. División con restauración.

9. Instrucciones para multiplicación y división en ensamblador.


3

D.A. PATTERSON, J.L. HENNESSY. Estructura y Diseño de Computadores. Reverté, 2000.

DORMIDO, S. CANTO M.A., MIRA J., DELGADO A.E. Estructura y Tecnología de Computadores. 2ª edición. Sanz y Torres, 2000.

PARHAMI, B. Computer Arithmetic. Oxford University Press, 2000.

P. DE MIGUEL. Fundamentos de los Computadores. 7ª edición. Paraninfo, 1999.

W. STALLINGS. Organización y Arquitectura de Computadores. 5ª edición, Prentice Hall, 2000.

Bibliografía


4

La operación de multiplicación de números en coma fija no suele estar contemplada directamente por las UAL, sino que se suele realizar mediante circuitos específicos:

•Construir un circuito multiplicador rápido exige una circuitería compleja, y las UAL sólo realizan directamente las operaciones aritméticas y lógicas más básicas.•La multiplicación se puede realizar en la UAL mediante una secuencia de sumas y desplazamientos controlados por la unidad de control (UC), si bien no resulta demasiado eficiente.•La multiplicación puede realizarse también mediante un programa en ensamblador que conste de un bucle con una secuencia de sumas y desplazamientos, aunque esto es mucho menos eficiente aún.

Terminología de la multiplicación:M x m = P

•M: multiplicando.•m: multiplicador.•P: producto o resultado.

1. Multiplicación binaria en coma fija


5

12

6

72

1 1 0 0

1 1 0

0 0 0 0

1 1 0 0

1 1 0 0

1 0 0 1 0 0 0

64 + 8 = 72

×multiplicando

resultado

A

B

PRODUCTOBINARIO

(×)0 1

0 0 0

1 0 1

multiplicador

Productos parciales

×

Multiplicación binaria en coma fija

M3 M2 M1 M0

m2 m1 m0

M3·m0 M2 ·m0 M1 ·m0 M0 ·m0

M3·m1 M2 ·m1 M1 ·m1 M0 ·m1

M3·m2 M2 ·m2 M1 ·m2 M0 ·m2

R6 R5 R4 R3 R2 R1 R0

×multiplicando

resultado

multiplicador

Productos parciales

×M m

R


6

Multiplicación binaria en coma fijaLa multiplicación en coma fija es una secuencia de desplazamientos y sumas

con extensión de signo.•Si los operandos están en binario puro, se rellenan con ceros a la izquierda.•Los operandos en complemento a 2 se rellenan a su izquierda con el bit de signo.•En cualquier caso, a la derecha se rellena con ceros.

Ejemplo: multiplicar M=101001102=16610 por m=000110012=2510

0000000010100110 M*m0*20 = M*1: M sin desplazar+ 0000000000000000 M*m1*21 = 0+ 0000000000000000 M*m2*22 = 0+ 0000010100110000 M*m3*23 = M*8: M desplazado 3 lugares+ 0000101001100000 M*m4*24 = M*16: M desplazado 4 lugares+ 0000000000000000 M*m5*25 = 0+ 0000000000000000 M*m6*26 = 0+ 0000000000000000 M*m7*27 = 0

0001000000110110 M*m

El producto de dos números binarios de n bits produce un resultado que puede tener hasta 2n bits de ancho.


7

La multiplicación es una operación costosa en tiempo de ejecución. Por tanto, es aconsejable evitar las multiplicaciones en los programas siempre que sea posible.

Si uno de los operandos (por ejemplo el multiplicador) es una constante conocida en tiempo de compilación (o ensamblaje), es frecuente que el compilador (o ensamblador) sustituya la multiplicación por otras operaciones.

Cuando el multiplicador es una constante potencia de 2, la multiplicación se puede sustituir por un desplazamiento del multiplicando hacia la izquierda.

•Si el multiplicador es 2k, se desplazará el multiplicando k lugares a la izquierda.

•Ejemplo: 11010012 · 23 = 11010010002

2. Multiplicación por un valor constante

00

1-n1-n 2a........2aN ⋅++⋅=

m00

m1-n1-n

m 2a........2a2N ++ ⋅++⋅=⋅


8

Cuando el multiplicador es una constante que no es una potencia de 2, la multiplicación puede descomponerse en una secuencia de instrucciones de desplazamiento y de suma.

•Ejemplo: multiplicar M=101001102=16610 por m=000110012=2510

Descomponemos el multiplicador m=25=16+8+1. Así, la operación será

M*25 = M*(16+8+1) = M*16+M*8+M

que se traduce en dos desplazamientos (de 3 y 4 lugares respectivamente) y dos sumas (consumiríamos una variable intermedia).

101001100000 Desplazamiento de M cuatro posiciones+010100110000 Desplazamiento de M tres posiciones+000010100110 M sin desplazar

1000000110110 Resultado de la suma (del producto)

Multiplicación por un valor constante


9

Vamos a ver:1) El algoritmo de lápiz y papel (o de suma-desplazamiento) para

multiplicar números en binario puro (sin signo) de n bits.2) Un circuito que permite realizar la operación utilizando dicho algoritmo.3) Una versión optimizada del algoritmo, con el correspondiente circuito.4) La versión final del algoritmo, aún más optimizada, acompañada del

correspondiente circuito.

Los circuitos se basan en:• Un sumador, que puede ser el de la UAL.• Varios registros de desplazamiento.• Un circuito secuencial de control, que puede ser parte de la UC.

3. Multiplicación por suma – desplazamiento


10

Multiplicación por S – D: 1ª versión

La multiplicación será un proceso iterativo, y en cada ciclo se realizarán las siguientes operaciones:

1. Se realiza el producto del multiplicando por el bit 0 del multiplicador, con lo cual obtendremos productos parciales que pueden valer lo mismo que el multiplicando desplazado (cuando el bit del multiplicador sea 1) o bien 0 (cuando dicho bit sea nulo).

2. Se desplazará el multiplicando un lugar hacia la izquierda para alinear correctamente los productos parciales, que estarán convenientemente rellenados con ceros a la izquierda y/o a la derecha (para ello, doblaremos el tamaño del multiplicando, e inicialmente lo rellenaremos con ceros a la izquierda).

3. Se desplaza o se rota el multiplicador un lugar hacia la derecha (por esto siempre se multiplica por el bit 0 del multiplicador).

4. Se sumará el producto parcial con la suma acumulada de los productos parciales obtenidos en los pasos anteriores (al principio el producto acumulado será 0).


11

Multiplicación por S – D: 1ª versiónCircuitería necesaria:

•Un registro de 2n bits capaz de realizar desplazamientos unitarios hacia la izquierda para el multiplicando.•Un registro de n bits capaz de realizar desplazamientos unitarios hacia la derecha para el multiplicador.•Un registro de 2n bits para el producto.•Un contador de 0 a n para contar el número de iteraciones.•Un sumador de 2n bits.•Un controlador para generar la secuencia de señales necesaria.

64-bit ALU

Control test

MultiplierShift right

ProductWrite

MultiplicandShift left

64 bits

64 bits

32 bits

Circuito para n = 32 bits con las conexiones y señales de control necesarias.


12


64-bit ALU

Control test


ProductWrite

MultiplicandShift left

64 bits

64 bits

32 bits

Operaciones de la fase de inicio:

1. Iniciar el registro Multiplicando (mitad superior con todos los bits a 0, mitad inferior con el multiplicando)

2. Iniciar el registro Multiplicador

3. Producto ← 0

4. Contador ← 0

Ejercicio: dibujar el diagrama de estados del controlador del circuito.

Producto ← Producto +Multiplicando

Inicio

¿Bit 0 delMultiplicador = 0?

Desplazamiento del registro Multiplicando a la izquierda

¿ Contador = n ?

Sí

1

0

Contador ← Contador+1

No

Desplazamiento del registro Multiplicador a la derecha

Fin


13

Multiplicación por S – D: 1ª versiónEjemplo: n=4, multiplicar M=10102=1010 por m=00112=310

“““Ninguna operación4

“1010 0000“Desplazar Multiplicando a la izqda.

0001 1110“0000Desplazar Multiplicador a la derecha

““0000Desplazar Multiplicador a la derecha





0001 1110““Producto ← Producto + Multiplicando2



0000 1010““Producto ← Producto + Multiplicando1

0000 00000000 10100011Valores iniciales0

ProductoMultiplicandoMultiplicadorPasoIteración


14

Multiplicación por S – D: 2ª versiónEn el circuito anterior sucede que:

•La mitad de los bits del registro Multiplicando siempre son 0, con lo cual sólo la mitad contiene datos útiles.•También sobra la mitad de la UAL, pues está sumando en cada paso el doble de datos de lo estrictamente necesario.

Por tanto, se ideó un algoritmo similar al anterior, pero sin duplicar el tamaño del multiplicador, y utilizando un sumador de n bits.

Puesto que las sumas son de n bits, el registro Producto estará dividido en dos mitades (Productoizq: mitad izquierda; Productoder: mitad derecha; P: registro completo).

•En cada iteración se suma sólo sobre la mitad izquierda.•Los desplazamientos se realizan sobre el registro completo.

Deja de ser necesario desplazar el registro Multiplicando.

Sigue siendo preciso desplazar el registro Multiplicador para consultar siempre su bit 0.


15


•Un registro de n bits para el multiplicando.•Un registro de n bits capaz de realizar desplazamientos lógicos unitarios hacia la derecha para el multiplicador.•Un sumador de n bits.•Un biestable para guardar el acarreo de las sumas (no aparece en el dibujo).•Un registro de 2n bits para el producto, que pueda cargarse en paralelo en su mitad izquierda dejando intacta la mitad derecha; este registro admitirá desplazamientos lógicos unitarios hacia la derecha del registro completo concatenando el biestable de acarreo por la izquierda.•Un contador de 0 a n para contar el número de iteraciones.•Un controlador para generar la secuencia de señales necesaria.

Circuito para n = 32 bits con las conexiones y señales de control necesarias. Multiplier

Shift right

Write

32 bits

64 bits

32 bits

Shift right

Multiplicand

32-bit ALU

Product Control test


16

Multiplicación por S – D: 2ª versiónOperaciones de la fase de inicio:

1. Iniciar el registro Multiplicando

2. Iniciar el registro Multiplicador

3. Producto ← 0

4. Contador ← 0


Write

32 bits

64 bits

32 bits

Shift right

Multiplicand

32-bit ALU

Product Control test


Productoizq ← Productoizq +Multiplicando

Inicio

¿Bit 0 delMultiplicador = 0?

Desplazamiento del registro Producto a la derecha

¿ Contador = n ?

Sí

1

0


No

Desplazamiento del registro Multiplicador a la derecha

Fin


17



0 0001 1110““Desplazar Producto a la derecha

0001 1110“0000Desplazar Multiplicador a la derecha






0 1111 0000““Productoizq ← Productoizq + Multiplicando2



0 1010 0000““Productoizq ← Productoizq + Multiplicando1


ProductoMultiplicandoMultiplicadorPasoIteración


18


En el circuito anterior sucede que:•Al principio, el registro Producto tiene la mitad de sus bits desperdiciados.•A medida que van realizándose pasos del algoritmo, el espacio desaprovechado del registro Producto se va reduciendo.•Los bits del multiplicador van dejando de ser útiles a medida que se van realizando los productos parciales (en realidad se van perdiendo si hacemos desplazamientos sobre el registro Multiplicador y no rotaciones).•El espacio desaprovechado del registro Producto es exactamente igual que el número de bits del multiplicador que necesitamos mantener en cada instante.

Por tanto, se incorporó una mejora al circuito, de forma que el registro Multiplicador desaparece, y el multiplicador se carga inicialmente en la mitad derecha del registro Producto.

En cada iteración, cuando vayamos a consultar un bit del multiplicador, consultaremos el bit menos significativo del registro Producto.


19


•Un registro de n bits para el multiplicando.•Un sumador de n bits.•Un biestable para guardar el acarreo de las sumas (no aparece en el dibujo).•Un registro de 2n bits para el producto, que pueda cargarse en paralelo en su mitad izquierda dejando intacta la mitad derecha, o cargarse en paralelo en su mitad derecha dejando intacta su mitad izquierda; este registro admitirá desplazamientos lógicos unitarios hacia la derecha del registro completo concatenando el biestable de acarreo por la izquierda.•Un contador de 0 a n para contar el número de iteraciones.•Un controlador para generar la secuencia de señales necesaria.


ControltestWrite

32 bits

64 bits

Shift rightProduct

Multiplicand

32-bit ALU


20

Multiplicación por S – D: 3ª versiónOperaciones de la fase de inicio:


2. Iniciar el registro Producto (mitad izquierda a 0, mitad derecha con el multiplicador)

3. Contador ← 0Productoizq ← Productoizq +

Multiplicando

Inicio

¿Bit 0 delProducto = 0?

Desplazamiento del registro Producto a la derecha

¿ Contador = n ?

Sí

1

0


No

Fin

ControltestWrite

32 bits

64 bits

Shift rightProduct

Multiplicand

32-bit ALU



21


““Ninguna operación4

0001 1110“Desplazar Producto a la derecha

0 0011 1100“Desplazar Producto a la derecha



0 1111 0001“Productoizq ← Productoizq + Multiplicando2




ProductoMultiplicandoPasoIteración

Los números utilizados están en binario puro.

El algoritmo se puede adaptar a números en complemento a 2.Con multiplicador negativo en la última iteración hay que restar en vez de sumar.


22

Multiplicación por S – D: ruta de datos 3ª versión

Productoc

A3

A0

A1

A2

Sumador de 4 bits

B3

B0

B1

B2

Multiplicador

Multiplicando

Z7 Z4Z5Z6 Z3 Z0Z1Z2

Reloj

L

S

L

S

ClrCE

L

INICIO

Clr

IniContador 0-3

CE

TC

Clr

Cuenta

Fin

Desplaza

Carga

CONTROLADOR

BitZ0

D


23

El algoritmo de lápiz y papel (o suma – desplazamiento) considera los bits del multiplicador uno a uno, y va generando productos parciales que va sumando y acumulando.

Los algoritmos de multiplicación por grupos solapados (G-S) generan productos parciales considerando los bits del multiplicador por grupos.

Los algoritmos de multiplicación por G-S analizan una “ventana” o grupo de nbits del multiplicador en cada iteración.

En función de los bits de la ventana, se generan uno o varios productos parciales.

De cara a la siguiente iteración, la ventana de bits analizados se desplaza un lugar hacia la derecha (las ventanas o grupos de bits del multiplicador se solapan en las sucesivas interaciones).

El caso de G-S más sencillo es el algoritmo de Booth, que considera grupos solapados de 2 bits en el multiplicador para generar los productos parciales.

4. Multiplicación por grupos solapados


24

Algoritmo de Booth

... = 2k+1-2j

jj+1k-1k

0... 11...110

El algoritmo analiza los bits del multiplicador 2 a 2 de derecha a izquierda:•Si detecta que está al final de una cadena de bits a 1 resta la mitad izquierda delregistro producto menos el multiplicando•Si detecta que está al principio de una cadena de bits a 1 suma la mitad izquierda del registro producto más el multiplicando.

El algoritmo de Booth presentado funciona para operandos en complemento a 2 (para binario puro habría que realizar una pequeña adaptación).

En un número binario, una cadena de bits a 1 equivale a una diferencia de dos potencias de 2 (es una suma de elementos de una progresión geométrica de razón 2).

Nada (en medio de cadena de unos)11

Restar (final de cadena de unos)01

Sumar (inicio de cadena de unos)10

Nada (en medio de cadena de ceros)00

OperaciónMultiplicadori-1Multiplicadori


25

Algoritmo de BoothEn definitiva, el algoritmo de Booth se basa en recodificar el multiplicador y

convertirlo en una secuencia de dígitos con valores 1, 0 y –1 (codificación de dígitos con signo).

1 cuando comienza cadena de bits a 1 (implica hacer una suma).-1 cuando termina cadena de bits a 1 (implica hacer una resta).0 en otro caso.

Ejemplo: recodificación del número 01001110C2

Ejemplo: recodificación del número 11100011C2

Los números en binario puro se recodifican añadiendo un bit a 0 a la izquierda del todo (ejercicio: probarlo).

Número recodificado

Número original 01110010

01 -10010-1

Número recodificado

Número original 11000111

-10 0100-10


26

Ejemplo: multiplicar M=10100110C2=-9010 por m=00011001C2=2510

Recodificamos el multiplicador y realizamos la operación:

0000000001011010 M*m0*(-20) = -1*M+ 1111111101001100 M*m1*21 = 2*M+ 0000000000000000 M*m2*22 = 0+ 0000001011010000 M*m3*(-23) = -8*M+ 0000000000000000 M*m4*24 = 0+ 1111010011000000 M*m5*25 = 32*M+ 0000000000000000 M*m6*26 = 0+ 0000000000000000 M*m7*27 = 0

1111011100110110 M*m

Algoritmo de Booth

Multiplicador recodificado

Multiplicador original 10011000

-10 10-1010


27

Algoritmo de BoothPodría emplearse la circuitería del algoritmo de suma-desplazamiento con

algunas pequeñas modificaciones (se parte de la versión 3):•Utilizar un sumador-restador.•Despreciar el bit de acarreo superior, ya que se manejan datos en complemento a 2.•Realizar desplazamientos aritméticos (extendiendo el signo).•Añadir un bit que se concatenará a la derecha del registro Producto, iniciado con un 0 y que se modificará cada vez que se haga un desplazamiento sobre Producto (la ventana de bits analizada en cada iteración está formada por el bit menos significativo del registro Producto y el bit añadido a su derecha).

ControltestWrite

32 bits

64 bits

Shift rightProduct

Multiplicand

32-bit ALU


28

Algoritmo de Booth



2. Iniciar el registro Producto (mitad izquierda a 0, mitad derecha con el multiplicador, bit p-1 a 0)

3. Contador ← 0

Aclaraciones:•p0: bit menos significativo del registro Producto.•p-1: bit añadido a la derecha del registro Producto.•Producto # p-1: registro Producto concatenado con el bit p-1.

ControltestWrite

32 bits

64 bits

Shift rightProduct

Multiplicand

32-bit ALU


Productoizq ← Productoizq -Multiplicando

Inicio

¿ p0p-1 ?

Desplazar Producto # p-1 a la derecha

¿ Contador = 0 ?

Fin

0011

Sí


10 01

Productoizq ← Productoizq +Multiplicando

No


29

Algoritmo de Booth

Ejemplo: n=4, multiplicar M=1010C2= -610 por m=0011C2=310

El multiplicando cambiado de signo es –M=0110C2


1110 1110“Desplazar Producto a la derecha






0110 0011 0“Productoizq ← Productoizq - Multiplicando1


ProductoMultiplicandoPasoIteración

Los números utilizados están en complemento a 2.El algoritmo se puede adaptar a números en binario puro.

Si el multiplicador comienza por 1, realizar un ajuste final sumando el multiplicador a la mitad izquierda del registro Producto.


30

En vez de ejecutar la multiplicación a través de un proceso iterativo de sumas y desplazamientos regulado por un controlador secuencial, el producto se puede realizar a partir de un sumador de múltiples sumandos (los productos parciales) convenientemente organizados.

Para construir multiplicadores de altas velocidades caben dos posibilidades:•Sumar los productos parciales rápidamente.•Reducir el número de productos parciales que hay que sumar.

Para sumar los productos parciales más rápido se puede recurrir por ejemplo a:•Las matrices de sumadores.•Los sumadores en árbol.

Para reducir el número de productos parciales se puede recurrir por ejemplo a:•Multiplicadores en base mayor que 2 (normalmente en base 4).•Recodificación de Booth utilizando grupos solapados de 3 ó más bits.

Otra técnica: guardar todos los posibles resultados en una ROM.•¡La ROM tendría 22n posiciones de 2n bits cada una!

5. Circuitos para multiplicación rápida


31

Multiplicar consiste en sumar varios productos parciales desplazados.

Primer enfoque para multiplicar rápidamente:1) Calcular los productos parciales mediante

puertas AND2) Sumar dichos productos parciales

mediante sumadores tradicionales.

Pega: retardo total grande.

Para mejorar las prestaciones del circuito, pueden utilizarse otros enfoques:

• Matriz de CSA.• Árbol de Wallace.• Árbol de Dadda.

También es posible multiplicar números con signo:

• Multiplicador de Pezaris.• Multiplicador de Baugh-Wooley.

Matriz de sumadores con acarreo propagado


32

La operación de división de números en coma fija no suele estar contemplada directamente por las UAL, sino que se suele realizar mediante circuitos específicos:

•Construir un circuito divisor rápido es aún más complicado que en el caso del multiplicador.•La división se puede realizar en la UAL mediante una secuencia de sumas, restas, comparaciones y desplazamientos controlados por la unidad de control (UC), si bien no resulta demasiado eficiente.•La división puede realizarse también mediante un programa en ensamblador que conste de un bucle con una secuencia de sumas, restas, comparaciones y desplazamientos, aunque esto es mucho menos eficiente aún.•Antes de dividir, los circuitos deben comprobar obligatoriamente si el divisor es igual o distinto de 0 para evitar desbordamientos.

Terminología de la división: D / d = C d x C + R = D•D: dividendo.•d: divisor.•C: cociente.•R: resto.

6. División binaria en coma fija


33

Es fácil elegir cada dígito del cociente, ya que sólo puede valer 0 ó 1.

Si el dividendo parcial es mayor o igual que el divisor, el siguiente dígito del cociente es 1, si no es 0.

112 8

0 14

1 1 1 0 0 0 0 1 0 0 0

1 0 0 0 1 1 1 0

0 1 1 0 01 0 0 00 1 0 0 0

1 0 0 00 0 0 0 0

0 0 0 00 0 0 0

cociente

resto

divisordividendo

-

-

-

-

División binaria en coma fija


34

La división es una operación costosa en tiempo de ejecución. Por tanto, es aconsejable evitar las multiplicaciones en los programas siempre que sea posible.

Si el divisor es una constante conocida en tiempo de compilación (o ensamblaje), el compilador (o ensamblador) puede sustituir la división por otras operaciones.

Cuando el divisor es una constante potencia de 2, el cociente de la división se puede obtener mediante por un desplazamiento del dividendo hacia la derecha (¡esto es cierto sólo para números en binario puro!).

•Si el divisor es 2k, el cociente se obtiene desplazando el dividendo k lugares a la derecha.•Los bits sobrantes (parte fraccionaria del resultado) constituirían el resto de la división entera, convenientemente escalado por 2k.

•Ejemplo: 11010012 / 23 ⇒ cociente = 11012, resto = 0012

Si el divisor es una constante que no es potencia de 2, el cálculo es complicado.

7. División por un valor constante

00

1-n1-n 2a........2aN ⋅++⋅= m0

0m1-n

1-nm2a........2a

2

N −− ⋅++⋅=


35

8. División con restauraciónEn primer lugar se presentará un algoritmo básico para dividir números en

binario puro (sin signo) de n bits.

A continuación se presentará un circuito que permite realizar la operación utilizando dicho algoritmo.

Seguidamente se presentará una versión optimizada del algoritmo, con el correspondiente circuito.

Se incluirá una tercera versión del algoritmo aún más optimizada acompañada del correspondiente circuito.

Finalmente se indicarán las modificaciones que será preciso introducir en los circuitos para poder dividir números con signo.

Los circuitos que vamos a ver a continuación se basan en:•Un sumador/restador, que puede ser el de la UAL.•Varios registros de desplazamiento.•Un circuito secuencial de control, que puede ser parte de la UC.


36

División con restauración: 1ª versiónLa división se realizará más o menos igual que como se hace con lápiz y papel.

Será un proceso iterativo de n+1 ciclos, en cada uno de los cuales se realizarán las siguientes operaciones:

1. Se resta el dividendo parcial menos el divisor. Si la resta es positiva seguimos por el paso 2, y si es negativa vamos al paso 3.

2. Resta positiva: el dividendo parcial cabe en el divisor. Por tanto, se añade un 1 al cociente, y se desplaza el mismo un lugar a la derecha. Ir a 4.

3. Resta negativa: el dividendo parcial no cabe en el divisor. Por tanto, se añade un 0 al cociente y se desplaza el mismo un lugar a la derecha. Se restaura el dividendo parcial sumándole el divisor. Ir a 4.

4. Se desplaza el divisor un lugar a la derecha.


37

Circuitería necesaria:•Un registro de 2n bits que inicialmente contendrá el dividendo.•Un registro de 2n bits capaz de realizar desplazamientos unitarios hacia la derecha para el divisor.•Un registro de n bits capaz de realizar desplazamientos unitarios hacia la izquierda para el cociente.•Un contador de 0 a n+1 para contar el número de iteraciones.•Un sumador / restador de 2n bits.•Un controlador para generar la secuencia de señales necesaria.


División con restauración: 1ª versión

64-bit ALU

Controltest

QuotientShift left

RemainderW rite

DivisorShift right

64 bits

64 bits

32 bits


38


1. Iniciar el registro Resto (mitad superior con todos los bits a 0, mitad inferior con el dividendo).

2. Iniciar el registro Divisor (mitad superior con el divisor, mitad inferior con todos los bits a 0).

3. Cociente ← 0

4. Contador ← 0


64-bit ALU

Controltest

QuotientShift left

RemainderW rite

Divisor

Shift right

64 bits

64 bits

32 bits

Ejercicio propuesto: dibujar el diagrama de estados del controlador del circuito.

Inicio

Resto←Resto-Divisor

¿Resto < 0?No Sí

No

Sí

Desplazar Cociente 1 bithacia la izquierda

Cociente0←1

Resto←Resto+DivisorDesplazar Cociente 1 bit

hacia la izquierdaCociente0←0

Contador←Contador+1

¿Contador=n+1?

Fin

Desplazar Divisor 1 bithacia la derecha


39

Ejemplo: n=4, dividir D=10102=1010 por d=00112=310

0000 0001““Resto ← Resto - Divisor5

“0000 0011“Desplazar Divisor a la derecha

““0011Resto≥0⇒ sll Cociente, Cociente0=1


““0001Resto≥0⇒ sll Cociente, Cociente0=1

0000 00010000 00010011Desplazar Divisor a la derecha


0000 1010“0000Resto<0⇒+Divisor, sll Cociente, Cociente0=0





“0001 10000001Desplazar Divisor a la derecha




RestoDivisorCocientePasoIteración



40

En el circuito anterior sucede que:•La mitad de los bits del divisor no contienen información útil.•Como consecuencia de lo anterior, también sobra la mitad de la UAL, pues está sumando y/o restando en cada paso el doble de datos de lo estrictamente necesario.

Por tanto, se ideó un algoritmo similar al anterior, pero sin duplicar el tamaño del divisor, y utilizando un sumador / restador de n bits.

Puesto que las sumas y restas son de n bits, el registro Resto estará dividido en dos mitades (Restoizq: mitad izquierda; Restoder: mitad derecha; Resto: registro completo).

•En cada iteración se suma y/o resta sólo sobre la mitad izquierda.•Los desplazamientos se realizan sobre el registro completo.

Deja de ser necesario desplazar el registro Divisor.Sigue siendo preciso desplazar el registro Cociente para escribir en su bit 0 el

nuevo dígito calculado en cada paso.El resto queda en la mitad izquierda del registro Resto.Nunca puede haber un 1 en el primer dígito del cociente: por consiguiente,

pueden reordenarse el desplazamiento y la resta de forma que se elimine una iteración del algoritmo.



41

Circuitería necesaria:•Un registro de n bits para el divisor.•Un registro de n bits capaz de realizar desplazamientos lógicos unitarios hacia la izquierda para el cociente.•Un sumador / restador de n bits.•Un registro de 2n bits para el resto, que pueda cargarse en paralelo en una mitaddejando intacta la otra mitad; este registro admitirá desplazamientos lógicos unitarios del registro completo hacia la izquierda.•Un contador de 0 a n para contar el número de iteraciones.•Un controlador para generar la secuencia de señales necesaria.



Controltest

QuotientShift left

Write

32 bits

64 bits

32 bits

Shift left

Divisor

32-bit ALU

Remainder


42


1. Iniciar el registro Divisor

2. Iniciar el registro Resto (mitad inferior con el dividendo, mitad superior con todos sus bits a 0)

3. Cociente ← 0

4. Contador ← 0

Controltest

QuotientShift left

Write

32 bits

64 bits

32 bits

Shift left

Divisor

32-bit ALU

Remainder



Inicio

Desplazar Resto 1 bithacia la izquierda

Restoizq←Restoizq-Divisor

¿Resto < 0?No Sí

No

Sí


Desplazar Cociente 1 bithacia la izquierda

Cociente0←1

Restoizq←Restoizq+DivisorDesplazar Resto 1 bit

hacia la izquierdaDesplazar Cociente 1 bit

hacia la izquierdaCociente0←0


¿Contador=n?

Desplazar Restoizq 1 bithacia la derecha

Fin


43



0011

0011

0001

“

0000

“

0000

“

“

0000

Cociente

0000 10100011Valores iniciales0

0001 0100“Desplazar Resto a la izquierda

0001 0000“Desplazar Restoizq a la derechaAjuste final

0010 0000“Resto≥0⇒ sll Resto, sll Cociente, Cociente0=1

0001 0000“Restoizq ← Restoizq – Divisor4

0100 0000“Resto≥0⇒ sll Resto, sll Cociente, Cociente0=1


0101 0000“Resto<0⇒ +Divisor, sll Resto, sll Cociente, Cociente0=0


0010 1000“Resto<0⇒ +Divisor, sll Resto, sll Cociente, Cociente0=0


RestoDivisorPasoIteración


44

En el circuito anterior sucede que:•Al principio, el registro Resto está completamente ocupado.•A medida que van realizándose pasos del algoritmo, parte del contenido del registro Resto comienza a estar desaprovechado.•Según realizamos pasos, obtenemos los bits del cociente uno a uno.•El espacio desaprovechado del registro Resto es exactamente igual que el número de bits del cociente que tenemos calculados en cada instante.

Por tanto, se incorporó una mejora al circuito, de forma que el registro Cociente desaparece.

El dividendo se carga inicialmente en la mitad derecha del registro Resto.

En cada iteración, cuando obtengamos un bit del cociente, lo almacenaremos en el bit menos significativo del registro Resto.

Al final el cociente queda en la mitad menos significativa del registro Resto, mientras que el resto queda en la mitad más significativa de dicho registro.



45

Circuitería necesaria:•Un registro de n bits para el divisor.•Un sumador / restador de n bits.•Un registro de 2n bits para el resto y el cociente, que pueda cargarse en paralelo en su mitad izquierda dejando intacta la mitad derecha, o cargarse en paralelo en su mitad derecha dejando intacta su mitad izquierda; este registro admitirádesplazamientos lógicos unitarios hacia la izquierda del registro completo. •Un contador de 0 a n para contar el número de iteraciones.•Un controlador para generar la secuencia de señales necesaria.



Write

32 bits

64 bits

Shift leftShift right

Remainder

32-bit ALU

Divisor

Controltest


46


1. Iniciar el registro Divisor

2. Iniciar el registro Resto (mitad izquierda a 0, mitad derecha con el dividendo)

3. Contador ← 0


Write

32 bits

64 bits

Shift leftShift right

Remainder

32-bit ALU

Divisor

Controltest


Inicio


Restoizq←Restoizq-Divisor

¿Resto < 0?No Sí

No

Sí


Resto0←1

Restoizq←Restoizq+DivisorDesplazar Resto 1 bit

hacia la izquierdaResto0←0


¿Contador=n?

Desplazar Restoizq 1 bithacia la derecha

Fin


47



0000 10100011Valores iniciales0

0001 0100“Desplazar Resto a la izquierda

0001 0011“Desplazar Restoizq a la derechaAjuste final

0010 00100010 0011

“Resto≥0⇒ Desplazar Resto a la izquierdaResto0=1


0100 00000100 0001

“Resto≥0⇒ Desplazar Resto a la izquierdaResto0=1


0010 10000101 00000101 0000

“Resto<0⇒ Restoizq ← Restoizq + DivisorDesplazar Resto a la izquierdaResto0=0


0001 01000010 10000010 1000

“Resto<0⇒ Restoizq ← Restoizq + DivisorDesplazar Resto a la izquierdaResto0=0


RestoDivisorPasoIteración


48

División con restauración

Los algoritmos y circuitos mostrados dividen números dados en binario puro.•Puede hacerse división con restauración para números en complemento a 2, aunque el algoritmo es complicado.

División de números en complemento a 2: se puede hacer pasando los operandos a positivos antes de hacer la división, y ajustando los signos del cociente y/o el resto si es preciso:

•Si el signo del dividendo y el del divisor coinciden, el cociente es positivo, y en caso contrario es negativo.•El signo del resto es el mismo que el del dividendo.


49

MIPS•La multiplicación y la división emplean dos registros especiales para guardar los resultados: Hi y Lo.•En la multiplicación, la parte más significativa del resultado queda en Hi y la menos significativa en Lo.•En la división, el cociente queda en Lo y el resto en Hi.•Instrucciones de multiplicación:

Con signo: mult.Sin signo: multu.

•Instrucciones de división:Con signo: div.Sin signo: divu.

MC68000:•Multiplicación (muls, mulu): operandos de 16 bits, resultado de 32 bits.•División (divs, divu): dividendo de 32 bits, divisor de 16 bits, cociente de 16 bits, resto de 16 bits.

9. Multiplicación y división en ensamblador

Documents

ESTRUCTURA Y TECNOLOGÍA DE COMPUTADORES · que se traduce en dos desplazamientos (de 3 y 4 lugares respectivamente) y dos sumas ... derecha para el multiplicador. •Un sumador de