03 - Aritmetica Computacional II

Prévia do material em texto

Arquitetura e Organização de 
Computadores
Aritmética Computacional
Parte II
Prof. Sílvio Fernandes
UNIVERSIDADE FEDERAL RURAL DO SEMI-ÁRIDO
DEPARTAMENTO DE CIÊNCIAS EXATAS E NATURAIS
CURSO DE CIÊNCIA DA COMPUTAÇÃO
1
Multiplicação
 Multiplicando número em decimais
Multiplicando
Multiplicador
Produto
2
Multiplicação
 Observações:
 número de bits do produto é muito maior que do
multiplicando e multiplicador
 se ignorarmos os bits de sinal, e o tamanho do
multiplicando for n bits e multiplicador for m bits, o
produto terá n+m bits
3
Multiplicação
 Usando o algoritmo anterior
4
Multiplicação
 Construindo o hardware
 Suponha multiplicando e multiplicador em registradores de
32 bits e produto em registrador de 64 bits inicializado com
0
 Precisamos mover o multiplicando para a esquerda um
dígito a cada passo
 Durante 32 etapas, um multiplicando de 32 bits moveria 32
bits para esquerda
 Precisamos de um registrador Multiplicando de 64 bits,
inicializado com o multiplicando de 32 bits na metade
direita e 0 na metade esquerda
 Esse registrador é deslocado à esquerda a cada etapa,
com a soma sendo acumulada no registrador Produto de
64 bits
5
Multiplicação
 Construindo o hardware
6
Multiplicação
7
Paso 0: Inicialização
8
Passo 1: verifica
9
Passo 1: soma
10
Passo 1: desloca
11
Passo 2: verifica
12
Passo 2: soma
13
Passo 2: desloca
14
Passo 3: verifica
15
Passo 3: apenas desloca
16
Passo 4: verifica
17
Passo 4: apenas desloca
18
Multiplicação
 Refinando para usar menos registradores
 O multiplicador inicia na metade direita do produto
19
Multiplicação Refinada
20
Passo 0: Inicialização
21
Passo 1: verifica e soma
22
Passo 1: desloca
23
Passo 2: verifica e soma
24
Passo 2: desloca
25
Passo 3: verifica e não soma
26
Passo 3: desloca
27
Passo 4: verifica e não soma
28
Passo 4: desloca
29
Multiplicação
 Multiplicando número negativos
 Solução 1:
 Converta para positivo, se for preciso.
 Multiplique como antes.
 Se sinais diferentes, negue a resposta.
 Solução 2:
 Algoritmo de Booth.
30
Multiplicação Booth
31
32
Contador=4
Passo 0 (7 x 3): Inicialização
Passo 1 (7 x 3)
33
Contador=4
Passo 1 (7 x 3)
34
Contador=4
Passo 1 (7 x 3)
35
Contador=3Observe que repetimos 
o último número no 
deslocamento
Passo 1 (7 x 3)
36
Contador=3
Passo 2 (7 x 3)
37
Contador=3
Passo 2 (7 x 3)
38
Contador=2Viu novamente?
Passo 2 (7 x 3)
39
Contador=2
Passo 3 (7 x 3)
40
Contador=2
Passo 3 (7 x 3)
41
Contador=2
Passo 3 (7 x 3)
42
Contador=1
Passo 3 (7 x 3)
43
Contador=1
Passo 4 (7 x 3)
44
Contador=1
Passo 4 (7 x 3)
45
Contador=0
Passo 4 (7 x 3)
46
Contador=0
Passo 4 (7 x 3 = 21)
47
Multiplicação
 O MIPS oferece um par separado de 
registradores de 32 bits, para conter o produto 
de 64 bits, chamados Hi e Lo
 Instrução multiply (mult): com sinal
 Instrução multiply unsigned (multu): sem sinal
 Para apanhar o produto de 32 bits inteiro, o 
programador usa move from lo (mflo)
 O montador MIPS gera uma pseudo-instrução
para multiplicar, que especifica 3 registradores 
de uso geral, gerando instruções mflo e mfhi
para colocar o produto nos registradores
50
Divisão
 A operação recíproca da multiplicação
 EX: Dividir 1.001.010dec por 1000dec:
 Dividendo = Quociente x divisor + resto
51
Divisor 1000dec
Quociente
Dividendo
Resto
Divisão
 Algoritmo e Hardware da divisão
52
Divisor
Deslocar à direita
ALU 64 bits
Resto
Escrever
Teste de 
controle
Quociente
Deslocar à 
esquerda
Divisão
 Algoritmo e Hardware da divisão
53
Início
1. Subtrai o registrador Divisor do 
registrador Resto e colocar o 
resultado no registrador Resto
Testar 
Resto
Resto ≥ 0 Resto < 0
2a. Deslocar o registrador 
Quociente para esquerda, 
definindo o novo bit mais à direita 
com 1
2b. Restaurar o valor original, 
somando o registrador Divisor ao 
registrador Resto, e colocar a 
soma no registrador Resto. 
Também deslocar o registrador 
Quociente para esquerda, 
definindo o novo bit menos 
significativo como 0
3. Deslocar o registrador Divisor 1 
bit para a direita
33ª
opera
ção?
Não: < 33 repetições
Sim: 33 repetições
Fim
54
Tentar dividir 7dec por 2dec ou 0000 0111bin por 0010bin
usando 4 bits
Iteração Etapa Quociente Divisor Resto
Valores Iniciais
1: Resto = Resto – Div
2b: Resto < 0 => +Div, sll Q, Q0 = 0
3: Deslocar Div direita
1: Resto = Resto – Div
2b: Resto < 0 => +Div, sll Q, Q0 = 0
3: Deslocar Div direita
1: Resto = Resto – Div
2b: Resto < 0 => +Div, sll Q, Q0 = 0
3: Deslocar Div direita
1: Resto = Resto – Div
2a: Resto ≥ 0 => sll Q, Q0 = 1
3: Deslocar Div direita
1: Resto = Resto – Div
2a: Resto ≥ 0 => sll Q, Q0 = 1
3: Deslocar Div direita
Divisão
 Até aqui, ignoramos os número com sinal na 
divisão.
 A solução mais simples é lembrar os sinais do 
divisor e do dividendo e depois negar o 
quociente se os sinais forem diferentes
 Fazer com que o sinal do resto diferente de zero
corresponda ao dividendo
55
Divisão
 Uma versão melhorada do Hardware
56
Divisor
ALU 32 bits
Resto
Deslocar à direita
Deslocar à esquerda
Escrever
Divisão
 Versão melhorada do Hardware
 Pode ser o mesmo usado para multiplicação
 O único requisito é um registrador de 64 bits, que 
pode deslocar para a esquerda ou para direita e 
uma ALU de 32 bits que soma ou subtraia
57
Divisão
 O MIPS utiliza os registradores Hi e Lo de 32 bits, 
tanto para multiplicação quanto para divisão
 Hi contém o resto
 Lo contém o quociente
 O MIPS possui 2 instruções
 Divide (div)
 Divide unsigned (divu)
 O montador MIPS permite que as instruções de 
divisão especifiquem 3 registradores, gerando as 
instruções mflo ou mfhi para colocar o resultado 
desejado em um registrador de uso geral
58
Divisão
 Instruções de divisão no MIPS ignoram o 
overflow, de modo que o software precisa 
determinar se o quociente é muito grande
 O software também precisa verificar se o divisor 
é igual a zero
59
Instruções MIPS reveladas até aqui
60
Categoria Instrução Exemplo Significado Comentário
Aritmética
Add add $s1, $s2, $s3 $s1 = $s2+$s3 3 operandos; overflow detectado
Subtract sub $s1, $s2, $s3 $s1 = $s2-$s3 3 operandos; overflow detectado
Add Immediate dddi $s1, $s2, 100 $s1 = $s2+100 +constante; overflow detectado
Add unsigned addu $s1, $s2, $s3 $s1 = $s2 + $s3 3 operandos; overflow não detectado
Subtract
unsigned
subu $s1, $s2, $s3 $s1 = $s2 - $s3 3 operandos; overflow não detectado
Add immediate
unsigned
addiu $s1, $s2, 10 $s1 = $s2 + 10 +contante; overflow não detectado
move from
coprocessor
register
mfc0 $s1, $epc $s1 = $epc Usado para copiar PC de exceção 
mais outros registradores especiais
multiply mult $s2, $s3 Hi, Lo = $s2*$s3 Produto com sinal, 64 bits, em Hi e Lo
Multiply
unsigned
multu $s2, $s3 Hi, Lo = $s2*$s3 Produto sem sinal, 64 bits, em Hi e Lo
Divide div $s2, $s3 Lo = $s2/$s3
Hi = $s2 mod $s3
Lo = quociente, Hi = resto
Divide unsigned divu $s2, $s3 Lo = $s2/$s3
Hi = $s2 mod $s3
Quociente e resto sem sinal
move from Hi mfhi $s1 $s1 = Hi Usado para obter cópia de Hi
move from Lo mflo $s1 $s1 = Lo Usado para objer cópia de Lo
Instruções MIPS reveladas até aqui61
Categoria Instrução Exemplo Significado Comentário
Lógica
And and $s1, $s2, $s3 $s1 = $s2 & $s3 3 operandos em reg; AND bit a bit
Or or $s1, $s2, $s3 $s1 = $s2 | $s3 3 operandos em reg; OR bit a bit
Nor nor $s1, $s2, $s3 $s1 = ~($s2 | $s3) 3 operandos em reg; NOR bit a bit
And Immediate andi $s1, $s2, 100 $s1 = $s2 & 100 AND bit a bit entre reg. e constante
Or Immediate ori $s1, $s2, 100 $s1 = $s2 | 100 OR bit a bit entre reg. e constante
Shift left logical sll $s1, $s2, 10 $s1 = $s2 << 10 Deslocamento à esquerda por const.
Shift rigth logical srl $s1, $s2, 10 $s1 = $s2 >> 10 Deslocamento à direita por const.
Transferência 
de dados
Load word lw $s1, 100($s2) $s1 = Mem[$s2+100] Dados da mem. para o registrador
Store Word sw $s1, 100($s2) Mem[$s2+100] = $s1 Dados do registrador para a mem.
load half lh $s1, 100($s2) $s1 = Mem[$s2+100] Halfword da memória para registrador
store half sh $s1, 100($s2) Mem[$s2+100] = $s1 Halfword de um reg. para memória
load byte lb $s1, 100($s2) $s1 = Mem[$s2+100] Byte da memória para registrador
store byte sb $s1, 100($s2) Mem[$s2+100] = $s1 Byte de um registrador para memória
load upper
immed.
lui $s1, 100 $s1 = 100 * 216 Carrega constante nos 16 bits mais 
altos
Instruções MIPS reveladas até aqui
62
Categoria Instrução Exemplo Significado Comentário
Desvio 
Condicional
Branch on equal beq $s1, $s2, L If($s1 == $s2) go to L Testa igualdade e desvia
Branch on not
equal
bne $s1, $s2, L If($s1 != $s2) go to L Testa desigualdade e desvia
Set on less than stl $s1, $s2, $s3 If($s2 < $s3) $s1 = 1;
Else $s1 = 0
Compara menor que
Set less than
immediate
stli $s1, $s2, 100 If($s2 < 100) $s1 = 1;
Else $s1 = 0
Compara menor que constante
Desvio
incondicional
Jump j L go to L Desvia para endereço de destino
Jump register jr $ra go to $ra Para switch e retorno de 
procedimento
Jump and link jal L $ra = PC + 4
go to L
Para chamada de procedimento
Referências
 PATTERSON, D. A. ; HENNESSY, J.L. Organização 
e projeto de computadores – a interface 
hardware software. 3. ed. Editora Campus, 
2005.
 STALLINGS, W. Arquitetura e organização de 
computadores: projeto para o desempenho. 8. 
ed. Prentice Hall, 2009.
63