Aritmética Representação de números 1 Representação de inteiros Números inteiros com sinal A representação mais comum é a representação em complemento para 2 Boas propriedades para adição e subtracção Como já viram em AC I... No entanto existem outras formas de representar: Magnitude Complemento para 1 Excesso m 2 Representação de inteiros Magnitude 1 bit de sinal seguido do valor absoluto do número Exemplos (em 8 bits) 0 0000 0000 -0 1000 0000 1 0000 0001 -1 1000 0001 41 0010 1001 -41 1010 1001 78 0100 1110 -78 1100 1110 OBS: A notação não tem boas propriedades para a adição: se fizer N + (-N) o resultado não dá 0... O ‘0’ pode ter duas representações diferentes... 3 Representação de inteiros Complemento para 1 O simétrico é a negação bit a bit Exemplos (em 8 bits) 0 0000 0000 -0 1111 1111 1 0000 0001 -1 1111 1110 41 0010 1001 -41 1101 0110 78 0100 1110 -78 1011 0001 OBS: Boas propriedades para adição, mas o ‘0’ pode ter duas representações diferentes... 4 Representação de inteiros Excesso m Representa-se o valor do número acrescido de m O menor número vale –m e é representado por 0’s Exemplo: excesso 128 (8 bits) 0 1000 0000 -0 1000 0000 1 1000 0001 -1 0111 1111 41 1010 1001 -41 0101 0111 78 1100 1110 -78 0011 0010 OBS: Quando m=2n-1 fica semelhante ao complemento para 2, mas com o bit de sinal trocado 5 Representação de inteiros Apesar de muito utilizada, a notação em complemento para 2 também tem um defeito: Existe mais um número negativo do que o número de positivos No caso da notação excesso-m, esse desequilíbrio pode ainda ser maior No entanto, não existe nenhuma notação “ideal”: o zero ter um única representação existirem tantos números negativos como positivos ter boas propriedades para adição/subtracção 6 Representação de números reais Norma IEEE 754 (versão mais recente: Ago/2008) Até meados dos anos 80, a representação de números reais não estava normalizada... Cada fabricante usava a sua representação Para ultrapassar problemas de compatibilidade, surgiu em 1985 a primeira versão da norma IEEE 754 A norma define: Os formatos de representação dos números reais Como devem ser feitos os arredondamentos Como devem ser feitas as operações Tratamento de excepções (ex: divisão por zero, underflow, overflow) … 7 Representação de números reais Formato de um número real (virgula flutuante) Precisão simples – 32 bits – float 1 bit que define o sinal (0 – positivo; 1 – negativo) 8 bits para o expoente (representado em excesso 127) 23 bits para a mantissa, representada em magnitude 1 Bit de sinal 8 bits 23 bits Expoente Mantissa 32 bits Valor do número: (-1)sinal 1.mantissa 2expoente 8 Representação de números reais Exemplo: Qual será o valor do número real C160 0000(hex)? 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 expoente mantissa sinal Sinal = 1 número negativo Expoente = 1000 0010 = 130 o expoente vale 3 (não esquecer que está em excesso 127) Mantissa = 0.1100 0000 … = 2-1 + 2-2 = 0.5 + 0.25 = 0.75 O valor do número será então: –1.75 23 = –14.0 9 Representação de números reais Significados especiais Expoente Mantissa Valor Obs. –127 == 0 0 128 == 0 infinito Depende do sinal 128 != 0 NaN (not a number) Valores não reais –127 != 0 0.mantissa 2-126 Forma desnormalizada Exemplos: 0000 0000(hex) = 0.0 7F80 0000(hex) = + FFFF FFFF(hex) = NaN 0040 0000(hex) = 0.5 * 2-126 10 Representação de números reais Precisão dupla – double Obtêm-se os valores de forma idêntica, mas os números são representados em 64 bits com 11 bits para o expoente (em excesso 1023) e 52 bits para a mantissa Gamas de representação (na forma normal) Precisão simples 1.2 10-38 a 3.4 1038 Precisão dupla 2.2 10-308 a 1.8 10308 11 Aritmética Multiplicação binária 12 Multiplicação binária Multiplicação (sem sinal) 1101 multiplicando (A) × 1010 multiplicador (B) 0000 1101 0000 1101 10000010 produto (P) Quando se multiplicam dois números de n bits (sem sinal), o resultado terá, no máximo, 2n bits. 1101 (13) × 1010 (10) = 10000010 (130) 13 Multiplicação binária Multiplicação (sem sinal) A3 A2 A1 A0 B3 B2 B1 B0 B0A3 B0A2 B0A1 B0A0 B1A3 B1A2 B1A1 B1A0 B2A3 B2A2 B2A1 B2A0 B3A3 B3A2 B3A1 B3A0 P6 P5 P4 P3 × P7 P2 ANDs entre os bits de A e os bits de B P1 P0 14 Multiplicação binária Utilizando vários adicionadores... A3 A2 A1 A0 × B3 B2 B1 B0 0 B0A3 B0A2 B0A1 B0A0 + B1A3 B1A2 B1A1 B1A0 cout1 S13 S12 S11 S10 + B2A3 B2A2 B2A1 B2A0 cout2 S23 S22 S21 S20 + B3A3 B3A2 B3A1 B3A0 cout3 S33 S32 S31 S30 P7 P6 P5 P4 P3 Somadores P2 P1 P0 15 Multiplicação binária A3 A2 A1 A0 B0 Pode-se seguir esta estrutura A3 A2 A1 A0 B1 X A3 A2 A1 A0 Cout B2 Cout B3 ADD Y S X A3 A2 A1 A0 0 ADD Y S X Cout ADD Y S P7 P6 P5 P4 P3 P2 P1 P0 16 Multiplicação binária Utilização de vários adicionadores Se os números a multiplicar são compostos por n bits então são necessários n – 1 adicionadores de n bits cada um Eventuais problemas: Excesso de material por exemplo, para multiplicar dois números de 32 bits seriam necessários 31 somadores de 32 bits Demasiado consumo de tempo durante um ciclo Num processador, ter um multiplicador deste género pode aumentar de forma significativa a duração de cada ciclo, devido aos tempos de propagação dos somadores 17 Multiplicação binária Alternativa: usar um único somador e registos O adicionador efectua todas as adições necessárias em n ciclos É necessário: Um registo para acumular as somas – RP Um registo de deslocamento para a esquerda e outro para a direita – RA e RB RP e RA são registos de 2n bits para RB, um registo de n bits é suficiente 18 Multiplicação binária Algoritmo básico (para inteiros sem sinal) Inicialização: RP ← 0, RA ← A, RB ← B Ciclo (n iterações) se ( RB0 == 1 ) // bit menos significativo em RB RP ← RP + RA RA ← RA << 1, RB ← RB >> 1 No final, o resultado da multiplicação está em RP 19 Multiplicação binária Hardware para o algoritmo básico B A Shift right Shift left RB RA RB0 ADD Load RP 20 Multiplicação binária Exemplo – multiplicar 1010 por 1001 (i.e. 109) Inicialização: RP: 0000 0000 RA: 0000 1010 RB: 1001 Ciclo 3 (RB0 = 0) RP: 0000 1010 RA: 0101 0000 RB: 0001 Ciclo 1 (RB0 = 1) RP: 0000 1010 RA: 0001 0100 RB: 0100 Ciclo 4 (RB0 = 1) RP: 0101 1010 RA: 1010 0000 RB: 0000 Ciclo 2 (RB0 = 0) RP: 0000 1010 RA: 0010 1000 RB: 0010 O resultado será então: RP: 01011010 = 21+23+24+26 = 2+8+16+64 = 90 21 Aritmética Aceleração da adição 22 Adição básica (Ripple-carry) Um circuito full adder (dado em AC1) A B Cin S Cout Soma os bits A e B com o transporte anterior (Cin), dando o resultado da soma (S) e o transporte que sai (Cout) 23 Adição básica (Ripple-carry) Adicionador Ripple-carry de n bits A0 B0 FA C0 S0 A1 C1 B1 FA S1 A2 C2 B2 FA S2 A3 C3 B3 FA C4 S3 Problema: Os transportes (Ci’s) têm que se propagar entre os full adders Admitindo que cada full adder impõe um atraso, o tempo necessário para ser feita a soma será proporcional a n 24 Adição básica (Ripple-carry) Outra maneira de ver PFA A B Cin S Cout PFA – Partial Full Adder 25 Adição básica (Ripple-carry) Outra maneira de ver A B PFA Cin P G S Cout Em que: Propagação de carry Geração de carry P AB G AB 26 Adição básica (Ripple-carry) Para um ripple adder de 4 bits A0 B0 PFA C0 P0 G0 A1 S0 C1 B1 PFA P1 G1 A2 S1 C2 B2 PFA P2 G2 A3 S2 C3 B3 PFA P3 S3 G3 C4 P’s e G’s podem ser calculados em paralelo (ao mesmo tempo) As somas (os S’s) têm que esperar que chegue o Ci respectivo 27 Adição básica (Ripple-carry) Para um ripple adder de 4 bits A0 B0 PFA C0 P0 G0 A1 S0 C1 B1 PFA P1 G1 A2 S1 C2 B2 PFA P2 G2 A3 S2 C3 B3 PFA P3 S3 G3 C4 Caminho crítico – corresponde ao pior caso na propagação dos sinais Tipicamente é o que atravessa mais portas lógicas 28 Acelerar a adição Genericamente tem-se: Ci 1 Gi Pi Ci Gi Ai Bi Pi Ai Bi C1 G0 P0C0 C2 G1 P1C1 G1 P1 G0 P0C0 G1 P1G0 P1P0C0 C3 G2 P2C2 G2 P2 G1 P1C1 G2 P2 G1 P1 G0 P0C0 G2 P2G1 P2P1G0 P2P1P0C0 C4 ... 29 Acelerar a adição Com base nessas equações obtém-se: A0 B0 PFA C0 P0 G0 A1 S0 C1 B1 PFA P1 A2 S1 G1 B2 PFA P2 A3 S2 G2 B3 PFA P3 S3 G3 C2 C3 C4 30 Adicionador Carry Lookahead Este tipo de adicionador designa-se por carry lookahead adder (CLA) Repare no atraso associado à propagação do carry neste caso corresponde ao de 2 portas lógicas E se quisesse construir um CLA de 8 bits ? Problema com o desenho anterior: para calcular carrys de ordem elevada (e.g. C7) precisaria de portas lógicas com muitas entradas... ...difícil de implementar na prática Uma abordagem mais realista seria usar portas com 2 entradas 31 Adicionador Carry Lookahead A0 C0 B0 A1 S0 PFA P0 G0 P01 B1 A2 S1 PFA C1 P1 G1 G01 B2 A3 S2 PFA P2 P23 G2 B3 S3 PFA C3 P3 G3 G23 C2 P03 G03 C4 32 Adicionador Carry Lookahead A0 C0 B0 A1 S0 PFA P0 G0 P01 B1 A2 S1 PFA C1 P1 G1 G01 B2 A3 S2 PFA P2 P23 G2 B3 S3 PFA C3 P3 G3 G23 C2 P03 G03 O caminho crítico está representado a vermelho C4 33 Adicionador Carry Lookahead A0 C0 B0 PFA A1 S0 B1 PFA A2 S1 B2 PFA A3 S2 B3 PFA A4 S3 B4 PFA A5 S4 B5 PFA A6 S5 B6 PFA A7 S6 B7 PFA S7 C8 34 Adicionador Carry Lookahead Comparação entre os adicionadores: (supondo que apenas são utilizadas portas lógicas com 2 entradas) Ripple-carry CLA Nº de bits Tempo Nº de portas Tempo Nº de portas 4 9tPD 20 7tPD 29 8 17tPD 40 11tPD 61 16 33tPD 80 15tPD 125 32 65tPD 160 19tPD 253 64 129tPD 320 23tPD 509 128 257tPD 640 27tPD 1021 35 Outros adicionadores Carry select adder A ideia consiste em preparar somas parciais para ambas as hipóteses de carry in O carry out do bloco anterior irá seleccionar qual dos 2 resultados é válido Carry skip adder Composto por vários blocos onde são calculados os P’s, mas não os G’s Os P’s são utilizados para propagar o carry ao bloco seguinte 36 Outros adicionadores Carry select adder (8 bits) A0...A3 0 Cin B0...B3 4-bit adder Cout A4...A7 0 Cin B4...B7 4-bit adder 1 0 Sel Sel. S0...S3 Cin 4-bit adder 1 Mux S4...S7 37 Outros adicionadores Carry skip adder (16 bits) A0..A3 C0 Ci B0..B3 4-bit adder Co A4..A7 Ci B4..B7 4-bit adder Co P4,7 S0..S3 S4..S7 A8..A11 Ci B8..B11 4-bit adder Co A12..A15 B12..B15 Ci 4-bit adder Co C16 P8,11 S8..S11 S12..S15 38 Síntese Evolução do tempo necessário para fazer uma soma de dois números representados com n bits Adicionador Tempo Ripple O(n) Carry lookahead O(log2 n) Carry skip O(√n) Carry select O(√n) n – número de bits O(x) – significa “evolui proporcionalmente com a grandeza x” 39 Síntese Adicionadores (tempos) 300 Ripple Tempo (x tPD ) 250 CLA 200 Select 150 Skip 100 50 0 0 32 64 96 128 Número de bits 40 Síntese Número de portas lógicas Adicionadores (número de portas) 2000 Ripple CLA 1500 Select 1000 Skip 500 0 0 32 64 96 128 Número de bits 41
Download
