Aritmética Computacional em Organização de Computadores

Prévia do material em texto

1
Organização de Computadores I
DCC006
Prof. Omar Paranaiba Vilela Neto
Aula 5 – Aritmética Computacional
2
Aritmética
• Onde nós estamos:
– Desempenho (segundos, ciclos, instruções)
– Abstrações:
 Arquitetura do conjunto de Instruções
 Assembly e Linguagem de Máquina
• E agora:
– Implementação da Arquitetura
32
32
32
operações
resultado
a
b
ALU
3
• Bits são bits 
— convenções define relação entre bits e números
• Números Binários (base 2)
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001...
decimal: 0...2n-1
 mais complicado:
números são finitos (overflow)
frações e números reais
números negativos 
i.e., MIPS não tem instrução subi; (addi pode 
somar um número negativo)
• Como nós representamos um número negativo?
i.e., qual padrão representará os números?
Números
4
• Sinal Magnitude:
000 = +0
001 = +1
010 = +2
011 = +3
100 = -0
101 = -1
110 = -2
111 = -3
Representações Possíveis
• Complemento de 1:
000 = +0
001 = +1
010 = +2
011 = +3
100 = -3
101 = -2
110 = -1
111 = -0
• Complemento de 2:
000 = +0
001 = +1
010 = +2
011 = +3
100 = -4
101 = -3
110 = -2
111 = -1
• Saídas: balanço, números de zeros, facilidade das operações
• Qual é a melhor? Porque? 
5
• 32 bit complemento de dois:
0000 0000 0000 0000 0000 0000 0000 0000two = 0ten
0000 0000 0000 0000 0000 0000 0000 0001two = + 1ten
0000 0000 0000 0000 0000 0000 0000 0010two = + 2ten
...
0111 1111 1111 1111 1111 1111 1111 1110two = + 2,147,483,646ten
0111 1111 1111 1111 1111 1111 1111 1111two = + 2,147,483,647ten
1000 0000 0000 0000 0000 0000 0000 0000two = – 2,147,483,648ten
1000 0000 0000 0000 0000 0000 0000 0001two = – 2,147,483,647ten
1000 0000 0000 0000 0000 0000 0000 0010two = – 2,147,483,646ten
...
1111 1111 1111 1111 1111 1111 1111 1101two = – 3ten
1111 1111 1111 1111 1111 1111 1111 1110two = – 2ten
1111 1111 1111 1111 1111 1111 1111 1111two = – 1ten
maxint
minint
MIPS
6
• Para negar um número em complemento de dois: inverter todos os 
bits e somar 1
Converter números de n bit em números com mais de n bits:
– MIPS 16 bit imediato convertido para 32 bits para aritmética
– copiar o mais significante bit (o bit de sinal) nos outros bits
0010 -> 0000 0010
1010 -> 1111 1010
– ”extensão do sinal" (lbu X lb)
Operações em Complemento de dois
7
• Como na escola primária (carry/borrow 1s)
 0111 0111 0110
+ 0110 - 0110 - 0101
• Operações em complemento de dois - facilidades
– subtração usando adição de números negativos 
 0111
+ 1010
• Overflow (resultado maior que palavra do computador):
– i.e., a soma de dois n-bit números não produz um número de n-bit 
 0111
+ 0001 note que o termo overflow é para o número,
 1000 ele não considera o carry “overflowed”
Adição & Subtração
8
• Quando somamos um número positivo com um negativo não tem overflow 
• Quando o sinal é o mesmo nas subtrações não tem overflow 
• Overflow ocorre quando o valor afeta o sinal:
– overflow quando somamos dois números positivos produzindo um 
negativo 
– ou, somando dois negativos dando um positivo
– ou, subtraindo um negativo de um positivo dando um negativo
– ou, subtraindo um positivo de um negativo dando um positivo
Detectando Overflow
9
• Ocorre uma exceção (interrupção) 
– Controle salta para um endereço predefinido para a exceção
– endereço Interrompido é salvo para possível retorno
• Detalhes baseado em software / linguagens
• Nem sempre desejamos detectar o overflow
— novas instruções do MIPS: addu, addiu, subu
nota: sltu, sltiu para comparações sem sinal
Efeitos do Overflow
10
• Problema: Considere uma função lógica com três entradas: A, B e C
Saída D é verdade se pelo menos uma entrada for verdade
Saída E é verdade se duas entradas forem verdade
Saída F é verdade se todas as três forem verdade
• Mostre a tabela verdade para estas três funções.
• Mostre as equações Booleanas para as três funções.
• Mostre uma implementação com portas inversoras, AND e OR.
Revisão: Álgebra Booleana & Portas
11
• Integrando uma ALU para supportar instruções andi e ori
– 1 bit ALU e usa-lo 32 vezes
• Implementação possível (soma de produtos):
b
a
operação
resultado
op a b res
ALU (arithmetic logic unit)
12
• Seleciona uma das entradas como saída, baseado em uma entrada 
de controle
• Integrando nossa ALU usando um MUX:
S
C
A
B
0
1
Revisão: Multiplexador
nota: Nós chamamos como mux 2-entrada 
 mesmo tendo 3 entradas!
13
• Não é fácil decidir o melhor caminho para a integração
– Não desejamos várias entradas para uma porta
– Não desejamos percorrer várias portas
– Para nosso propósito, a facilidade de compreensão é importante
• Vermos 1-bit ALU para soma:
• 1o - Como poderíamos integrar 1-bit ALU para add, and e or?
 2o - Como poderíamos integrar 32-bit ALU?
Implementações Diferentes
cout = a b + a cin + b cin
sum = a xor b xor cin
Sum
CarryIn
CarryOut
a
b
14
Integrando 32 bit ALU
b
0
2
Result
Operation
a
1
CarryIn
CarryOut
Result31
a31
b31
Result0
CarryIn
a0
b0
Result1
a1
b1
Result2
a2
b2
Operation
ALU0
CarryIn
CarryOut
ALU1
CarryIn
CarryOut
ALU2
CarryIn
CarryOut
ALU31
CarryIn
1o
2o
15
• Complemento de dois: negar b e somar.
• Como fazer para negar?
• Uma solução:
Como subtrair (a – b) ?
0
2
Result
Operation
a
1
CarryIn
CarryOut
0
1
Binvert
b
16
Também podemos escolher inverter a. Como obtemos um “a NOR b”?
Acrescentando uma função NOR
17
• Necessário suportar instrução set-on-less-than (slt)
– lembre-se: slt é uma instrução aritmética 
– produz 1 se rs < rt e 0 se não
– usar subtração: (a-b) < 0 implica em a < b
• Necessário suportar teste de igualdade (beq $t5, $t6, $t7)
– usar subtração: (a-b) = 0 implica a = b
Construindo a ALU para o MIPS
Suportando slt
19
20
Teste de igualdade
• Linhas de controle:
000 = and
001 = or
010 = add
110 = subtract
111 = slt
•Note: zero é um 1 quando o resultado é zero!
21
Conclusão
• Podemos integrar uma ALU para suportar o conjunto de instruções do 
MIPS 
– idéia chave: usar multiplexador para selecionar a saída
– podemos fazer subtrações usando complemento de dois
– podemos replicar 1-bit ALU para produzir 32-bit ALU
• Pontos importantes sobre hardware
– todas as portas estão sempre trabalhando
– a velocidade da porta é afetada pelo número de entradas da porta
– a velocidade de um circuito é afetada pelo número de portas em série
• Nosso primeiro foco: compreensão; entretanto,
– Mudanças na organização podem melhorar o desempenho
(similar a usar um algoritmo melhor em software)
– vejamos dois exemplos para soma e multiplicação
22
• Uma 32-bit ALU é tão rápida quanto uma 1-bit ALU?
• Existe mais de uma forma para somar?
– dois extremos: ripple carry e soma de produtos (sum-of-
products)
Você pode ver a propagação? 
c1 = b0c0 + a0c0 + a0b0
c2 = b1c1 + a1c1 + a1b1 c2 = 
c3 = b2c2 + a2c2 + a2b2 c3 = 
c4 = b3c3 + a3c3 + a3b3 c4 = 
Problema: somador “ripple carry” é lento
23
• Uma solução entre nossos dois extremos
• Motivação: 
– Se nós não conhecemos o valor do carry-in, como podemos fazer?
– Poderíamos gerar o “carry”? gi = ai bi 
– Poderíamos propagar o “carry”? pi = ai + bi
• Did we get rid of the ripple?
c1 = g0 + p0c0 
c2 = g1 + p1c1 c2 = 
c3 = g2 + p2c2 c3 = 
c4 = g3 + p3c3 c4 =
Somador “Carry-lookahead”
24
• 
Princípio para integrar grandes somadores
CarryIn
Result0--3
ALU0
CarryIn
Result4--7
ALU1
CarryIn
Result8--11ALU2
CarryIn
CarryOut
Result12--15
ALU3
CarryIn
C1
C2
C3
C4
P0
G0
P1
G1
P2
G2
P3
G3
pi
gi
pi + 1
gi + 1
ci + 1
ci + 2
ci + 3
ci + 4
pi + 2
gi + 2
pi + 3
gi + 3
a0
b0
a1
b1
a2
b2
a3
b3
a4
b4
a5
b5
a6
b6
a7
b7
a8
b8
a9
b9
a10
b10
a11
b11
a12
b12
a13
b13
a14
b14
a15
b15
Carry-lookahead unit
25
• Mais complicado que soma
– Resolvida através de somas e deslocamentos
• Mais tempo e mais área de chip
• Veremos 3 versões baseadas em algoritmos que aprendemos na 
escola
 0010 (multiplicando)
__x_1011 (multiplicador)
• Números negativos: converter e multiplicar 
– Há técnicas melhores
Multiplicação
26
Multiplicação: Implementação 
Done
1. Test
Multiplier0
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
32nd repetition?
Start
Multiplier0 = 0Multiplier0 = 1
No: < 32 repetitions
Yes: 32 repetitions
64-bit ALU
Control test
Multiplier
Shift right
Product
Write
Multiplicand
Shift left
64 bits
64 bits
32 bits
27
Segunda Versão
Multiplier
Shift right
Write
32 bits
64 bits
32 bits
Shift right
Multiplicand
32-bit ALU
Product Control test
Done
1. Test
Multiplier0
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
32nd repetition?
Start
Multiplier0 = 0Multiplier0 = 1
No: < 32 repetitions
Yes: 32 repetitions
28
Versão Final 
Control
testWrite
32 bits
64 bits
Shift rightProduct
Multiplicand
32-bit ALU
Done
1. Test
Product0
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
32nd repetition?
Start
Product0 = 0Product0 = 1
No: < 32 repetitions
Yes: 32 repetitions
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28