Tópicos em Arquitetura de Computadores - 4027 João Angelo Martini UniversidadeEstadual de Maringá...

Tópicos em Arquitetura de Tópicos em Arquitetura de Computadores - 4027Computadores - 4027

João Angelo MartiniJoão Angelo Martini

UniversidadeUniversidade Estadual de Estadual de MaringáMaringá

Departamento de InformáticaDepartamento de Informática

Mestrado em Ciência da ComputaçãoMestrado em Ciência da Computação

2

Aula de Aula de HojeHoje

Aritmética ComputacionalAritmética Computacional

3

Aritmética Aritmética ComputacionalComputacional

Aritmética ComputacionalAritmética ComputacionalCircuitos Aritméticos: circuitos utilizados para construir a ULA (Unidade Lógica e Aritmética)

Adição

Exemplo de adição em decimal (dígitos de 0 a 9):

Cada posição só pode representar um dígito, por isso, gera um carry (vai um)

3 7 6

4 6 1+

3 7 6

4 6 1

7

+

13 7 6

4 6 1

3 7

+

3 7 6

4 6 1

8 3 7

1

+

4

Aritmética Aritmética ComputacionalComputacional

Aritmética ComputacionalAritmética ComputacionalAdição em Binário :

ExemploCada posição só pode representar um dígito, por isso, gera um carry

a) 0

0

0

+

b) 0

1

1

+

c) 1

0

1

+

d) 1

1

10

+

1 0 1 0 1

0 0 1 1 1+

1 0 1 0 1

0 0 1 1 1

0

+

1 0 1 0 1

0 0 1 1 1

0 0

+

1 0 1 0 1

0 0 1 1 1

1 0 0

+

1 0 1 0 1

0 0 1 1 1

1 1 0 0

+

1 0 1 0 1

0 0 1 1 1

1 1 1 0 0

+

1 1 1 11 10 0

cin

cout Soma

5

Aritmética Aritmética ComputacionalComputacional

A B Cin S Cout

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

Entradas Saídas

A

+B

S

Cin

Cout

Cin

6

Aritmética Aritmética ComputacionalComputacional

A B Cin S Cout

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

Entradas Saídas

A B Cin

A B Cin

A B Cin

A B Cin

S = A B Cin + A B Cin + A B Cin + A B Cin

7

Aritmética Aritmética ComputacionalComputacional

A B Cin S Cout

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

Entradas Saídas

Cout = A B Cin + A B Cin + A B Cin + A B Cin

A B Cin

A B Cin

A B Cin

A B Cin

8

Aritmética Aritmética ComputacionalComputacional

S = A B Cin + A B Cin + A B Cin + A B Cin

Simplificando as expressõesSimplificando as expressões

S = A (B Cin + B Cin)+ A (B Cin + B Cin)

Fazendo X = B + Cin e X = B Cin

Como B + Cin = B Cin + B Cin e B Cin = B Cin + B Cin

S = A + X

S = A X+ A X

S = A + B + Cin

A e A em evidência

S = A (B + Cin)+ A (B Cin)

9

Aritmética Aritmética ComputacionalComputacional

Cout = A B Cin + A B Cin + A B Cin + A B Cin

Simplificando as expressõesSimplificando as expressões

0 0 1 0

0 1 1 1

B

A

A

B

CinCin Cin

P2=BCin

P3=ACin

P1=AB Cout = AB+BCin+ACin

10

Aritmética Aritmética ComputacionalComputacionalCircuito SomadorCircuito Somador

Cout = AB+BCin+ACin

S = A + B + Cin

A

B

Cin

S

Cout

B + Cin

A + B + Cin

AB

BCin

ACin

AB+BCin+AC

in

11

Somador de 4 Somador de 4 bitsbits

Somador Somador Somador Somador

S0S1S2S3 C1C2C3C4

C0A0B0A1B1A2B2A3B3

12

Somador Bit Somador Bit SliceSlice

Somador

S3 C3C4

A3B3

A

B

Cin

S

Cout

Atraso de 1 porta lógica

Atraso de 1 porta lógica

Para gerar o carry seguinte há 2 estágios de portas lógicas

13

Somador de 4 Somador de 4 bitsbits

Somador Somador Somador Somador

S0S1S2S3 C1C2C3C4

C0A0B0A1B1A2B2A3B3

Somador Ripple-CarrySomador Ripple-Carry

• Ripple-Carry: Ondulação ou Propagação do Carry. Carry-Out de um estágio se transforma no Carry-In do estágio seguinte.

• Ai e Bi “alimentam” os somadores em paralelo, mas o circuito deve esperar a propagação dos Carries para concluir a operação.

14

Aritmética Aritmética ComputacionalComputacional

Aritmética ComputacionalAritmética ComputacionalSubtração

Exemplo de subtração em decimal (dígitos de 0 a 9):

Empresta 1 da coluna da esquerda para formar a dezena

7 6

5 8-

7 6

5 8

-

16

8

7 6

5 8

8

-

6

1

15

Aritmética Aritmética ComputacionalComputacional

Aritmética ComputacionalAritmética ComputacionalSubtração em Binário

Exemplo

a) 0

0

0

-

b) 0

1

1

-

c) 1

0

1

-

d) 1

1

0

-

Gera um “empresta-1” (carry out) da coluna seguinte: a 1a coluna passa a valer 210=102

O carry out será subtraído da coluna seguinte na continuação da operação

1

16

Aritmética Aritmética ComputacionalComputacional

Aritmética ComputacionalAritmética ComputacionalSubtração em Binário :

Exemplo Gera um “empresta-1” (carry out) da coluna seguinte: a 1a coluna passa a valer 102=210

1 0 1 0

0 0 1 1-

1 0 1 0

0 0 1 1

-

1 0 1 0

0 0 1 1

-

1

1

1

cin

Subtração

1

1

1

0

1 0 1 0

0 0 1 1

-1

1

1

011

1

1 0 1 0

0 0 1 1

-1

1

1

011

1

0

1 0 1 0

0 0 1 1

-1

1

1

011

1

011

1

1 0 1 0

0 0 1 1

-1

1

1

011

1

011

10

17

ExercíciExercíciosos

1. Obter a Tabela Verdade para o circuito subtrator de 1 bit (considere como entradas: A, B e Cin; e como saídas: S e Cout).

2. Obtenha as expressões para a subtração S e para o Cout a partir da Tabela Verdade.

3. Desenhe o diagrama de portas lógicas do circuito subtrator.

18

SoluçõSoluçõeses

A B Cin S Cout

0 0 0 0 0

0 0 1 1 1

0 1 0 1 1

0 1 1 0 1

1 0 0 1 0

1 0 1 0 0

1 1 0 0 0

1 1 1 1 1

Entradas Saídas Tabela Verdade para o Subtrator1)

19

SoluçõSoluçõeses

A B Cin S Cout

0 0 0 0 0

0 0 1 1 1

0 1 0 1 1

0 1 1 0 1

1 0 0 1 0

1 0 1 0 0

1 1 0 0 0

1 1 1 1 1

Entradas Saídas

S = A B Cin + A B Cin + A B Cin + A B Cin

2)

20

SoluçõSoluçõeses

A B Cin S Cout

0 0 0 0 0

0 0 1 1 1

0 1 0 1 1

0 1 1 0 1

1 0 0 1 0

1 0 1 0 0

1 1 0 0 0

1 1 1 1 1

Entradas Saídas

S = A B Cin + A B Cin + A B Cin + A B Cin

Cout = A B Cin + A B Cin + A B Cin + A B Cin

2)

21

SoluçõSoluçõeses

S = A B Cin + A B Cin + A B Cin + A B Cin

Simplificando as expressõesSimplificando as expressões

S = A (B Cin + B Cin)+ A (B Cin + B Cin)

Fazendo X = B + Cin e X = B Cin

Como B + Cin = B Cin + B Cin e B Cin = B Cin + B Cin

S = A + X

S = A X+ A X

S = A + B + Cin

A e A em evidência

S = A (B + Cin)+ A (B Cin)

2)

22

SoluçõSoluçõeses

Cout = A B Cin + A B Cin + A B Cin + A B Cin

Simplificando as expressõesSimplificando as expressões

0 1 1 1

0 0 1 0

B

A

A

B

CinCin Cin

P2=BCin

P3=ACin

P1=AB

2)

Cout = AB+BCin+ACin

23

SoluçõSoluçõesesCircuito SubtratorCircuito Subtrator

S = A + B + Cin

A

B

Cin

S

Cout

3)

Cout = AB+BCin+ACin

24

ULA: Somador e ULA: Somador e SubtratorSubtrator

RIRI

UCUC

SomadorSomador

SubtratorSubtrator

ULA

CPU

ULA com 2 circuitos para efetuar a adição e a subtração

25

Exemplo: ULA Exemplo: ULA SimplificadaSimplificada

A

B

26

Adição e Subtração Adição e Subtração em em

Complemento de 2Complemento de 2Exemplos de Adição:

a) 7

(+5)

2

710=01112 1000

+ 1

1001

Complemento de 2 do valor -710

1001

0101

1110 =-210

1

510=01012

+

Cout=0

Cin=0

Cin=0

Cout=0Overflow=0

em Complemento de 2

0001

+ 1

0010

Complemento de 2 de -210

-

-

0

0

+

27

Adição e Subtração Adição e Subtração em em

Complemento de 2Complemento de 2Exemplos de Adição:

b) 4

(+4)

0

410=01002 1011

+ 1

1100

Complemento de 2 do valor -410

1100

0100

0000 =010

1

+

Cout=1

Cin=1

Cin=1

Cout=1Overflow=0

em Complemento de 2

1111

+ 1

0000

Complemento de 2 de 010

-

1

Despreza o carry

+

28

Adição e Subtração Adição e Subtração em em

Complemento de 2Complemento de 2Exemplos de Adição:

c) +3

(+4)

7

310=00112

0011

0100

0111 =710

0

+

Cout=0

Cin=0

Cin=0

Cout=0Overflow=0

em Complemento de 2

+

410=01002

0

+

29

Adição e Subtração Adição e Subtração em em

Complemento de 2Complemento de 2Exemplos de Adição:

d) 4

(-1)

5

410=010021011

+ 1

1100

Complemento de 2 do valor -410

1100

1111

1011 =-510

1

+

Cout=1

Cin=1

Cin=1

Cout=1Overflow=0

em Complemento de 20100

+ 1

0101

Complemento de 2 de -510

-

1

Despreza o carry

-

110=00012

1110

+ 1

1111

Complemento de 2 do valor -110

+

30

Adição e Subtração Adição e Subtração em em

Complemento de 2Complemento de 2Exemplos de Adição:

e) +5

(+4)

9

510=01012

0101

0100

1001 =910

1

+

Cout=0

Cin=1

Cin=1

Cout=0Overflow=1

em Complemento de 2

+

+

410=01002

0 Erro de OverflowErro de Overflow

10012=910

Não dá para representar 9 com Não dá para representar 9 com registrador de 4 bits, com 1 bit de registrador de 4 bits, com 1 bit de sinalsinal

2 números 2 números positivos positivos

somados não somados não podem resultar podem resultar

num número num número negativonegativo

31

Adição e Subtração Adição e Subtração em em

Complemento de 2Complemento de 2Exemplos de Adição:

f) 7

(-6)

13

710=011121000

+ 1

1001

Complemento de 2 do valor -710

1001

1010

0011 =310

0

+

Cout=1

Cin=0

Cin=0

Cout=1Overflow=1

em Complemento de 2

-

1

Despreza o carry

-

610=01102

1001

+ 1

1010

Complemento de 2 do valor -610

2 números negativos somados 2 números negativos somados não podem resultar num número não podem resultar num número positivopositivo

+

32

Adição e Subtração Adição e Subtração em em

Complemento de 2Complemento de 2Subtração

A Subtração pode ser efetuada usando um circuito Somador

Minuendo

- Subtraendo

Subtração

Usa o Complemento de 2 do Usa o Complemento de 2 do Subtraendo e soma-o ao MinuendoSubtraendo e soma-o ao Minuendo

33

210=00102

Adição e Subtração Adição e Subtração em em

Complemento de 2Complemento de 2Exemplos de Subtração:

a) 2

(+7)

5710=01112

1000

+ 1

1001

Complemento de 2 do valor 710

0010

1001

1011 =-510

+

Cout=0

Cin=0

Cin=0

Cout=0Overflow=0

em Complemento de 2

0100

+ 1

0101

Complemento de 2 de -510

-

0

0

-

34

Adição e Subtração Adição e Subtração em em

Complemento de 2Complemento de 2Exemplos de Subtração:

b) 5

(+2)

3

510=01012 1101

+ 1

1110

Complemento de 2 do valor 210

0101

1110

0011 =310

210=00102

+

Cout=1

Cin=1

Cin=1

Cout=1Overflow=0

em Complemento de 2

1

1

-

Despreza o carry

35

1101

+ 1

1110

Complemento de 2 do valor 210

Adição e Subtração Adição e Subtração em em

Complemento de 2Complemento de 2Exemplos de Subtração:

c) 5

(+2)

7

510=01012 1010

+ 1

1011

Complemento de 2 do valor -510

1011

1110

1001 =-710

210=00102

+

Cout=1

Cin=1

Cin=1

Cout=1Overflow=0

em Complemento de 2

1

1

-

Despreza o carry

-

-

1

0110

+ 1

0111

Complemento de 2 de -710

36

Adição e Subtração Adição e Subtração em em

Complemento de 2Complemento de 2Exemplos de Subtração:

d) 5

(-2)

7

510=01012 1101

+ 1

1110

Complemento de 2 do valor 210

0101

0010

0111 =710

210=00102

+

Cout=0

Cin=0

Cin=0

Cout=0Overflow=0

em Complemento de 2

0

0

-

0001

+ 1

0010

Complemento de 2 do valor -210

Complemento de 2 de -2=2

37

Adição e Subtração Adição e Subtração em em

Complemento de 2Complemento de 2Exemplos de Subtração:

e) 7

(-7)

14

710=01112 1000

+ 1

1001

Complemento de 2 do valor 710

0111

0111

1110 =-210

+

Cout=0

Cin=0

Cin=1

Cout=0Overflow=1

em Complemento de 2

0

1

-

0110

+ 1

0111

Complemento de 2 do valor -710

Complemento de 2 de -7=71 1

Erro de OverflowErro de Overflow

011102=1410

Não dá para representar 14 com Não dá para representar 14 com registrador de 4 bits, com 1 bit de registrador de 4 bits, com 1 bit de sinalsinal

38

Adição e Subtração Adição e Subtração em em

Complemento de 2Complemento de 2Exemplos de Subtração:

f) (-6)

(+4)

10

610=01102 1001

+ 1

1010

Complemento de 2 do valor 610

1010

1100

0110 =610

+

Cout=0

Cin=0

Cin=0

Cout=1Overflow=1

em Complemento de 2

1

0

-

1011

+ 1

1100

Complemento de 2 do valor 410

Erro de OverflowErro de Overflow

-

410=01002

2 números negativos somados 2 números negativos somados não podem resultar num número não podem resultar num número positivopositivo

39

Circuito Circuito Somador/Subtrator em Somador/Subtrator em

Complemento de 2Complemento de 2

A B S

0 0 0

0 1 1

1 0 1

1 1 0

Entradas Saída Símbolo da Porta XORSímbolo da Porta XORTV da Porta XORTV da Porta XOR

A

BS

Obs: Para obter o circuito Obs: Para obter o circuito somador/subtrator em complemento de 2 somador/subtrator em complemento de 2 vamos usar a porta XORvamos usar a porta XOR

40

Circuito Circuito Somador/Subtrator em Somador/Subtrator em

Complemento de 2Complemento de 2

A B S

0 0 0

0 1 1

1 0 1

1 1 0

Entradas Saída

TV da Porta XORTV da Porta XOR

X

0S

Se fixar uma entrada Se fixar uma entrada em 0em 0

X=0

0 S=0

X=1

0 S=1

Deixando uma entrada Deixando uma entrada de controle em 0, o de controle em 0, o dado “X” é copiado dado “X” é copiado para a saídapara a saída

41

Circuito Circuito Somador/Subtrator em Somador/Subtrator em

Complemento de 2Complemento de 2

A B S

0 0 0

0 1 1

1 0 1

1 1 0

Entradas Saída

TV da Porta XORTV da Porta XOR

X

1S

Se fixar uma entrada Se fixar uma entrada em 1em 1

X=0

1 S=1

X=1

1 S=0

Deixando uma Deixando uma entrada de controle entrada de controle em 1, o dado “X” é em 1, o dado “X” é complementado na complementado na saída: S=Xsaída: S=X

Para obter o complemento de 2 Para obter o complemento de 2 precisa somar 1 ao bit menos precisa somar 1 ao bit menos significativo do dadosignificativo do dado

42

Circuito Circuito Somador/Subtrator em Somador/Subtrator em

Complemento de 2Complemento de 2C=C=Controle da Controle da Operação C=0 Operação C=0 A Aii+B+Bii

C=1 C=1 A Aii-B-Bii

Cin

A B

S

CinCout

A B

S

CinCoutS0S1

A1 A0

C0

B1 B0

B_SEL0B_SEL1

A B

S

CinCoutS2S3

A3 A2

S2S3

Cout

B3 B2

B_SEL2B_SEL3

A B

S

Cout

S1 S0 A0

B0

+0

C=0

A0

B0

+1

C=1

Com

ple

men

to d

e 2

de

B

43

ExercíciExercíciosos1. Projete um circuito somador/subtrator em complemento de 2

usando um MUX para fazer o controle da geração do complemento de 2 do dado (subtraendo).

2. O custo do “novo” circuito somador/subtrator é maior ou menor que o do circuito anterior?

44

SoluçõSoluçõeses1. Projete um circuito somador/subtrator em complemento de 2

usando um MUX para fazer o controle da geração do complemento de 2 do dado (subtraendo).

Cin

A B

S

CinCout

A B

S

CinCoutS0S1

A1 A0

C0

B1 B0

B_SEL0B_SEL1

A B

S

CinCoutS2S3

A3 A2

S2S3

Cout

B3 B2

B_SEL2B_SEL3

A B

S

Cout

S1 S0

MUX MUX MUX MUX

45

SoluçõSoluçõeses2. O custo do “novo” circuito somador/subtrator é maior ou

menor que o do circuito anterior?

C

S

B i

B i

C

Para circuitos de 4 bits:

Circuito 1: 4 Portas XOR

Circuito 2: 4x5=20 Portas

Decisão de Projeto:

-Arquitetura: decide se vai oferecer adição em Complemento de 2

-Organização: decide como implementar (escolhe entre o circuito 1 e o circuito 2)MUX

46

Somador de Alto Somador de Alto DesempenhoDesempenho

Somador Somador Somador Somador

S0S1S2S3 C1C2C3C4

C0A0B0A1B1A2B2A3B3

Somador Ripple-CarrySomador Ripple-Carry

Somador Convencional: Atrasos para propagar o carry

Somador ConvencionalSomador Convencional

47

Somador de Alto Somador de Alto DesempenhoDesempenho

Somador Somador Somador Somador

S0S1S2S3 C1C2C3C4

C0A0B0A1B1A2B2A3B3

CL: Lógica para antecipar o carry sem passar pelo somador

Somador Carry LookaheadSomador Carry Lookahead

CL CL CL

48

Somador de Alto Somador de Alto DesempenhoDesempenho

Ci+1 = AiBi + AiCi +BiCi

Expressão do Carry do Somador

Ci+1 = AiBi + Ci (Ai+Bi)

1. Fatorando a expressão

2. Chamando AiBi de Gi e Ai+Bi de Pi

Ci+1 = Gi + PiCi

3. Substituindo os índices para obter os carries para um somador de 4 bits

C1 = G0 + P0C0

C1 = G0

4. Para simplificar a análise, vamos considerar C0=0 para soma

A B C-out0 0 0 “nada”0 1 C-in “propaga”1 0 C-in “propaga”1 1 1 “gera”

49

Somador de Alto Somador de Alto DesempenhoDesempenho

C2 = G1 + P1C1

Expressão do Carry do Somador

C2 = G1 + P1G0

5. Substituindo C1=G0

6. Obtendo C3

C3 = G2 + P2C2

7. Substituindo C2 = G1 + P1G0

C3 = G2 + P2(G1 + P1G0)

C4 = G3 + P3C3

8. Obtendo C4

C3 = G2 + P2G1 + P2P1G0

C4 = G3 + P3(G2 + P2G1 + P2P1G0)

C4 = G3 + P3G2 + P3P2G1 + P3P2P1G0

50

ExercícExercícioio1. Faça o diagrama de blocos do circuito somador de 4

bits com a Lógica Carry Lookahead.

2. Calcule o atraso para gerar os carries.

51

SoluçõSoluçõeses1. Faça o diagrama de blocos do circuito somador de 4

bits com a Lógica Carry Lookahead.

52

SoluçõSoluçõeses2. Calcule o atraso para gerar os carries.

Atraso de 3 Atraso de 3 Portas para gerar Portas para gerar o carryo carry

1 Porta

2 Portas

2 Portas

O somador introduz mais um O somador introduz mais um atraso de 2 Portas para gerar atraso de 2 Portas para gerar a Somaa Soma