Notas da terceira edição - jeiks.netjeiks.net/wp-content/uploads/2012/06/slides_AC.pdf · Notas da terceira edição ... já aprendeu sobre desenvolvimento com lógica e ... –

Notas da terceira edição

Nota: essas notas normalmente são complementadas poroutros materiais, como problemas do texto que podemser trabalhados em sala de aula. É provável que vocêqueira personalizar esse material para que se ajuste àsnecessidades dos seus alunos. Essas notas foramprepararadas com base em uma turma de alunos quejá aprendeu sobre desenvolvimento com lógica efreqüentou um laboratório prático de programação delinguagem assembly que não segue um formato deaula comum.

1

Capítulo 1

2

Introdução

• O objetivo deste curso é mostrar como os computadores funcionam

• Mas o que queremos dizer com a palavra “computador”?

• Diferentes tipos: desktop, servidores, dispositivos embutidos

– Diferentes usos: automóveis, design gráfico, finanças, genética...

– Diferentes fabricantes: Intel, Apple, IBM, Microsoft, Sun...

– Diferentes tecnologias subjacentes e diferentes custos!

• Analogia: Pense em um curso sobre “veículos automotivos”

– Muitas semelhanças de um veículo para outro (por exemplo, volantes)

– Grandes diferenças de um veículo para outro (por exemplo, gasolina, álcool)

• Melhor maneira de aprender:

– Concentrar em um exemplo específico e aprender como ele funciona

– Abordar princípios gerais e perspectivas históricas

3

Por que aprender esse assunto?

• Você deseja se tornar um “cientista da computação”

• Você deseja desenvolver softwares utilizáveis (precisam de desempenho)

• Você precisa tomar uma decisão em relação a uma compra ou oferecer conselhosde “especialista”

• Tanto o hardware quanto o software afetam o desempenho:

– O algoritmo determina o número de instruções na origem

– Linguagem/compilador/arquitetura determinam as instruções da máquina(Capítulos 2 e 3)

– Processador/memória determinam a velocidade com que as instruções sãoexecutadas (Capítulos 5, 6 e 7)

• Avaliando e entendendo o desempenho no Capítulo 4

4

O que é um computador?

• Componentes:

– entrada (mouse, teclado)

– saída (monitor, impressora)

– memória (unidades de disco, DRAM, SRAM, CD)

– rede

• Nosso foco principal: o processador (caminho de dados e controle)

– Implementado usando milhões de transistores

– Impossível de entender olhando para os transistores

– Precisamos...

5

Abstração

• Uma boa dica para obter mais informaçõesé aprofundar-se nos componentes

• Uma abstração omite detalhes desnecessáriose ajuda a entender a complexidade

Quais são alguns dos detalhes que aparecemnestas abstrações familiares?

6

Programaem linguagemde alto nível(em C)

Programa emlinguagem demáquina binária(para MIPS)

Compilador

Programaem linguagemassembly(para MIPS)

Assembler

swap (int v[], int k){int temp;

temp = v[k];v[k] = v[k+1];v[k+1] = temp;

}

swap:muliaddlwlwswswjr

$2,$2,$15,$16,$16,$15$31

$5, 4$4, $20($2)4($2)0($2)4($2)

000000001010000100000000000000011000000000000001100110000001100000100001100011000110001000000000000000000000100011001111001000000000000000000100101011001111001000000000000000000000101011000110001000000000000000000100000000111110000000000000000000000100

Como os computadores funcionam?

• É preciso entender abstrações como:

– Software de aplicações

– Software de sistemas

– Linguagem assembly

– Linguagem de máquina

– Aspectos de arquitetura, como caches, memória virtual, canalização

– Lógica seqüencial, máquinas de estado finito

– Lógica combinatória, circuitos aritméticos

– Lógica booleana, 1s e 0s

– Transistores usados para construir portões lógicos (CMOS)

– Semicondutores/silício usados para construir transistores

– Propriedades dos átomos, elétrons e dinâmica quantitativa

• Muito o que aprender!

7

Arquitetura do conjunto de instruções

• Uma abstração muito importante

– interface entre o hardware e o software de baixo nível

– padroniza instruções, padrões de bits de linguagem de máquina etc.

– vantagem: diferentes implementações da mesma arquitetura

– desvantagem: algumas vezes impede o uso de inovações

Verdadeiro ou falso: A compatibilidade binária é extremamente importante?

• Arquiteturas de conjunto de instruções modernas:

– IA-32, PowerPC, MIPS, SPARC, ARM e outras

8

Perspectiva histórica

• O ENIAC, construído na Segunda Guerra Mundial, foi o primeiro computador definalidade geral– Usado para calcular tabelas de disparo de artilharia– 24 metros de comprimento por 2,5 metros de altura e dezenas de centímetros de

profundidade– Cada um dos 20 registradores de 10 dígitos tinha 60 centímetros de comprimento– Usava 18.000 válvulas– Efetuava 1.900 adições por segundo

– Desde então:

Lei de Moore:

A capacidade dos transistoresdobra a cada 18 a 24 meses

9

Capítulo 2

10

Instruções

• Linguagem da máquina

• Vamos trabalhar com a arquitetura do conjunto de instruções MIPS– Semelhante a outras arquiteturas desenvolvidas desde a década de 1980– Quase 100 milhões de processadores MIPS fabricados em 2002– Usada pela NEC, Nintendo, Cisco, Silicon Graphics, Sony...

11

1400

1300

1200

1100

1000

900

800

700

600

500

400

300

200

100

01998 2000 2001 20021999

Outro

SPARC

Hitachi SH

PowerPC

Motorola 68K

MIPS

IA-32

ARM

Milh

ões

de p

roce

ssad

ores

Aritmética MIPS

• Todas as instruções possuem três operandos

• A ordem do operando é fixa (destino primeiro)

Exemplo:Código C: a = b + c

Código MIPS: add a, b, c

(falaremos sobre registradores em breve)

“O número natural de operandos para uma operação como adição étrês... Exigir que cada instrução tenha exatamente três operandos, nemmais nem menos, está de acordo com a filosofia de manter o hardwaresimples.”

12

Aritmética MIPS

• Princípio de projeto: a simplicidade favorece a regularidade.

• É claro, isso complica algumas coisas...

Código C: a = b + c + d;

Código MIPS: add a, b, cadd a, a, d

• Os operandos precisam ser registradores, apenas 32 registradores fornecidos

• Cada registrador contém 32 bits

• Princípio de projeto: quanto menor, melhor. Por quê?

13

Registradores versus memória

• Os operandos das instruções aritméticas precisam ser registradores– apenas 32 registradores fornecidos

• O compilador associa variáveis com registradores

• E quanto aos programas com muitas variáveis?

14

E/S

Controle

Caminhode dados

Processador

Memória

Entrada

Saída

Organização da memória

• Vista como um array grande e unidimensional, com um endereço.

• Um endereço de memória é um índice para o array.

• “Endereçamento de byte” significa que o índice aponta para um byte da memória.

15

0

1

2

3

4

5

6

. . .

8 bits de dados

8 bits de dados

8 bits de dados

8 bits de dados

8 bits de dados

8 bits de dados

8 bits de dados

Organização da memória

• Os bytes são bons, mas a maioria dos itens de dados usam “words” maiores

• Para o MIPS, uma word possui 32 bits ou 4 bytes.

Os registradores armazenam 32 bits de dados

• 232 bytes com endereços de byte de 0 a 232–1

• 230 words com endereços de byte 0, 4, 8, ... 232–4

• As words são alinhadasPor exemplo, quais são os 2 bits menos significativosde um endereço de word?

16

04

12

32 bits de dados

8

32 bits de dados

32 bits de dados

32 bits de dados

Instruções

• Instruções load e store

• Exemplo:

Código C: A[12] = h + A[8];

Código MIPS: lw $t0, 32($s3)add $t0, $s2, $t0sw $t0, 48($s3)

• Pode se referir aos registradores por nome (por exemplo, $s2, $t2) em vez donúmero

• A instrução store word tem o destino por último

• Lembre-se de que os operandos são registradores, não memória!

Não podemos escrever: add 48($s3), $s2, 32($s3)

17

Nosso primeiro exemplo

• Você pode descobrir o código?

swap(int v[ ], int k);{ int temp;

temp = v[k]v[k] = v[k+1];v[k+1] = temp;

} swap:muli $2, $5, 4

� add $2, $4, $2lw $15, 0($2)lw $16, 4($2)sw $16, 0($2)sw $15, 4($2)jr $31

18

Até agora, aprendemos:

• MIPS

– carga de words mas endereçamento de bytes

– aritmética apenas em registradores

• Instrução Significado

add $s1, $s2, $s3 $s1 = $s2 + $s3sub $s1, $s2, $s3 $s1 = $s2 – $s3lw $s1, 100($s2) $s1 = Memory[$s2+100]sw $s1, 100($s2) Memory[$s2+100] = $s1

19

Linguagem de máquina

• Instruções, como registradores e words de dados, também possuem 32 bits detamanho

– Exemplo: add $t1, $s1, $s2

– Registradores têm números, $t1=9, $s1=17, $s2=18

• Formato da instrução:

000000 10001 10010 01000 00000 100000

op rs rt rd shamt funct

• Você sabe o significado dos nomes de campo?

20

Linguagem de máquina

• Pense nas instruções load-word e store-word

– O que o princípio da regularidade nos levaria a fazer?

– Novo princípio: Um bom projeto exige comprometimento

• Introduza um novo tipo de formato de instrução

– Tipo I para instruções de transferência de dados

– Outro formato era o tipo R para o registrador

• Exemplo: lw $t0, 32($s2)

35 18 9 32

op rs rt número de bit 16

• Qual é o compromisso?

21

Conceito do programa armazenado

• Instruções são bits

• Programas são armazenados na memória

– para serem lidos ou escritos exatamente como os dados

• Ciclo de execução e busca

– As instruções são buscadas e colocadas em um registrador especial

– Os bits no registrador “controlam” as ações subseqüentes

– Busca a próxima instrução e continua

22

Memória para dados, programas,compiladores, editores etc.

ProcessadorMemória

Controle

• Instruções de tomada de decisão

– altera o fluxo de controle

– por exemplo, mudar a “próxima” instrução a ser executada

• Instruções de desvio condicionais do MIPS:

bne $t0, $t1, Labelbeq $t0, $t1, Label

• Exemplo:

if (i==j) h = i + j;bne $s0, $s1, Labeladd $s3, $s0, $s1

Label: ....

23

Controle

• Instruções de desvio incondicionais do MIPS:

j label

• Exemplo:

if (i!=j) beq $s4, $s5, Lab1h=i+j; add $s3, $s4, $s5

else j Lab2h=i-j; Lab1: sub $s3, $s4, $s5

Lab2: ...

• Você pode construir um “loop for” simples?

24

Até agora:

• Instrução Significado

add $s1,$s2,$s3 $s1 = $s2 + $s3sub $s1,$s2,$s3 $s1 = $s2 – $s3lw $s1,100($s2) $s1 = Memory[$s2+100]sw $s1,100($s2) Memory[$s2+100] = $s1bne $s4,$s5,L Next instr. is at Label if $s4 � $s5beq $s4,$s5,L Next instr. is at Label if $s4 = $s5j Label Next instr. is at Label

• Formatos:

25

op rs rd shamt funct

endereço de 16 bits


R

I

J

op

op

rs

rt

rt

Fluxo de controle

• Temos: beq e bne; e branch-if-less-than?

• Nova instrução:

if $s1 < $s2 then$t0 = 1

slt $t0, $s1, $s2 else$t0 = 0

• Podemos usar essa instrução para construir “blt $s1, $s2, Label”

– agora podemos construir estruturas de controle gerais

• Note que o assembler precisa de um registrador para fazer isso

– existe uma política das convenções de uso para registradores

26

Política das convenções de usoNome Número do registrador Uso

$zero 0 O valor constante 0

$v0-$v1 2-3 Valores para resultados eavaliação de expressões

$a0-$a3 4-7 Argumentos

$t0-$t7 8-15 Temporários

$s0-$s7 16-23 Valores salvos

$t8-$t9 24-25 Mais temporários

$gp 28 Ponteiro global

$sp 29 Pointeiro de pilha

$fp 30 Pointeiro de quadro

$ra 31 Endereço de retorno

Registrador 1 ($at) reservado para o assembler, 26-27 para o sistema operacional

27

Constantes

• Constantes pequenas são usadas muito freqüentemente (50% dos operandos)Por exemplo: A = A + 5;

B = B + 1;C = C - 18;

• Soluções? Por que não?

– coloque “constantes típicas” na memória e carregue-as.

– crie registradores “hard-wired” (como $zero) para constantes como um.

• Instruções MIPS:

addi $29, $29, 4slti $8, $18, 10andi $29, $29, 6ori $29, $29, 4

• Princípio de projeto: Torne o caso comum rápido. Que formato?

28

E quanto às constantes maiores?

• Gostaríamos de ser capazes de carregar uma constante de 32 bits em umregistrador

• Precisamos usar duas instruções; nova instrução “load upper immediate”:

• Depois, precisamos acertar os bits de ordem inferior, por exemplo:

29

00000000000000001010101010101010

preenchido com zeroslui $t0, 1010101010101010

ori $t0, $t0, 1010101010101010

1010101010101010 0000000000000000

0000000000000000 1010101010101010

1010101010101010 1010101010101010

ori

Linguagem assembly versus linguagem de máquina

• O assembly fornece uma representação simbólica conveniente

– muito mais fácil do que escrever números

– por exemplo, destino primeiro

• A linguagem de máquina é realidade subjacente

– por exemplo, o destino não é mais o primeiro

• O assembly pode fornecer “pseudoinstruções”

– por exemplo, “move $t0, $t1” existe apenas no assembly

– seria mais bem implementada usando “add $t0,$t1,$zero”

• Ao considerar o desempenho, você deve contar as instruções reais

30

Outras questões

• Abordadas em seu laboratório de programação de linguagem assembly:

– suporte para procedimentos

– linkers, carregadores, layout da memória

– pilhas, quadros, recursão

– manipulação de strings e ponteiros

– interrupções e exceções

– chamadas de sistema e convenções

• Veremos alguns desses mais adiante

• Estudaremos as otimizações de compilador no Capítulo 4.

31

Visão geral do MIPS

• instruções simples, todas com 32 bits

• muito estruturado, nenhuma bagagem desnecessária

• apenas três formatos de instrução

• nos baseamos no compilador para obter desempenho– quais são os objetivos do compilador?

• ajudamos o compilador onde podemos

32

op rs rd shamt funct



R

I

J

op

op

rs

rt

rt

Endereços em desvios e jumps

• Instruções:

bne $t4,$t5,Label A próxima instrução está em Label se $t4 � $t5

beq $t4,$t5,Label A próxima instrução está em Label se $t4 = $t5

j Label A próxima instrução está em Label

• Formatos:

• Os endereços não são de 32 bits– Como manipular isso com instruções load e store?

33

op rs endereço de 16 bits


I

J op

rt

Endereços em desvios

• Instruções:

bne $t4,$t5,Label A próxima instrução está em Label se $t4�$t5beq $t4,$t5,Label A próxima instrução está em Label se $t4=$t5

• Formatos:

• Poderíamos especificar um registrador (como lw e sw) e acrescentá-lo ao endereço

– use o registrador de endereço de instrução (PC = contador do programa)

– a maioria dos desvios é local (princípio da localidade)

• As instruções jump usam apenas bits de ordem superior do PC

– limites de endereço de 256 MB

34

op rs endereço de 16 bitsI rt

Resumindo

Operandos MIPS

Nome Exemplo Comentários

32registradores

$s0-$s7, $t0-$t9, $zero,$a0-$a3, $v0-$v1, $gp, $fp, $sp,$ra, $at

Locais rápidos para dados. No MIPS, os dados precisam estar em registradores para a realização deoperações aritméticas. O registrador MIPS $zero sempre é igual a 0. O registrador $at é reservado para oassembler tratar de constantes grandes.

230 words namemória

Memória[0],Memória[4].....Memória[4294967292]

Acessadas apenas por instruções de transferência de dados. O MIPS utiliza endereços em bytes, de modoque os endereços em words seqüenciais diferem em 4 vezes. A memória contém estruturas de dados, arrayse spilled registers, como aqueles salvos nas chamadas de procedimento.

Assembly do MIPS

Categoria Instrução Exemplo Significado Comentários

Aritmética add [TD]add $s1,$s2,$s3[TN] [TD]$s1 = $s2 + $s3[TN] Três operandos; dados nos registradoressubtract [TD]sub $s1,$s2,$s3[TN] [TD]$s1 = $s2- $s3[TN] Três operandos; dados nos registradoresadd immediate addi $s1,$s2,100[TN] [TD]$s1=$s2 + 100[TN] Usada para somar constantes

Transferênciade dados

load word [TD]lw $s1,100($s2)[TN] $s1 = Memória[$s2 + 100 Dados da memória para o registrador

store word [TD]sw $s1,100($s2)[TN] Memória[$s2 + 100] = $s1 Dados do registrador para a memóriaload byte lb $s1,100($s2)[TN] $s1 = Memória[$s2 + 100 Byte da memória para o registradorstore byte sb $s1,100($s2)[TN] Memória[$s2+100] = $s1 Byte de um registrador para a memóriaload upper immed. [TD]lui $s1,100[TN] [TD]$s1 = 100 * 216[TN] Carrega constante nos 16 bits mais altos

Desviocondicional

branch on equal beq $s1,$s2,25 if ($s1 == $s2) go toPC + 4 + 100

Testa igualdade; desvio relativo ao PC

branch on not equal bne $s1,$s2,25 if ($s1 != $s2) go to PC + 4 + 100 Testa desigualdade; relativo ao PCset on less than slt $s1,$s2,$s3 if ($s2 < $s3) $s1 = 1; else $s1 =

0Compara menor que; usado com beq, bne

set less thanimmediate

slti $s1,$s2,100 if ($s2 < 100) $s1 = 1; else $s1 = 0 Compara menor que constante

Desvioincondicional

jump j 2500 go to 10000 Desvia para endereço de destino

jump register jr $ra go to [TD]$ra[TN] Para switch e retorno de procedimentojump and link jal 2500 [TD]$ra[TN] = PC + 4. go to 10000 Para chamada de procedimento

35

36

1. Endereçamento imediato

op rs rt Imediato

2. Endereçamento em registrador

op rs rt rd . . . funct Registradores

Registrador

3. Endereçamento de base

op rs rt

op rs rt

op

Endereço

Endereço

Endereço

Registrador +

4. Endereçamento relativo ao PC

5. Endereçamento pseudodireto

Memória

Byte Halfword Word

Word

Word

PC

PC

Memória

Memória

Arquiteturas alternativas

• Alternativa de projeto:

– forneça operações mais poderosas

– o objetivo é reduzir o número de instruções executadas

– o risco é um tempo de ciclo mais lento e/ou uma CPI mais alta

— “O caminho em direção à complexidade da operação é, portanto,repleto de perigos. Para evitar esses problemas, os projetistas passarampara instruções mais simples.

• Vejamos (brevemente) o IA-32

37

IA-32

• 1978: O Intel 8086 é anunciado (arquitetura de 16 bits)• 1980: O coprocessador de ponto flutuante 8087 é acrescentado• 1982: O 80286 aumenta o espaço de endereçamento para 24 bits; mais instruções• 1985: O 80386 estende para 32 bits; novos modos de endereçamento• 1989-1995: O 80486, Pentium e Pentium Pro acrescentam algumas instruções

(especialmente projetadas para um maior desempenho)• 1997: 57 novas instruções “MMX” são acrescentadas; Pentium II• 1999: O Pentium III acrescenta outras 70 instruções (SSE)• 2001: Outras 144 instruções (SSE2)• 2003: A AMD estende a arquitetura para aumentar o espaço de endereço para 64

bits; estende todos os registradores para 64 bits, além de outras mudanças (AMD64)• 2004: A Intel se rende e abraça o AMD64 (o chama EM64T) e inclui mais extensões

de mídia

• Essa história ilustra o impacto das “algemas douradas” da compatibilidade“adicionando novos recursos da mesma forma que se coloca roupas em umasacola”, uma arquitetura “difícil de explicar e impossível de amar”.

38

Visão geral do IA-32

• Complexidade:

– instruções de 1 a 17 bytes de tamanho

– um operando precisa agir como origem e destino

– um operando pode vir da memória

– modos de endereçamento complexos, por exemplo, “índice base ou escaladocom deslocamento de 8 ou 32 bits”

• Graça salvadora:

– as instruções mais usadas não são difíceis de construir

– os compiladores evitam as partes da arquitetura que são lentas

“O que o 80x86 perde em estilo é compensado naquantidade, tornando-o belo, do ponto de vistaapropriado”

39

Registradores e endereçamento de dados do IA-32

• Registradores no subconjunto de 32 bits que surgiram com o 80386

40

Códigos de condição

Nome

EAX

ECX

EDX

EBX

ESP

EBP

ESI

EDI

31 0

CS

SS

DS

ES

FS

GS

EIP

EFLAGS

Uso

GPR0

GPR1

GPR2

GPR3

GPR4

GPR5

GPR6

GPR7

Ponteiro do segmento de código

Ponteiro do segmento de pilha (topo da pilha)

Ponteiro do segmento de dados 0




Ponteiro de instrução (PC)

Restrições de registrador do IA-32

• Os registradores não são de “finalidade geral” — observe as restrições abaixo

Modo Descrição Restrições de registrador Equivalente MIPS

Registrador indireto Endereço está em um registrador. não ESP ou EBP lw $s0,0($s1)

Modo base com 8 ou 32 bits dedeslocamento

Endereço é o conteúdo do registrador basemais deslocamento.

não ESP ou EBP lw $s0,100($s1)#deslocamento� 16 bits

Base mais índice escalado O endereço é Base + (2Escala x Índice), ondeEscala tem o valor 0, 1, 2 ou 3.

Base: qualquer GPRÍndice: não ESP

mul $t0,$s2,4add $t0,$t0,$s1lw $s0,0($t0)

Base mais índice escalado com 8 ou32 bits de deslocamento

O endereço é Base + (2Escala x Índice) +deslocamento, onde Escala tem o valor 0, 1, 2

ou 3.

Base: qualquer GPRÍndice: não ESP

mul $t0,$s2,4add $t0,$t0,$s1lw $s0,100($t0)#deslocamento

� 16 bits

FIGURA 2.42 Modos de endereçamento de 32 bits do IA-32 com restrições de registrador e o código MIPS equivalente. O modo de endere-çamento Base mais Índice Escalado, que não aparece no MIPS ou no PowerPC, foi incluído para evitar as multiplicações por quatro (fator de escala 2) paratransformar um índice de um registrador em um endereço em bytes (ver Figuras 2.34 e 2.36). Um fator de escala 1 é usado para dados de 16 bits, e um fatorde escala 3 para dados de 64 bits. O fator de escala 0 significa que o endereço não é escalado. Se o deslocamento for maior do que 16 bits no segundo ouquarto modos, então o modo MIPS equivalente precisaria de mais duas instruções: um lui para ler os 16 bits mais altos do deslocamento e um add parasomar a parte alta do endereço ao registrador base $s1 (a Intel oferece dois nomes diferentes para o que é chamado modo de endereçamento com base -com base e indexado -, mas eles são basicamente idênticos, e os combinamos aqui).

41

Instruções típicas do IA-32

• Quatro tipos principais de instruções de inteiro:

– Movimento de dados, incluindo move, push, pop

– Aritmética e lógica (registrador de destino ou memória)

– Fluxo de controle (uso de códigos de condição/flags)

– Instruções de string, incluindo movimento e comparação de strings

Instrução Função

JE nome se for igual(códigos de condição) {EIP=nome};EIP-128 nome < EIP+128

JMP nome EIP=nomeCALL nome SP=SP-4; M[SP]=EIP+5; EIP=nome;MOVW EBX,[EDI+45] EBX=M[EDI+45]PUSH ESI SP=SP-4; M[SP]=ESIPOP EDI EDI=M[SP]; SP=SP+4ADD EAX,#6765 EAX= EAX+6765TEST EDX,#42 Define códigos de condição (flags) com EDX e 42MOVSL M[EDI]=M[ESI];

EDI=EDI+4; ESI=ESI+4

FIGURA 2.43 Algumas instruções IA-32 típicas e suas funções. Uma lista de operaçõesfreqüentes aparece na Figura 2.44. O CALL salva na pilha o EIP da próxima instrução (EIP é o PC da Intel).

42

Formatos de instruções IA-32

• Formatos típicos: (observe os diferentes tamanhos)

43

4 4 8

8 32

6 81 1 8

5 3

4 323 1

7 321 8

Imediato

a. JE EIP + deslocamento

JECondi-

ção Deslocamento

b. CALL

CALL Deslocamento (offset)

c. MOV EBX, [EDI + 45]

MOV d w Pós-byte r/m Deslocamento

d. PUSH ESI

PUSH Reg

e. ADD EAX, #6765

ADD Reg w Imediato

f. TEST EDX, #42

TEST w Pós-byte

Resumo

• A complexidade da instrução é apenas uma variável

– instrução mais baixa versus CPI mais alta/velocidade de clock mais baixa

• Princípios de projeto:

– a simplicidade favorece a regularidade

– menor é mais rápido

– um bom projeto exige comprometimento

– torne o caso comum rápido

• Arquitetura do conjunto de instruções

– uma abstração muito importante!

44

Capítulo 3

45

Números

• Bits são apenas bits (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

• Obviamente, torna-se mais complicado:números são finitos (overflow)frações e números reaisnúmeros negativospor exemplo, nenhuma instrução subi do MIPS; addi pode somarum número negativo

• Como representamos os números negativos?Por exemplo, que padrões de bit representarão esses números?

46

Representações possíveis

• Sinal e magnitude: Complemento a um Complemento a dois000 = +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

• Questões: equilíbrio, número de zeros, facilidade de operações

• Qual é o melhor? Por quê?

47

MIPS

• Números de 32 bits com sinal:

48

000000000000

000000000000

000000000000

000000000000

000000000000

000000000000

000000000000

000000010010

bin

bin

bin

= 0= + 1= + 2

dec

dec

dec

...

...

= + 2,147,483,646= + 2,147,483,647= - 2,147,483,648= - 2,147,483,647= - 2,147,483,646

dec

dec

dec

dec

dec

01110111100010001000

11111111000000000000

11111111000000000000

11111111000000000000

11111111000000000000

11111111000000000000

11111111000000000000

11101111000000010010

bin

bin

bin

bin

bin

minint

111111111111

111111111111

111111111111

111111111111

111111111111

111111111111

111111111111

111111111111

bin

bin

bin

= - 3= - 2= - 1

dec

dec

dec

maxint

Operações de complemento a dois

• Negar um número de complemento a dois: inverta todos os bits e some 1

– lembre-se: “negar” e “inverter” são muito diferentes!

• Converter números de n bits em números com mais de n bits:

– o campo imediato de 16 bits do MIPS é convertido em 32 bits para aritmética

– copie o bit mais significativo (o bit de sinal) para os outros bits

0010 –> 0000 00101010 –> 1111 1010

• “extensão de sinal” (lbu versus lb)

49

Adição e subtração

• Exatamente como aprendemos na escola (emprestar/subir 1s)0111 0111 0110

+ 0110 – 0110 – 0101

• Facilidade de operações do complemento a dois

– subtração usando adição para números negativos0111

+ 1010

• Overflow (resultado muito grande para a word finita do computador):

– por exemplo, somar dois números de n bits não produz um número de n bits0111

+ 0001 note que o termo overflow é um pouco confuso;1000 ele não significa que um carry “transbordou”

50

Detectando overflow

• Nenhum overflow quando somar um número positivo com um negativo

• Nenhum overflow quando sinais são iguais para subtração

• O overflow ocorre quando o valor afeta o sinal:

– overflow ao somar dois positivos produz um negativo

– ou, somar dois negativos produz um positivo

– ou, subtraia um negativo de um positivo e obtenha um negativo

– ou, subtraia um positivo de um negativo e obtenha um positivo

• Considere as operações A + B e A – B

– Pode ocorrer overflow se B for 0?

– Pode ocorrer overflow se A for 0?

51

Efeitos do overflow

• Uma exceção (interrupção) ocorre

– O controle salta para um endereço predefinido para exceção

– O endereço interrompido é salvo para uma possível retomada

• Detalhes baseados na linguagem/sistema de software

– exemplo: controle de vôo versus dever de casa

• Nem sempre desejamos detectar overflow – novas instruções MIPS: addu, addiu,subu

– Nota: addiu ainda com extensão de sinal– Nota: sltu, sltiu para comparações sem sinal

52

Multiplicação

• Mais complexa do que a adição

– realizada através de deslocamento e adição

• Mais tempo e mais área

• Vejamos três versões baseadas em um algoritmo da escola0010 (multiplicando)

x 1011 (multiplicador)

• Números negativos: converta e multiplique

– existem técnicas melhores mas não as veremos

53

Multiplicação: Implementação

54

Controle

MultiplicandoDeslocar

à esquerda

64 bits

ALU de 64 bits

ProdutoEscrever

64 bits

Teste decontrole

MultiplicadorDeslocarà direita

32 bits

Multiplicador0 = 1 1. TestarMultiplicador0

Multiplicador0 = 0

1a. Soma multiplicando ao produto ecoloca o resultado no registrador Produto

2. Deslocar registrador Multiplicando 1 bit à esquerda

Não: < 32 repetições

Sim: 32 repetições

Fim

3. Deslocar registrador Multiplicador 1 bit à direita

Início

Caminho de dados

32ª repetição?

Versão final

• O multiplicador inicia na metade direita do produto

55

O que entra aqui?

Multiplicando

32 bits

ALU de 32 bits

ProdutoDeslocar à direita

Escrever

Teste decontrole

64 bits

Início

Produto0 = 1 1. TestarProduto0

Produto0 = 0

3. Desloque o registrador Produto 1 bit para a direita

32ª repetição?Não: < 32 repetições

Sim: 32 repetições

Fim

Ponto flutuante (um breve exame)

• Precisamos de uma maneira de representar

– números com frações, por exemplo, 3,1416

– números muito pequenos, por exemplo, 0,000000001

– números muito grandes, por exemplo, 3,15576 × 109

• Representação:

– sinal, expoente, significando: (–1)sinal × significando × 2expoente

– mais bits para o significando fornece mais precisão

• mais bits para o expoente aumenta a faixa

• Padrão de ponto flutuante IEEE 754:

– precisão única: expoente de 8 bits, significando de 23 bits

– precisão dupla: expoente de 11 bits, significando de 52 bits

56

Padrão de ponto flutuante IEEE 754

• O bit “1” inicial do significando está implícito

• O expoente é “desviado” para facilitar a classificação

– todos os 0s são o menor expoente, todos os 1s são o maior

– desvio do 127 para precisão única e do 1023 para precisão dupla

– resumo: (–1)sinal × (1 + significando) × 2expoente – desvio

• Exemplo:

– decimal: –0,75 = – ( ½ + ¼ )

– binário: –0,11 = – 1,1 × 2–1

– ponto flutuante: expoente = 126 = 01111110

– precisão única IEEE: 10111111010000000000000000000000

57

Adição de ponto flutuante

58

Controle Deslocaà direita

ALU grande

Sinal Expoente Fração Sinal Expoente Fração

ALU pequena

Diferençado expoente

0 1 0 1 0 1

0 1 0 1

Incrementa oudecrementa

Desloca paraesquerda ou direita

Hardware dearredondamento

Sinal Expoente Fração

Início

1. Compare os expoentes dos dois números.Desloque o menor número para a direita até

que seu expoente combine com o expoente maior.

2. Some os significandos

3. Normalize a soma, deslocando para a direitae incrementando o expoente, ou deslocando para

a esquerda e decrementando o expoente.

Overflow ouunderflow?

Sim

Sim

ExceçãoNão

Não

4. Arredonde o significando parao número de bits apropriado

Aindanormalizado?

Fim

Complexidades do ponto flutuante

• As operações são um pouco mais complicadas (veja o texto)

• Além do overflow podemos ter o “underflow”

• A precisão pode ser um grande problema

– O IEEE 754 mantém dois bits extras, guarda e arredondamento

– quatro modos de arredondamento

– positivo dividido por zero produz “infinidade”

– zero dividido por zero não produz um número

– outras complexidades

• Implementar o padrão pode ser arriscado

• Não usar o padrão pode ser ainda pior

– veja no texto a descrição do 80x86 e o bug do Pentium!

59

Resumo do Capítulo 3

• A aritmética de computador é restrita por uma precisão limitada

• Os padrões de bit não têm um significado inerente mas existem padrões

– complemento a dois

– ponto flutuante IEEE 754

• As instruções de computador determinam o “significado” dos padrões de bit

• O desempenho e a precisão são importantes; portanto, existem muitascomplexidades nas máquinas reais

• A escolha do algoritmo é importante e pode levar a otimizações de hardwarepara espaço e tempo (por exemplo, multiplicação)

• Você fazer uma revisão pode ser uma boa idéia (a Seção 3.10 é uma ótima leitura!)

60

Capítulo 4

61

Desempenho

• Meça, informe e resuma

• Faça escolhas inteligentes

• Veja através da propaganda de marketing

• Vital para entender a motivação organizacional subjacente

Por que alguns hardwares são melhores do que outrospara diferentes programas?

Que fatores do desempenho de sistema são relacionadosao hardware? (por exemplo, precisamos de uma novamáquina ou de um novo sistema operacional?)

Como o conjunto de instruções da máquina afeta odesempenho?

62

Qual destes aviões possui o melhor desempenho?

Avião Passageiros Autonomia(milhas)

Velocidade(milhas por hora)

Boeing 737-100 101 630 598

Boeing 747 470 4150 610

BAC/Sud Concorde 132 4000 1350

Douglas DC-8-50 146 8720 544

• O quanto mais rápido é o Concorde comparado com o 747?

• O quanto maior é o 747 do que o Douglas DC-8?

63

Desempenho do computador: TEMPO, TEMPO, TEMPO

• Tempo de resposta (latência)

– Quanto tempo leva para meu trabalho ser realizado?

– Quanto tempo leva para realizar um trabalho?

– Quanto tempo preciso esperar para a consulta ao banco de dados?

• Vazão (throughput)

– Quantos trabalhos a máquina pode realizar ao mesmo tempo?

– Qual é a velocidade de execução média?

– Quanto trabalho está sendo feito?

• Se atualizarmos uma máquina com um novo processador, em que melhoramos?

• Se acrescentarmos uma máquina ao laboratório, em que melhoramos?

64

Tempo de execução

• Tempo decorrido

– conta tudo (acessos a disco e a memória, E/S etc.)

– um número útil, mas normalmente não é ideal para fins de comparação

• Tempo de CPU

– não conta E/S ou tempo gasto executando outros programas

– pode ser dividido em tempo de sistema e tempo de usuário

• Nosso foco: tempo de CPU do usuário

– tempo gasto executando as linhas de código que estão “em” nosso programa

65

Definição de desempenho do livro

• Para um programa sendo executado na máquina X,

DesempenhoX = 1 / Tempo_execuçãoX

• “X é n vezes mais rápido do que Y”

DesempenhoX / DesempenhoY = n

• Problema:

– a máquina A executa um programa em 20 segundos

– a máquina B executa o mesmo programa em 25 segundos

66

Ciclos de clock

• Em vez de informar o tempo de execução em segundos, normalmente usamosciclos

segundos=

ciclosx

segundosprograma programa ciclos

• As marcações de clock indicam quando iniciar as atividades (uma abstração):

• tempo de ciclo = tempo entre as marcações = segundos por ciclo

• velocidade de clock (freqüência) = ciclos por segundo (1 Hz. = 1 ciclo/segundo)

Um clock de 4 Ghz possui um tempo de ciclo de1

4 10109

12

xx =250 picosegundos (ps)

67

tempo

Como melhorar o desempenho

segundos=

ciclosx

segundosprograma programa ciclos

• Portanto, para melhorar o desempenho (tudo mais sendo igual), vocêpode (aumentar ou diminuir?)

o número de ciclos necessários para um programa, ou

o tempo de ciclo de clock ou, dito de outra maneira,

a velocidade de clock.

68

Quantos ciclos são necessários para um programa?

• Poderíamos considerar que o número de ciclos é igual ao número de instruções

Essa suposição é incorreta;diferentes instruções levam diferentes períodos de tempo emdiferentes máquinas.

Por quê? Dica: lembre-se de que essas são instruções de máquina,não linhas de código C.

69

Tempo

1ª in

stru

ção

2ª in

stru

ção

3ª in

stru

ção

4ª in

stru

ção

5ª in

stru

ção

6ª in

stru

ção

..

.

Diferentes números de ciclos para diferentes instruções

• A multiplicação leva mais tempo do que a adição

• As operações de ponto flutuante levam mais tempo do que as operações de inteiros

• Acessar a memória leva mais tempo do que acessar os registradores

• Importante: Mudar o tempo de ciclo normalmente muda o número de ciclosnecessários para várias instruções (veja mais posteriormente)

70

tempo

Exemplo

• Nosso programa favorito é executado em 10 segundos no computador A, quepossui um clock de 4 GHz. Estamos tentando ajudar um projetista de computadora construir uma nova máquina B, que execute esse programa em 6 segundos.O projetista determinou que um aumento substancial na velocidade de clock épossível, mas esse aumento afetará o restante do projeto da CPU, fazendo com queo computador B exija 1,2 vez mais ciclos de clock do que o computador A para esseprograma. Que velocidade de clock devemos pedir para que o projetista almeje?

• Não entre em pânico! Podemos resolver isso facilmente usando os princípiosbásicos

71

Agora que entendemos os ciclos

• Um determinado programa exigirá

– um determinado número de instruções (instruções de máquina)

– um determinado número de ciclos

– um determinado número de segundos

• Temos um vocabulário que relaciona essas quantidades:

– tempo de ciclo (segundos por ciclo)

– velocidade de clock (ciclos por segundo)

– CPI (ciclos por instrução)uma aplicação com excessivo uso de ponto flutuante podeter uma CPI mais alta

– MIPS (milhões de instruções por segundo)isso seria mais alto para um programa usando instruções simples

72

Desempenho

• O desempenho é determinado pelo tempo de execução

• Qualquer uma das outras variáveis igualam o desempenho?

– número de ciclos para executar o programa?

– número de instruções no programa?

– número de ciclos por segundo?

– número médio de ciclos por instrução?

– número médio de instruções por segundo?

• Armadilha comum: pensar que uma das variáveis é indicadora do desempenho,quando na realidade não é.

73

Exemplo de CPI

• Suponha que tenhamos duas implementações da mesma arquitetura do conjunto deinstruções (ISA)

Para um determinado programa,

A máquina A tem um tempo de ciclo de clock de 250 ps e uma CPI de 2,0A máquina B tem um tempo de ciclo de clock de 500 ps e uma CPI de 1,2

Que máquina é mais rápida para esse programa e quão mais rápida ela é?

• Se duas máquinas possuem a mesma ISA, qual de nossas quantidades (porexemplo, velocidade de clock, CPI, tempo de execução, número de instruções,MIPS) será sempre idêntica?

74

Exemplo de número de instruções

• Um projetista de compilador está tentando decidir entre duas seqüências de códigopara um determinada máquina. Com base na implementação de hardware, existemtrês classes diferentes de instruções: Classe A, Classe B e Classe C, e elas exigemum, dois e três ciclos, respectivamente.

A primeira seqüência de código possui 5 instruções: 2 de A, 1 de B e 2 de C.A segunda seqüência possui 6 instruções: 4 de A, 1 de B e 1 de C.

Que seqüência será mais rápida? O quanto mais rápida? Qual é a CPI para cadaseqüência?

75

Exemplo de MIPS

• Dois compiladores diferentes estão sendo testados para uma máquina de 4 GHzcom três classes diferentes de instruções: Classe A, Classe B e Classe C, e elasexigem um, dois e três ciclos, respectivamente. Ambos os compiladores são usadospara produzir código para um grande software.

O código do primeiro compilador usa 5 milhões de instruções da Classe A, 1 milhãode instruções da Classe B e 1 milhão de instruções da Classe C.

O código do segundo compilador usa 10 milhões de instruções da Classe A, 1milhão de instruções da Classe B e 1 milhão de instruções da Classe C.

• Que seqüência será mais rápida de acordo com o MIPS?

• Que seqüência será mais rápida de acordo com o tempo de execução?

76

Benchmarks

• A melhor forma de determinar desempenho é executando uma aplicação real

– Usa programas típicos do workload esperado

– Ou, típico da classe de aplicações esperada — por exemplo,compiladores/editores, aplicações científicas, design gráfico etc.

• Benchmarks pequenos

– ótimos para arquitetos e projetistas

– fácil de padronizar

– pode ser forçado

• SPEC (System Performance Evaluation Cooperative)

– as empresas concordaram sobre um conjunto de programas e entradas reais

– valioso indicador do desempenho (e da tecnologia do compilador)

– ainda pode ser forçado

77

Jogos de benchmark

• A Intel reconheceu, envergonhada, na sexta-feira que um bug em um programa desoftware conhecido como um compilador levou a empresa a anunciar umavelocidade 10 por cento maior dos seus chips microprocessadores em umbenchmark da área. Entretanto, os analistas do setor disseram que o erro decodificação foi um comentário infeliz sobre uma prática comum de “mentir” nostestes de desempenho padronizados. O erro foi atribuído à Intel dois dias atrás pelaconcorrente Motorola, em um teste conhecido como SPECint92. A Intel reconheceuque havia “otimizado” seu compilador para melhorar suas pontuações de teste.A empresa também havia dito que não gostava da prática, mas que foi forçadaa fazer as otimizações porque seus concorrentes estavam fazendo o mesmo.No coração do problema da Intel está a prática de “ajustar” os programas decompilador para reconhecerem certos problemas de computação no teste e, então,substituir por partes especiais do código escritas a mão.

Sábado, 6 de janeiro de 1996 — New York Times

78

SPEC ‘89

• “Melhorias” e desempenho de compilador

79

0

100

200

300

400

500

600

700

800

tomcatvfppppmatrix300eqntottlinasa7doducspiceespressogcc

Compilador melhorado

Taxa

de

dese

mpe

nho

SP

EC

BenchmarkCompilador

SPEC CPU2000

Benchmarks de inteiros Benchmarks de ponto flutuante

Nome Descrição Nome Tipo

gzip Compactação Wupwise Cromodinâmica Quânticavpr Posicionamento e roteamento de circuitos FPGA Swim Modelo de água rasagcc O compilador C Gnu Mgrid Solver multigrade no campo 3D potencialmcf Otimização combinatória Applu Equação diferencial parcial parabólica/elípticacrafty Programa de xadrez Mesa Biblioteca de gráficos tridimensionaisparser Programa de processamento de textos Galgel Dinâmica computacional de fluidoseon Visualização por computador Art Reconhecimento de imagem usando redes neuraisperlbmk Aplicação Perl Equake Simulação de propagação de ondas sísmicasgap Teoria de grupo, interpretador Facerec Reconhecimento de imagem de rostosvortex Banco de dados orientado a objetos Ammp Química computacionalbzip2 Compactação Lucas Teste de primalidadetwolf Simulador de posicionamento e roteamento de circuitos Fma3d Simulação de choque usando método de elementos finitos

Sixtrack Projeto de acelerador de física nuclear de alta energiaApsi Meteorologia: distribuição de poluentes

FIGURA 4.5 Os benchmarks SPEC CPU2000. Os 12 benchmarks de inteiros no lado esquerdo da tabela são escritos em C e C++, enquanto os ben-chmarks de ponto flutuante no lado direito são escritos em Fortran (77 ou 90) e em C. Para obter mais informações sobre o SPEC e os benchmarks SPEC,veja www.spec.org. Os benchmarks SPEC CPU usam o tempo de relógio como métrica, mas, como há pouca E/S, eles medem o desempenho da CPU.

80

SPEC 2000

Dobrar a velocidade de clock dobra o desempenho?

Uma máquina com uma velocidade de clock mais lenta pode ter um desempenho melhor?

81

Experiência

• Telefone para um grande vendedor de computadores e diga que você está comdificuldade de decidir entre dois computadores diferentes, especificamente, queestá confuso quanto aos pontos fortes e fracos dos processadores

(Por exemplo, entre Pentium 4 2Ghz e Celeron M 1.4 Ghz)

• Que tipo de resposta você provavelmente receberá?

• Que tipo de resposta você poderia dar a um amigo com a mesma dúvida?

82

Lei de Amdahl

Tempo de execução após melhoria = Tempo de execução não afetado+ (Tempo de execução afetado / Quantidade de melhoria)

• Exemplo:

“Suponha que um programa seja executado em 100 segundos em umamáquina, com multiplicação responsável por 80 segundos desse tempo. O quantoprecisamos melhorar a velocidade da multiplicação se queremos que o programaseja executado 4 vezes mais rápido?”

Que tal torná-lo 5 vezes mais rápido?

• Princípio: torne o caso comum rápido

83

Exemplo

• Suponha que melhoramos uma máquina fazendo todas as instruções de pontoflutuante serem executadas cinco vezes mais rápido. Se o tempo de execução dealgum benchmark antes da melhoria do ponto flutuante é 10 segundos, qual será oaumento de velocidade se metade dos 10 segundos é gasta executando instruçõesde ponto flutuante?

• Estamos procurando um benchmark para mostrar a nova unidade de pontoflutuante descrita acima e queremos que o benchmark geral mostre um aumento develocidade de 3 vezes. Um benchmark que estamos considerando é executadodurante 100 segundos com o hardware de ponto flutuante antigo. Quanto do tempode execução as instruções de ponto flutuante teriam que considerar para produzirnosso aumento de velocidade desejado nesse benchmark?

84

Lembre-se

• O desempenho é específico a um determinado programa

– O tempo de execução total é um resumo consistente do desempenho

• Para uma determinada arquitetura, os aumentos de desempenho vêm de:

• aumentos na velocidade de clock (sem efeitos de CPI adversos)

– melhorias na organização do processador que diminuem a CPI

– melhorias no compilador que diminuem a CPI e/ou a contagem de instruções

– escolhas de algoritmo/linguagem que afetam a contagem de instruções

• Armadilha: esperar que a melhoria em um aspecto do desempenho de uma máquinaafete o seu desempenho total

85

Vamos construir um processador

• Estamos quase prontos para entrar no Capítulo 5 e iniciar a construção de umprocessador

• Primeiro, vamos revisar a lógica booleana e construir a ALU de que precisaremos(material do Apêndice B)

86

32

32

32

a

b

ALU

operação

resultado

Revisão: Álgebra booleana e portões

• Problema: Considere uma função lógica com três entradas: A, B e C.

A saída D é verdadeira se pelo menos uma entrada for verdadeiraA saída E é verdadeira se exatamente duas entradas forem verdadeirasA saída F é verdadeira apenas se todas as três entradas forem verdadeiras

• Mostre a tabela de verdade para essas três funções.

• Mostre as equações booleanas para essas três funções.

• Mostre a implementação consistindo de portões inversores, AND e OR.

87

b

a resultado

operação op resba

Uma ALU (unidade lógica aritmética)

• Vamos construir uma ALU para dar suporte às instruções andi e ori

– construiremos apenas uma ALU de 1 bit e usaremos 32 deles

• Implementação possível (soma-dos-produtos):

88

Revisão: o multiplexador

• Seleciona uma das entradas para ser a saída, com base em uma entrada de controle

Nota: chamamos isso de um mux de duas entradas, mesmoque ele tenha três entradas!

• Vamos construir nossa ALU usando um MUX:

89

S

A

BC0

1

Diferentes implementações

• Não é fácil decidir a “melhor” maneira de construir algo

– não queremos entradas demais em um único portão

– não queremos ter que atravessar muitos portões

– para nossos objetivos, a facilidade de compreensão é importante

• Vejamos uma ALU de 1 bit para adição:

• Como poderíamos construir uma ALU de 1 bit para add, and e or?

• Como poderíamos construir uma ALU de 32 bits?

90

Sum

CarryIn

CarryOut

a

b

c = a b + a c + b cout in in

sum = a xor b xor cin

Construindo uma ALU de 32 bits

91

OperaçãoCarryIn

Resultado

CarryOut

a

b

1

0

2+

a0 CarryInALU0

CarryOutb0

CarryIn

a1 CarryInALU1

CarryOutb1

Resultado0

Resultado1

a2 CarryInALU2

CarryOutb2

a31 CarryInALU31

b31

Result 2ado

Result 31ado

......

...

Operação

E quanto à subtração (a – b)?

• Método do complemento a dois: simplesmente negue b e some.

• Como negamos?

• Uma solução muito inteligente:

92

Binvert

a

b

CarryIn

CarryOut

1

0

2+

1

0

Operação

Resultado

Acrescentando uma função NOR

• Também podemos escolher inverter a. Como obtemos um “a NOR b”?

93

Binvert

a

b

CarryIn

CarryOut

Operação

Resultado1

0

2+

1

1

0

0

Ainvert

Adequando a ALU ao MIPS

• Precisamos oferecer suporte à instrução set-on-less-than (slt)

• lembre-se: slt é uma instrução aritmética

– produz um 1 se rs < rt e produz um 0 em caso contrário

– use subtração: (a–b) < 0 implica a < b

• Precisamos aceitar teste de igualdade (beq $t5, $t6, $t7)

• use subtração: (a–b) = 0 implica a = b

94

Suporte a slt

• Podemos imaginar a idéia?

95

Binvert

a

b

CarryIn

CarryOut

1

0

2+

ResultadoResultado

1

0

Ainvert

1

0

3Less

Binvert

a

b

CarryIn

1

0

2+

1

0

3Less

Set

Overflow

Ainvert

1

0

OperaçãoOperação

Detecçãode overflow

Use esta ALU para o bit mais significativo

Todos os outros bits

Suporte a slt

96

...

a0

Operação

CarryInALU0Less

CarryOut

b0

CarryIn

a1 CarryInALU1Less

CarryOut

b1

Result 0ado

Result 1ado

a2 CarryInALU2Less

CarryOut

b2

a31 CarryInALU31Less

b31

Result 2ado

Result 31ado

......

...

Binvert

...

Ainvert

0

0

0 Overflow

...

Set

CarryIn

...

a0

Operação

CarryInALU0Less

CarryOut

b0

a1 CarryInALU1Less

CarryOut

b1

Result0

Result1

a2 CarryInALU2Less

CarryOut

b2

a31 CarryInALU31Less

b31

Result2

Result31

......

...

Bnegate

...

Ainvert

0

0

0 Overflow

...

Set

CarryIn...

...Zero

Teste de igualdade

• Observe as linhas de controle:

0000 = and0001 = or0010 = add0110 = subtract0111 = slt1100 = NOR

• Nota: zero é um 1 quando oresultado é zero!

97

Conclusão

• Podemos construir uma ALU para aceitar o conjunto de instruções MIPS

– idéia básica: usar um multiplexador para selecionar a saída que desejamos

– podemos realizar subtração eficientemente usando o complemento a dois

– podemos duplicar uma ALU de 1 bit para produzir uma ALU de 32 bits

• Pontos importantes sobre hardware

– todos os portões estão sempre operando

– a velocidade de um portão é influenciada pelo número de entradas do portão

– a velocidade de um circuito é influenciada pelo número de portões na série (no“caminho crítico” ou no “nível mais profundo da lógica”)

• Nosso foco principal: compreensão; entretanto,

– Mudanças inteligentes na organização podem melhorar o desempenho(semelhante a usar melhores algoritmos no software)

– Vimos isso na multiplicação; agora vejamos na adição

98

Problema: o somador com carry ripple é lento

• Uma ALU de 32 bits é tão rápida quanto uma ALU de 1 bit?

• Existe mais de uma maneira de fazer adição?

– dois extremos: carry ripple e soma-de-produtos

Você consegue ver o ripple? Como você se livraria dele?

c1 = b0c0 + a0c0 + a0b0c2 = b1c1 + a1c1 + a1b1c2 =c3 = b2c2 + a2c2 + a2b2 c3 =c4 = b3c3 + a3c3 + a3b3 c4 =

Inviável! Por quê?

99

Somador com carry look-ahead

• Um método intermediário entre nossos dois extremos

• Motivação:

– Se não soubéssemos o valor do carry-in, o que poderíamos fazer?

– Quando sempre geraríamos um carry? gi = ai bi

– Quando propagaríamos o carry? pi = ai + bi

• Nos livramos do ripple?

c1 = g0 + p0c0c2 = g1 + p1c1 c2 =c3 = g2 + p2c2 c3 =c4 = g3 + p3c3 c4 =

Viável! Por quê?

100

Use princípio para construir somadores maiores

• Não podemos construir um somador de16 bits dessa maneira... (grande demais)

• Poderíamos usar o carry ripple dossomadores CLA de 4 bits

• Melhor ainda: use o princípio CLAnovamente!

101

a4 CarryIn

ALU1P1G1

b4a5b5a6b6a7b7

a0 CarryIn

ALU0P0G0

b0a1b1a2b2a3b3

CarryIn

Resultado0–3

pigi

ci + 1

pi + 1gi + 1

C1

Resultado4–7

a8 CarryIn

ALU2P2G2

b8a9b9

a10b10a11b11

ci + 2

pi + 2gi + 2

C2

Resultado8–11

a12 CarryIn

ALU3P3G3

b12a13b13a14b14a15b15

ci + 3

pi + 3gi + 3

C3

Resultado12–15

ci + 4C4

CarryOut

Unidade de carry lookahead

Resumo da ALU

• Podemos construir uma ALU para aceitar adição MIPS• Nosso foco está na compreensão, não no desempenho• Processadores reais usam técnicas mais sofisticadas para aritmética• Onde o desempenho não é vital, as linguagens de descrição de hardware permitem

que os projetistas automatizem completamente a criação do hardware!

module MIPSALU (ALUctl, A, B, ALUOut, Zero);input [3:0] ALUctl;input [31:0] A,B;output reg [31:0] ALUOut;output Zero;assign Zero = (ALUOut==0); // Zero é verdadeiro se ALUOut é 0; vai para algum lugaralways @(ALUctl, A, B) // reavalia se estes mudarem

case (ALUctl)0: ALUOut <= A & B;1: ALUOut <= A | B;2: ALUOut <= A + B;6: ALUOut <= A - B;7: ALUOut <= A < B ? 1:0;12: ALUOut <= ~(A | B); // resultado é nordefault: ALUOut <= 0; // default é 0, não deverá acontecer;

endcaseendmodule

FIGURA B4.3 Uma definição comportamental em Verilog de uma ALU MIPS. Isso poderia ser sintetizado por meiode uma biblioteca de módulos contendo operações aritméticas e lógicas básicas.

102

Capítulo 5

103

O processador: caminho de dados e controle

• Estamos prontos para ver uma implementação do MIPS

• Simplificada para conter apenas:

– instruções de referência à memória: lw, sw

– instruções lógicas e aritméticas: add, sub, and, or, slt

– instruções de fluxo de controle: beq, j

• Implementação genérica:

– use o contador de programa (PC) para fornecer endereço de instrução

– obtenha a instrução da memória

– leia os registradores

– use a instrução para decidir exatamente o que fazer

• Todas as instruções usam a ALU após lerem os registradoresPor quê? Referência à memória? Aritmética? Fluxo de controle?

104

Mais detalhes de implementação

• Visão abstrata/simplificada:

Dois tipos de unidades funcionais:

– elementos que operam nos valores de dados (combinacionais)

– elementos que contêm estado (seqüenciais)

105

Add Add

PC Endereço Instrução

Memóriade instruções

Dados

Nº do RegistradorRegistradores ALU Endereço

Memóriade dados

Dados

4

Nº do Registrador

Nº do Registrador

Elementos de estado

• Sem clock versus com clock

• Clocks usados na lógica síncrona

– quando um elemento que contém estado deve ser atualizado?

106

Período de clock Transição de subida

Transição de descida

tempo de ciclo

Um elemento de estado sem clock

• O trinco set-reset

– a saída depende das entradas presentes e também das entradas passadas

107

R

S

Q

Q

Trincos e flip-flops

• A saída é igual ao valor armazenado dentro do elemento (não é necessário pedirpermissão para olhar o valor)

• A mudança do estado (valor) é baseada no clock

• Trincos: sempre que as entradas mudarem e o clock for afirmado

• Flip-flop: o estado muda apenas em uma transiçãode clock (metodologia de acionamento por transição)

“Logicamente verdadeiro”— poderia significar eletricamente baixo

Uma metodologia de clocking define quando os sinais podem ser lidos e quandopodem ser escritos — não desejaríamos ler um sinal ao mesmo tempo em que eleestivesse sendo escrito

108

Trinco D

• Duas entradas:

– o valor de dados a ser armazenado (D)

– o sinal de clock (C) indicando quando ler e armazenar D

• Duas saídas:

– o valor do estado interno (Q) e seu complemento

109

C

D

Q

Q

D

C

Q

Flip-flop D

• A saída muda apenas na transição do clock

110

D

C

Q

D

C

Dlatch

D

C

QD

latch

D

C

QQ

QQ

Nossa implementação

• Uma metodologia de acionamento por transição

• Execução típica:

– ler conteúdo de alguns elementos de estado,

– enviar valores através de alguma lógica combinacional

– escrever os resultados em um ou mais elementos de estado

111

Elementode estado

2

Elementode estado

1Lógica combinacional

Ciclo de clock

Arquivo de registrador

• Construído usando flip-flops D

112

. . .Mux

Mux

Registrador deleitura número 1


Registrador 0

Registrador 1

Registrador n – 2

Registrador n – 1

Dados daleitura 1

Dados daleitura 2

Banco de registradores



Registradorpara escrita

Dados paraescrita

Dados daleitura 1

Dados daleitura 2

Write

Você entende? Qual é o “Mux” acima?

Abstração

• Certifique-se de ter entendido as abstrações!

• Algumas vezes é fácil achar que entendeu, quando não entendeu

113

Mux

C

Select

32

32

32

B

A

Mux

Select

B31

A31

C31

Mux

B30

A30

C30

Mux

B0

A0

C0

...

...

Arquivo de registrador

• Nota: ainda usamos o clock real para determinar quando escrever

114

01

n –1

n

C

D

C

D

C

D

C

D

...

...

Escrita

Número doregistrador

Dados parao registrador

Decodificadorn-para-2n

Registrador 0

Registrador 1

Registrador n – 2

Registrador n – 1

Implementação simples

• Inclui as unidades funcionais de que precisamos para cada instrução

115

Endereçode instrução

Instrução


a. Memória de instruções

PC

b. Contador de programa

Add Soma

c. Somador

EscreveMem

Endereço

Dadosparaescrita

Dadosda

leitura

Memóriade dados

LeMem

a. Unidade de memória de dados

Extensãode sinal

b. Unidade de extensão de sinal

16 32

Números dosregistradores

Dados

5

5

5

Registradorde leitura 1



Dadospara escrita

Dados daleitura 1

Dados daleitura 2

Registradores

EscreveReg

a. Registradores

Dados

4Operação da ALU

ZeroALUResultado

da ALU

b. ALU

Por que precisamos disso?

Construindo o caminho de dados

• Use multiplexadores para uni-los

116

Add

PCEndereçode Leitura

Instrução

Memória deinstruções




Dadospara escrita

Registradores

Dadosda leitura 1

Dadosda leitura 2

EscreveReg

Extensãode sinal

Deslo-camentode 2 à

esquerda

OrigALU

Mux

Mux

Mux

AddResultado

da ALU

Operação da ALU

ALUZero

Resultadoda ALU

OrigPC

EscreveMem

Endereço

Dadospara escrita

Dadosda leitura

Memóriade dados

LeMem

MemparaReg

4

4

16 32

Controle

• Selecionar as operações a serem realizadas (ALU, leitura/escrita etc.)

• Controlar o fluxo de dados (entradas do multiplexador)

• Informações vêm dos 32 bits da instrução

• Exemplo:

add $8, $17, $18 Formato de instrução:

000000 10001 10010 01000 00000 100000

op rs rt rd shamt funct

• Operação da ALU com base no tipo de instrução e código de função

117

Controle

• Por exemplo, o que a ALU deve fazer com essa instrução

• Exemplo: lw $1, 100($2)

35 2 1 100

op rs rt offset de 16 bits

• Entrada do controle da ALU

0000 AND0001 OR0010 add0110 subtract0111 set-on-less-than1100 NOR

• Por que o código para subtrair é 0110 e não 0011?

118

Controle

• Precisa descrever hardware para calcular entrada de controle da ALU de 4 bits

– tipo de instrução dada00 = lw, sw01 = beq, OpALU calculado do tipo de instrução10 = aritmética

– código de função para aritmética

• Descreva-o usando uma tabela verdade (pode se tornar portões):

OpALU Campo func.

OperaçãoOpALU1 OpALU 0 F5 F4 F3 F2 F1 F0

0 0 X X X X X X 0010X 1 X X X X X X 01101 X X X 0 0 0 0 00101 X X X 0 0 1 0 01101 X X X 0 1 0 0 00001 X X X 0 1 0 1 00011 X X X 1 0 1 0 0111

FIGURA 5.13 A tabela verdade para os três bits de controle da ALU (chamados Operação). As entradas são OpALU e o campo de código func.Apenas as entradas para as quais o controle da ALU é ativado são mostradas. Algumas entradas “don’t care” foram incluídas. Por exemplo, como OpALUnão usa a codificação 11, a tabela verdade pode conter entradas 1X e X1, em vez de 10 e 01. Além disso, quando o campo func é usado, os dois primeirosbits (F5 e F4) dessas instruções são sempre 10; portanto, eles são termos don’t care e são substituídos por XX na tabela verdade.

119

Instrução RegDst OrigALUMempara

RegEscreve

RegLe

MemEscreve

Mem Branch ALUOpl ALUOp0formato R 1 0 0 1 0 0 0 1 0

lw 0 1 1 1 1 0 0 0 0sw X 1 X 0 0 1 0 0 0beq X 0 X 0 0 0 1 0 1

120

Add

PC Endereçode Leitura

Instrução[31 0]:





Dadosparaescrita Registradores

Dadosda

leitura 1

Dadosda

leitura 2

Instrução [5:0]

Instrução [15 0]:

Instrução [15 11]:



Instrução [31:26]


esquerda

1

Mux

0

AddResultado

da ALU

ALUZero

Resultadoda ALU Endereço

Dadosparaescrita

Dadosda

leitura

Memóriade dados

4

16 32

11

1

Mux

Mux

Mux

00

0

Controle

RegDstBranchLeMemMemparaRegOpALUEscreveMemOrigALUEscreveReg

Extensãode sinal

Controleda ALU

Controle

• Lógica combinacional simples (tabelas verdade)

121

Iw sw beq

Op0

Op1

Op2

Op3

Op4

Op5

RegDst

OrigALU

Branch

Entradas

Formato R

Saídas

MemparaReg

EscreveReg

LeMem

EscreveMem

OpALU1

OpALU0

Operação 2

Opera 1ção

Opera 0ção

Operation

F3

F2

F1

F0

F (5–0)

OpALU

Bloco de controle da ALU

OpALU0

OpALU1

Nossa estrutura de controle simples

• Toda a lógica é combinacional

• Esperamos que tudo se acalme e a coisa certa seja feita

– a ALU pode não produzir a “resposta certa” imediatamente

– usamos sinais de escrita junto com o clock para determinar quando escrever

• Tempo de ciclo determinado pela duração do caminho mais longo

Estamos ignorando alguns detalhes como tempos de setup e hold

122

Elementode estado

2

Elementode estado

1Lógica combinacional

Ciclo de clock

Implementação de ciclo único

• Calcule o tempo de ciclo considerando os retardos insignificantes, exceto:– memória (200ps),

ALU e somadores (100ps)acesso ao arquivo de registrador (50ps)

123

Add

PCEndereçode Leitura

Instrução





Dadospara escrita

Registradores

Dadosda leitura 1

Dadosda leitura 2

EscreveReg

Extensãode sinal


esquerda

OrigALU

Mux

Mux

Mux

AddResultado

da ALU

Operação da ALU

ALUZero

Resultadoda ALU

OrigPC

EscreveMem

Endereço

Dadospara escrita

Dadosda leitura

Memóriade dados

LeMem

MemparaReg

4

4

16 32

Nosso direcionamento

• Problemas de ciclo único:– e se tivéssemos uma instrução mais complicada, como ponto flutuante?– desperdício de área

• Uma solução:– usar um tempo de ciclo “menor”– fazer com que diferentes instruções usem diferentes números de ciclos– um caminho de dados “multiciclo”:

124

PC Endereço

Memória

Dados

Instruçãoou dados

Registradorde instrução

Registradorde dados

da memória

Dados

Nº do RegistradorRegistradores

Nº do Registrador

Nº do Registrador

A

B

ALU SaídaALU

Método multiciclo

• Vamos reutilizar unidades funcionais

– ALU usada para calcular endereço e incrementar o PC

– Memória usada para instrução e dados

• Nossos sinais de controle não serão determinados diretamente pela instrução

– por exemplo, o que a ALU deve fazer para uma instrução “subtração”?

• Usaremos uma máquina de estado finito para controle

125

Método multiciclo

• Divida as instruções em etapas, cada uma durando um ciclo– equilibre a quantidade de trabalho a ser feito– restrinja cada ciclo para usar apenas uma unidade funcional

• No final de um ciclo– armazene os valores para uso em ciclos posteriores (a coisa mais fácil a fazer)– introduza registradores “internos” adicionais

126

Endereço

Memória

DadosMem

Dadospara escrita

Instrução[25:21]

Instrução[20:16]

Instrução[15:0]


Instrução[15:0]

Registradorde dados

da memória

Instrução[15:11]




Dados paraescrita

Dadosda

leitura 1

Dadosda

leitura 2

Registradores

Extensãode sinal

A

B

Desloca-mentode 2 à

esquerda

ZeroALU

Resultadoda ALU

SaídaALU

PC Mux

0Mux

1

0Mux

1

0Mux

1

0123

4

16 32

Mux

0

1

Instruções da perspectiva da ISA

• Considere cada instrução da perspectiva da ISA.

• Exemplo:

– A instrução add muda um registrador.

– Registrador especificado pelos bits 15:11 da instrução.

– Instrução especificada pelo PC.

– Novo valor é a soma (“op”) dos dois registradores.

– Registradores especificados pelos bits 25:21 e 20:16 da instrução

Reg[Memory[PC][15:11]] <= Reg[Memory[PC][25:21]] opReg[Memory[PC][20:16]]

– Para conseguir isso, precisamos desmembrar a instrução (um tanto comointroduzir variáveis ao programar).

127

Desmembrando uma instrução

• Definição ISA da aritmética:

Reg[Memory[PC][15:11]] <= Reg[Memory[PC][25:21]] opReg[Memory[PC][20:16]]

• Poderia ser dividida em:

– IR <= Memory[PC]

– A <= Reg[IR[25:21]]

– B <= Reg[IR[20:16]]

– ALUOut <= A op B

– Reg[IR[20:16]] <= ALUOut

• Esquecemos uma parte importante da definição da aritmética!

– PC <= PC + 4

128

Conceito subjacente do método multiciclo

• Definimos cada instrução da perspectiva ISA (faça isso!)

• Divida-a em etapas seguindo nossa regra de que os dados fluem através de, nomáximo, uma grande unidade funcional (por exemplo, distribua o trabalho entre asetapas)

• Introduza novos registradores conforme necessário (por exemplo, A, B, ALUOut,MDR, etc.)

• Finalmente, experimente concentrar o máximo em cada etapa (evite ciclosdesnecessários), enquanto também tenta compartilhar etapas quando possível(minimiza o controle e ajuda a simplificar a solução)

• Resultado: a implementação multiciclo do nosso livro!

129

Cinco etapas de execução

• Busca da instrução

• Decodificação da instrução e busca dos registradores

• Execução, cálculo do endereço de memória ou conclusão do desvio

• Acesso à memória ou conclusão da instrução tipo R

• Etapa de escrita adiada (write-back)

AS INSTRUÇÕES LEVAM DE 3 A 5 CICLOS!

130

Etapa 1: Busca da instrução

• Use o PC para obter a instrução e colocá-la no registrador Instrução.

• Incremente o PC em 4 e coloque o resultado novamente no PC.

• Pode ser descrita brevemente usando a RTL (Register-Transfer Language —linguagem de transferência de registrador)

IR <= Memory[PC];PC <= PC + 4;

Podemos descobrir os valores dos sinais de controle?

Qual é a vantagem de atualizar o PC agora?

131

Etapa 2: Decodificação da instrução e busca dosregistradores

• Leia os registradores rs e rt no caso de precisarmos deles

• Calcule o endereço de desvio no caso de a instrução ser um branch

• RTL:

A <= Reg[IR[25:21]];B <= Reg[IR[20:16]];ALUOut <= PC + (sign-extend(IR[15:0]) < 2);

• Não estamos definindo quaisquer linhas de controle com base no tipo de instrução(estamos ocupados “decodificando-a” em nossa lógica de controle)

132

Etapa 3 (dependente da instrução)

• ALU está desempenhando uma de três funções, com base no tipo de instrução

– Referência à memória:

ALUOut <= A + sign-extend(IR[15:0]);

– Tipo R:

ALUOut <= A op B;

– Branch:

if (A==B) PC <= ALUOut;

133

Etapa 4: (Tipo R ou acesso à memória)

• Loads e stores acessam a memória

MDR <= Memory[ALUOut];ou

Memory[ALUOut] <= B;

• Instruções Tipo R terminam

Reg[IR[15:11]] <= ALUOut;

A escrita na verdade ocorre no final do ciclo na transição

134

Etapa 5: Escrita adiada

• Reg[IR[20:16]] <= MDR;

Que instrução precisa disso?

135

Resumo

EtapaAção para instruções

tipo R Ação para instruções de acesso à memória Ação para desvios Ação para jumps

Busca da instrução IR <= Memória[PC]PC <= PC + 4

Decodificação da instrução ebusca dos registradores

A <= Reg[IR[25:21]]B <= Reg[IR[20:16]]

SaídaALU <= PC + (estende-sinal (IR[15:0]) << 2)

Execução, cálculo do endereço,conclusão do desvio/jump

SaídaALU <= A op B SaídaALU <= A + estende-sinal(IR[15:0])

if (A == B)PC <= SaídaALU

PC <= {PC [31:28],(IR[25:0]],2’b00)}

Acesso à memória ouconclusão de instrução tipo R

Reg[IR[15:11]]<=SaídaALU

Load: MDR <= Memória[SaídaALU]ouStore: Memória [SaídaALU] <= B

Conclusão da leitura damemória

Load: Reg[IR[20:16]] <= MDR

FIGURA 5.30 Resumo das etapas realizadas para executar qualquer classe de instrução. As instruções levam de três a cinco etapas de execu-ção. As duas primeiras etapas são independentes da classe de instrução. Após essas etapas, uma instrução leva ainda de um a três ciclos para ser concluí-da, dependendo da classe de instrução. As entradas vazias da etapa de acesso à memória ou a etapa de conclusão da leitura da memória indicam que aclasse de instrução específica leva menos ciclos. Em uma implementação multiciclo, uma nova instrução será iniciada tão logo a instrução atual seja con-cluída; portanto, esses ciclos não são ociosos ou desperdiçados. Na verdade, como mencionado anteriormente, o banco de registradores lê todos os ci-clos, mas, como o IR não muda, os valores lidos do banco de registradores são idênticos. Em especial, o valor lido para o registrador B durante a etapa dedecodificação da instrução, para uma instrução de desvio ou tipo R, é o mesmo valor armazenado em B durante a etapa de execução e, depois, usado naetapa de acesso à memória para uma instrução store word.

136

Perguntas simples

• Quantos ciclos serão necessários para executar este código?

lw $t2, 0($t3)lw $t3, 4($t3)beq $t2, $t3, Label #considere notadd $t5, $t2, $t3sw $t5, 8($t3)

Label: ...

• O que está ocorrendo durante o 8º ciclo da execução?

• Em que ciclo ocorre a adição real de $t2 e $t3?

137

138

Endereço

MemóriaDadosMem

Dadospara escrita

Instrução[31:26]

Instrução [25:0]

Instrução[25:21]

Instrução[20:16]


Instrução[15:0]

Instrução[15:0]

Registradorde dados

da memória

Instrução[15:11]

Instrução [5:0]




Dados paraescrita

Dadosda

leitura 1

Dadosda

leitura 2

Registradores

Extensãode sinal

A

B


esquerda


esquerda

ZeroALU

Resultadoda ALU

SaídaALU

PC 0Mux

1

0Mux

1

0Mux

1

0Mux

1

0123

0

1

2

4

26 28

16 32

Mux

Mux

Controleda ALU

EscrevePCCond

EscrevePC

IouD

LeMem

EscreveMem

MemparaReg

EscreveIR

Saídas

Controle

Op[5:0]

OrigPC

OpALU

OrigBALU

OrigAALU

EscreveReg

RegDst

PC [31:28]

Endereçodo jump[31:0]

Revisão: Máquinas de estado finito

• Máquinas de estado finito:

– um conjunto de estados e

– próxima função de estado (determinada pelo estado atual e pela entrada)

– função de saída (determinada pelo estado atual e possivelmente pela entrada)

– Usaremos uma máquina de Moore (saída com base apenas no estado atual)

139

Entradas

Estado atual

Clock

Função depróximo estado

Funçãode saída

Próximoestado

Saídas

Revisão: Máquinas de estado finito

• Exemplo:

B.37 Um amigo gostaria que você construísse um “olho eletrônico” para ser usadocomo um dispositivo de segurança falso. O dispositivo consiste em três luzesalinhadas, controladas pelas saídas Esquerda, Centro e Direita, que, se afirmadas,indicam que uma luz deve ser ligada. Apenas uma luz é acesa de cada vez, ea luz “move-se” da esquerda para a direita e, depois, da direita para a esquerda,afugentando, assim, os ladrões, que acreditam que o dispositivo está monitorandosuas ações. Desenhe uma representação gráfica para a máquina de estado finitousada para especificar o olho eletrônico. Note que a velocidade do movimento doolho será controlada pela velocidade do clock (que não deve ser muito alta) e quebasicamente não existem entradas.

140

Implementando o controle

• O valor dos sinais de controle depende de:

– que instrução está sendo executada

– que etapa está sendo realizada

• Use as informações que acumulamos para especificar uma máquina de estado finito

– especifique a máquina de estado finito graficamente ou

– use microprogramação

• A implementação pode ser derivada da especificação

141

Cálculo do endereçode memória

OrigAALU = 1OrigBALU = 10

OpALU = 00

Execução


OpALU = 10

Conclusãodo branch


OpALU = 01EscrevePCCond

OrigPC = 01

Conclusãodo jump

EscrevePCOrigPC = 10

(Op

= 'L

W')

(Op = 'SW

')Acesso àmemória

Acesso àmemória

LeMemIouD = 1

EscreveMemIouD = 1

Conclusão de tipo R

RegDst = 1EscreveReg

MemparaReg = 0

Etapa deconclusãoda leiturade memória

RegDst = 1EscreveReg

MemparaReg = 0

Início

Busca da instrução

LeMemOrigAALU = 0

IouD = 0EscreveIR

OrigBALU = 01OpALU = 00EscrevePC

OrigPC = 00


OpALU = 00

(Op = 'LW

') ou (O

p = 'SW')

(Op

= tip

o R)

(Op

= 'B

EQ

')

(Op

= 'J

')

0

2

3

4

5 7

6 8 9

1

Busca dos registradores/decodificação da instruçãoEspecificação gráfica da FSM

• Nota:

– não se preocupe se não for mencionada

– afirmada se apenas nome

– caso contrário, valor exato

• Quantos bits de estado serãonecessários?

142

Máquina de estado finito para controle

• Implementação:

143

EscrevePC

EscrevePCCond

IouD

MemparaReg

OrigPC

OpALU

OrigBALU

OrigAALU

EscreveReg

RegDst

NS3NS2NS1NS0

Op5

Op4

Op3

Op2

Op1

Op0

S3

S2

S1

S0

EscreveIR

LeMem

EscreveMem

Lógica de controle

Saídas

Entradas

Registrador de instruçãoCampo opcode

� Registrador de estado

Implementação PLA

• Se seu selecionasse uma linha horizontal ou vertical, você poderia explicá-la?

144

Implementação da ROM

• ROM = “Read Only Memory”

– os valores dos locais de memória são fixados antecipadamente

• Uma ROM pode ser usada para implementar uma tabela verdade

– se o endereço for m bits, podemos endereçar 2m entradas na ROM.

– nossas saídas são os bits de dados para os quais o endereço aponta.

m é a “altura” e n é a “largura”

145

nm

0 0 0 0 0 1 10 0 1 1 1 0 00 1 0 1 1 0 00 1 1 1 0 0 01 0 0 0 0 0 01 0 1 0 0 0 11 1 0 0 1 1 01 1 1 0 1 1 1

Implementação da ROM

• Quantas entradas existem?6 bits para opcode, 4 bits para estado = 10 linhas de endereço(por exemplo, 210 = 1024 endereços diferentes)

• Quantas saídas existem?16 saídas do controle do caminho de dados, 4 bits de estado = 20 saídas

• A ROM possui 210 x 20 = 20K bits (e um tamanho bastante incomum)

• Muito ineficiente, já que, para muitas das entradas, as saídas são iguais– por exemplo, opcode freqüentemente é ignorado

146

ROM versus PLA

• Divida a tabela em duas partes

– 4 bits de estado indicam as 16 saídas, 24 × 16 bits de ROM

– 10 bits informam os próximos 4 bits de estado, 210 × 4 bits of ROM

– Total: 4,3 Kbits de ROM

• A PLA é muito menor

– pode compartilhar termos de produto

– precisa apenas entradas que produzem uma saída ativa

– pode levar em conta don’t cares

• O tamanho é (no. de entradas × no. de termos-produto) + (no. de saídas × no. determos-produto)

Para este exemplo = (10x17)+(20x17) = 510 células de PLA

• As células de PLA normalmente possuem o tamanho aproximado de uma célula deROM (ligeiramente maior)

147

Outro estilo de implementação

• Instruções complexas: o “próximo estado” normalmente é o estado atual + 1

148

Unidade decontrole

PLA ou ROM

Saídas

EscrevePCEscrevePCCond

IouD

LeMem

EscreveMem

EscreveIR

Entrada

1

Somador

Estado

Lógica se seleçãode endereço

Op[

5–0]

Campo opcodedo registrador Instruction

�

MemparaReg

OrigPC

OpALU

OrigBALU

OrigAALU

EscreveReg

RegDst

CtlEnd

EscreveB

PLA ou ROM

1

Somador

Estado

Mux

3 2 1 0

CtlEnd

0

ROM de despacho 2 ROM de despacho 1

Lógica de seleçãode endereço

Op

Campo opcode doregistrador Instruction

Detalhes

149

ROM de despacho 1Op Nome do opcode Valor

000000 formato R 0110000010 jmp 1001000100 beq 1000100011 lw 0010101011 sw 0010

ROM de despacho 2Op Nome do opcode Valor

100011 lw 0011101011 sw 0101

Númerodo estado

Ação do controle de endereço Valor deCtlEnd

0 Usa o estado incrementado 31 Usa a ROM de despacho 1 12 Usa a ROM de despacho 2 23 Usa o estado incrementado 34 Substitui o número do estado por 0 05 Substitui o número do estado por 0 06 Usa o estado incrementado 37 Substitui o número do estado por 0 08 Substitui o número do estado por 0 09 Substitui o número do estado por 0 0

Microprogramação

• Quais são as microinstruções?

150

Unidade decontrole

Memória de microcódigo

Saídas

EscrevePCEscrevePCCondIouDLeMemEscreveMemEscreveIREscreveBMemparaRegOrigPCOpALUOrigBALUOrigAALUEscreveRegRegDstCtlEnd

Caminhode dados

Entrada

1

Somador

Contador de microprograma

Lógica de seleção de endereço

Op[

5–0]

Campo opcode doregistrador Instruction

Microprogramação

• Uma metodologia de especificação

– apropriada se houver centenas de opcodes, modos, ciclos etc.

– sinais especificados simbolicamente usando microinstruções

Rótulo Controle daALU

SRC1 SRC2 Controle doregistrador

Memória ControleEscrevePC

Seqüenciação

Fetch Add PC 4 Lê PC ALU SeqAdd PC Extshft Lê Dispatch 1

Mem 1 Add A Extend Dispstch 2LW2 Lê ALU Seq

Escreve MDR FetchSW2 Escreve

ALUFetch

Rformat1 Código Func A B SeqEscreve ALU Fetch

BEQ1 Subt A B ALUOut-cond

Fetch

JUMP1 Endereço dejump

Fetch

• Duas implementações da mesma arquitetura possuem o mesmo microcódigo?

• O que um microassembler faria?

151

Formato da microinstrução

Nome do campo Valor Sinais ativos ComentárioControle da ALU Add OpALU = 00 Faz com que a ALU realize uma soma.

Subt OpALU = 01 Faz com que a ALU realize uma subtração; isso implementa a comparação para desvios.Func code OpALU = 10 Usa o código de função da instrução para determinar o controle da ALU.

SRC1 PC OrigAALU = 0 Usa o PC como a primeira entrada da ALU.A OrigAALU = 1 O registrador A é a primeira entrada da ALU.

SRC2 B OrigBALU = 00 O registrador B é a segunda entrada da ALU.4 OrigBALU = 01 Usa 4 como a segunda entrada da ALU.Extend OrigBALU = 10 Usa a saída da unidade de extensão de sinal como a segunda entrada da ALU.Extshft OrigBALU = 11 Usa a saída da unidade de deslocamento em dois bits como a segunda entrada da ALU.

Controle dosRegistradores

Read Lê dois registradores usando os campos rs e rt do IR como os números de registrador e colocandoos dados nos registradores A e B.

Write ALU EscreveReg,RegDst = 1,MemparaReg = 0

Escreve num registrador usando o campo rd do IR como o número de registrador e o conteúdo deSaídaALU como os dados.

Write MDR EscreveReg,RegDst = 0,MemparaReg = 1

Escreve num registrador usando o campo rt do IR como o número de registrador e o conteúdo deMDR como os dados.

Memória Read PC LeMem,IouD = 0,

Lê a memória usando o PC como o endereço; escreve o resultado no IR (e no MDR).

Read ALU LeMem,IouD = 1

Lê a memória usando SaídaALU como o endereço; escreve o resultado no MDR.

Write ALU EscreveMem,IouD = 1

Escreve na memória usando SaídaALU como o endereço e o conteúdo de B como os dados.

Controle deescrita no PC

ALU OrigPC = 00,EscrevePC

Escreve a saída da ALU no PC.

ALUOut-cond OrigPC = 01,EscrevePCCond

Se a saída Zero da ALU estiver ativa, escreve o PC com o conteúdo do registrador SaídaALU.

jump address OrigPC = 10,EscrevePC

Escreve o PC com o endereço de jump da instrução.

Seqüenciamento Seq CtlEnd = 11 Escolhe a próxima microinstrução seqüencialmente.Fetch CtlEnd = 00 Vai para a primeira microinstrução para iniciar uma nova instrução.Dispatch 1 CtlEnd = 01 Despacha usando a ROM 1.Dispatch 2 CtlEnd = 10 Despacha usando a ROM 2.

152

Maximamente versus minimamente codificado

• Nenhuma codificação:

– 1 bit para cada operação de caminho de dados

– mais rápido, exige mais memória (lógica)

– usada para Vax 780 — incrível memória de 400K!

• Muita codificação:

– envia as microinstruções através da lógica para obter sinais de controle

– usa menos memória, mais lento

• Contexto histórico do CISC:

– Muita lógica para colocar em um único chip com tudo mais

– Use uma ROM (ou mesmo RAM) para armazenar o microcódigo

– É fácil acrescentar novas instruções

153

Microcódigo: negociações

• A distinção entre especificação e implementação às vezes é vaga

• Vantagens da especificação:

– Fácil de projetar e escrever

– Projeto da arquitetura e do microcódigo em paralelo

• Vantagens da implementação (ROM fora do chip)

– Fácil de mudar, já que os valores estão na memória

– Pode emular outras arquiteturas

– Pode fazer uso dos registradores internos

• Desvantagens da implementação, MAIS LENTA, agora que:

– O conteúdo é implementado no mesmo chip do processador

– Agora a ROM não é mais rápida do que a RAM

– Não há necessidade de voltar e fazer mudanças

154

Perspectiva histórica

• Nas décadas de 1960 e 1970, a microprogramação era muito importante paraimplementar máquinas

• Isso levou a ISAs mais sofisticadas e ao VAX

• Na década de 1980, os processadores RISC com base em pipelining se tornarampopulares

• Também é possível canalizar as microinstruções!

• As implementações dos processadores de arquitetura IA-32 desde o 486 usam:

– “controle hardwired” para implementações mais simples (menos ciclos, controleFSM implementado usando PLA ou lógica aleatória)

– “controle microcodificado” para instruções mais complexas (grande número deciclos, loja de controle central)

• A arquitetura IA-64 usa a ISA no estilo RISC e pode ser implementada sem umagrande loja de controle central

155

Pentium 4

• O pipelining é importante (o último IA-32 sem ela foi o 80386 em 1985)

• O pipelining é usado para as instruções simples beneficiadas pelos compiladores

“Explicado de forma simples, uma implementação de alto desempenho precisagarantir que as instruções simples sejam executadas rapidamente e que o pesodas complexidades do conjunto de instruções penalize as instruções complexas,usadas com menos freqüência.”

156

Controle

Controle

Controle

Controle

Interfacede E/S

Cache de instrução

Cachede dados

Ponto flutuantee multimídiaaperfeiçoados

Caminhode dadosde inteiro Cache

secundárioe interfacede memória

Suporte a hyperthreadingde pipelining avançado

Capítulo 7

Capítulo 6

Pentium 4

• Em algum lugar em todo esse controle, precisamos manipular instruçõescomplexas

• O processador executa microinstruções simples, de 70 bits de largura (hardwired)• 120 linhas de controle para o caminho de dados de inteiro (400 para ponto flutuante)• Se uma instrução exigir mais de 4 microinstruções para ser implementada, controle

da ROM de microcódigo (8000 microinstruções)• Isso é complicado!

157

Controle

Controle

Controle

Controle

Interfacede E/S

Cache de instrução

Cachede dados

Ponto flutuantee multimídiaaperfeiçoados

Caminhode dadosde inteiro Cache

secundárioe interfacede memória

Suporte a hyperthreadingde pipelining avançado


• Se entendermos as instruções...Podemos construir um processador simples!

• Se as instruções duram diferentes períodos de tempo, o multiciclo é melhor

• O caminho de dados é implementado usando:

– Lógica combinacional para aritmética

– Elementos de preservação de estado para se lembrar dos bits

• Controle implementado usando:

– Lógica combinacional para implementação de ciclo único

– Máquina de estado finito para implementação de multicilo

158

Capítulo 6

159

Pipelining

• Melhore o desempenho aumentando a vazão da instrução

A aceleração ideal é o número de estágios no pipeline. Conseguimos isso?

160

Pipelining

• O que o facilita

– todas as instruções possuem o mesmo tamanho

– apenas alguns formatos de instrução

– operandos de memória aparecem apenas em loads e stores

• O que o dificulta?

– riscos estruturais: suponha que tivéssemos apenas uma memória

– riscos de controle: necessidade de se preocupar com instruções ramificadas

– riscos de dados: uma instrução depende de uma instrução anterior

• Construiremos um pipeline simples e veremos esses problemas

• Falaremos sobre os processadores modernos e o que realmente o torna difícil

– tratamento de exceções

– tentar melhorar o desempenho com execução fora de ordem etc.

161

Conceito básico

• O que precisamos acrescentar para realmente dividir os caminhos dedados em estágios?

162

WB: Escrita adiadaMEM: Acesso àmemória

IF: Busca de instruções ID: Decodificação deinstruções/leitura do

banco de registradores

EX: Execução/cálculode endereço

1Mux

0

Endereço

Dadospara escrita

Dadosda leitura

Memóriade dados




Dadospara escrita

Registradores

Dados daleitura 1

Dados daleitura 2

ALU

Zero

Resul-tado da ALU

ADDResultado

doSomadorDes-

loc. 2esq.

Endereço

Instrução

Extensãode sinal

0Mux

1

16 32

4

Add

0Mux

1


PC

Caminho de dados em pipeline

Você consegue encontrar um problema mesmo se não houver dependências?Que instruções podemos executar para manifestar o problema?

163

Add

Endereço



Inst

ruçã

o


Registradorpara escritaDados paraescrita

Dadosda leitura 1

Dadosda leitura 2

RegistradoresEndereço

Dadospara escrita

Dadosda leitura

Memóriade dados

AddResul-

tado doSomador

ALU

Desloc.2 esq.

Extensãode sinal

PC

4

ID/EXIF/ID EX/MEM MEM/WB

16 32

0Mux

1

0Mux

1

0Mux

1

Resul-tado da

ALU

Caminho de dados corrigido

164

Add

Endereço Registradorde leitura 1



Dadosda leitura

Dados daleitura 1

Dados daleitura 2

Registradores Endereço

Dadospara escrita

Dadospara escrita

Memóriade dados

AddResultado

doSomador

ALUZero

Desloc.2 esq.

PC

4


16 32

0Mux

1

Inst

ruçã

o


Extensãode sinal

Resul-tado da ALU0

Mux

1

0Mux

1

Representando pipelines graficamente

• Pode ajudar a responder questões como estas:

– quantos ciclos leva para executar esse código?

– qual é a ALU sendo executada durante o ciclo 4?

– use essa representação para ajudar a entender os caminhos de dados

165

Ordem deexecução doprograma(em instruções)

lw $1, 100($0)

lw $2, 200($0)

lw $3, 300($0)

Tempo (em ciclos declock)

CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC7

IM DMReg RegALU

IM DMReg RegALU

IM DMReg RegALU

Controle do pipeline

166

Add




Dadosda leitura

Dados daleitura 1

Dados daleitura 2


Dadospara escrita

Dadosda leitura

Memóriade dados

AddResultado

doSomador

ALUZero

Desloc.2 esq.

PC

4


16 32

0Mux

1

Inst

ruçã

o


Extensãode sinal

Resul-tado da ALU0

Mux

1

1Mux

0

6

0Mux

1

OrigPC

EscreveReg

Instrução(15-0)

Instrução(20-16)

Instrução(15-11)

OrigALU

Controleda ALU

OpALU

RegDst

Branch

EscreveMem

LeMem

MemparaReg

Controle de pipeline

• Temos 5 estágios. O que precisa ser controlado em cada estágio?

– Busca da instrução e incremento do PC

– Decodificação da instrução / Busca do registrador

– Execução

– Estágio de memória

– Escrita adiada

• Como o controle seria manipulado em uma fábrica de automóveis?

– um espetacular centro de controle dizendo a todo mundo o que fazer?

– deveríamos usar uma máquina de estado finito?

167

Controle do pipeline

• Transfira os sinais de componente exatamente como os dados

Instrução

Linhas de controle do estágio decálculo de endereço/execução

Linhas de controle do estágiode acesso à memória

Linhas de controledo estágio de

escrita do resultado

RegDst OpALU1 OpALU0 OrigALU Branch LeMemEscreve

MemEscreve

RegMem para

Reg

Formato R 1 1 0 0 0 0 0 1 0

lw 0 0 0 1 0 1 0 1 1

sw X 0 0 1 0 0 1 0 X

beq X 0 1 0 1 0 0 0 X

168

Caminho de dados com controle

169

WB

M

EX

WB

M WB

Add




Dadosda leitura

Dados daleitura 1

Dados daleitura 2


Dadospara escrita

Dadosda leitura

Memóriade dados

AddResultado

doSomador

ALUZero

Desloc.2 esq.

PC

4

ID/EX

IF/ID

EX/MEM

MEM/WB

16 32

0Mux

1

Inst

ruçã

o


Extensãode sinal

Resul-tado da ALU0

Mux

1

0Mux

1

6

0Mux

1

OrigPC

Escr

eveR

eg

Instrução(15-0)

Instrução(20-16)

Instrução(15-11)

OrigALU

ControleALU

OpALU

RegDst

Branch

Escr

eveM

em

LeMem

Mem

para

Reg

Controle

Dependências

• Problemas com o início da próxima instrução antes do término da primeira

– dependências que “voltam no tempo” são hazards de dados

170

Ordem deexecuçãodo programa(em instruções)

sub $2, $1, $3

and $12, $2, $5

or $13, $6, $2

add $14, $2, $2

sw $15, 100($2)

Tempo (em ciclos de clock)CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9

IM DMReg Reg

IM DMReg Reg

IM DMReg Reg

IM DMReg Reg

IM DMReg Reg

10 10 10 10 10/–20 –20 –20 –20 –20Valor doregistrador $2:

Solução de software

• Faça o compilador garantir a inexistência de hazards

• Onde inserimos os “nops”?

sub $2, $1, $3and $12, $2, $5or $13, $6, $2add $14, $2, $2sw $15, 100($2)

• Problema: isso realmente nos torna lentos!

171

Forwarding

• Use resultados temporários, não espere que eles sejam escritos– forwarding do arquivo de registrador para manipular read/write para o mesmo

registrador– forwarding da ALU

172


10 10 10 10 10/–20 –20 –20 –20 –20Valor do registrador $2:Valor de EX/MEM: X X X –20 X X X X X

Valor de MEM/WB: X X X X –20 X X X X


sub $2 $1, $3

and $12, $2 $5

or $13, $6, $2

add $14, $2 $2

sw $15, 100($2)

IM DMReg Reg

IM DMReg Reg

IM DMReg Reg

IM DMReg Reg

IM DMReg Reg

E se este $2 fosse $13?

Forwarding

• A idéia principal (alguns detalhes não mostrados)

173

ALU

Memóriade dados

Registradores

Mux

Mux

ID/EX EX/MEM MEM/WB

Unidade deforwarding

EX/MEM.RegistradorRd

MEM/WB.RegistradorRd

RsRt

Rt

Rd

ForwardB

ForwardA

Mux

Mux

Forwarding nem sempre é possível

• Load word ainda pode causar um hazard:– uma instrução tenta ler um registrador seguindo uma instrução load que escreve

no mesmo registrador.

Portanto, precisamos de uma unidade de detecção de hazard para “deter” (stall) ainstrução load

174


lw $2, 20($1)

and $4, $2, $5

or $8, $2, $6

add $9, $4, $2

slt $1, $6, $7


IM DMReg Reg

IM DMReg Reg

IM DMReg Reg

IM DMReg Reg

IM DMReg Reg

Stalls

• Podemos ocasionar um stall no pipeline mantendo uma instrução no mesmoestágio

175

bolha


lw $2, 20($1)

and torna-se nop

add $4, $2, $5

or $8, $2, $6

add $9, $4, $2

IM DMReg Reg

IM DMReg Reg

IM DMReg Reg

IM DMReg Reg

IM DMReg Reg

Tempo (em ciclos de clock)CC 1 CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9 CC 10

Unidade de detecção de hazard

• Ocasione um stall deixando que uma instrução que não escreverá nada prossiga

176

0 M

WB

WB

Memóriade dados


Mux

Mux

Mux

Mux

ALU

ID/EX

EX/MEM

MEM/WB


PC

Controle

EX

M

WB

IF/ID

Mux

Unidade dedetecção

de hazards

ID/EX.MemRead

Inst

ruçã

o

Esc

reve

PC

Esc

reve

IF/ID

Registradores

Rt

Rd

RsRt

IF/ID.RegistradorRs

IF/ID.RegistradorRt

IF/ID.RegistradorRt

IF/ID.RegistradorRd

ID/EX.RegistradorRt

Hazards de desvio

• Quando decidimos desviar, outras instruções estão no pipeline!

• Estamos prevendo “desvio não tomado”– precisamos acrescentar hardware para descartar instruções seestivermos errados

177

Reg


40 beq $1, $3, 28

44 and $12, $2, $5

48 or $13, $6, $2

52 add $14, $2, $2

72 lw $4, 50($7)


IM DMReg Reg

IM DMReg Reg

IM DM Reg

IM DMReg Reg

IM DMReg Reg

Descartando instruções

Nota: também movemos a decisão de desvio para o estágio ID

178

Controle

+

4

PC

Registradores=

+

ALU

ID/EX

EX/MEM

EX/MEM

WB

M

EX

Desloc.2 esq.

IF.Flush

IF/ID

Mux

Mux

Mux

Mux

Mux

Mux

WB

WBM

0


Unidade dedetecção

de hazards

Exten-são desinal


Memóriade dados

Desvios

• Se o desvio for tomado, temos uma penalidade de um ciclo

• Para nosso projeto simples, isso é razoável

• Com pipelines mais profundos, a penalidade aumenta e a previsão de desvioestático diminui drasticamente o desempenho

• Solução: previsão de desvio dinâmico

Um esquema de previsão de dois bits

179

Previsão tomada Previsão tomada

Previsão não tomada Previsão não tomada

Não tomado

Não tomado

Não tomada

Não tomado

Tomado

Tomado

Tomado

Tomado

Previsão de desvio

• Técnicas sofisticadas:

– Um “buffer de destino de desvio” nos ajuda a consultar o destino.

– Correlacionar previsores que baseiem a previsão no comportamento global e nosdesvios recentemente executados (por exemplo, previsão para uma instrução dedesvio específica com base no que ocorreu nos desvios anteriores).

– Previsores de competição que usam diferentes tipos de estratégias de previsão econtrolam qual delas está sendo melhor executada.

– Um “espaço de retardo de desvio” que o compilador tenta preencher com umainstrução útil (forma a parte do retardo de um ciclo da ISA).

• Previsão de desvio é especialmente importante porque permite que outras técnicasde pipelining mais avançadas sejam eficazes!

• Os processadores modernos prevêem corretamente 95% das vezes!

180

Melhorando o desempenho

• Tente evitar stalls! Por exemplo, reordene estas instruções:

lw $t0, 0($t1)lw $t2, 4($t1)sw $t2, 0($t1)sw $t0, 4($t1)

• Programação de pipeline dinâmica

– O hardware escolhe que instruções executar em seguida

– Executará instruções fora de ordem (por exemplo, não espera que umadependência seja resolvida, e sim continua executando!)

– Especula sobre desvios e mantém o pipeline cheio (pode precisar reverter se aprevisão for incorreta)

• Tentando explorar o paralelismo em nível de instrução

181

Pipelining avançado

• Aumenta a profundidade do pipeline

• Inicia mais de uma instrução em cada ciclo (despacho múltiplo)

• Desdobramento de loop para expor mais ILP (melhor programação)

• Processadores “superescalares”

– DEC Alpha 21264: pipeline de 9 estágios, despacho de 6 instruções

• Todos os processadores modernos são superescalares e despacham instruçõesmúltiplas normalmente com algumas limitações (por exemplo, diferentes “pipes”)

• VLIW: Very Long Instruction Word (palavra de instrução muito longa) – despachomúltiplo estático (se baseia mais na tecnologia do compilador)

• Essa aula forneceu o conhecimento de que você precisa para aprender mais!

182


• O pipelining não melhora a latência, mas melhora a vazão

183

Vel

ocid

ade

de c

lock

Men

orM

aior

Menos Mais

Instruções por clock (IPC = 1/CPI)

Multiciclo(Seção 5.5)

Ciclo único(Seção 5.4)

Pipelineprofundo

Pipeline

Despacho múltiplocom pipeline

profundo (Seção 6.10)

Despacho múltiplocom pipeline(Seção 6.9)

Har

dwar

e

Com

part

ilhad

oE

spec

ializ

ado

1 Várias

Latência no uso das instruções

Multiciclo(Seção 5.5)

Ciclo único(Seção 5.4)

Pipelineprofundo

Pipeline

Despacho múltiplocom pipeline profundo

(Seção 6.10)

Despacho múltiplocom pipeline(Seção 6.9)

Capítulo 7

184

Memórias: Revisão

• SRAM:

– o valor é armazenado em um par de portões invertidos

– muito rápida, mas ocupa mais espaço do que a DRAM (4 a 6 transistores)

• DRAM:

– o valor é armazenado como uma carga no capacitor (precisa ser atualizada)

– muito pequena, porém, mais lenta do que a SRAM (fator de 5 a 10)

185

AB

AB

Linha de word

Transistor de passagem

Capacitor

Linha de bit

Explorando a hierarquia da memória

• Os usuários querem memórias grandes e rápidas!Os tempos de acesso da SRAM são 0,5 a 5 ns ao custo de US$ 4000 a

US$ 10000 por GB.Os tempos de acesso são 50 a 70 ns ao custo de US$ 100 a US$ 200 2004

por GB.Os tempos de acesso a disco são 5 a 20 milhões de ns ao custo de

US$ 0,50 a US$ 2 por GB.

• Tente oferecer isso a eles

– Construa uma hierarquia de memória

186

…

Níveis na hierarquiade memória

CPU

Nível 1

Nível 2

Nível n

Tamanho da memória em cada nível

Aumentando a distânciada CPU no tempo

de acesso

Localidade

• Um princípio que faz da hierarquia de memória uma boa idéia

• Se um item for referenciado,

localidade temporal: tenderá a ser referenciada novamente em breve

localidade espacial: itens próximos tenderão a ser referenciados em breve

Por que o código possui localidade?

• Nosso foco inicial: dois níveis (superior, inferior)

– bloco: unidade mínima de dados

– acerto: os dados solicitados estão no nível superior

– falha: os dados solicitados não estão no nível superior

187

Cache

• Dois problemas:

– Como sabemos se um item de dados está no cache?

– Se estiver, como encontrá-lo?

• Nosso primeiro exemplo:

– O tamanho do bloco é uma word de dados

– “diretamente mapeado”

Para cada item de dados no nível inferior, existe exatamenteum local no caminho onde ele pode estar.Por exemplo, muitos itens no nível inferior compartilham locaisno nível superior

188

Cache diretamente mapeado

• Mapeamento: O endereço é o módulo do número de blocos no cache

189

Cache

Memória

00001 10001

010

100

101

111

110

000

001

011

00101 01001 01101 10101 11001 11101


• Para MIPS:

De que tipo de localidade estamos nos valendo?

190

Endereço (mostrando as posições dos bits)

Dados

Acerto

Dados

Tag

Validadealid Tag

3220

Índicex012

102310221021

=

Índicex

20 10

Offsetdo byte

31 30 13 12 11 2 1 0


• Tirando vantagem da localidade espacial:

191

V

32

16

=

18 8

31 14 13 2 1 06 5

4

256Entradas

Mux

3232 32

Endereço (mostrando as posições dos bits)

Acerto TagOffset

do byteDados

Índice Offset do bloco

18 bits 512 bits

Tag Dados

Acertos versus falhas

• Acertos de leitura

– é isso o que queremos!

• Falhas de leitura

– ocasione um stall na CPU, busque o bloco da memória, distribua para o cache,reinicie

• Acertos de escrita:

– podem substituir os dados no cache e na memória (escrita direta)

– escrevem os dados apenas no cache (escrita adiada no cache posteriormente)

• Falhas de escrita:

– lêem o bloco inteiro para o cache, depois escrevem a word

192

Problemas de hardware

• Facilite a leitura de múltiplas words usando bancos de memória

• Isso pode ficar muito mais complicado...

193

CPU

Cache

CPU

Cache

CPU

Cache

Barramento

Memória

a. Organização de memóriacom uma word de largura

Multiplexador

Barramento

Memória

b. Organização de memória larga

Barramento

Banco dememória 0

Banco dememória 1

Banco dememória 2

Banco dememória 3

c. Organização de memória intercalada

Desempenho

• Aumentar os tamanhos de bloco tende a reduzir a taxa de falhas:

• Use caches divididos porque existe mais localidade espacial no código:

Programa Tamanho de blocoem words

Taxa de falhasde instrução

Taxa de falhade dados

Taxa de falhascombinadas efetiva

gcc 1 6,1% 2,1% 5,4%

4 2,0% 1,7% 1,9%

spice 1 1,2 1,3 1,2%

4 0,3 0,6 0,4%

194

1 KB

8 KB

16 KB

64 KB

256 KB

256

40%

35%

30%

25%

20%

15%

10%

5%

0%

Taxa

de

falh

as

64164

Tamanho de bloco (bytes)

Desempenho

• Modelo simplificado:

Tempo de execução = (ciclos de execução + ciclos de stall) × tempo de ciclo

Ciclos de stall = número de instruções × taxa de falhas × penalidade de falha

• Duas maneiras de melhorar o desempenho:

– reduzir a taxa de falhas

– reduzir a penalidade de falhas

O que acontece se aumentarmos o tamanho de bloco?

195

Reduzindo a taxa de falhas com associatividade

Comparado com o mapeamento direto, forneça uma série de referências que:

– resulte em uma taxa de falhas usando um cache associativo de duas vias

– resulte em uma taxa de falhas maior usando um cache associativo de duas viasconsiderando que usamos a estratégia de substituição “usada menos recentemente”

196

Tag Tag Dados DadosTagTag Dados Dados Tag Tag Dados DadosTagTag Dados Dados

Tag Tag Dados DadosTagTag Dados Dados

0

1

TagTag Dados Dados

0

1

2

3

Tag DadosBloco

0

1

2

3

4

5

6

7

Conjunto

Conjunto

Associativa por conjunto de quatro vias

Associativa por conjunto de duas vias

Associativa por conjunto de oito vias (totalmente associativa)

Associativa por conjunto de uma via(diretamente mapeada)

Uma implementação

197

Dados Dados Dados DadosV V V VTag Tag Tag Tag

=

22 8

31 30 12 11 10 9 8 3 2 1 0

012

253254255

= =

22

=

32

Índice

Multiplexador 4 para 1

Acerto Dados

Desempenho

198

Associatividade

Taxa

de

falh

as

0Uma via Duas vias

3%

6%

9%

12%

15%

Quatro vias Oito vias

1 KB

2 KB

4 KB

8 KB

16 KB32 KB

64 KB 128 KB

Reduzindo a penalidade de falhas com caches multinível

• Acrescente um segundo cache de nível:

– normalmente o cache primário está no mesmo chip do processador

– use SRAMs para acrescentar outro cache acima da memória principal (DRAM)

– a penalidade de falhas diminui se os dados estiverem no cache de segundo nível

• Exemplo:

– CPI de 1,0 em uma máquina de 5 GHz com uma taxa de falhas de 5%, acesso aDRAM de 100 ns

– Acrescentar cache de segundo nível com tempo de acesso de 5 ns diminui a taxade falhas para 0,5%

• Usando caches multinível:

– tente otimizar o tempo de acerto no cache de primeiro nível

– tente otimizar a taxa de falhas no cache de segundo nível

199

Complexidades de cache

– Nem sempre é fácil entender as implicações dos caches:

200

04 16 32

200

400

600

800

1000

1200

64 128 256 512 1024 2048 4096

Inst

ruçõ

es/it

em

Radix Sort

Quicksort

Tamanho (K itens a ordenar)

016 32

400

800

1200

1600

2000

64 128 256 512 1024 2048 4096

Cic

los

de c

lock

/item

Radix Sort

Quicksort


Comportamento observado de Radix Sortversus Quicksort

Comportamento teórico de Radix Sortversus Quicksort

8 4 8

Complexidades de cache

• Veja o porquê:

• O desempenho do sistema de memória normalmente é um fator crítico

– caches multinível, processadores em pipeline, dificultam a previsãode resultados

– otimizações de compilador para aumentar a localidade algumas vezesprejudicam o ILP

• Difícil prever o melhor algoritmo: é preciso dados experimentais

201

04 16 32

1

2

3

4

5

64 128 256 512 1024 2048 4096

Falh

as d

e ca

che/

item

Radix Sort

Quicksort


8

Memória virtual

• A memória principal pode atuar como um cache para o armazenamento secundário(disco)

• Vantagens:

– ilusão de ter mais memória física

– remanejamento do programa

– proteção

202

Endereços virtuaisTradução de endereço

Endereços físicos

Endereços do disco

Páginas: blocos de memória virtual

• Falhas de página: Os dados não estão na memória; recupere-os do disco

– enorme penalidade de falha; portanto, as páginas devem ser bastante grandes(por exemplo, 4KB)

– é importante reduzir as falhas de página (LRU vale a pena)

– pode manipular as falhas no software em vez de no hardware

– como a escrita direta é muito onerosa, usamos escrita adiada

203

31 30 29 28 27 3 2 1 015 14 13 12 11 10 9 8

29 28 27 3 2 1 010 9 815 14 13 12 11

Endereço virtual

Número de página virtual Offset de página

Tradução

Número de página física Offset de página

Endereço físico

Tabelas de página

204

1111011

11

1

0

0

Número de páginavirtual

Tabela de páginas

Página física ouendereço de discoValidade

Memória física

Armazenamento em disco

Tabelas de página

205

31 30 29 28 27 3 2 1 015 14 13 12 11 10 9 8

29 28 27 3 2 1 015 14 13 12 11 10 9 8

20 12

18

Registrador de tabela de páginas

Endereço virtual


Validade Número de página física

Tabela de páginas

Se for 0, então a páginanão está presente na memória

Número de página física Offset de página

Endereço físico

Tornando a tradução de endereço rápida

• Um cache para traduções de endereço: translation-lookaside buffer (TLB)

Valores típicos: 16-512 entradas,taxa de falhas: 0,01% – 1%penalidade de falhas: 10-100 ciclos

206

011

11

0

0

000

11

0

0

011

11

0

0

1111

1

1000

1

1001

1

111101

011000

111101

TLB

TagNúmero de

página virtual Validade

Validade

Modificaçã

o

Modificaçã

o

Referência

Referência

Endereço depágina física

Memória física

Tabela de páginas

Endereços de páginafísica ou de disco

Armazenamento em disco

TLBs e caches

207

Endereço virtual

Acesso à TLB

Exceção defalha de TLB

Não Acerto deTLB?

Sim

Endereço físico

NãoEscrita?

Sim

Tente ler os dadosda cache

Não Bit de acessode escrita

ligado?

Sim

Stall de falha decache duranteleitura do bloco

NãoAcerto de cache?

Sim

Exceção de proteçãode escrita Tente escrever os

dados na cache

Envie os dadospara a CPU

Stall de falha decache duranteleitura do bloco

NãoAcerto de cache?

Sim

Escreva os dados na cache,atualize o bit de modificação

e coloque os dados e oendereço no buffer de escrita

TLBs e caches

208

=

=

20

31 30 29 3 2 1 014 13 12 11 10 9

=====

12

20

18

32

8 4 2

12

8

Endereço virtual


Validade

Modificaçã

o

Tag Número de página física

Número de página física Offset de páginaEndereço físico

Tag de endereço físico Índice de cacheOffset

de blocoOffset

de byte

Validade TagDados

Cache

Acertode cache

Dados

TLB

TLB hit

Sistemas modernos

Característica Intel Pentium P4 AMD Opteron

Endereço virtual 32 bits 48 bitsEndereço físico 36 bits 40 bitsTamanho de página 4KB, 2/4MB 4KB, 2/4MBOrganização de TLB 1 TLB para instruções e 1 TLB para dados

Ambas são associativas por conjunto dequatro viasAmbas usam substituição pseudo-LRUAmbas têm 128 entradasFalhas de TLB tratadas por hardware

2 TLBs para instruções e 2 TLBs para dadosAmbas as TLBs L1 são totalmente associativas, substituição LRUAmbas as TLBs L2 são associativas por conjunto de quatro vias, LRU com round-robinAmbas as TLBs L1 têm 40 entradasAmbas as TLBs L2 têm 512 entradasFalhas de TLB tratadas por hardware

FIGURA 7.34 Tradução de endereços e hardware TLB para o Intel Pentium P4 e o AMD Opteron. O tamanho de word define o tamanho máximo do endereço virtual, mas um processador nãoprecisa usar todos esses bits. O tamanho de endereço físico é independente do tamanho de word. O P4 tem uma TLB para instruções e uma TLB idêntica separada para dados, enquanto o Opteronpossui uma TLB L1 e uma TLB L2 para instruções e TLBs L1 e L2 idênticas para dados. Os dois processadores fornecem suporte para páginas grandes, que são usadas para coisas como o sistemaoperacional ou para mapear um buffer de quadro. O esquema de página grande evita o uso de um grande número de entradas para mapear um único objeto que está sempre presente.

Característica Intel Pentium P4 AMD Opteron

Organização de cache L1 Caches de instruções e de dados divididos Caches de instruções e de dados divididosTamanho de cache L1 8KB para dados, cache de trace de 96KB para

instruções RISC (operações RISC de 12K)64KB cada para instruções/dados

Associatividade de cache L1 Associativa por conjunto de 4 vias Associativa por conjunto de 2 viasSubstituição L1 Substituição LRU aproximada Substituição LRUTamanho de bloco L1 64 bytes 64 bytesPolítica de escrita L1 Escrita direta Escrita adiadaOrganização de cache L2 Unificada (instruções e dados) Unificada (instruções e dados)Tamanho de cache L2 512KB 1024KB (1MB)Associatividade de cache L2 Associativa por conjunto de 8 vias Associativa por conjunto de 16 viasSubstituição L2 Substituição LRU aproximada Substituição LRU aproximadaTamanho de bloco L2 128 bytes 64 bytesPolítica de escrita L2 Escrita direta Escrita adiada

FIGURA 7.35 Caches de primeiro nível e segundo nível do Intel Pentium P4 e do AMD Opteron. As caches primárias do P4 são fisicamente indexadas e rotuladas; para umadescrição das alternativas, veja o Detalhe na página 527.

209

Sistemas modernos

• As coisas estão ficando complicadas!

MPU AMD Opteron Intrinsity FastMATH Intel Pentium 4 Intel PXA250 Sun UltraSPARC IV

Conjunto de instruções IA-32, AMD64 MIPS32 IA-32 ARM SPARC v9Aplicação pretendida Servidor Embutido Desktop Embutido de baixo

consumoServidor

Tamanho do die (mm2)(2004)

193 122 217 356

Instruções despachadaspor clock

3 2 3 operações RISC 1 4 × 2

Velocidade de clock (2004) 2,0GHz 2,0GHz 3,2GHz 0,4GHz 1,2GHzCache de instruções 64KB, associativa por

conjunto de 2 vias16KB, diretamentemapeada

cache de trace com 12000operações RISC (~96 KB)

32KB, associativa porconjunto de 32 vias


Latência (clocks) 3 4 4 1 2Cache de dados 64KB, associativa por

conjunto de 2 vias16KB, associativa porconjunto de 1 via




Latência (clocks) 3 3 2 1 2Entradas de TLB (TLBI/D/L2)

40/40/512/512 16 128/128 32/32 128/512

Tamanho de páginamínimo

4KB 4KB 4KB 1KB 8KB

Cache L2 on-chip 1024KB,associativa porconjunto de 16 vias

1024KB,associativa porconjunto de 4 vias

512KB,associativa por conjuntode 8 vias

— —

Cache L2 off-chip — — — — 16MB, associativa porconjunto de 2 vias

Tamanho de bloco (L1/L2,bytes)

64 64 64/128 32 32

FIGURA 7.36 Microprocessadores para desktops, embutidos e para servidores em 2004. De uma perspectiva da hierarquia de memória, aprincipal diferença entre as categorias é a cache L2. Não há uma cache L2 para o embutido de baixo consumo, uma grande L2 on-chip para oembutido e para o desktop e uma off-chip de 16 MB para o servidor. As velocidades de clock de processador também variam: 0,4 GHz para embutidode baixo consumo, 1 GHz ou mais alta para o restante. Observe que o UltraSPARC IV possui dois processadores no chip.

210

Alguns problemas

• As velocidades do processador continuam a aumentar muito rápido

– muito mais rápido do que os tempos de acesso à DRAM ou ao disco

• Desafio de projeto: lidar com essa crescente disparidade

– Prefetching? Caches de terceiro nível e mais? Projeto de memória?

211

1

1980

1981

10

100

1.000

10.000

100.000

1982

1983

1984

1985

1986

1987

1988

1989

1990

1991

1992

1993

1994

1995

1996

1997

1998

1999

2000

2001

2002

2003

2004

2005

CPUDesempenho

Memória

Ano

Capítulos 8 e 9(abordagem parcial)

212

Interface entre processadores e periféricos

• O projeto de E/S é afetado por muitos fatores (expansibilidade, resiliência)• Desempenho:

– latência de acesso– vazão– conexão entre os dispositivos e o sistema– a hierarquia de memória– o sistema operacional

• Uma variedade de usuários diferentes (por exemplo, bancos, supercomputadores,engenheiros)

213Disco Disco

Processador

Cache

Barramento de E/S de memória

Memóriaprincipal

Controladorde E/S

Controladorde E/S

Controladorde E/S

Saídagráfica

Rede

Interrupções

E/S

• Importante, mas negligenciada

“As dificuldades em avaliar e projetar sistemas de E/S freqüentemente têmrelegado a E/S à condição de segunda classe”

“os cursos em todos os aspectos da computação, da programação à arquiteturade computador, normalmente ignoram a E/S ou a abordam superficialmente”

“os livros-texto deixam o assunto para o final, o que pode fazer com que alunos einstrutores o pulem”

• CULPADOS!

– não veremos a E/S em muito detalhe aqui.

– não deixe de ler o Capítulo 8 inteiro.

– você provavelmente assistirá a uma aula de rede!

214

Dispositivos de E/S

• Dispositivos muito diversos– comportamento (por exemplo, entrada versus saída)– parceiro (quem está no outro lado?)– velocidade de dados

215

Disco Disco

Processador

Cache

Barramento de E/S de memória

Memóriaprincipal

Controladorde E/S

Controladorde E/S

Controladorde E/S

Saídagráfica

Rede

Interrupções

FIGURA 8.2 Uma coleção típica de dispositivos de E/S. As conexões entre os dispositivos deE/S, processador e memória normalmente são chamadas de barramentos. A comunicação entreos dispositivos e o processador utiliza interrupções e protocolos no barramento, conforme veremosneste capítulo. A Figura 8.11, na página 585, mostra a organização para um PC desktop.

Exemplo de E/S: Unidades de disco

• Para acessar dados:

– busca: posiciona a cabeça sobre a trilha correta (3 a 14 ms em média)

– latência rotacional: espera pelo setor desejado (0,5 rpm)

– transferência: recupera os dados (um ou mais setores; 30 a 80 MB/seg)

216

Setores

Pratos

Prato

Trilhas

Trilha

Exemplo de E/S: Barramentos

• Link de comunicação compartilhado (um ou mais fios)

• Projeto difícil:– pode ser gargalo– extensão do barramento– número de dispositivos– negociações (buffers para largura de banda maior aumenta a latência)– suporte para muitos dispositivos diferentes– custo

• Tipos de barramento:– processador-memória (curto, projeto personalizado e de alta velocidade)– backplane (alta velocidade, freqüentemente padronizado; por exemplo, PCI)– E/S (longo, diferentes dispositivos; por exemplo, USB, Firewire)

• Síncrono versus assíncrono– usam um clock e um protocolo síncronos, rápidos e pequenos, mas cada

dispositivo precisa operar na mesma velocidade e a variação de clock exige que obarramento seja curto

– não usam um clock, mas usam hanshaking

217

Padrões de barramento de E/S

• Hoje temos dois padrões de barramento dominantes:

Características Firewire (1394) USB 2.0

Tipo de barramento E/S E/SLargura básica do barramento de dados (sinais) 4 2Clock assíncrono assíncronoLargura de banda máxima teórica 50MB/seg (Firewire 400) ou 100MB/seg

(Firewire 800)0,2MB/seg (baixa velocidade), 1,5MB/seg (velocidadeplena) ou 60MB/seg (velocidade alta)

Facilidade de conexão sim simNúmero máximo de dispositivos 63 127Tamanho máximo do barramento (fio de cobre) 4,5 metros 5 metrosNome do padrão IEEE 1394, 1394b USB Implementors Forum

FIGURA 8.9 Principais características dos dois padrões de barramento de E/S dominantes.

218

Outros aspectos importantes

• Arbitração de barramento:

– arbitração de margarida (não muito justa)

– arbitração centralizada (exige um árbitro), por exemplo, PCI

– detecção de colisão, por exemplo, Ethernet

• Sistema operacional:

– polling

– interrupções

– acesso direto à memória (DMA)

• Técnicas de análise de desempenho:

– teoria do enfileiramento

– simulação

– análise; por exemplo, encontrar o link mais fraco (veja “Projeto de sistema deE/S”)

• Muitos desenvolvimentos recentes

219

ATA paralelo(100MB/seg)

ATA paralelo(100MB/seg)

(20 MB/seg)

Barramento PC(132MB/seg)

CSA(0,266GB/seg)

AGP 8X(2,1GB/seg)

ATA serial(150MB/seg)

Disco

ProcessadorPentium 4

Ethernet 1 Gbit

Hubcontroladorde memória

(bridge norte)82875P

DIMMs damemóriaprincipal

DDR 400(3,2GB/seg)

DDR 400(3,2GB/seg)

ATA serial(150MB/seg)

Disco

AC/97(1MB/seg)

Estéreo(som

surround) USB 2.0(60MB/seg)

. . .

Hubcontrolador

de E/S(bridge sul)82801EB

Saídagráfica

(266MB/seg)

Barramento do sistema (800MHz, 604GB/seg)

CD/DVD

Fita

Ethernet 10/100 Mbit

Pentium 4

• Opções de E/S

220

Chip set 875P Chip set 845GL

Segmento de destino PC dedesempenho

PC de menorcusto

Barramento do sistema (64 bits) 800/533MHz 400MHzHub controlador de memória (“bridge norte”)

Tamanho do pacote, pinos 42,5 x 42,5mm,1005

37,5 x 37,5mm,760

Velocidade da memória DDR 400/333/266 SDRAM

DDR 266/200,PC133 SDRAM

Barramentos de memória, larguras 2x72 1x64Número de DIMMs, suporte a Mbit daDRAM

4, 128/256/512Mbits

2, 128/256/512Mbits

Capacidade máxima da memória 4GB 2GBCorreção de erro da memória disponível? sim nãoBarramento gráfico AGP, velocidade sim, 8X ou 4X nãoControlador gráfico Externo Interno

(Extreme Graphics)Interface CSA Gigabit Ethernet sim nãoVelocidade de interface da bridge sul (8 bits) 266MHz 266MHz

Hub controlador de E/S (“bridge sul”)

Tamanho do pacote, pinos 31 x 31mm, 460 31 x 31mm, 421Barramento PCI: largura, velocidade,masters

32 bits, 33MHz,6 masters

32 bits, 33MHz,6 masters

Controlador MAC Ethernet, interface 100/10Mbits 100/10MbitsPortas USB 2.0, controladoras 8, 4 6, 3Portas ATA 100 2 2Controlador ATA serial 150, portas sim, 2 nãoControlador RAID 0 sim nãoControlador de áudio AC-97, interface sim simGerenciamento de E/S SMbus 2.0, GPIO SMbus 2.0, GPIO

FIGURA 8.12 Dois chip sets de E/S Pentium 4 da Intel. A bridge norte 845GL utiliza muito menospinos do que o 875, com apenas um barramento de memória e omitindo o barramento AGP e a inter-face Gigabit Ethernet. Observe que a natureza serial do USB e da ATA serial significa que mais duasportas USB e mais duas portas ATA serial precisam de apenas mais 39 pinos na bridge sul do chip set875 versus o chip set 845GL.

Falácias e armadilhas

• Falácia: O tempo médio para falha (MTTF) indicado para discos é 1.200.000 horas ouquase 140 anos, de modo que os discos praticamente nunca falham.

• Falácia: O armazenamento de disco magnético está com seus dias contados; serásubstituído.

• Falácia: Um barramento de 100 MB/seg pode transferir 100 MB por segundo.

• Armadilha: Mover funções da CPU para o processador de E/S, esperando melhoraro desempenho sem análise.

221

Multiprocessadores

• Idéia: criar computadores poderosos conectando muitos computadores menores

boa notícia: funciona para compartilhamento de tempo(melhor do que um supercomputador)

má notícia: é muito difícil escrever bons programas concorrentes,muitas falhas comerciais

222

Processador Processador Processador

Cache Cache Cache

Barramento único

Memória E/S

Processador Processador Processador

Cache Cache Cache

Memória Memória Memória

Rede

. . .

. . .

. . .

Perguntas

• Como os processadores paralelos compartilham dados?

– espaço de endereço único (SMP versus NUMA)

– transferência de mensagens

• Como os processadores paralelos são coordenados?

– sincronização (bloqueios, semáforos)

– primitivas send/receive embutidas

– protocolos de sistema operacional

• Como eles são implementados?

– conectados por um único barramento

– conectados por uma rede

223

Supercomputadores

Representação dos 500 maiores sites de supercomputador durante uma década:

224

SIMD (Single Instruction Multiple Data)

Cluster(rede de estaçõesde trabalho)

Cluster(rede deSMPs)

MPPs(MassivelyParallelProcessors)

SMPs(SharedMemoryMultiprocessors)

Uniprocessadores

500

93 93 94 94 95 95 96 96 97 97 98 98 99 99 00

400

300

200

100

0

Usar múltiplos processadores – uma idéia antiga

• Alguns projetos SIMD:

Instituição NomeNúmero máximo de

processadores Bits/proc.Velocidade de clock

do proc. (MHz) Número de FPUsTamanho/sistema de

memória máximo (MB)BW/sistema de

comunicações (MB/s) Ano

Universidade deIllinois

Illiac IV 64 64 13 64 1 2.560 1972

ICL DAP 4.096 1 5 0 2 2.560 1980Goodyear MPP 16.384 1 10 0 2 20.480 1982Thinking Machines CM-2 65.536 1 7 2048 (opcional) 512 16.384 1987Maspar MP-1216 16.384 4 25 0 256 ou 1024 23.000 1989

FIGURA 9.11.1 Características de cinco computadores SIMD. Número de FPUs significa o número de unidades de ponto flutuante.

• Os custos para o Illiac IV aumentaram de US$ 8 milhões em 1966 para US$ 32milhões em 1972 apesar da conclusão de apenas ¼ da máquina. Levou três outrosanos para que ele estivesse operacional!

“Por sorte ou por azar, os arquitetos de computadornão são facilmente desencorajados”

Muitos projetos e idéias interessantes, muitas falhas, poucos sucessos

225

Topologias

226

Clusters

• Construídos a partir de computadores inteiros

• Redes independentes e escaláveis

• Vantagens:

– Muitas aplicações receptivas a máquinas frouxamente agrupadas

– Exploram redes locais

– Econômicos / fáceis de expandir

• Desvantagens:

– Custos de administração não necessariamente baixos

– Conectados usando barramento de E/S

• Altamente disponíveis devido à separação das memórias

• Em teoria, devemos ser capazes de fazer melhor

227

Google

• Serve uma média de 1.000 consultas por segundo

• Usa 6.000 processadores e 12.000 discos

• Dois locais físicos no Vale do Silício e dois na Virgínia

• Cada local está conectado à Internet usando OC48 (2488 Mbit/seg)

• Confiabilidade:

– Em um dia típico, 20 máquinas precisam ser reiniciadas (erros de software)

– Menos de 2% das máquinas são substituídas a cada ano

Em certo sentido, são idéias simples bem executadas.Melhores (e mais baratas) do que outros métodosenvolvendo maior complexidade.

228

Comentários finais

• Evolução versus revolução“Na maioria das vezes, o custo da inovação é devido a ser muito problemático paraos usuários de computador.”

“A aceitação de idéias de hardware exige aceitação pelas pessoas de software;portanto, as pessoas de hardware precisam aprender mais sobre software. Alémdisso, se as pessoas de software quiserem boas máquinas, elas precisam aprendermais sobre hardware para serem capazes de se comunicar com — e, portanto,influenciar — os projetistas de hardware.”

229

(Compatívela nível binário)

(Novasbibliotecas)

(Recompilar) (Reprogramar)

Mic

ropr

ogra

maç

ão

Pip

elin

ing

Cac

he

Mul

tipro

cess

ador

com

tim

e sh

arin

g

Mem

ória

vir

tual

Sup

eres

cala

r

Inst

ruçõ

es d

e m

ultim

ídia

Inst

ruçõ

es v

etor

iais

RIS

C

Mul

tipro

cess

ador

CC

-UM

A

Mul

tipro

cess

ador

CC

-NU

MA

Clu

ster

s

SIM

D m

assi

vo

Mic

ropr

oces

sado

r de

pro

cess

amen

to p

aral

elo

Uso

esp

ecia

l

Evolucionário Revolucionário

Documents

Notas da terceira edição - jeiks.netjeiks.net/wp-content/uploads/2012/06/slides_AC.pdf · Notas da terceira edição ... já aprendeu sobre desenvolvimento com lógica e ... –