Capítulo 3

Aritmética de Computadores

Aritmética para Computadores

� Operações com inteiros

� Adição e subtração

� Multiplicação e divisão

� Lidado com estouro aritmético

� Números reais em ponto flutuante

� Representação e operações

Adição de Inteiros

� Exemplo: 7 + 6

� Estouro se o resultado estiver fora do intervalo

� Somando operandos +ve e –ve, não existe estouro

� Somando dois operandos +ve

� Estouro se o resultado do bit de sinal é 1

� Somando dois operandos –ve

� Estouro se o resultado do bit de sinal é 0

0 + 0 = 01 + 0 = 11 + 1 = 10 = 0 + carry de 1 p/ próxima posição

Subtração de Inteiros

� Adiciona negação do segundo operando

� Exemplo: 27 – 13 = 27 – (13) = 14

27: 1101113: - 0110114: 01110

� Estouro se o resultado estiver fora do intervalo

� Subtraindo dois operandos +ve ou dois operandos –ve, não existe estouro (lembrete: x – y = x + (-y))

� Subtraindo operando +ve de –ve

� Estouro se o resultado do bit de sinal for 0

� Subtraindo operando –ve de +ve� Estouro se o resultado do bit de sinal for 1

0 – 0 = 01 – 1 = 01 – 0 = 10 – 1 → toma emprestado → 10–1=1

Complementa e adiciona 1

Condições de Estouro

� Combinação de operações, operandos e resultados que indicam estouro

Lidando com Estouro

� Algumas linguagens (e.g., C) ignoram estouro

� Use as instruções do MIPS addu, addui, subu paraignorar o estouro

� Outras linguagens (e.g., Ada, Fortran) exigemlançar uma exceção

� Use as instruções do MIPS add, addi, sub paraconsiderar estouro

� No estouro, invocar o manipulador de exceção

� Salvar PC no registrador do contador de programa daexceção (EPC)

� Salta para o endereço do tratador pré-definido

� Instrução mfc0 (move do coprocessador reg) pode acessaro valor do EPC, para retornar depois da ação corretiva

Aritmética para Multimedia

� Processamento gráfico e de mídia opera em vetores de dados de 8 e 16 bits

� Use somador de 64 bits, com cadeia de carry

particionado

� Opera em vetores de 8×8-bit, 4×16-bit, ou 2×32-bit

� SIMD (single-instruction, multiple-data)

� Saturando operações

� Para overflow, o resultado é o maior valor representável

� c.f. módulo aritmético de complemento de 2

� E.g., botão com saturação pararia no volume mais alto ( )( ) ww

overflowunsigned rrl 22mod_

≤−⇔

Multiplicação

� Começe com a abordagem de multiplicação longa

1000× 1001

10000000 0000 1000 1001000

Comprimento do produto é a soma dos comprimentos do operando

multiplicando

multiplicador

produto

O comprimento da multiplicação de um multiplicando n e um multiplicador m é um produto n + m

Copia multiplicando se o dígito for 1

Hardware de Multiplicação

Inicialmente 0

O LSB do multiplicador determina se o multipicando é adicionado ao registrador do produto

Estes três passos são repetidos 32 vezes para obter o produto

Exemplo

� Usando números de 4 bits para salvar espaço, multiplique 210 × 310 ou 00102 × 00112 usando o algoritmo de multiplicação

Multiplicador Otimizado

� Executa os passos em paralelo: soma/desloca

� O multiplicador e o multiplicando são deslocados enquanto o multiplicando é adicionado ao produto

� Caso o bit do multiplicador seja um

O produto é deslocado para direita

O multiplicador é colocado no MSB do registrador de produto

Um ciclo por soma do produto parcial

Multiplicador Mais Rápido

� Usa somadores múltiplos

� Balanceamento de custo/desempenho

� Este hardware “desenrola o laço” para usar 31 somadores

� Várias multiplicação executadas em paralelo para minimizar tempo

Multiplicação do MIPS

� Dois registradores de 32 bits para o produto

� HI: 32 bits mais significante

� LO: 32 bits menos significante

� Instruções

� mult rs, rt / multu rs, rt

� Produto de 64 bits em HI/LO

� mfhi rd / mflo rd

� Move de HI/LO para rd

� Pode tesar o valor de HI para checar se o produto estourou os 32 bits

� mul rd, rs, rt

� 32 bits menos significante do produto –> rd

Exercício 1

� Efetue as seguintes operações

a) 1012 + 112

b) 10110112 + 10110102

c) 10012 – 1012

d) 110102 – 100112

Exercício 2

� Efetue as seguintes multiplicações:

a) 11012 × 10102

b) 101012 × 1102

c) 100110101102 × 11112

Exercício 3

� Usando números de 4 bits para salvar espaço, multiplique 310 × 410 ou 00112 × 01002 usando o algoritmo de multiplicação

Divisão

� Checa por divisor 0

� Abordagem da divisão longa

� Se os bits do divisor ≤ dividendo

� 1 bit no quociente, subtrai

� Caso contrário

� 0 bit no quociente, abaixa próximo bit de dividendo

� Restaurando a divisão

� Faz a substração, e se o resto for < 0, adiciona o divisor de volta

� Divisão com sinal

� Divide usando valores absoluto

� Ajusta o sinal do quociente e resto quando necessário

10011000 1001010

-100010101 1010-1000

10

operandos de n-bit produz quociente e resto de n-bit

quociente

dividendo

resto

divisor

Dividendo=Quociente×Divisor+Resto ∴Dividendo=9×8+2=74

div

idendo

Exercício

� Realize a divisão de 01112 por 00102

� Realize a divisão de 1101002 por 1002

110100 100-100 1101

101-100

10100-100

0

111 10-10 11

11-10

1

Hardware da Divisão

Inicialmente dividendo

Inicialmente divisor na metade

esquerda

Exemplo

� Usando uma versão de 4 bits do algoritmo, tente dividir 710 por 210 ou 01112 por 00102

Exercício

� Usando uma versão de 4 bits do algoritmo, tente dividir 610 por 210 ou 0000 01102 por 00102

Divisor Otimizado

� Um ciclo por subtração do resto parcial

� Parece bastante como um multiplicador!

� Mesmo hardware pode ser usado para ambos

Combina o registrador do quociente com a metade direita do registrador do resto

Divisão Mais Rápida

� Não pode usar hardware paralelo como no multiplicador

� Subtração está condicionada no sinal do resto

� Divisores mais rápidos geram mútiplos bits do quociente por passo

� Ainda exige múltiplos passos

Divisão do MIPS

� Usa registradores HI/LO para resultado

� HI: resto de 32 bits

� LO: quociente de 32 bits

� Instruções

� div rs, rt / divu rs, rt

� Sem estouro ou checagem de divisão por 0

� Software deve executar checagens se necessário

� Usa mfhi, mflo para acessar resultado

Ponto Flutuante

� Representação de números não-inteiros

� Incluindo números muito pequenos e muito grandes

� Como notação científica (um dígito à esquerda do ponto decial)

� –2.34 × 1056

� +0.002 × 10–4

� +987.02 × 109

� Em binário

� ±1.xxxxxxx2 × 2yyyy

� Tipos float e double em C

normalizado

não normalizado

Normalizado: um número em notação de ponto flutuante que não tem líder 0s

Padrão de Ponto Flutuante

� Definido pela IEEE Std 754-1985

� Desenvolvido em resposta a divergência de representações

� Problemas de portabilidade de código científico

� Agora, quase universalmente adotado

� Duas representações

� Precisão simples (32-bit)

� Precisão dupla (64-bit)

Formato de Ponto Flutuante IEEE

� S: bit de sinal (0 ⇒ positivo, 1 ⇒ negativo)� Para suportar ainda mais bits, IEEE 754 faz o uso implícito

do líder 1-bit dos números binários normalizados� precisão simples: o número é 24 bits (implica 1+uma fração de 23 bits)� Precisão dupla: o número é 53 bits (implica 1+uma fração de 52 bits)

� Expoente: excesso de representação: expoente real+viés� Assegure que o expoente é não sinalizado� Simples: Viés = 127; Duplo: Viés = 1023

S Expoente Fração

r. simples: 8 bitsr. dupla: 11 bits

r. simples: 23 bitsr. dupla: 52 bits

Viés)(ExpoenteS 2Fração)(11)(x −×+×−=

O significante representa o número de 24- ou 53-bits que é 1 mais a fração; e a fração quando referimos o número de 23- e 52-bits

Formato de Ponto Flutuante IEEE

� Os bits da fração representam um número entre 0 e 1 e E representa o valor no campo do expoente

� Se numerarmos os bits da fração da esquerda para direita s1, s2, s3,…, então o valor é

� A notação desejável deve representar o expoente mais negativo como 00..002 e o mais positivo como 11..112

� Esta convenção é chamda notação de viés

� Expoente sendo subtraído do viés para representar o maior e menor valor do expoente real

� Se usarmos o bit de sinal em E, diminuiríamos o intervalo de número que podem ser representados

( ) ( ) ( ) ( )( ) VESsss

−−−−×+×+×+×+×− 223222111

321K

Intervalo da Precisão Simples

� Expoentes 00000000 e 11111111 reservado

� Menor valor

� Expoente: 00000001⇒ expoente real = 1 – 127 = –126

� Fração: 000…00 ⇒ significante = 1.0

� ±1.0 × 2–126 ≈ ±1.2 × 10–38

� Maior valor

� Expoente: 11111110⇒ expoente real = 254 – 127 = +127

� Fração: 111…11 ⇒ significante ≈ 2.0

� ±2.0 × 2+127 ≈ ±3.4 × 10+38

Intervalo da Precisão Dupla

� Expoentes 0000…00 e 1111…11 reservado

� Menor valor

� Expoente: 00000000001⇒ expoente real = 1 – 1023 = –1022

� Fração: 000…00 ⇒ significante = 1.0

� ±1.0 × 2–1022 ≈ ±2.2 × 10–308

� Maior valor

� Expoente: 11111111110⇒ expoente real = 2046 – 1023 = +1023

� Fração: 111…11 ⇒ significante ≈ 2.0

� ±2.0 × 2+1023 ≈ ±1.8 × 10+308

Precisão do Ponto Flutuante

� Precisão relativa

� Todos os bits de fração são significativos

� Simples: aproximadamente 2–23

� Equivalente a 23 × log102 ≈ 23 × 0.3 ≈ 6 dígitos decimais de precisão

� Duplo: aproximadamente 2–52

� Equivalente a 52 × log102 ≈ 52 × 0.3 ≈ 16 dígitos decimais de precisão

Exemplo de Ponto Flutuante (1)

� Representar –0.75

� O número -0.7510 é também -3/410 ou -3/2210

� Representado pela fração binária -112/22

10 ou -1.12×2-1

� –0.75 = (–1)1 × 1.12 × 2–1, onde S = 1

� 1 + Fração = .1000…002

� Expoente Real (i.e., ER = E - V) deve ser igual a –1� Simples: E = –1 + 127 = 126 = 011111102

� Duplo: E = –1 + 1023 = 1022 = 011111111102

� Simples: 1011111101000…00

� Duplo: 1011111111101000…00

sinal expoente fração

Exemplo de Ponto Flutuante (2)

� Qual número é representado pelo seguinte flutuante de precisão simples

11000000101000…00

� S = 1 (representa número negativo)

� Fração = 01000…002 = 1×2-2 = 0.25

� Expoente = 100000012 = 129

� x = (–1)1 × (1 + 0.25) × 2(129 – 127)

= (–1) × 1.25 × 22

= –5.0

Exercício (1)

� Representar -0.5 em ponto flutuante com precisao simples e dupla

� Representar 0.25 em ponto flutuante com precisao simples e dupla

� Representar -0.4375 em ponto flutuante com precisao simples e dupla

Exercício (2)

� Qual número é representado pelo seguinte flutuante de precisão simples

11111111100000…00

10000000100000…00

Adição de Ponto Flutuante

� Consideremos um exemplo decimal de 4 dígitos� 9.999 × 101 + 1.610 × 10–1

� 1. Alinhas os pontos decimais� Deslocar número com expoente menor

� 9.999 × 101 + 0.016 × 101

� 2. Adicionar significante� 9.999 × 101 + 0.016 × 101 = 10.015 × 101

� 3. Normalizar o resultado & checar estouro positivo/negativo� 1.0015 × 102

� 4. Arredondar e normalizar, se necessário� 1.002 × 102

127 ≥ 2 ≥ -126

Adição de Ponto Flutuante

� Agora consideremos um exemplo binário de 4 digitos

� 1.0002 × 2–1 + –1.1102 × 2–2 (0.5 + –0.4375)

� 1. Alinhar pontos binários

� Deslocar número com expoente menor

� 1.0002 × 2–1 + –0.1112 × 2–1

� 2. Adicionar significante

� 1.0002 × 2–1 + –0.1112 × 2–1 = 0.0012 × 2–1

� 3. Normalizar resultado & checar estouro positivo/negativo

� 1.0002 × 2–4, sem estouro positivo/negativo

� 4. Arredondar e renormalizar, se necessário

� 1.0002 × 2–4 (sem mudança)

� 0.0001000 = 8 / 27 = 0.0625

127 ≥ -4 ≥ -126

Hardware para Adicionar PF

� Muito mais complexo do que o somador de inteiros

� Fazê-lo em um ciclo de relógio levaria muito tempo

� Muito mais longo do que operações com números inteiros

� Relógio mais lento penaliza todas as instruções

� Somador de ponto flutuante geralmente leva mais ciclos de relógio

� Pode ser pipelined

Algoritmo do Somador de PF

� Passo 1 e 2 similar ao exemplo do slide anterior

� Adicionar o significante do número com o menor expoente e então somar os dois significantes

� Passo 3 normaliza os resultados, forçando a verificação do estouro

� Precisão simples: o máximo exp. é 127 e o mínimo é -126

� Precisão dupla: o máximo exp. é 1023 e o mínimo é -1022

Hardware para Somador de PF

Passo 1

Passo 2

Passo 3

Passo 4

⇒ subtrai expoentes

⇒ multiplexador

⇒ multiplexador

Exercício

� Tente somar os números 0.2510 e 0.12510 em binário usando o algoritmo do somador em ponto flutuante

Multiplicação de Ponto Flutuante

� Consideremos um exemplo decimal de 4 dígitos� 1.110 × 1010 × 9.200 × 10–5

� 1. Adicionar expoentes� Para expoentes negativos, subtrair viés de soma

� Novo expoente = 10 + (–5) = 5

� 2. Multiplicar significantes� 1.110 × 9.200 = 10.212 ⇒ 10.212 × 105

� 3. Normalizar o resultado & checar estouro� 1.0212 × 106

� 4. Arredondar e renomalizar, se necessário� 1.021 × 106

� 5. Determinar o sinal do resultado apartir dos sinais dos operandos� +1.021 × 106

Multiplicação de Ponto Flutuante

� Agora consideremos um exemplo binário de 4 bits� 1.0002 × 2–1 × –1.1102 × 2–2 (0.5 × –0.4375)

� 1. Adicionar expoentes� Novo expoente: –1 + (–2) = –3

� Viés: (–1 + 127) + (–2 + 127) = –3 + 254 – 127 = –3 + 127

� 2. Multiplicar significantes� 1.0002 × 1.1102 = 1.1102 ⇒ 1.1102 × 2–3

� 3. Normalizar o resultado & checar estouro� 1.1102 × 2–3 sem estouro positivo/negativo

� 4. Arredondar e renormalizar, se necessário� 1.1102 × 2–3 (nenhuma mudança)

� 5. Determinar o sinal: +ve × –ve ⇒ –ve� –1.1102 × 2–3

� 0.001110 = 14 / 26 = –0.21875

ER = E - V

Algoritmo do Multiplicador de PF

� Inicia com o cálculo do novo do produto, seguido da multiplicação dos significantes e por uma normalização

� Checa se houve estouro no tamanho do expoente, e então o produto é arredondado

� Se o arredondamento levar a normalização, checa-se novamente o tamanho dos expoentes

Hardware para Aritmética de PF

� Multiplicador de ponto flutuante é de complexidade similar ao somador

� Mas usa um multiplicador para o significante em vez de um somador

� Hardware de ponto flutuante geralmente realiza

� Adição, subtração, multiplicação, divisão, raiz quadrada

� Conversão entre ponto flutuante ↔ inteiro

� Operações geralmente levam vários ciclos de relógio

� Pode ser pipelined

Instruções de PF no MIPS

� Hardware de PF é o coprocessador 1� Processador adjunto que estende o ISA

� Registradores de PF são separados� Precisão simples de 32: $f0, $f1, … $f31� Pareado para decisão dupla: $f0/$f1, $f2/$f3, …

� Versão 2 do MIPs ISA suporta reg’s de PF de 32 × 64-bit

� Instruções de PF operam somente em registradoresde PF� Programas geralmente não realizam operações de

inteiro em PF, ou vice-versa� Mais registradores com impacto mínimo no tamanho

do código

� Instruções de load e store de PF� lwc1, ldc1, swc1, sdc1 w ⇒ word

d ⇒ double word

Instruções de PF no MIPS

� Aritmética de precisão simples� add.s, sub.s, mul.s, div.s

� e.g., add.s $f0, $f1, $f6

� Aritmética de precisão dupla� add.d, sub.d, mul.d, div.d

� e.g., mul.d $f4, $f4, $f6

� Comparação de precisão simples e dupla� c.xx.s, c.xx.d (xx representa eq, lt, le, …)

� Seta ou limpa bit do código de condição do PF� e.g. c.lt.s $f3, $f4

� Desvia num código de condição de PF (true ou false)� bc1t, bc1f

� e.g., bc1t TargetLabel

Exemplo de PF: °F para °C

� Código C :float f2c (float fahr) {

return ((5.0/9.0)*(fahr - 32.0));}

� fahr em $f12, resultado em $f0, literais no espaço de memória global

� Código MIPS compilado:f2c: lwc1 $f16, const5($gp)

lwc1 $f18, const9($gp)div.s $f16, $f16, $f18lwc1 $f18, const32($gp)sub.s $f18, $f12, $f18mul.s $f0, $f16, $f18jr $ra

0($gp)

4($gp)

8($gp)

Interpretação de Dados

� Bits não têm significado inerente

� Eles podem representar inteiros com/sem sinal, números de ponto flutuante e instruções

� Interpretação depende das instruções aplicadas

� Representações computacionais de números

� Intervalo e precisão finita

� Necessário levar em conta o tamanho finito das palavras nos programas

The BIG Picture

Associatividade

� Programas paralelos podem intercalar operações em ordens inesperadas

� Suposição da associatividade pode falhar devido as aproximações e a precisão limitada

(x+y)+z x+(y+z)

x -1.50E+38 -1.50E+38

y 1.50E+38

z 1.0 1.0

1.00E+00 0.00E+00

0.00E+00

1.50E+38

� Precisa validar programas paralelos sob diferentes níveis de paralelismo

O número 1.5010x1038 é muito maior do que 1

Divisão e Deslocamento para Direita

� Deslocamento para esquerda por i multiplica um inteiro por 2i

� Deslocamento para direita divide por 2i?

� Somente para inteiros sem sinal

� Para inteiros com sinal

� Deslocamento à direita aritmético: replica o bit de sinal

� e.g., –5 / 4

� 111110112 >> 2 = 111111102 = –2

� O resultado é -210 em vez de -110; próximo, mas não exato

� c.f. 111110112 >>> 2 = 001111102 = +62

Observações Finais (1)

� Aritmética de suporte dos ISAs

� Inteiros com sinal e sem sinal

� Aproximação de ponto flutuante para números reais

� Intervalo e precisão limitada

� Operações podem causar estouro positivo e negativo

� ISA do MIPS

� Instruções do núcleo: 54 mais frequentemente usadas (próximo slide)

� 100% do SPECINT, 97% do SPECFP

� Outras instruções: menos frequente

Observações Finais (2)

Exercício 1

� Tente multiplicar os números 0.2510 e 0.12510

em binário usando o algoritmo do multiplicador em ponto flutuante

Exercício 2

� Emule o código assembly da conversão de Farenheit para Celsius usando o emulador Mars

� Dica: converta os números para ponto flutuante, antes de inserir nos registradores $f0, $f1, etc

� Para uma entrada de 40 farenheit, o resultado é 0x408e38e4 ou 4.4444447

� Para checar os resultados, use o conversor disponível no site http://www.h-schmidt.net/FloatConverter/

Exercício 3

� Escreva um programa em assembly do MIPS que capture o valor do raio de uma esfera e exiba o valor do volume e da área da superfície da esfera. Sabe-se que o volume da esfera é dado por (4/3) ×π×r3 e que a área da superfície é dada por 4×π ×r2. Assuma π=3.14

� Dica: transforme o valor de π em uma fração