1
Aritmética
Representação de números
2
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
3
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...
4
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...
5
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
6
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
7
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) …
8
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
Expoente MantissaBit desinal
1 8 bits 23 bits
32 bits
Valor do número: (-1)sinal 1.mantissa 2expoente
9
Representação de números reais
Exemplo:
Qual será o valor do número real C160 0000(hex)?
00011 100 0110 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
10
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
11
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
12
Aritmética
Multiplicação binária
13
Multiplicação binária
Multiplicação (sem sinal)
1101 multiplicando (A)
× 1010 multiplicador (B)
0000
1101
0000
1101
10000010 produto (P)
1101 (13) × 1010 (10) = 10000010 (130)
Quando se multiplicam dois números de n bits (sem sinal), o resultado terá, no máximo, 2n bits.
14
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
P7 P6 P5 P4 P3 P2 P1 P0
ANDs entre os bits de A e os bits de B
15
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 P2 P1 P0
Somadores
16
Multiplicação binária
B3
A3 A2 A1 A0
B2
A3 A2 A1 A0
B1
A3 A2 A1 A0
B0
A3 A2 A1 A0
0
P7 P6 P5 P4 P3 P2 P1 P0
Cout
Cout
Cout
X Y
S
ADD
X Y
S
ADD
X Y
S
ADD
Pode-se seguir esta estrutura
17
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
18
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
19
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
20
Multiplicação binária
Hardware para o algoritmo básico
RAShift left
RPLoad
ADD
A
RBShift right
B
RB0
21
Multiplicação binária
Exemplo – multiplicar 1010 por 1001 (i.e. 109)
Inicialização:RP: 0000 0000RA: 0000 1010RB: 1001
Ciclo 1 (RB0 = 1)RP: 0000 1010RA: 0001 0100RB: 0100
Ciclo 2 (RB0 = 0)RP: 0000 1010RA: 0010 1000RB: 0010
Ciclo 3 (RB0 = 0)RP: 0000 1010RA: 0101 0000RB: 0001
Ciclo 4 (RB0 = 1)RP: 0101 1010RA: 1010 0000RB: 0000
O resultado será então:
RP: 01011010 = 21+23+24+26 = 2+8+16+64 = 90
22
Aritmética
Aceleração da adição
23
Adição básica (Ripple-carry)
Um circuito full adder (dado em AC1)
AB
Cin
Cout
S
Soma os bits A e B com o transporte anterior (Cin), dando o resultado da soma (S) e o transporte que sai (Cout)
24
Adição básica (Ripple-carry)
Adicionador Ripple-carry de n bits
FA
A0 B0
S0
FA
A1 B1
FA
A2 B2
FA
A3 B3
C1 C2C0
C3
S1 S2 S3
C4
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
25
Adição básica (Ripple-carry)
Outra maneira de ver
AB
Cin
Cout
S
PFA
PFA – Partial Full Adder
26
Adição básica (Ripple-carry)
Outra maneira de ver
ABG
BAP
Em que:
Propagação de carry
Geração de carry
PFA
A B
S
P G Cout
Cin
27
Adição básica (Ripple-carry)
Para um ripple adder de 4 bits
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
PFA
A0 B0
S0
P0 G0
PFA
A1 B1
S1PFA
A2 B2
S2PFA
A3 B3
S3
P1 G1C1 C2
C0
P2 G2 P3 G3
C4C3
28
Adição básica (Ripple-carry)
Para um ripple adder de 4 bits
PFA
A0 B0
S0
P0 G0
PFA
A1 B1
S1PFA
A2 B2
S2PFA
A3 B3
S3
P1 G1C1 C2
C0
P2 G2 P3 G3
C4C3
Caminho crítico – corresponde ao pior caso na propagação dos sinais
Tipicamente é o que atravessa mais portas lógicas
29
Acelerar a adição
Genericamente tem-se:
0012012122
0001122
11122
2223
CPPPGPPGPG
CPGPGPG
CPGPG
CPGC
001011
00011
1112
CPPGPG
CPGPG
CPGC
0001 CPGC
iii
iii
iiii
BAP
BAG
CPGC
1
...C 4
30
Acelerar a adição
Com base nessas equações obtém-se:
PFA
A0 B0
S0
P0 G0
PFA
A1 B1
S1PFA
A2 B2
S2PFA
A3 B3
S3
P1 G1C1
C2
C0
P2 G2 P3 G3
C4
C3
31
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
32
Adicionador Carry Lookahead
PFA
A0 B0
PFA
A1 B1
PFA
A2 B2
PFA
A3 B3
S0 S1 S2 S3
G01P01
G03P03
G23P23
P0 G0 P1 G1 P2 G2 P3 G3
C0
C1
C2
C3
C4
33
Adicionador Carry Lookahead
PFA
A0 B0
PFA
A1 B1
PFA
A2 B2
PFA
A3 B3
S0 S1 S2 S3
G01P01
G03P03
G23P23
P0 G0 P1 G1 P2 G2 P3 G3
C0
C1
C2
C3
C4
O caminho crítico está representado a vermelho
34
Adicionador Carry Lookahead
PFA
A0 B0
PFA
A1 B1
PFA
A2 B2
PFA
A3 B3
S0 S1 S2 S3 PFA
A4 B4
PFA
A5 B5
PFA
A6 B6
PFA
A7 B7
S4 S5 S6 S7C0
C8
35
Adicionador Carry Lookahead
Comparação entre os adicionadores:(supondo que apenas são utilizadas portas lógicas com 2 entradas)
Nº de bitsRipple-carry CLA
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
36
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
37
Outros adicionadores
Carry select adder (8 bits)
4-bitadder
S0...S3 S4...S7
Sel.
A0...A3
0 14-bit
adder
Mux
4-bitadder
A4...A7B0...B3 B4...B7
Sel
Cout Cin Cin
0 1
Cin0
38
Outros adicionadores
Carry skip adder (16 bits)
C16C0
4-bitadder
S0..S3
A0..A3 B0..B3
Ci Co
4-bitadder
S4..S7
A4..A7 B4..B7
Ci Co
4-bitadder
S8..S11
A8..A11 B8..B11
Ci Co
4-bitadder
S12..S15
A12..A15 B12..B15
Ci Co
P4,7 P8,11
39
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”
40
Síntese
Adicionadores (tempos)
0
50
100
150
200
250
300
0 32 64 96 128
Número de bits
Tem
po (
x t P
D)
Ripple
CLA
Select
Skip
41
Adicionadores (número de portas)
0
500
1000
1500
2000
0 32 64 96 128
Número de bits
Núm
ero
de p
orta
s ló
gica
s
Ripple
CLA
Select
Skip
Síntese