View
118
Download
4
Category
Preview:
Citation preview
Aritmética
Aula 03
Computador de von Neumann
Unidade lógica e aritmética
Diz respeito a: Desempenho (segundos, ciclos, instruções) Abstrações:
Arquitetura do Conjunto de Instruções Linguagem Assembly e Linguagem de
Máquina Para que serve:
Implementar a Arquitetura
32
32
32
operation
result
a
b
ALU
Aritmética MIPS • Todas as instruções usa 3 registradores• A ordem dos registradores é fixa (primeiro o registrador
destino)
Exemplo:
C code: A = B + C
MIPS code: add $s0, $s1, $s2
(associado às variáveis pelo compilador)
• Instrução slt – set on less thanif $s1 < $s2 then $t0 = 1
slt $t0, $s1, $s2 else $t0 = 0
Fluxo de Controle
Bits são apenas bits (sem nenhum significado inerente)— convenções definem a 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
Naturalmente resultam em algumas sofisticações:números são finitos (overflow)números fracionários e reaisnúmeros negativosp.ex., no MIPS não existe instrução de subtração
imediata - addi pode adicionar um número negativo) Como representamos números negativos?
i.e., que padrões de bits representam os números?
Números
Sinal e Magnitude Complemento de 1 Complemento de 2000 = +0 000 = +0 000 = +0001 = +1 001 = +1 001 = +1010 = +2 010 = +2 010 = +2011 = +3 011 = +3 011 = +3100 = -0 100 = -3 100 = -4101 = -1 101 = -2 101 = -3110 = -2 110 = -1 110 = -2111 = -3 111 = -0 111 = -1
Comparações: balanceamento, número de zeros, facilidade de operações Qual é o melhor? Por que?
Possíveis Representações
Números sinalizados de 32 bits:
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
Negar um número em complemento de 2: inverter todos os bits e
somar 1
lembrança: “negar” e “inverter” são diferentes!
Convertendo um número de n bits em números com mais de n bits:
Um dado imediato de 16 bits do MIPS é convertido para 32 bits em
aritmética
Copiar o bit mais significativo (o bit de sinal) para outros bits
0010 -> 0000 0010
1010 -> 1111 1010
"sign extension"
Operações em Complemento de 2
Como no curso primário (carry/borrow) 0111 0111 0110
+ 0110 - 0110 - 0101
Operações em complemento de 2 subtração usando soma de números negativos
0111+ 1010
Overflow (resultado muito grande para um computador de tamanho de palavra finito): P.ex., somando dois números de n-bits não resulta em n-bits
0111 + 0001 note que o bit de overflow é enganoso,
1000 ele não significa um carry de transbordo
Adição & Subtração
Não ocorre overflow quando se soma um número positivo e um negativo quando os sinais são os mesmos para a subtração
Overflow ocorre quando o valor afeta o sinal: quando somando dois positivos resulta num negativo ou, somando dois negativos resulta num positivo ou, subtraindo um negativo de um positivo e dá um negativo ou, subtraindo um positivo de um negativo e dá um positivo
Considerar as operações A + B, e A – B Pode ocorrer overflow se B é 0 ? Pode ocorrer overflow se A é 0 ?
Detectando Overflow
Uma exceção (interrupt) ocorre A instrução salta para endereço predefinido para a
rotina de exceção O endereço da instrução interrompida é salvo para
possível retorno
Nem sempre se requer a detecção do overflow— novas instruções MIPS: addu, addiu, subu
nota: addiu still sign-extends!nota: sltu, sltiu for unsigned comparisons
Efeitos do Overflow
Problema: Considerar uma função lógica com 3 entradas: A, B, e C.
A saída D é “true” se pelo menos uma entrada é “true” A saída E é “true” se exatamente duas entradas são “true”
A saída F é “true” somente se todas as três entradas são “true”
Mostrar a tabela verdade para essas três funções.
Mostrar as equações Booleanas para as três funções.
Mostrar uma implementação consistindo de portas inversoras, AND, e OR.
Revisão: Álgebra Booleana & Portas
Seja uma ALU para suportar as instruções andi e ori Projetar uma ALU de 1 bit, e replicá-la 32 vezes
Possível implementação (soma-de-produtos):
b
a
operation
result
op a b res
Uma ALU (arithmetic logic unit)
Seleciona uma das entradas para a saída, baseado numa entrada de controle
Seja construir a nossa ALU usando um MUX:
S
CA
B
0
1
Revisão: Multiplexador
nota: mux de 2-entradas embora tenha 3 entradas!
Não é fácil decidir a “melhor” forma para construir algo Não queremos muitas entradas para uma única porta (fan-in) Não queremos distribuir para muitas portas (fan-out) Para o nosso propósito, facilidade de compreensão é importante
Seja a ALU de 1-bit para soma:
Como construir uma ALU de 1-bit para soma, AND e OR? Como construir uma ALU de 32-bits?
Implementação de ALU de um bit
cout = a b + a cin + b cin
sum = a xor b xor cinSum
CarryIn
CarryOut
a
b
Construindo uma ALU de 32 bits
b
0
2
Result
Operation
a
1
CarryIn
CarryOut
Result31a31
b31
Result0
CarryIn
a0
b0
Result1a1
b1
Result2a2
b2
Operation
ALU0
CarryIn
CarryOut
ALU1
CarryIn
CarryOut
ALU2
CarryIn
CarryOut
ALU31
CarryIn
Técnica do complemento de 2: apenas negar b e somar.
Como negar?
Solução:
E sobre subtração (a – b) ?
0
2
Result
Operation
a
1
CarryIn
CarryOut
0
1
Binvert
b
Deve suportar a instrução set-on-less-than (slt)
lembrar: slt é uma instrução aritmética
produz um 1 se rs < rt, e 0 caso contrário
usar subtração: (a - b) < 0 implica a < b
Deve suportar o teste para igualdade (beq $t5, $t6, $t7)
usar subtração: (a - b) = 0 implica a = b
Outras operações da ALU do MIPS
Suportando slt
Desenhando a idéia?
0
3
Result
Operation
a
1
CarryIn
CarryOut
0
1
Binvert
b 2
Less
0
3
Result
Operation
a
1
CarryIn
0
1
Binvert
b 2
Less
Set
Overflowdetection
Overflow
a.
b.
Seta31
0
ALU0 Result0
CarryIn
a0
Result1a1
0
Result2a2
0
Operation
b31
b0
b1
b2
Result31
Overflow
Binvert
CarryIn
Less
CarryIn
CarryOut
ALU1Less
CarryIn
CarryOut
ALU2Less
CarryIn
CarryOut
ALU31Less
CarryIn
Teste de igualdade
•Nota: zero é 1 quando o resultado é zero!
Seta31
0
Result0a0
Result1a1
0
Result2a2
0
Operation
b31
b0
b1
b2
Result31
Overflow
Bnegate
Zero
ALU0Less
CarryIn
CarryOut
ALU1Less
CarryIn
CarryOut
ALU2Less
CarryIn
CarryOut
ALU31Less
CarryIn
Linhas de controle
000 = and001 = or010 = add110 = subtract111 = slt
Operation
Binvert
Conclusão Podemos construir uma ALU para suportar o conjunto de instruções
MIPS
-- usando multiplexador para selecionar a saída desejada realizando uma subtração usando o complemento de 2 replicando uma ALU de 1-bit para produzir uma ALU de 32-bits
Pontos importantes sobre o hardware Todas as portas estão sempre trabalhando A velocidade de uma porta é afetada pelo número de entradas da porta A velocidade de um circuito é afetado pelo número de portas em série
(no caminho crítico ou nivel mais profundo da lógica) Mudanças inteligentes na organização pode melhorar o desempenho
(similar a usar algoritmos melhores em software)
Uma ALU de 32-bits é tão rápida quanto uma ALU de 1-bit? Existem mais de uma forma de somar?
dois extremos: ripple carry e soma-de-produtos
Voce pode ver a propagação do vai-um? Como resolvê-lo?
c1 = a0c0 + b0c0 + a0b0 = (a0 + b0)c0 + a0b0
c2 = a1c1 + b1c1 + a1b1
c3 = a2c2 + b2c2 + a2b2
c4 = a3c3 + b3c3 + a3b3
Problema: somador ripple carry (vai-um propagado) é lento
Uma técnica intermediária entre dois extremos Motivação:
Se não sabemos o valor do carry-in, o que fazemos? Quando sempre geramos um carry? gi = ai bi
Quando propagamos um carry? pi = ai + bi
Resolvemos o ripple calculando o vai-um antecipadamente, usando as equações:
c1 = g0 + p0c0
c2 = g1 + p1c1
c3 = g2 + p2c2
c4 = g3 + p3c3
Somador de vai-um antecipado - (Carry-lookahead) - CLA
usar o princípio de CLA novamente!
Construção de somadores grandes
CarryIn
Result0--3
ALU0
CarryIn
Result4--7
ALU1
CarryIn
Result8--11
ALU2
CarryIn
CarryOut
Result12--15
ALU3
CarryIn
C1
C2
C3
C4
P0G0
P1G1
P2G2
P3G3
pigi
pi + 1gi + 1
ci + 1
ci + 2
ci + 3
ci + 4
pi + 2gi + 2
pi + 3gi + 3
a0b0a1b1a2b2a3b3
a4b4a5b5a6b6a7b7
a8b8a9b9
a10b10a11b11
a12b12a13b13a14b14a15b15
Carry-lookahead unit
Mais complicado que somaRealizado via deslocamento e soma
Mais tempo e mais áreaVejamos 3 versões baseados no algoritmo
0010 (multiplicando)
__x_1011 (multiplicador)
Números negativos: converter e multiplicar
Multiplicação
Multiplicação: Implementação
Done
1. TestMultiplier0
1a. Add multiplicand to product andplace 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
MultiplierShift right
ProductWrite
MultiplicandShift left
64 bits
64 bits
32 bits
Segunda Versão
MultiplierShift right
Write
32 bits
64 bits
32 bits
Shift right
Multiplicand
32-bit ALU
Product Control test
Done
1. TestMultiplier0
1a. Add multiplicand to the left half ofthe product and place the result inthe 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
Versão Final
ControltestWrite
32 bits
64 bits
Shift rightProduct
Multiplicand
32-bit ALU
Done
1. TestProduct0
1a. Add multiplicand to the left half ofthe product and place the result inthe 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
Multiplicação Paralela
a5 a4 a3 a2 a1 a0 = A
x b5 b4 b3 b2 b1 b0 = B ___________________________________ a5b0 a4b0 a3b0 a2b0 a1b0 a0b0 = W1 a5b1 a4b1 a3b1 a2b1 a1b1 a0b1 = W2 a5b2 a4b2 a3b2 a2b2 a1b2 a0b2 = W3 a5b3 a4b3 a3b3 a2b3 a1b3 a0b3 = W4 a5b4 a4b4 a3b4 a2b4 a1b4 a0b4 = W5 a5b5 a4b5 a3b5 a2b5 a1b5 a0b5 = W6_________________________________________________________________ P11 P10 P9 P8 P7 P6 P5 P4 P3 P2 P1 P0 = AxB=P
CPA – Carry Propagation Adder Faz a adição de 2 números A e B para produzir o resultado A +
B. CSA – Carry Save Adder Faz a adição de 3 números A, B e D, produzindo dois resultados:
soma S e vai-um C. Matematicamente, tem-se A + B + D = S + C.
A = 1 1 1 1 0 1 B = 0 1 0 1 1 0 D = 1 1 0 1 1 1 __________________________ C = 1 1 0 1 1 1 S = 0 1 1 1 0 0 __________________________ A + B + D = S + C = 1 0 0 0 1 0 1 0
Somadores
Circuito de Multiplicação Paralela
Gerador de multiplicandos deslocados
CSA1 CSA2
CSA3
CSA4
CPA
A B
P = A x B
111011 110111
gerador de multiplicandos deslocados
111011 111011 000000 111011 111011 111011
CSA1 CSA2
CSA3
CSA4
CPA
10100001011111101001101001100100
100100011010001111000001100100
001100101101010011000000
110010101101
12345
13
4
4
1
1
A B
AxB
Exemplo
Ponto Flutuante Necessitamos de uma forma para representar
Números com frações, p.ex., 3.1416
Números muito pequenos, p.ex., .000000001
Números muito grandes, p.ex., 3.15576 109
Representação: Sinal, expoente, significando: (–1)sinal significando 2expoente
Mais bits para o significando dá mais resolução
Mais bits para o expoente aumenta o intervalo (range)
Padrão ponto flutuante IEEE 754: Precisão simples: expoente de 8 bits, significando de 23 bits
Precisão dupla: expoente de 11 bits, significando de 52 bit
Padrão de ponto flutuante IEEE 754 O primeiro bit (leading bit), “1” do significando é implícito
Expoente é “polarizado” para fazer a separação facilmente bias de 127 para precisão simples e 1023 para precisão dupla
Resumo: (–1)sinal significando) 2expoente – bias
Exemplo:
decimal: -.75 = -3/4 = -3/22
binário: -.11 = -1.1 x 2-1
Ponto flutuante: expoente = 126 = 01111110
Precisão simples IEEE: 10111111010000000000000000000000
Complexidade do Ponto Flutuante
Além do overflow tem “underflow”
Precisão pode ser um grande problema
IEEE 754 mantem dois extra bits, guard e round
Quatro modos de arredondamento
positivo dividido por zero resulta em “infinito”
zero dividido por zero resulta em “not a number”
Outras complexidades A Implementação do padrão pode ser complicado Não usar o padrão pode ser mesmo pior
Formato
s é o bit de sinal s = 0 positivo s=1 negativo
exp é usado para obter Efrac é usado para obter M
Valor representado (-1)s M 2E
Significando M é um valor fracionário no intervalo [1.0,2.0), para números normalizados e [0 e 1) para números denormalizados
Exponente E fornece o peso em potência de dois
Representação ponto flutuanteRepresentação ponto flutuante
s exp frac
Valores numéricos NormalizadosValores numéricos NormalizadosCondição
exp 000…0 e exp 111…1Expoente codificado como valor polarizado (biased)
E = exp – biasexp : valor não sinalizado bias : valor da polarização
Precisão Simples: 127 (exp: 1…254, E: -126…127)Precisão dupla: 1023 (exp: 1…2046, E: -1022…1023)Em geral: bias = 2e-1 - 1, onde e e´ o numero de bits do
expoente
Significando codificado com bit 1 mais significativo (leading bit) implicito M = 1.xxx…x2
xxx…x: bits da fracMinimo quando 000…0 (M = 1.0)Maximo quando 111…1 (M = 2.0 – )O bit extra (leading bit 1) e´ obtido “implicitamente”
Valores denormalizadosValores denormalizados Condição
exp = 000…0 Valor
Valor do Expoente E = –Bias + 1 Valor do Significando M = 0.xxx…x2
xxx…x: bits de frac Casos
exp = 000…0, frac = 000…0 Representa valor 0 Nota-se que existem valores distintos +0 e –0
exp = 000…0, frac 000…0 Numeros muito próximos de 0.0 Perde precisão à medida que vai diminuindo “ underflow gradual”
Valores especiaisValores especiais Condição
exp = 111…1 Casos
exp = 111…1, frac = 000…0 Representa valor(infinito) Operação que transborda (overflow) Ambos positivo e negativo P. ex., 1.0/0.0 = 1.0/0.0 = +, 1.0/0.0 =
exp = 111…1, frac 000…0 Not-a-Number (NaN) Nenhum valor numérico pode ser determinado P. ex., sqrt(–1),
Resumo da codificação de números reais em ponto flutuanteResumo da codificação de números reais em ponto flutuante
NaNNaN
+
0
+Denorm +Normalizado-Denorm-Normalizado
+0
Representação ilustrativa de 8 bits Representação ilustrativa de 8 bits Representação ponto flutuante de 8 bits
O bit de sinal e´ o bit mais significativo.Os seguintes quatro bits são expoente, com
bias de 7.Os últimos três bits bits são frac
Semelhante a forma geral no formato IEEEnormalizado, denormalizadoRepresentação de 0, NaN, infinito
s exp frac
02367
Valores Relativos ao ExpoenteValores Relativos ao Expoente exp E 2E
0 0000 -6 1/64 (denorms)1 0001 -6 1/642 0010 -5 1/323 0011 -4 1/164 0100 -3 1/85 0101 -2 1/46 0110 -1 1/27 0111 0 18 1000 +1 29 1001 +2 410 1010 +3 811 1011 +4 1612 1100 +5 3213 1101 +6 6414 1110 +7 12815 1111 n/a (inf, NaN)
Intervalo Intervalo s exp frac E Valor
0 0000 000 -6 00 0000 001 -6 1/8*1/64 = 1/5120 0000 010 -6 2/8*1/64 = 2/512…0 0000 110 -6 6/8*1/64 = 6/5120 0000 111 -6 7/8*1/64 = 7/5120 0001 000 -6 8/8*1/64 = 8/5120 0001 001 -6 9/8*1/64 = 9/512…0 0110 110 -1 14/8*1/2 = 14/160 0110 111 -1 15/8*1/2 = 15/160 0111 000 0 8/8*1 = 10 0111 001 0 9/8*1 = 9/80 0111 010 0 10/8*1 = 10/8…0 1110 110 7 14/8*128 = 2240 1110 111 7 15/8*128 = 2400 1111 000 n/a inf
Mais perto de zero
maior denormmenor norm
perto de 1 abaixo
perto de 1 acima
maior norm
números denormalizados
númerosNormalizados
Distribuição de valoresDistribuição de valoresFormato de 6-bits tipo IEEE
e = 3 bits de expoentef = 2 bits de fracaobias e´ 3
Notar como a distribuição fica mais densa perto de zero.
-15 -10 -5 0 5 10 15
Denormalized Normalized Infinity
Distribuição de Valores perto de zeroDistribuição de Valores perto de zero
Formato de 6-bits, tipo IEEEe = 3 bits de expoentef = 2 bits de fraçãoBias igual a 3
-1 -0,5 0 0,5 1Denormalized Normalized Infinity
Numeros interessantesNumeros interessantesDescrição exp frac valor numéricoZero 00…00 00…00 0.0menor Pos. Denorm. 00…00 00…01 2– {23,52} X 2–
{126,1022}
Single 1.4 X 10–45
Double 4.9 X 10–324
maior Denorm. 00…00 11…11 (1.0 – ) X 2– {126,1022}
Single 1.18 X 10–38
Double 2.2 X 10–308
menor Pos. Norm. 00…01 00…00 1.0 X 2– {126,1022}
Um 01…11 00…00 1.0 maior Normalized 11…10 11…11 (2.0 – ) X
2{127,1023}
Single 3.4 X 1038
Double 1.8 X 10308
Operações em ponto flutuanteOperações em ponto flutuanteConceitualmente
Primeiro computar o resultado exatoFazê-lo enquadrar na precisão desejada
transborda se o expoente for muito grandearredonda para caber no frac
Modos de arredondamento 1.40 1.60 1.50 2.50 –1.50
Zero 1 1 1 2 –1Round down (-) 1 1 1 2 –2Round up (+) 2 2 2 3 –1Nearest Even (default) 1 2 2 2 –2
Nota:1. Round down: resultado e´perto mas não maior que o resultado verdadeiro.2. Round up: resultado e´perto mas não menor do que o resultado verdadeiro.
Multiplicação em FPMultiplicação em FPOperandos(–1)s1 M1 2E1 * (–1)s2 M2 2E2
Resultado exato(–1)s M 2E
Sinal s: s1 xor s2Significando M: M1 * M2Expoente E: E1 + E2
Representação finalse M ≥ 2, deslocar à direita M, incrementar
E se E fora do intervalo, overflow Arredonda M para caber em frac
Adição FPAdição FP Operandos
(–1)s1 M1 2E1
(–1)s2 M2 2E2
Assumir E1 > E2 Resultado exato
(–1)s M 2E
Sinal s, significando M: Resultado de alinhamento e adição
Expoente E: E1 Representação final
Se M ≥ 2, deslocar à direita M, incrementa E Se M < 1, deslocar à esquerda M de k posições,
decrementar E de k Overflow se E fora do intervalo arredonda M para caber em frac
(–1)s1 M1
(–1)s2 M2
E1–E2
+
(–1)s M
Ariane 5Ariane 5 Explodiu 37 segundos
após decolagem Por que?
Foi computada a velocidade horizontal como número em ponto flutuante
Convertido para inteiro de 16-bits
Funcionou bem para Ariane 4
Ocorreu Overflow para Ariane 5
Foi usado o mesmo software
Recommended