Organización del Computador I Verano

Aritmética (3 de 3) Basado en el capítulo 4 del libro de Patterson y Hennessy

Verano 2004 Profesora Borensztejn

MULTIPLICACIONES

• Si el multiplicador y el multiplicando son de n bits, el número de dígitos del producto puede tener hasta 2n bits.

• El algoritmo de multiplicación básico es igual al que todos sabemos:

Repetir 32 veces:

1. Comprobar el bit mas bajo del multiplicador, si es uno, sumar el multiplicando al producto

2. Desplazar el multiplicando 1 bit a la izquierda

3. Desplazar el multiplicador 1 bit a la derecha

10000100

1011

1011

00000000

1100

1011

Hardware del multiplicador

ALU de 64 bits

Multiplicando

Multiplicador

Producto ControlWrite

Shift Left

Shift Right

suma

bit0

32 bits

64 bits

64 bits

El control genera las señales apropiadas, en el momento apropiado:

• Chequea el bit0

• Si bit0=1, activa write del producto

• Activa las señales shift left y shift right.

El multiplicando se inicializa con la mitad superior en cero.

El multiplicando, el multiplicador y el producto se guardan en registros.

Sistemas secuenciales y combinacionales

• Un registro está formado por un conjunto de elementos de memoria• Un elemento de memoria almacena un estado, y su salida en un instante del tiempo depende de

su entrada y de su estado en el instante anterior. Se llaman secuenciales.

• En los sistemas combinacionales, las salidas solo dependen de las entradas. Por ejemplo: la ALU

xt yt+1=f(xt, qt)qt

Sistemas secuenciales

• Por ejemplo, un contador módulo 4.

• Los sistemas secuenciales pueden ser síncronos o asíncronos. En el primer caso, se utiliza una señal de reloj como entrada para señalar los tiempos en que el elemento de estado se debe actualizar.

Q(t)=0

yt+1=1

Q(t)=1 Q(t)=2 Q(t)=3

yt+1=2 yt+1=3 yt+1=3

Elementos de EstadoRelojes

T

Flanco de subida

Flanco de bajada

fT

1

El reloj es una señal con un tiempo de ciclo fijo.

Elementos de Estado : Memoria

• Tienen dos Estados : Q=0 y Q=1

• Pueden ser síncronos o asíncronos

• Síncronos: disparados por flanco o por nivel

• Flip-Flop = biestable síncrono por flanco

Biestable Asíncrono S-R

Q

Q

R

S S R Q Q

0 0 Q Q

1 0 1 0

0 1 0 1

1 1 prohibida

S=set

R=reset

S(t)

R(t)

Q(t)

Q(t)

1

01

0

1

01

0

Q(t+tpd)=S(t)+Q(t)=1+0=0

Q(t+2tpd)=R(t+tpd)+Q(t+tdp)=0+0=1

Q

Q

R

S

Biestable Asíncrono S-R (1-0)

Q(t+tpd)=R(t)+Q(t)=0+1=0

Q(t+2tpd)=S(t+tpd)+Q(t+tdp)=1+0=0

Biestable Asíncrono S-R

S(t)

R(t)

Q(t)

Q(t)

1

01

0

1

01

0

Q=0 Q=1 Q=0

Q

QR

S

Combinación Inestable 1-1

S(t)

R(t)

Q(t)

Q(t)

1

01

0

1

01

0

Q=0 oscilación Estado desconocido

Q

QR

S

Biestables Síncronos: Tipo D

• Se construye a partir del biestable S-R.

• No tiene restricción respecto a las entradas

• Síncrono por flanco.

D

clk

D Q

Q

D Q Q

0 0 1

1 1 0

Registros• Se construyen a partir de n biestables D.• La entrada se carga en el registro cuando la señal Write está

habilitada y el clk da el flanco.• Un registro desplazamiento tiene dos señales adicionales:

una para desplazar a la izquierda y otra a la derecha.

clk

D0..7

D7 D6 D5 D4 D3 D2 D1 D0

Q0..7

WriteShift Left

Shift Right

Mejora al algoritmo de la multiplicación

• Suma el multiplicando a la parte alta del producto, luego de sumar desplaza a la derecha el producto. Trabaja con un sumador de 32 bits.

ALU de 32 bits

Multiplicando

Multiplicador

Producto ControlWrite

Shift Right

suma

bit0

32 bits

32 bits

64 bits

Shift Right

Más mejoras al algoritmo de la multiplicación

• Guarda el multiplicador en la parte baja del registro producto.

ALU de 32 bits

Multiplicando

Producto ControlWrite

suma

bit0

32 bits

64 bits

Shift Right

Multiplicaciones con signo• No funciona!

• ¿Que sucede si el multiplicando es negativo?

• Hay que extender el signo mientras lo acumulamos en el registro producto

00101100

0000

1011

00000000

0100

1011

11101100

0000

111011

00000000

0100

1011

Incorrecto!

Correcto!

Multiplicaciones con signo

• No funciona!

• ¿Que sucede si el multiplicador es negativo?

• No tiene sentido!!!!

Incorrecto!

11000100

1011

1011

00000000

1100

1011

Multiplicaciones con signo• No funciona si interpretamos los

números con signo! • Alternativas:

– Convertir el multiplicando y el multiplicador a números positivos, luego multiplicar, y luego aplicar el signo correspondiente al producto, recordando extender el signo a la izquierda.

– Buscar otros algoritmos

11000100

1011

1011

00000000

1100

1011

Multiplicaciones con signo

00111100= 25+ 24 + 23 + 22 = 26-22

01101111= 26+ 25 + 23 + 22 + 21 + 20 = 27-25 + 24 -20

Esto quiere decir que podemos generar el producto de forma diferente:

restando al inicio de la cadena de unos

sumando al final de una cadena de unos

00111100= 25+ 24 + 23 + 22 = 26-22

01101111= 26+ 25 + 23 + 22 + 21 + 20 = 27-25 + 24 -20

Multiplicaciones con signo

10000100

1011

1011

00000000

1100

1011

Observación:

M * 1100= M* (23+ 22)= M* (24- 22)

Desplazar

Desplazar

Sumar

Sumar

00010100

0000

1011

00000000

1100

1011

Desplazar

Desplazar

Restar

Desplazar

Incorrecto!

Correcto!!

Algoritmo de Both (multiplicar)• Observa de a dos bits del multiplicador

Bit Bit String Acción

Actual Anterior

0 0 cadena de ceros --

0 1 fin cadena de 1’s suma

1 0 principio cadena de 1’s resta

1 1 cadena de 1’s --

El algoritmo cambia el primer paso del algoritmo anterior en función de los dos bits observador. En el segundo paso, se desplaza el producto a la derecha. El número de iteraciones es igual a n.

Algoritmo de Both (multiplicar)

Multiplicando Multiplicador Acción Producto

1101 1100 nada (00) 0000 0000110 0000 0000110 nada (00) 0000 0000

11 0000 000011 restar (10) 0101 0000

1 0010 10001 nada(11) 0010 1000

0001 0100

desplaza

desplaza

desplaza

desplaza

¿Porqué funciona para números con signo?

Demostraciónactual anterior

ai ai-1(ai-1-ai)

sumar b

00

000

10 1

1

-11

1

nada

nada

restar b

El producto, para n=4, se puede escribir de la siguiente manera:

332

221

110

001

2

2

2

2

*b*aa

*b*aa

*b*aa

*b*aa-

DemostraciónObservemos dos términos consecutivos:

3

32

221

110

001

2

2

2

2

*b*aa

*b*aa

*b*aa

*b*aaP -

2

22

11

11

0

221

110

2**2**2**2**

22

babababa

*b*aa *b*aa

1

111

1

111

121

11

*2*22*

2*2*2*2*

abaab

aabaab

DemostraciónRecordando que a-1 =0

10

11

22

33 2*2*2*2** aaaabP

a en C2

Conclusión: El algoritmo de Booth trata al multiplicador como un número en complemento a 2.

MIPS: MULT y MULTU

• Ambas instrucciones dejan la palabra de menos peso en el registro Lo y la palabra de mas peso en el registro Hi.

• Ambas instrucciones ignoran el desbordamiento si el producto no cabe en 32 bits. – Desbordamiento para números sin signo: el registro Hi es distinto de cero. – Desbordamiento para números con signo: el registro Hi es distinto de la extensión de signo del registro Lo.

0 rs rt 0x18

31 26 21 16 11 6 0

0

0 rs rt 0x19

31 26 21 16 11 6 0

0

mult rs, rt

multu rs, rt

La División

El algoritmo de división básico es igual al que todos sabemos:

Repetir 33 veces1. Resto=Resto menos Divisor2. Si Resto es mayor o igual a cero

1. desplazar a la izquierda el cociente y escribir un 1 en su bit menos significativo

Sino1. restaurar el valor original del

Resto, desplazar el cociente e introducir un cero en su bit menos significativo

3. Desplazar el divisor 1 bit a la derecha

4. Ir a 1

1001010 100010011000-

00010 101 1010

1000-

10

Divisor

Cociente

Dividendo

Resto

Hardware del divisor

ALU de 64 bits

Divisor

Cociente

Resto ControlWrite

Shift Right

Shift Left

resta32 bits

64 bits

64 bits

El control genera las señales apropiadas, en el momento apropiado.

El algoritmo es el de prueba y error. Si hubo error (nocabe) hay que restaurar el valor del resto.

El resto se inicializa con el dividendo.

El divisor, a cada iteración se desplaza a la derecha para alinearse con el dividendo. Ocupa inicialmente los 32 bits más altos del registro de 64 bits.

suma

Ejemplo: 7 div 2Iteración Paso Cociente Divisor Resto

0 inicio 0 0010 0000 0000 01111 resto - divisor 0 0010 0000 1110 0111

resto < 0 0 0010 0000 0000 0111desplazar divisor 0 0001 0000 0000 0111

2 resto - divisor 0 0001 0000 1111 0111resto < 0 0 0001 0000 0000 0111desplazar divisor 0 0000 1000 0000 0111

3 resto - divisor 0 0000 1000 1111 1111resto < 0 0 0000 1000 0000 0111desplazar divisor 0 0000 0100 0000 0111

4 resto - divisor 0 0000 0100 0000 0011resto > 0 1 0000 0100 0000 0011desplazar divisor 1 0000 0010 0000 0011

5 resto - divisor 1 0000 0010 0000 0001resto > 0 11 0000 0010 0000 0001desplazar divisor 1 0000 0001 0000 0011

El divisor es de 32 bits, y se va desplazando a la derecha en un registro de 64 bits se puede ahorrar espacio, y hardware si en lugar de desplazar el divisor a la derecha, se desplaza el resto a la izquierda. (mismo cambio que en el multiplicador). La ALU queda ahora de 32 bits.

Mejora al algoritmo de la división

ALU de 32 bits

Divisor

Cociente

Resto ControlWrite

Shift Left

suma32 bits

32 bits

64 bits

Shift Left

resta

Más mejoras al algoritmo de la división

• Guarda el cociente en la parte baja del registro resto.

ALU de 32 bits

Divisor

Resto ControlWrite

suma

32 bits

64 bits

Shift RightShift Left

resta

Ejemplo : 7 div 2 Iteración Paso Divisor Resto

0 inicio 0010 . 0000 0111desplazar resto 0010 . 0000 1110

1 resto - divisor 0010 . 1110 1110resto <0, desplaza resto, 0 en coc. 0010 . 0001 1100

2 resto - divisor 0010 . 1111 1100resto <0, desplaza resto, 0 en coc. 0010 . 0011 1000

3 resto - divisor 0010 . 0001 1000resto >0, desplaza resto, 1 en coc. 0010 . 0011 0001

4 resto - divisor 0010 . 0001 0001resto >0, desplaza resto, 1 en coc. 0010 . 0010 0011

5 desplazar resto 0001 0011

Mismo hw para multiplicar y dividir

ALU de 32 bits

Divisor

Resto ControlWrite

suma

32 bits

64 bits

Shift RightShift Left

ALU de 32 bits

Multiplicando

Producto ControlWrite

suma

bit0

32 bits

64 bits

Shift Right

resta

División con signo

• La solución mas simple es operar con los valores absolutos.

• Luego se ajustan los signos del cociente y del resto.

• Se debe cumplir que:– Dividendo=Cociente*Divisor + Resto– Regla: El dividendo y el resto deben tener el

mismo signo

FIN Aritmética(3 de 3)