Aritmetica para computadores U Brasilia

Prévia do material em texto

Aritmética para 
Computadores
Universidade de Brasília
Departamento de Ciência da Computação
Tópicos
Representação em Complemento de Dois
Adição e Subtração
Unidade Lógico Aritmética
Multiplicação e Divisão
Ponto Flutuante
Complemento de Dois
Recapitulando: a representação de números em 
complemento de dois baseia-se nos seguintes 
pesos:
bn-1 bn-2 ... b2 b1 b
(- 2n-1) 2n-2 ... 22 21 20
Ex:
100101 = 1*(-25) + 1*22 + 1*20 = -32 + 4 + 1 = -27
Inteiros no MIPS
O MIPS utiliza 32 bits para representar um 
inteiro. Considerando números sem sinal:
0000 0000 0000 0000 0000 0000 0000 0000dois = 0dez
0000 0000 0000 0000 0000 0000 0000 0001dois = 1dez
0000 0000 0000 0000 0000 0000 0000 0010dois = 2dez
…
 1111 1111 1111 1111 1111 1111 1111 1101dois = 4.294.967.293dez
 1111 1111 1111 1111 1111 1111 1111 1110dois = 4.294.967.294dez
 1111 1111 1111 1111 1111 1111 1111 1111dois = 4.294.967.295dez
Em Complemento de 2...
0000 0000 0000 0000 0000 0000 0000 0000dois = 0dez
0000 0000 0000 0000 0000 0000 0000 0001dois = 1dez
0000 0000 0000 0000 0000 0000 0000 0010dois = 2dez
…
 0111 1111 1111 1111 1111 1111 1111 1101dois = 2.147.483.645dez
 0111 1111 1111 1111 1111 1111 1111 1110dois = 2.147.483.646dez
 0111 1111 1111 1111 1111 1111 1111 1111dois = 2.147.483.647dez
1000 0000 0000 0000 0000 0000 0000 0000dois = -2.147.483.648dez
1000 0000 0000 0000 0000 0000 0000 0001dois = -2.147.483.647dez
1000 0000 0000 0000 0000 0000 0000 0010dois = -2.147.483.646dez
…
 1111 1111 1111 1111 1111 1111 1111 1101dois = -3dez
 1111 1111 1111 1111 1111 1111 1111 1110dois = -2dez
 1111 1111 1111 1111 1111 1111 1111 1111dois = -1dez
Instruções e Complemento de 2
A questão de números com e sem sinal não afeta só as 
operações aritméticas, mas também as operações de load.
A função de um load com sinal é de copiar o sinal 
repetidamente até preencher o registrador. Sua intenção 
é colocar no registrador uma representação correta do 
número. Instrução load byte (lb) replica o sinal
Um load sem sinal simplesmente preenche o registrador 
com zeros à esquerda dos dados. Instrução load byte 
unsigned (lbu) não replica o sinal.
Lb x lbu
Lb $t1, 0($t0) F7 Sinal replicado
Lbu $t2, 0($t0) F7
$t0
$t1
$t2
F7 F012 …… F7
FFFFFF
000000 Zero replicado
Comparação em Complemento de 2
As seguintes instruções trabalham com inteiros 
com sinal:
slt (set on less than)
Slti (set on less than immediate)
Já as seguintes consideram os números com não 
negativos:
sltu (set on less than unsigned)
Sltiu (set on less than immediate unsigned)
Como a representação afeta a comparação ?
Adição e Subtração
! Vamos adicionar 6dez a 7dez:
0000 0000 0000 0000 0000 0000 0000 0111dois = 7dez
0000 0000 0000 0000 0000 0000 0000 0110dois = 6dez +
0000 0000 0000 0000 0000 0000 0000 1101dois = 13dez
... 0 0 0 1 1 1
... 0 0 0 1 1 0
 
... 
(0)(1)(1)(0)(0)
(0)1(1)0(1)1(0)1(0)0(0)0
Estouro de representação (overflow)
Em complemento de 2, a soma de dois sinais de 
mesmo sinal gera estouro se o resultado for de 
sinal diferente
Ex: Pos + Pos = Neg ou Neg + Neg = Pos
Por outro lado, a soma de números sem sinal pode 
não produz estouro, se considerarmos estes 
como sendo endereços de memória
Estouro de representação (overflow)
No MIPS, temos dois tipos de instruções 
aritméticas:
Add (add), addi (add immediate) e sub (subtract) 
levantam uma exceção quando ocorre overflow
addu (add unsigned), addiu (add immediate 
unsigned) e subu (subtract unsigned) não levantam 
exceção em caso de overflow.
Acessando Bits
Algumas vezes interessa acessar campos de uma 
palavra, e não apenas a palavra inteira
Algumas instruções auxiliam o acesso a bits em 
uma palavra
Operações de deslocamento (shift) movem os bits 
a esquerda ou a direita, introduzindo zeros na 
extremidade
Operações lógicas bit a bit, como AND e OR 
Deslocamento
Deslocamentos ou shifts movem todos os bits em 
uma palavra para a direita (shift right) ou para a 
esquerda (shift left), preenchendo as posições que 
não receberam bits vizinhos com zeros.
Ex: suponha que o registrador $s0 contenha a 
seguinte palavra:
$s0 = 0000 0000 0000 0000 0000 0000 0000 1101dois
Qual será a palavra contida em $s0 ao realizarmos 
um shift left de 6 bits??
$s0 = 0000 0000 0000 0000 0000 0011 0100 0000dois
Instruções de Deslocamento
No MIPS, as instruções de deslocamento são: 
sll (shift left logical): desloca os bits em uma palavra em n 
bits para a esquerda, preechendo os n bits mais à direita com 
zeros.
Ex: sll $t2, $s0, 6 # desloca $s0 em 6 bits para a
#esquerda, armazenando em $t2.
# em C: $t2 = $s0 << 6
srl (shift right logical): desloca os bits em uma palavra em n 
bits para a direita, preechendo os n bits mais à esquerda com 
zeros.
Ex: srl $t2, $s0, 6 #desloca $s0 em 6 bits para a
#direita, armazenando em $t2
# em C: $t2 = $s0 >> 6
Formato Instruções
Podemos agora voltar ao formato de instrução 
tipo-R:
O nome do campo shamt vem de shift ammount, 
ou quantidade de deslocamento. A codificação da 
instrução sll $t2, $s0, 6 fica então como:
 op rs rt rd shamt funct 
 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
 0 0 16 10 6 0 
Aplicações
Selecionar um byte:
srl $t0, $t0, 8
0000 0000 0000 0000 0101 0110 0111 1000
0000 0000 0000 0000 0000 0000 0101 0110
Multiplicar por 2n:
sll $t0, $t0, 2 # multiplica por 22 = 4
0000 0000 0000 0000 0000 0000 0101 0110
0000 0000 0000 0000 0000 0001 0101 1000
AND e OR
and $t0, $t1, $t2
$t1 = 0000 0000 0000 0000 0000 1101 0000 0000dois
$t2 = 0000 0000 0000 0000 0011 1100 0000 0000dois
$t0 = 0000 0000 0000 0000 0000 1100 0000 0000dois
or $t0, $t1, $t2
$t1 = 0000 0000 0000 0000 0000 1101 0000 0000dois
$t2 = 0000 0000 0000 0000 0011 1100 0000 0000dois
$t0 = 0000 0000 0000 0000 0011 1101 0000 0000dois
Unidade Lógico Aritmética
ALU [Arthritic Logic Unit or (rare) Arithmetic Logic Unit] A random-
number generator supplied as standard with all computer systems
O MIPS tem uma ULA de 32 bits que realiza as 
operações lógicas e aritmáticas básicas
Para ilustrar sua construção, segue a descrição 
de uma ULA com as seguintes operações:
soma/subtração em complemento de 2
operação lógica AND
operação lógica OR
operação slt (set on less than, 1 se a < b)
detecção de overflow
Elementos Básicos
Multiplexador
0
1
A
B
S
00
01
X0
S
X1
10
11
X2
X3
2x1 4x1
Elementos Básicos ...
Somador
CarryIn
Soma
a
b
CarryOut
+
Entradas Saídas
a b CarryI
n
CarryOu
t
Som
a
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
ULA de 1-bit
A ULA de 1 bit (soma, and, or) pode então ser 
representada por:
Operação
a
b
Saída
0
1
2
CarryIn
+
CarryOut
ULA de 32 bits
CarryIn
CarryOut
ULA 0
a0
b0
CarryIn
CarryOut
ULA 1
a1
b1
CarryIn
ULA 31
a31
b31
Resultado0
Resultado1
Resultado31
CarryIn Operação
Incluindo Subtração
b
InverteBit
0
1
Operação
a
Saída
0
1
2
CarryIn
+
CarryOut
Adaptando ao MIPS
A maior parte das instruções de MIPS já pode ser 
executada por esta ULA.
A instrução slt ainda não é suportada.
A instrução slt gera saída 1 se rs < rt, e 0 caso contrário. 
Assim, todos os bits, com excessão do bit menos 
significativo, são fixados em zero.
O bit menos significativo depende doresultado da 
comparação.
Inclui-se a entrada Less na ULA para prover a operação 
slt
ULA com slt
b
InverteBit
0
1
Operação
a
0
1
2
CarryIn
+
CarryOut
3Less
Calculando slt
O bit menos significativo da ULA deve ser 1 se rs 
< rt
Calcula-se este valor subtraindo rs de rt e 
tomando-se o bit de sinal:
se rs – rt < 0, rt > rs
Utiliza-se o próprio subtrator da ULA para obter 
este valor, modificando-se o último estágio 
Último Estágio da ULA
b
InverteBit
0
1
Operação
a
Saída
0
1
2
CarryIn
+
3Less
 Overflow
Set
Overflow
ULA de 32 bits
ULA 0
a0
b0
ULA 1
a1
b1
ULA 31
a31
b31
Resultado0
Resultado1
Resultado31
Operação
Overflow
0
0
Set
InverteBit
Testando igualdade
As instruções bne e beq testam se dois valores 
são iguais ou não
Para testar igualdade subtrai-se os dois 
operandos e testa-se se o resultado é zero:
A = B se A – B = 0
Teste: operação NOR entre os bits do resultado
Igual = not(R0 or R1 or ... or R31) 
Comparação
ULA 0
a0
b0
ULA 1
a1
b1
ULA 31
a31
b31
Resultado0
Resultado1
Resultado31
Operação
Overflow0
0
Set
NegaBit
Zero
Multiplicação
Multiplication is vexation, Division is as bad;
The rule of three doth puzzle me, And practice drives me mad.
Anonymous, 1570
Multiplicando 1 0 0 0dez
Multiplicador × 1 0 0 1dez
 1 0 0 0
 0 0 0 0
 0 0 0 0
 1 0 0 0 
Produto 1 0 0 1 0 0 0dez
Multiplicação
Se um operando tem n bits e outro m bits, o 
resultado pode necessitar até n+m bits
Algoritmo básico: 
Deslocamentos e somas
Se o i-ésimo bit do multiplicador é 1, somar o 
multiplicando deslocado i vezes a esquerda ao 
resultado parcial
Algoritmo Básico
 
 
 
 
64 bits
64 bits
32 bits
Multiplicando
Deslocamento à esquerda
Teste de 
controle
Multiplicador
Deslocamento à 
direita
Unidade Lógica 
Aritmética
 (64 bits)
Produto escrita
Início
Teste do 
Multiplicador0
Multiplicador0 = 0Multiplicador0 = 1
1) Some o multiplicando ao produto e 
coloque o resultado no registrador Produto
2) Desloque o registrador 
Multiplicando 1 bit à esquerda
3) Desloque o registrador 
Multiplicador 1 bit à direita
32a repetição?
Fim
Não: < 32 repetições
Sim: 32 repetições
Algoritmo Passo a Passo
Iteração Passo Multiplicador Multiplicando Produto
0 Valores iniciais 0011 0000 0010 0000 0000
1a :1 Prod = Prod + Mcand 0011 0000 0010 0000 0010
2: Deslocamento à esquerda do Multiplicando 0011 0000 0100 0000 0010
3: Deslocamento à direita do Multiplicador 0001 0000 0100 0000 0010
1 1a :1 Prod = Prod +Mcand 0001 0000 0100 0000 0110
2: Deslocamento à esquerda do Multiplicando 0001 0000 1000 0000 0110
3: Deslocamento à direita do Multiplicador 0000 0000 1000 0000 0110
2 1: 0 Nenhuma operação 0000 0000 1000 0000 0110
2: Deslocamento à esquerda do Multiplicando 0000 0001 0000 0000 0110
3: Deslocamento à direita do Multiplicador 0000 0001 0000 0000 0110
4 1: 0 Nenhuma operação 0000 0001 0000 0000 0110
2: Deslocamento à esquerda do Multiplicando 0000 0010 0000 0000 0110
3: Deslocamento à direita do Multiplicador 0000 0010 0000 0000 0110
Otimizando a Multiplicação
No algoritmo anterior, metade dos bits do 
multiplicando são sempre 0
O somador tem 64 bits
Num dado passo, apenas 32 bits são somados
Otimização:
O resultado tem 64 bits
O multiplicando tem 32 bits
O somador tem 32 bits
Soma-se os 32 bits mais significativos e desloca-
se o resultado para a direita
Multiplicador II
 
 
 
 
32 bits
64 bits
32 bits
Multiplicando (fixo)
Teste de 
controle
Deslocamento à 
direita
Unidade Lógica
 Aritmética
 (32 bits)
(Produto) escrita
Deslocamento à direita
Multiplicador
Algoritmo
Início
Teste do 
Multiplicador0
Multiplicador0 = 0Multiplicador0 = 1
1) Some ao multiplicando à metade esquerda 
do produto
 2) Desloque o registrador Produto 1 bit à direita
3) Desloque o registrador Multiplicador 1 bit à 
direita
32a repetição?
Fim
Não: < 32 
repetições
Sim: 32 repetições
Exemplo Multiplicação II
Iteração Passo Multiplicador Multiplicando Produto
0 Valores iniciais 0011 0010 0000 0000
1a :1 Prod = Prod + Mcand 0011 0010 0010 0000
2: Deslocamento à direita do Produto 0011 0010 0001 0000
3: Deslocamento à direita do Multiplicador 0001 0010 0001 0000
1 1a :1 Prod = Prod + Mcand 0001 0010 0011 0000
2: Deslocamento à direita do Produto 0001 0010 0001 1000
3: Deslocamento à direita do Multiplicador 0000 0010 0001 1000
2 1: 0 Nenhuma operação 0000 0010 0001 1000
2: Deslocamento à direita do Produto 0000 0010 0000 1100
3: Deslocamento à direita do Multiplicador 0000 0010 0000 1100
4 1: 0 Nenhuma operação 0000 0010 0000 1100
2: Deslocamento à direita do Produto 0000 0010 0000 0110
3: Deslocamento à direita do Multiplicador 0000 0010 0000 0110
Multiplicando: 0010
Multiplicador: 
0011
Versão Final
Uma maneira de melhorar o multiplicador fazer com que o 
multiplicador e produto compartilhem o mesmo 
registrador (64 bits)
No inicio, o multiplicador é colocado na primeira metade 
do registrador Produto-Multiplicador (menos 
significativa)
Desta maneira quando desloquemos este registrador 
(Produto-Multiplicador) poderemos testar o bit menos 
significativo do multiplicador (para ver se é 0 ou 1) e, 
simultaneamente, deslocar o produto
No final este registrador vai conter só o produto
Versão Final 
 
 
 
 
 
32 bits
64 bits
Multiplicando (fixo)
Teste de 
controle
Unidade Lógico
 Aritmética
 (32 bits)
(Produto-Multiplicando) escrita
Deslocamento à direita
Fluxo
Início
Teste do 
Multiplicador0
Multiplicador0 = 0Multiplicador0 = 1
1) Some ao multiplicando à metade esquerda 
do produto (colocar o resultado na metade 
esquerda do registrador Produto-
Multiplicador)
 2) Desloque o registrador Produto-Multiplicador 
1 bit à direita
32a repetição?
Fim
Não: < 32 repetições
Sim: 32 repetições
Exemplo III
Iteração Passo Multiplicando Produto
0 Valores iniciais 0010 0000 0011
1a :1 Prod = Prod + Mcand 0010 0010 0011
2: Deslocamento à direita do Produto 0010 0001 0001
1 1a :1 Prod = Prod + Mcand 0010 0011 0001
2: Deslocamento à direita do Produto 0010 0001 1000
2 1: 0 Nenhuma operação 0010 0001 1000
2: Deslocamento à direita do Produto 0010 0000 1100
4 1: 0 Nenhuma operação 0010 0000 1100
2: Deslocamento à direita do Produto 0010 0000 0110
Multiplicando: 0010
Multiplicador: 
0011
Multiplicando Números com Sinal
 Os algoritmos vistos anteriormente funcionam bem para 
números sem sinal;
Para que os mesmos funcionem com números com sinal, 
teríamos que lembrar que os números possuem na 
verdade um número infinito de dígitos, sendo um número 
positivo precedido de infinitos zeros e um número 
negativo precedido de infinitos uns.
Assim, nos deslocamentos, deveríamos estender o sinal 
do produto.
Ao invés de investigar mais este caminho, vamos ver um 
outro algoritmo, que funciona para números com sinal.
Algoritmo de Booth
Suponha que precisamos que precisamos 
multiplicar 2dez por 6dez, ou 00102 por 01102
00102
 01102
-------
0000
 0010
 0010
 0000
-------------------
 000011002
Deslocamento (0 no multiplicador)
soma (1 no multiplicador)
soma (1 no multiplicador)
deslocamento (0 no multiplicador)
Algoritmo de Booth ...
Booth observou que uma ULA que possatanto somar como 
subtrair pode chegar ao mesmo resultado de diferentes 
maneiras.
Outro fator que constatou o Booth era que as operações 
de deslocamentos eram mais rápidas que as de soma (e 
subtração)
Exemplo: 21dez 14dez = 294dez
Além disso, (14dez = 16dez – 2dez) ou
0011102 = 0100002 – 0000102
Algoritmo de Booth ...
Esta constatação pode ser aplicada a qualquer 
sequência de 1's
A transformação abaixo é chamada de 
recoidificação
0 1 0 1 0 12 (21dez)
 0 0 1 1 1 02 (14dez)
 0 +1 0 0 -1 0
-----------------------------------------
●Multiplicando
•Multiplicador
•Multiplicador 
recodificado de Booth
string de 1s
Algoritmo de Booth ...
Usando esta técnica, o resultado da multiplicação 
pode ser obtido através de somas e subtrações:
0 1 0 1 0 12 (21dez)
 0 0 1 1 1 02 (14dez)
 0 +1 0 0 -1 0
-----------------------------------------
Deslocadesloca
soma
desloca
subtrai
●Multiplicando
•Multiplicador
•Multiplicador 
recodificado de Booth
Codificação
Na prática, as somas e subtrações podem ser 
determinadas analisando-se pares de bits 
adjacentes
Bit atual Bit a direita Explicação Exemplo
1 0 Início de uma rodada de 1s 00001111000
1 1 Méio de uma rodada de 1s 00001111000
0 1 Fim de uma rodada de 1s 00001111000
0 0 Meio de uma rodada de 0s 00001111000
0 1 1 1 1 0
string de 1s
Exemplo Booth
Multiplicando: 00102 = 2dez Resultado: 1111 10102
Multiplicador: 11012 = -3dez
Iteração Passo Multiplicando Produto
0 Valores iniciais 0010 0000 1101 0
1 1c :10 Prod = Prod - Mcand 0010 1110 1101 0
2: Deslocamento à direita do Produto 0010 1111 0110 1
2 1b :01 Prod = Prod + Mcand 0010 0001 0110 1
2: Deslocamento à direita do Produto 0010 0000 1011 0
3 1c: 10 Prod = Prod - Mcand 0010 1110 1011 0
2: Deslocamento à direita do Produto 0010 1111 0101 1
4 1d: 11 nenhuma operação 0010 1111 0101 1
2: Deslocamento à direita do Produto 0010 1111 1010 1
Deslocamento aritmético à direita: 
extensão de sinal
Multiplicação no MIPS
 MIPS provê um par de registradores de 32 bits para 
armazenar o resultado, de 64 bits: Hi e Lo
Duas instruções de multiplicação:
mult = multiplicação com sinal (ex: mult $s0, $s1)
multu = multiplicação sem sinal (ex: multu $s0, $s1)
Ambas ignoram overflow (se o resultado não couber em 
32 bits).
Existem duas instruções para pegar o resultado dos 
registrados Hi e Lo:
mflo = move from lo (ex: mflo $s0)
Mfhi = move from hi (ex: mfhi $s0)
Exemplo MIPS
 00011111111111111111111111111111 11000000000000000000000000000000
 Hi Lo
01000000000000000000000000000000X $t2
01111111111111111111111111111111$t1
00011111111111111111111111111111$t3
11000000000000000000000000000000$t4mflo $t4
mfhi $t3
mul $t1, $t2 # t1 * t2
Não especificamos registrador destino: produto pode ser ~264; 
3 etapas: