01/03/2012
1
Arquitectura de Computadoras Primavera 2012
1
Números con y sin signo
Suma y resta
Operaciones Lógicas
Construyendo una ALU
Multiplicación
División
Punto Flotante 2
Los números son representados en base 2 Cada digito de un número binario es llamado
bit Los números sin signo son representados de
la siguiente manera:
3
0
0
1
1
30
30
31
3110 2222 xxxxY
Ejemplo:
El número binario 10112 es la representación de:
4
10
0123
11
1208
11214081
21212021
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5
MSB Bit Mas Significativo LSB Bit Menos Significativo
Palabras de 32-bits pueden representar 232 diferentes patrones, por lo cual estas combinaciones representan los números de 0 a 232 -1
0000 0000 0000 0000 0000 0000 0000 0000 = 010
0000 0000 0000 0000 0000 0000 0000 0001 = 110
………
1111 1111 1111 1111 1111 1111 1111 1110 = 429496729410
1111 1111 1111 1111 1111 1111 1111 1111 = 429496729510
La representación que es fácilmente implementada en hardware es el Complemento a 2´s
El complemento a 2´s se obtiene de
6
xx
xx
xx
1
01
1
0
0
1
1
30
30
31
31 2222 xxxx
01/03/2012
2
Ejemplo: obtener la representación de -210
La representación en complemento a 2´s se realiza invirtiendo todos los bits y sumando uno
7
00000010210
11111110
1
11111101
Extensión de Signo
En ocasiones se requiere operar con números de diferentes longitudes
Por ejemplo: se desea sumar un número de 16 bits con un número de 8 bits.
Para operarlos se requiere realizar la extensión de signo del operando mas pequeño
Ejemplo:
8
11111110 1111101111111111
Los números hexadecimales se representan con 16 dígitos que se muestran a continuación
Hexadecimal Binario
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
Hexadecimal Binario
8 1000
9 1001
A 1010
B 1011
C 1100
D 1101
E 1110
F 1111
9
Un número binario se puede convertir a hexadecimal de la siguiente forma
0 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1
6 A F 1
10
Un número hexadecimal se puede convertir a binario de la siguiente forma
Las mismas reglas aplican para números octales, pero los grupos de bits se reducen a 3
1 1 1 0 1 1 0 0 0 1 1 1 0 0 1 0
E C 7 2
11
En la suma, los dígitos (bits) son sumados de derecha a izquierda, con acarreos pasados al siguiente digito de la izquierda.
Los bits se suma siguiendo estas reglas
0
+ 0
0
0
+ 1
1
1
+ 0
1
1
+ 1
1 0
Acarreo Carry
12
01/03/2012
3
Ejemplo: Sumar 3 = 011 + 1 =001
Ejemplo: suma 6 y 7 representados en 16 bits
1 1
0 1 1
+ 0 0 1
1 0 0
acarreos
1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1
13
La resta se realiza de la misma forma que la suma pero siguiendo estas reglas
0
- 0
0
0
- 1
1 1
1
- 0
1
1
- 1
0
Prestado Borrow
14
Ejemplo: resta 3 = 011 - 1 =001
Ejemplo: Resta 7 - 6 representados en 16 bits
0 1 1
- 0 0 1
0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
- 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
15
La resta también se puede obtener usando el complemento a 2’s.
El operando apropiado se complementa a 2’s y se suman.
Ejemplo 1 1 1 1 1 1 1 1 1 1 1 1 1 1
7 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
-6 + 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
16
Un sobreflujo ocurre cuando el resultado de una operación no puede ser representado con el hardware disponible
En otras palabras si el resultado no puede ser representado en el número de bits usados, por ejemplo 32-bits
El sobreflujo solo puede producirse cuando se suman operandos con el mismo signo
17
Cuando los números tienen signos opuestos. El resultado no puede generar un sobreflujo
Esto se debe a que el resultado no puede ser mayor que los números operados.
Ejemplo:
-10+4 = -6
18
01/03/2012
4
El sobreflujo en la resta tiene el principio opuesto.
Números con signos diferentes pueden producir un sobreflujo ejemplo: 6 – (-8) = 14
Números con el mismo signo no producen sobreflujo Ejemplo: -14 – (-20) = 6
19
Como determinar cuando un sobreflujo se ha producido?
La representación usada es complemento a 2´s entonces el sobreflujo se puede determinar en base al bit de signo
Operación Operando A Operando B Resultado indicando
overflow
A + B ≥ 0 ≥ 0 < 0
A + B < 0 < 0 ≥ 0
A – B ≥ 0 < 0 < 0
A – B < 0 ≥ 0 ≥ 0
20
Sumamos 3 + 3 = 6 representados en 3 bits en complemento a 2´s
El resultado es un número negativo -2 = 110 por lo cual se produce un sobreflujo
1 1
0 1 1
+ 0 1 1
1 1 0
21
Sumamos -3 + (-2) = -5 representados en 3 bits en complemento a 2´s
El resultado es un número positivo 3 = 011 por lo cual se produce un sobreflujo
1 0 1
+ 1 1 0
1 0 1 1
22
Sumamos 7 + (-6) = 1 representados en 4 bits en complemento a 2´s
El resultado es un número positivo 1 = 0001 por lo cual no se produce sobreflujo
1 1
0 1 1 1
+ 1 0 1 0
1 0 0 0 1
23
El sobreflujo solo se detecta en operaciones con signo
En la arquitectura MIPS, se distingue entre estas dos representaciones por medio de adicional la letra u a las instrucciones para indicar que no se requiere detectar overflow
add, addi y sub realizan operaciones con signo
addu, addiu, subu no consideran el signo
24
01/03/2012
5
Las operaciones lógicas que se realizan incluyen
Corrimiento Izquierdo
Corrimiento derecho
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0
25
AND bit por bit
OR bit por bit
0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1
26
Unidad Aritmética Lógica (ALU) es el corazón del datapath se encarga de realizar todas las operaciones aritméticas y lógicas
Debido a que la arquitectura que estamos estudiando es de 32-bits necesitamos una ALU que opere números de 32-bits
Esta ALU será construida a partir de ALUs de 1 bit
27
Las operaciones lógicas son fáciles porque se mapean directamente a compuertas
A
B C
B
A
D
A E
Compuerta AND
Compuerta OR
Inversor
A B A•B A+B A
0 0 0 0 1
0 1 0 1 1
1 0 0 1 0
1 1 1 1 0
28
Para decidir entre que operación deseamos realizar, se utiliza un multiplexor
CTRL Y
0 A
1 B
CTRLBCTRLAY
A
B
CTRL
Y
0
1
Y CTRL
A
B
29
Diseño de ALU con dos operaciones:
AND
OR
0
1
A
B
operación
Resultado
30
01/03/2012
6
Sum
s
0
1
1
0
Carry
c
0
0
0
1
0
0 +
0
1 +
1 0 0 0
1
0 +
1 0
1
1 +
0 1
x
y +
s c
Sum Carry
(a) The four possible cases
x y
0
0
1
1
0
1
0
1
(b) Truth table
x
y s
c
HAx
y
s
c
(c) Circuit (d) Graphical symbol
Sum
s
0
1
1
0
Carry
c
0
0
0
1
0
0 +
0
1 +
1 0 0 0
1
0 +
1 0
1
1 +
0 1
x
y +
s c
Sum Carry
(a) The four possible cases
x y
0
0
1
1
0
1
0
1
(b) Truth table
x
y s
c
HAx
y
s
c
(c) Circuit (d) Graphical symbol
Sum
s
0
1
1
0
Carry
c
0
0
0
1
0
0 +
0
1 +
1 0 0 0
1
0 +
1 0
1
1 +
0 1
x
y +
s c
Sum Carry
(a) The four possible cases
x y
0
0
1
1
0
1
0
1
(b) Truth table
x
y s
c
HAx
y
s
c
(c) Circuit (d) Graphical symbol
31
Cin A B Cout S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
1 1 1 1 0
1 0 0 0 1
1 1 1 1 0
1 1 0 1 0
1 1 1 1 1
inCBAS
ininout BCACABC 32
(b) Truth table
w 0 w 1
0
0
1
1
1
0
1
f s 1
0
s 0
w 2 w 3
f
s 1
w 0
w 1
00
01
s 0
w 2
w 3
10
11
(a) Graphic symbol f
(c) Circuit
s 1
w 0
w 1
s 0
w 2
w 3
33
0
w 0
w 1
0
1
w 2
w 3
0
1
f 0
1
s 1
s
34
Nuestro diseño de ALU de 1-bit incluyendo las siguientes operaciones
AND
OR
SUMA
+
00
01
10
11
Carry Out
A
B
Carry In
Resultado
Operación
35
1-bit ALU A0
B0
Carry In
1-bit ALU A1
B1
1-bit ALU A31
B31
Carry Out
Operación
Resultado 0
Resultado 1
Resultado 31
36
01/03/2012
7
Para incluir la resta dentro de la ALU, debemos considerar como obtener el complemento a 2´s de un número
Considere que pasaría si el primer carry de entrada fuera uno en lugar de cero.
El resultado sería
1BA
37
Ahora considere invertir el operando B
La resta puede ser implementada simplemente por medio de invertir el operando B y poner el carry de entrada a 1
BA
BA
BABA
)1(1
38
+
00
01
10
11
Carry Out
A
B
Carry In
Resultado
Operación
0
1
Inversión
39
ALU puede realizar: suma, resta, AND y OR, pero nos falta implementar las comparaciones
SLT (Set Less Than)
slt $t0,$t1,$t2
manera otra de 0
21 Si 10
ttt
40
Considere la resta A-B
Debemos poner el LSB
1 si a<b, es decir el resultado es negativo
cero de otra manera, i.e., resultado positivo
BA
BBBABA
00
41
En complemento a 2’s el bit del signo es 1 para números negativos
0 para números positivos
El bit del signo después de restar A-B puede darnos el resultado adecuado
El sumador debe tener una salida extra en el bit mas significativo que debe ser retroalimentada al bit menos significativo
42
01/03/2012
8
+
00
01
10
11
Carry Out
A
B
Carry In
Resultado
Operación
0
1
Inversión
Less
43
+
00
01
10
11
Carry Out
A
B
Carry In
Resultado
Operación
0
1
Inversión
Less
Set
44
1-bit ALU
A0
B0
Carry In
1-bit ALU A1
B1
1-bit ALU
A31
B31
Carry Out
Resultado 0
Resultado 1
Resultado 31
Operación
0
0 Set
Less
Inversión
45
Sobreflujo: el resultado es muy grande (o muy pequeño) para ser representado propiamente
Ejemplo: - 8 < = números binarios de 4-bit <= 7
Sobreflujo ocurre cuando:
2 números positivos y la suma es negativa
2 números negativos y la suma es positiva
Como ejercicio prueben que el sobreflujo puede ser detectado usando lo siguiente:
Acarreo de entrada al MSB Acarreo de salida del MSB
0 1 1 1
0 0 1 1 +
1 0 1 0
1
= 7
= 3
1
= – 6
1 0
= – 4
= – 5
= 7
1 1 0 0
1 0 1 1 +
0 1 1 1
1 0
46
Carry into MSB Carry out of MSB Para N-bit ALU: overflow = Cin[N - 1] XOR Cout[N - 1]
A0
B0
1-bit ALU
Result0
Cin0
Cout0
A1
B1
1-bit ALU
Result1
Cin1
Cout1
A2
B2
1-bit ALU
Result2
Cin2
A3
B3
1-bit ALU
Result3
Cin3
Cout3
Overflow
X Y X XOR Y
0 0 0
0 1 1
1 0 1
1 1 0
47
+
00
01
10
11
Carry Out
A
B
Carry In
Resultado
Operación
0
1
Inversión
Less Set
Overflow
48
01/03/2012
9
1-bit ALU
A0
B0
Carry In
1-bit ALU A1
B1
1-bit ALU
A31
B31
Carry Out
Resultado 0
Resultado 1
Resultado 31
Operación
0
0 Overflow
Set
Less
Inversión
49
Las instrucciones que nos falta considerar son los saltos condicionales
beq branch if equal
bne branch if not equal
En ambos casos se comparan dos registros y
la condición de salto es que los registros sean iguales o diferentes
50
La forma mas fácil de comprobar si dos números son iguales es restarlos
Si son diferentes entonces
BABA 0
BABA 0
51
Realmente lo que necesitamos agregar a nuestro diseño de ALU es una manera de detectar cuando el resultado es cero
La forma mas fácil de detectar el cero es:
03031 RRRcero
52
1-bit ALU
A0
B0
Carry In
1-bit ALU A1
B1
1-bit ALU
A31
B31
Carry Out
Resultado 0
Resultado 1
Resultado 31
Operación
0
0 Overflow
Set
Less
Inversión
Cero
A
B
Resultado
Overflow Cero
Carry Out
Operación
53
0 0 1 1
0 0 1 0 +
0 1 0 1
1
= 3
= 2
0
= 5
0 0
Sumador Completo
A0 B0
Cin0 Cout0
Sumador Completo
A1 B1
Sumador Completo
A2 B2
Sumador Completo
A3 B3
Cout1 Cout2 Cout3
54 S0 S1 S2 S3
01/03/2012
10
x 0 y 0
g 0 p 0
s 0
Etapa 0
c 0
x 1 y 1
g 1 p 1
s 1
Etapa 1
c 1
55
x 1 y 1
g 1 p 1
s 2
Etapa 1
c 2
c 3
x 1 y 1
g 1 p 1
s 3
Etapa 1
c 4
Examine la tabla de verdad del sumador completo
0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1
a b Cin Cout S
Cout = a • b + Cin • (a + b)
S = a’b’c + a’bc’ + ab’c’ + abc
= a b c
a
b
Cin
Cout
S
In general, for bit i: ci+1 = ai bi + ci (ai+bi)
where ci = Cout, ci-1= Cin
Obtenga el acarreo de salida Ci en terminos de las entradas principales: ci+2 = ai+1 bi+1 + ci+1 (ai+1 + bi+1)
=ai+1 bi+1 + (ci(ai + bi) + ai bi) (ai+1 + bi+1)
ai+1 bi+1
ci+2
Si+1
FAi+1 ci+1
Si
ai bi
ci FAi
• Creamos una funciones auxiliares:
Generación: gi= ai bi y Propagación: pi = ai + bi
c1 = a0 b0 + c0(a0 + b0) = g0 + (p0 c0)
c2 = a1 b1 + (a1 + b1) (a0 b0 + c0(a0 + b0)) = g1 + p1 g0+ p1 p0 c0
58
x 1 y 1
g 1 p 1
x 0 y 0
c 2
x 0 y 0
c 0
c 1
g 0 p 0
A B C-out 0 0 0 “Kill” 0 1 C-in “propaga” 1 0 C-in “propaga” 1 1 1 “genera”
P = A xor B G = A and B
Cin
C1 =G0 + C0 P0
C2 = G1 + G0 P1 + C0 P0 P1
C3 = G2 + G1 P2 + G0 P1 P2 + C0 P0 P1 P2
G
C4 = . . .
P
A0
B0
S0 G0 P0
A1
B1
S1 G1 P1
A2
B2
S2 G2 P2
A3
B3
S3 G3 P3
p0
c0g0
c1
p0
c0g0
p1g1
c2
p0
c0g0
p1g1
p2g2
p3g3
c4
c1 = g0 + c0 p0
c2 = g1 + g0p1 + c0 p0 p1
c4 = g3 + g2 p3 + g1 p2 + g0 p1 p2 + c0 p0 p1 p2 p3
01/03/2012
11
C2 = G1 + G0 P1 + C0 P0 P1
C3 = G2 + G1 P2 + G0 P1 P2 + C0 P0 P1 P2
C1 =G0 + C0 P0
G P
C4 = . . .
C L A
4-bit Adder
4-bit Adder
4-bit Adder
G0 P0
C0 • Carries are generated by CLA, not RC adder
62
Divide y Vencerás Formula soluciones en términos de componentes sencillos
Diseña cada uno de los componentes (Sub-problemas)
Generación y Prueba Dada una colección de bloques de construcción, busca formas para
integrarlos y que alcancen los requerimientos
Refinamiento (ejemplo, carry lookahead) Resuelve la mayor parte del problema (i.e., ignora algunas
restricciones o casos especiales), examine y corrige los problemas o desventajas que se te presenten.
Trabaja en puntos que sabes como resolver Lo s puntos desconocidos serán “obvios” cuando empieces a
progresar.