Chapter Four
Arithmetic for Computers
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-1
Arithmetic
•
•
Where we've been:
– Performance (seconds, cycles, instructions)
– Abstractions:
Instruction Set Architecture
Assembly Language and Machine Language
What's up ahead:
– Implementing the Architecture
operation
a
32
ALU
result
32
b
32
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-2
Numbers
•
•
•
•
Bits are just bits (no inherent meaning)
— conventions define relationship between bits and numbers
Binary numbers (base 2)
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001...
decimal: 0...2n-1
Of course it gets more complicated:
numbers are finite (overflow)
fractions and real numbers
negative numbers
e.g., no MIPS subi instruction; addi can add a negative number)
How do we represent negative numbers?
i.e., which bit patterns will represent which numbers?
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-3
Possible Representations
•
Sign Magnitude:
000 = +0
001 = +1
010 = +2
011 = +3
100 = -0
101 = -1
110 = -2
111 = -3
•
•
One's Complement
Two's Complement
000 = +0
001 = +1
010 = +2
011 = +3
100 = -3
101 = -2
110 = -1
111 = -0
000 = +0
001 = +1
010 = +2
011 = +3
100 = -4
101 = -3
110 = -2
111 = -1
Issues: balance, number of zeros, ease of operations
Which one is best? Why?
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-4
MIPS
•
32 bit signed numbers:
0000
0000
0000
...
0111
0111
1000
1000
1000
...
1111
1111
1111
0000 0000 0000 0000 0000 0000 0000two = 0ten
0000 0000 0000 0000 0000 0000 0001two = + 1ten
0000 0000 0000 0000 0000 0000 0010two = + 2ten
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1110two
1111two
0000two
0001two
0010two
=
=
=
=
=
+
+
–
–
–
2,147,483,646ten
2,147,483,647ten
2,147,483,648ten
2,147,483,647ten
2,147,483,646ten
maxint
minint
1111 1111 1111 1111 1111 1111 1101two = – 3ten
1111 1111 1111 1111 1111 1111 1110two = – 2ten
1111 1111 1111 1111 1111 1111 1111two = – 1ten
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-5
Two's Complement Operations
•
Negating a two's complement number: invert all bits and add 1
– remember: “negate” and “invert” are quite different!
•
Converting n bit numbers into numbers with more than n bits:
– MIPS 16 bit immediate gets converted to 32 bits for arithmetic
– copy the most significant bit (the sign bit) into the other bits
0010
-> 0000 0010
1010
-> 1111 1010
– "sign extension" (lbu vs. lb)
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-6
Novas instruções
•
•
•
instruções “unsigned”: (exemplo de aplicação, cálculo de memória)
sltu $t1, $t2, $t3
# diferença é “sem sinal”
slti e sltiu
# envolve imediato, com ou sem sinal
•
Exemplo pag 215: supor $s0 = FF FF FF FF e $s1 = 00 00 00 01
slt
$t0, $s0, $s1
como $s0 < 0 e $s1 > 0  $s0<$s1  $t0 = 1
sltu
$t0, $s0, $s1
como $s0 e $s1 não tem sinal  $s0>$s1  $t0 = 0
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-7
Cuidados com extensão 16 bits
•
•
•
•
•
beq $s0, $s1, nnn
# salta para PC + nnn se teste OK
nnn tem 16 bits e PC tem 32 bits
– estender de 16 para 32 bits antes daoperação aritmética
se nnn > 0
– preencher com zeros à esquerda
se nnn < 0
CUIDADO
– preencher com 1´s à esquerda
– verificar
por este motivo operação é chamada de
– EXTENSÃO DE SINAL
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-8
Addition & Subtraction
•
Just like in grade school (carry/borrow 1s)
0111
0111
0110
+ 0110
- 0110
- 0101
•
Two's complement operations easy
– subtraction using addition of negative numbers
0111
+ 1010
•
Overflow (result too large for finite computer word):
– e.g., adding two n-bit numbers does not yield an n-bit number
0111
+ 0001
note that overflow term is somewhat misleading,
1000
it does not mean a carry “overflowed”
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-9
Detecting Overflow
•
•
•
No overflow when adding a positive and a negative number
No overflow when signs are the same for subtraction
CONDIÇÕES DE OVERFLOW
op
A
B
resultado
A+B
+
+
-
A+B
-
-
+
A-B
+
-
-
A-B
-
+
+
Em hardware, comparar o “vai-um” e o
“vem-um” com relação ao bit de sinal
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-10
Effects of Overflow
•
•
An exception (interrupt) occurs
– Control jumps to predefined address for exception (EPC —
EXCEPTION PROGRAM COUNTER)
– Interrupted address is saved for possible resumption
• mfc0 (move from system control): copia endereço do EPC para
qualquer registrador
Don't always want to detect overflow
— new MIPS instructions: addu, addiu, subu
note: addiu still sign-extends!
note: sltu, sltiu for unsigned comparisons
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-11
Instruções (fig 4.52 - pag 309)
add
add immediate
add unsigned
add immediate unsigned
subtract
subtract unsigned
and
and immediate
or
or immediate
shift left logical
shift right logical
load upper immediate
load word
store word
load byte unsigned
store byte
branch on equal
branch on not equal
jump
jump and link
jump register
set less than
set less than immediate
set less than unsigned
set less than immediate unsigned
add
addi
addu
addiu
sub
subu
and
andi
or
ori
sll
srl
lui
lw
sw
lbu
sb
beq
bne
j
jal
jr
slt
slti
sltu
sltiu
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
R
I
R
I
R
R
R
I
R
I
R
R
I
I
I
I
I
I
I
J
J
R
R
I
R
I
multiply
multiply unsigned
divide
divide unsigned
move from Hi
move from Lo
move from system control (EPC)
fp add single
fp add doublr
fp subtract single
fp subtract double
fp multiply single
fp multiply double
fp divide single
fp divide double
load word to fp single
store word to fp single
branch on fp true
branch on fp false
fp compare single
(x= eq,neq,lt,le,gt,ge)
fp compare double
(x= eq,neq,lt,le,gt,ge)
1998 Morgan Kaufmann Publishers
mult
multu
div
divu
mfhi
mflo
mfc0
add.s
add.d
sub.s
sub.d
mul.s
mul.d
div.s
div.d
lwc1
swc1
bclt
bclf
c.x.s
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
I
I
I
I
R
c.x.d
R
Ch4-12
Review: Boolean Algebra & Gates
•
Problem: Consider a logic function with three inputs: A, B, and C.
Output D is true if at least one input is true
Output E is true if exactly two inputs are true
Output F is true only if all three inputs are true
•
Show the truth table for these three functions.
•
Show the Boolean equations for these three functions.
•
Show an implementation consisting of inverters, AND, and OR gates.
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-13
An ALU (arithmetic logic unit)
•
Let's build an ALU to support the andi and ori instructions
– we'll just build a 1 bit ALU, and use 32 of them
operation
a
op a
b
res
result
b
•
Possible Implementation (sum-of-products):
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-14
Review: The Multiplexor
•
Selects one of the inputs to be the output, based on a control input
S
•
A
0
B
1
C
note: we call this a 2-input mux
even though it has 3 inputs!
Lets build our ALU using a MUX:
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-15
Different Implementations
•
Not easy to decide the “best” way to build something
•
– Don't want too many inputs to a single gate
– Dont want to have to go through too many gates
– for our purposes, ease of comprehension is important
Let's look at a 1-bit ALU for addition:
CarryIn
a
Sum
b
cout = a b + a cin + b cin
sum = a xor b xor cin
CarryOut
•
How could we build a 1-bit ALU for add, and, and or?
•
How could we build a 32-bit ALU?
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-16
Building a 32 bit ALU
CarryIn
a0
b0
Operation
CarryIn
ALU0
Result0
CarryOut
Operation
CarryIn
a1
a
0
b1
CarryIn
ALU1
Result1
CarryOut
1
Result
a2
2
b
b2
CarryIn
ALU2
Result2
CarryOut
CarryOut
a31
b31
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
CarryIn
ALU31
1998 Morgan Kaufmann Publishers
Result31
Ch4-17
What about subtraction (a – b) ?
•
•
•
Two's complement approch: just negate b and add.
a - b = a + (- b)
How do we negate?
(- a) = comp2(a) = comp1(a) + 1
A very clever solution:
Binvert
Operation
CarryIn
a
0
1
b
0
Result
2
1
CarryOut
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-18
Subtrator
B
~B
0
1
B
equivalente à

Binv
Binv
Binv




+
+
+
+
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-19
Tailoring the ALU to the MIPS
•
Need to support the set-on-less-than instruction (slt)
– remember: slt is an arithmetic instruction
– produces a 1 if rs < rt and 0 otherwise
– use subtraction: (a-b) < 0 implies a < b
•
Need to support test for equality (beq $t5, $t6, $t7)
– use subtraction: (a-b) = 0 implies a = b
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-20
Supporting slt
Binvert
Operation
CarryIn
a
•
0
Can we figure out the idea?
1
Result
b
0
2
1
Less
Rs
0
bit de sinal
3
a.
CarryOut
Rt
subtração
Rd
Binvert
Operation
CarryIn
a
0
1
Result
b
0
2
1
Less
3
Set
Overflow
detection
b.
Overflow
Operation
CarryIn
Binvert
a0
b0
CarryIn
ALU0
Less
CarryOut
a1
b1
0
CarryIn
ALU1
Less
CarryOut
a2
b2
0
CarryIn
ALU2
Less
CarryOut
Result0
Result1
Result2
CarryIn
a31
b31
0
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
CarryIn
ALU31
Less
Result31
Set
Overflow
1998 Morgan Kaufmann Publishers
Ch4-22
Test for equality
•
Notice control lines:
000
001
010
110
111
=
=
=
=
=
and
or
add
subtract
slt
Bnegate
Operation
a0
b0
CarryIn
ALU0
Less
CarryOut
Result0
a1
b1
0
CarryIn
ALU1
Less
CarryOut
Result1
a2
b2
0
CarryIn
ALU2
Less
CarryOut
Result2
Zero
•Note: zero is a 1 when the result is zero!
a31
b31
0
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
CarryIn
ALU31
Less
Result31
Set
1998 Morgan Kaufmann Publishers
Overflow
Ch4-23
ALU
ALUop
A
32 bits: A, B, result
Zero
1 bit: Zero, Overflow
Result
B
3 bits: ALUop
Overflow
ALUop
Binv-OP
Instrução
0 00
and
0 01
or
0 10
add
1 10
sub
1 11
slt
1 10
beq
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-24
Conclusion
•
We can build an ALU to support the MIPS instruction set
– key idea: use multiplexor to select the output we want
– we can efficiently perform subtraction using two’s complement
– we can replicate a 1-bit ALU to produce a 32-bit ALU
•
Important points about hardware
– all of the gates are always working
– the speed of a gate is affected by the number of inputs to the gate
– the speed of a circuit is affected by the number of gates in series
(on the “critical path” or the “deepest level of logic”)
•
Our primary focus: comprehension, however,
– Clever changes to organization can improve performance
(similar to using better algorithms in software)
– we’ll look at two examples for addition and multiplication
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-25
Problem: ripple carry adder is slow
CarryIn
•
•
Is a 32-bit ALU as fast as a 1-bit ALU?
atraso (ent  soma ou carry = 2G)
n estágios 2nG
Is there more than one way to do addition?
– two extremes:
ripple carry (2nG)
sum-of-products (2G)
a0
b0
Operation
CarryIn
ALU0
Result0
CarryOut
a1
b1
CarryIn
ALU1
Result1
CarryOut
a2
b2
CarryIn
ALU2
Result2
CarryOut
Can you see the ripple? How could you get rid of it?
c1
c2
c3
c4
=
=
=
=
b0c0
b1c1
b2c2
b3c3
+
+
+
+
a0c0
a1c1
a2c2
a3c3
+
+
+
+
a0b0
a1b1
a2b2
a3b3
c2 =
c3 =
c4 =
a31
b31
CarryIn
ALU31
Result31
Not feasible! Why?
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-26
Carry-lookahead adder
•
•
An approach in-between our two extremes
Motivation:
– If we didn't know the value of carry-in, what could we do?
– When would we always generate a carry?
gi = ai bi
– When would we propagate the carry?
pi = ai + bi
•
Did we get rid of the ripple?
c1
c2
c3
c4
=
=
=
=
•
g0
g1
g2
g3
+
+
+
+
p0c0
p1c1
p2c2
p3c3
c2 =
c3 =
c4 =
Feasible! Why?
atraso: ent  gi pi (1G)
gi pi  carry (2G)
total: 5G independente de n
carry  saídas (2G)
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-27
Use principle to build bigger adders
CarryIn
a0
b0
a1
b1
a2
b2
a3
b3
CarryIn
Result0--3
ALU0
P0
G0
pi
gi
Carry-lookahead unit
C1
a4
b4
a5
b5
a6
b6
a7
b7
a8
b8
a9
b9
a10
b10
a11
b11
a12
b12
a13
b13
a14
b14
a15
b15
ci + 1
CarryIn
Result4--7
ALU1
P1
G1
•
•
•
pi + 1
gi + 1
C2
ci + 2
CarryIn
Result8--11
ALU2
P2
G2
pi + 2
gi + 2
C3
ci + 3
Can’t build a 16 bit adder this way... (too big)
Could use ripple carry of 4-bit CLA adders
Better: use the CLA principle again!
– super propagate (ver pag 243)
– super generate (ver pag 245)
– ver exercícios 4.44, 45 e 46 (não será
cobrado)
CarryIn
Result12--15
ALU3
P3
G3
pi + 3
gi + 3
C4
ci + 4
CarryOut
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-28
Multiplication
•
•
•
More complicated than addition
– accomplished via shifting and addition
More time and more area
Let's look at 3 versions based on gradeschool algorithm
810
910
1000 multiplicando
1001 multiplicador
1000
0000
produtos parciais
0000
1000
7210 1001000 max= (24–1) *(24–1) = 225
225 > 128  8 bits
32 * 32 bits  64 bits
•
Negative numbers: convert and multiply
– there are better techniques, we won’t look at them
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-29
Multiplication: Implementation
Start
Multiplier0 = 1
1. Test
Multiplier0
Multiplier0 = 0
1a. Add multiplicand to product and
place the result in Product register
2. Shift the Multiplicand register left 1 bit
3. Shift the Multiplier register right 1 bit
Multiplicand
32nd repetition?
Shift left
No: < 32 repetitions
Yes: 32 repetitions
64 bits
Done
Multiplier
Shift right
64-bit ALU
32 bits
Product
Write
Control test
64 bits
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-30
Second Version
Start
Multiplier0 = 1
1. Test
Multiplier0
Multiplier0 = 0
1a. Add multiplicand to the left half of
the product and place the result in
the left half of the Product register
2. Shift the Product register right 1 bit
3. Shift the Multiplier register right 1 bit
Multiplicand
32nd repetition?
32 bits
No: < 32 repetitions
Yes: 32 repetitions
Done
Multiplier
Shift right
32-bit ALU
32 bits
Product
Shift right
Write
Control test
64 bits
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-31
Final Version
Multiplicand
Start
32 bits
Product0 = 1
1. Test
Product0
Product0 = 0
1a. Add multiplicand to the left half of
the product and place the result in
the left half of the Product register
32-bit ALU
2. Shift the Product register right 1 bit
32nd repetition?
No: < 32 repetitions
Yes: 32 repetitions
Product
Shift right
Write
Control
test
Done
64 bits
• No MIPS:
• dois novos registradores de uso dedicado para
multiplicação: Hi e Lo (32 bits cada)
• mult $t1, $t2
# Hi Lo  $t1 * $t2
• mfhi $t1
# $t1  Hi
• mflo $t1
# $t1  Lo
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-32
Algoritmo de Booth (visão geral)
•
•
•
•
•
•
Idéia: “acelerar” multiplicação no caso de cadeia de “1´s” no
multiplicador:
0 1 1 1 0 * (multiplicando) =
+ 1 0 0 0 0 * (multiplicando)
- 0 0 0 1 0 * (multiplicando)
Olhando bits do multiplicador 2 a 2
– 00 nada
– 01 soma (final)
– 10 subtrai (começo)
– 11 nada (meio da cadeia de uns)
Funciona também para números negativos
Para o curso: só os conceitos básicos
Algoritmo de Booth estendido
– varre os bits do multiplicador de 2 em 2
Vantagens:
– (pensava-se: shift é mais rápido do que soma)
– gera metade dos produtos parciais: metade dos ciclos
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-33
Geração rápida dos produtos parciais
X0 Y0
X2
X1
X0
X1 Y0
X0 Y1
Y0
Y1
Y2
X0
X1
X2
X2 Y0
X2 Y1
X2 Y2
X1 Y1
X0Y2
X1 Y2
Y0
Y1
X2 Y0
X1 Y0
X0 Y0
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
Y2
X2 Y1
X1 Y1
X0 Y1
1998 Morgan Kaufmann Publishers
X2 Y 2
X1 Y 2
X0 Y 2
Ch4-34
Carry Save Adders (soma de produtos parciais)
a3 b3
a2 b2
a1 b1
a0 b0
A
e3
e2
e1
B
E
F
Traditional adder
e0
Traditional adder
f3
f2
f1
f0
Traditional adder
s5
s4
s3
b3 e3
s2
f3
b2 e2
s1
f2
S
s0
b1 e1
f1
b0 e0
f0
A
B
E
F
Carry save adder
a3
a2
a1
a0
Carry save adder
C'
s'4 c'3
s'3 c'2
s'2 c'1
s'1 c'0
S'
s'0
Traditional adder
S
s5
s4
s3
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
s2
s1
s0
1998 Morgan Kaufmann Publishers
Ch4-35
Divisão
29  3 
29 = 3 * Q + R = 3 * 9 + 2
2910 = 011101
011101
11
310 = 11
11
01001
00101
11
10
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
Q=9
R=2
Como implementar em hardware?
1998 Morgan Kaufmann Publishers
Ch4-36
Alternativa 1: divisão com restauração
• hardware não sabe se “vai caber ou não”
• registrador para guardar resto parcial
• verificação do sinal do resto parcial
• caso negativo  restauração
29 – 3 * 24 = -19
-19 + 3 * 24 = 29
q4 = 1
q4 = 0
29 – 3 * 23 =
5
q3 = 1
5 – 3 * 22 = -7
-7 + 3 * 22 = 5
q2 = 1
q2 = 0
Restauração
5 – 3 * 21 = -1
-1 + 3 * 21 = 5
q1 = 1
q1 = 0
Restauração
5 – 3 * 20 =
q0 = 1
2
R = 11 = 2
Restauração
q4q3q2q1q0 = 01001 = 9
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-37
Alternativa 2: divisão sem restauração
Regras
se resto parcial
se resto parcial
> 0 próxima operação
< 0 próxima operação
se operação corrente
se operação corrente
+
-
soma
subtração
qi = 1
qi = 1
29 – 3 * 24 = -19 < 0
-19 + 3 * 23 = 5 > 0
5 – 3 * 22 = -7 < 0
-7 + 3 * 21 = -1 < 0
-1 + 3 * 20 = 2
próx = SOMA
próx = SUB
próx = SOMA
próx = SOMA
q4 = 1
q3 = 1
q2 = 1
q1 = 1
q0 = 1
Resto = 2
Quociente =
11111 ??
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
objetivo
R0
1998 Morgan Kaufmann Publishers
Ch4-38
Alternativa 2: conversão do resultado
1 1 1 1 1  (24  23  22  21  20 )
16 - 8 + 4 - 2 - 1
...1 1 ...  2  2( n1)  2( n1) (2  1)  2( n1)
n
1 111 1
0101 1
01
• Nº de somas: 3
• Nº de subtrações:2
• Total: 5
• OBS: se resto < 0 deve haver correção
de um divisor para que resto > 0
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-39
Comparação das alternativas
29
29
5
5
5
5
-1
2
-7
-1
2
com
sem
-7
-19
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-40
Hardware para divisão: terceira alternativa
Start
1. Shift the Remainder register left 1 bit
Divisor
2. Subtract the Divisor register from the
left half of the Remainder register and
place the result in the left half of the
Remainder register
32 bits
Remainder >
– 0
Test Remainder
Remainder < 0
32-bit ALU
3a. Shift the Remainder register to the
left, setting the new rightmost bit to 1
Remainder
Shift right
Shift left
Write
Control
test
3b. Restore the original value by adding
the Divisor register to the left half of the
Remainder register and place the sum
in the left half of the Remainder register.
Also shift the Remainder register to the
left, setting the new rightmost bit to 0
32nd repetition?
64 bits
No: < 32 repetitions
Yes: 32 repetitions
Done. Shift left half of Remainder right 1 bit
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-41
Instruções
• No MIPS:
• dois novos registradores de uso dedicado para
multiplicação: Hi e Lo (32 bits cada)
• mult $t1, $t2
# Hi Lo  $t1 * $t2
• mfhi $t1
# $t1  Hi
• mflo $t1
# $t1  Lo
• Para divisão:
• div $s2, $s3
• divu $s2, $s3
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
# Lo  $s3 / $s3
Hi  $s3 mod $s3
# idem para “unsigned”
1998 Morgan Kaufmann Publishers
Ch4-42
Ponto Flutuante
•
•
•
Objetivos:
– representação de números não inteiros
– aumentar a capacidade de representação (maiores ou menores)
Formato padronizado
1.XXXXXXXXX ..... * 2yyy
(no caso geral Byyy)
No MIPS:
S
exp
mantissa ou significando
8
23
 exp
 faixa
 mantissa  precisão
sinal-magnitude
(-1)S F * 2E
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-43
Ponto Flutuante e padrão IEEE 754
expoente  [-128 , 127]
se 210  103
128 = 8 + 10 * 12;
2128 = 2(8 + 10 * 12) = 28 * 2(10 * 12)  2 * 1038
overflow  Nº > 1038
underflow  Nº < 10-38
um implícito
PADRÃO IEEE 754
1.XXXXXXXXXXX
S
exp
mantissa ou significando
8
23
mantissa: precisão simples: 23 bits (+1)
precisão dupla: 52 bits (+1)
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-44
Padrão IEEE754: bias
Nº = (-1)S (1 + Mantissa) * 2E
Para simplificar a ordenação (sorting): BIAS
0
127
exp
Bias
255
No padrão: 2 (nE - 1) - 1 = 127
EXP = CAMPOEXP - BIAS
exp
Exemplo: representar - 0,7510 = - (1/2 + 1/4)
- 0,7510 = - 0,112 = -1,11 * 2-1
mantissa = 1000000 ......
(23 bits)
campo expoente: - 1 + 127 = 12610 = 0111 11102
1
0111 1110
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1000 0000 0000 0000 0000 000
1998 Morgan Kaufmann Publishers
Ch4-45
Tabela de faixas de representação do IEEE 754
Precisão simples
Precisão dupla
Expoente Mantissa Expoente Mantissa
Significado
0
0
0
0
0
0
0
0
0
Número não normalizado
1 – 254
qquer
1 – 2046
qquer
Número normalizado
255
0
2047
0
infinito
255
0
2047
0
NaN (not a number)
8bits
23(+1)
11
52(+1)
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-46
Soma em ponto flutuante
Start
1. Compare the exponents of the two numbers.
Shift the smaller number to the right until its
exponent would match the larger exponent
2. Add the significands
3. Normalize the sum, either shifting right and
incrementing the exponent or shifting left
and decrementing the exponent
Overflow or
underflow?
Yes
No
Exception
4. Round the significand to the appropriate
number of bits
No
Still normalized?
Yes
Done
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-47
ULA para soma em ponto flutuante
Sign
Exponent
Significand
Sign
Exponent
Significand
Compare
exponents
Small ALU
Exponent
difference
0
1
0
Control
1
0
1
Shift smaller
number right
Shift right
Big ALU
0
1
0
Increment or
decrement
1
Shift left or right
Rounding hardware
Sign
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
Exponent
Add
Normalize
Round
Significand
1998 Morgan Kaufmann Publishers
Ch4-48
Multiplicação em ponto flutuante
Start
1. Add the biased exponents of the two
numbers, subtracting the bias from the sum
to get the new biased exponent
2. Multiply the significands
3. Normalize the product if necessary, shifting
it right and incrementing the exponent
Overflow or
underflow?
Yes
No
Exception
4. Round the significand to the appropriate
number of bits
No
Still normalized?
Yes
5. Set the sign of the product to positive if the
signs of the original operands are the same;
if they differ make the sign negative
Done
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
1998 Morgan Kaufmann Publishers
Ch4-49
Conjunto de instruções do MIPS para fp
Fig 4.47
Mario Côrtes - MO401 - IC/Unicamp- 2002s1
Pag 291
1998 Morgan Kaufmann Publishers
Ch4-50