Aula 15: Ciclo de Execução e Introdução ao Pipelinefernanda/2016-1/FAC/aulas/aula15.pdf · I...

Aula 15: Ciclo de Execucao e Introducao ao Pipeline

Fernanda Passos

Universidade Federal Fluminense

Fundamentos de Arquiteturas de Computadores

Material baseado nos slides do prof. Diego Passos

Fernanda Passos (UFF) Ciclo de Execucao; Intro. ao Pipeline FAC 1 / 43

Revisao


Na Ultima Aula. . .

Comecamos a falar sobre as instrucoes de maquina.I Operacoes simples que o hardware e capaz de executar.

Programas executados por um computador sao armazenados como sequencias deinstrucoes na memoria.

I Ha um registrador especial chamado PC.I Ele armazena o endereco da proxima instrucao a ser executada.I A cada nova instrucao executada, PC e incrementado.


Na Ultima Aula. . . (II)

Discutimos tipos de instrucao.I Instrucoes aritmeticas.I Instrucoes logicas.I Instrucoes de desvio condicional.I Instrucoes de desvio incondicional.I . . .

Vimos exemplos destes tipos de instrucao na arquitetura MIPS.I add.I beq.I and.I . . .


Na Ultima Aula. . . (III)

Tambem vimos que instrucoes tem formatos especıficos.I Esquema de representacao.I Define quais e como informacoes sao guardadas na instrucao.

Finalmente, discutimos os operandos de uma instrucao.I “Parametros” da operacao a ser executada.I Podem ser, por exemplo, imediatos (constantes numericas) ou registradores.


Ciclo de Execucao de uma Instrucao


Ciclo de Execucao de uma Instrucao

Um processador funciona em ciclos.I De tempos em tempos, ele executa a mesma sequencia de passos.I Potencialmente, com entradas diferentes.I Manipulando as entradas, obtemos os resultados desejados.

Estes ciclos consistem na execucao de instrucoes.I As entradas sao os dados.I Mas tambem as instrucoes em si.

F Mudando o programa, tambem mudamos a saıda.


Composicao (Basica) do Ciclo de Execucao de uma Instrucao

Vista na aula passada:

Buscar Instrução Interpretar Instrução Executar Instrução

Proxima instrucao e buscada na memoria.Instrucao e interpretada.

I i.e., reconhecem-se o tipo, os operandos, etc.Operacao indicada e executada.


Ciclo de Execucao: Mais Detalhadamente

Partes do ciclo mostrado no slide anterior sao “complexas”.I Interpretar instrucao.I Executar instrucao.

Ha varios detalhes que ocorrem dentro de cada uma.Usualmente, definimos o ciclo de execucao de uma instrucao de forma mais detalhada.


Ciclo de Execucao: Mais Detalhadamente (II)

InícioDecodificar a Operação a

Ser RealizadaTérmino

Buscar Instrução na Memória

Buscar Operandos(Se Houver)

Executar a Operação

Armazenar Resultado

(Se Houver)

Ha fases de Busca de Operandos e Armazenamento de Resultado.I No esquema anterior, faziam parte de Interpretar Instrucao e Executar Instrucao.

Nos proximos slides, discutiremos cada uma destas fases.


Buscar Instrucao

Primeiro passo na execucao da instrucao:I Descobrir qual ela e.

Instrucoes sao armazenadas na MP.Processador so consegue manipular informacoes em seus registradores.

I Logo, antes de mais nada, processador precisa trazer instrucao da MP para algum registrador.I Nao um registrador qualquer: o IR.

F Instruction Register.Em algumas arquiteturas, as instrucoes tem comprimento fixo.

I e.g., MIPS, com instrucoes de 32 bits.Em outras, comprimento pode ser variavel.

I e.g., x86, com instrucoes de ate 15 bytes.I Neste caso, busca da instrucao pode nao ser tao simples.


Buscar Instrucao (II)

A busca de uma instrucao, portanto, e basicamente uma leitura da memoria.Como o processador sabe o endereco a ser lido?

I Ja discutido anteriormente.I Ha um outro registrador especial que o armazena.I O Program Counter, ou PC.

F Outros nomes: IC (Instruction Counter), IP (Instruction Pointer).PC tem que ser constantemente atualizado.

I Para apontar para a proxima instrucao a ser executada.I Normalmente, instrucoes sao executadas na ordem em que aparecem em memoria.I Logo, apos a leitura da instrucao atual, PC ja e incrementado.


Decodificar a Instrucao

Objetivo geral: entender a instrucao.I i.e., entender o que a sequencia de bits representa.

Envolve uma serie de sub-tarefas:I Qual e a operacao a ser realizada?I Qual e o formato da instrucao?I Onde estao os operandos?


Decodificar a Instrucao (II)

0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0

Opcode:

000000(2) = 0(10)

Significado:

Operação Lógicaou

Aritmética

Operando 1:

10001(2)=17(10)

Significado:

PrimeiroOperando está

no Reg. 17

Operando 2:

10010(2)=18(10)

Significado:

SegundoOperando está

no Reg. 18

Resultado:

01000(2)=8(10)

Significado:

ArmazenarResultadono Reg. 8

Campo nãoUtilizado

NestaInstrução

(deve sempreser 0)

Função:

100000(2)=32(10)

Significado:

Operação de Soma

0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0


Decodificar a Instrucao (III)

Primeiro passo, normalmente, e reconhecer o opcode.I Dado o opcode, geralmente, o restante do formato da instrucao e conhecido pelo processador.I i.e., processador sabe como tratar os demais bits da instrucao.I Adicionalmente, opcode define o tipo de operacao a ser realizada.

0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0

Opcode:

000000(2) = 0(10)

Significado:

Operação Lógicaou

Aritmética

Formato: R

Operando 1:

Registrador

Operando 2:

Registrador

Resultado:

RegistradorDeslocamento Função


Decodificar a Instrucao (IV)

Uma vez reconhecido o formato da instrucao, pode-se descobrir a localizacao dosoperandos.

I Podem estar ja em registradores.I Podem ser constantes numericas especificadas na propria instrucao.I Podem ser enderecos de memoria.

O opcode da instrucao determina a semantica dos bits dos operandos.I i.e., o que fazer com eles para encontrar os operandos.I e.g., usar como identificador de um registrador, somar com uma constante para obter um

endereco de memoria.


Busca de Operandos

Note que nem toda instrucao possui operandos.Exemplo: instrucao nop no x86.

I No Operation.I Instrucao que nao faz “nada”.

F Embora cause efeitos colaterais, como incrementar o PC.Mas na enorme maioria dos casos, instrucoes possuirao ao menos um operando.

I Sempre verdade no MIPS, por exemplo.


Busca de Operandos (II)

A busca de operandos consiste na tarefa de encontrar os valores sob os quais serarealizada a operacao.Os respectivos bits sao passados como entrada de componentes internos do processador.

I Como somadores, deslocadores, multiplexadores, . . .Um caso comum ocorre quando operando esta na MP.

I Endereco e dado por alguma combinacao de valores em registradores e constantes especıficasna propria instrucao.

I Processador requisita leitura a MP.


Busca de Operandos (III)

1 0 0 1

Registrador 0

0 0 1 1

Registrador 1

Seletor Mux

Somador

0 1

Outro

Dado

Note que mesmo para operandos emregistradores, ha algo a se fazer nestaetapa.

I Bits do registrador especificado devemser “conectados” ao(s) componente(s)adequado(s).


Busca de Operandos (IV)

1 0 0 1

Registrador 0

0 0 1 1

Registrador 1

Seletor Mux

Somador

0 1

Imediato

(Instrução)

Endereço do

Operando

na MP

Note ainda que certos casos de busca deoperandos requerem a execucao de algumtipo de processamento.

I Comumente, somas.I Algumas vezes deslocamentos

(multiplicacoes por potencias de 2).Exemplo: instrucao load word no MIPS.

I Endereco: valor de registrador +imediato.


Execucao da Operacao

Uma vez que os bits dos operandos estejam “conectados” aos componentes corretos doprocessador, a instrucao e executada.Esta execucao geralmente consiste em algum tipo de operacao logica-aritmetica.

I Somar dois numeros.I Calcular um xor bit a bit.I . . .

Em alguns casos particulares, a operacao pode ser simplesmente nao fazer nada com odado.

I e.g., deixar o dado passar.I Exemplo: operacoes de leitura ou escrita na memoria.


Execucao da Operacao (II)

Esta fase tambem consiste em “configurar” alguns componentes da CPU.Determinados componentes precisam de informacoes adicionais.

I Linhas de controle.I Especificam como o componente deve agir sobre os dados.

Exemplos classicos:I Um multiplexador: sinal na linha de controle seleciona entre primeira e segunda entrada.I Unidade logica-aritmetica: sinal nas linhas de controle selecionam operacao logica aritmetica

a ser realizada.Os sinais destas linhas de controle sao geralmente determinados a partir de campos dainstrucao.

I Como opcode e funcao, no caso do MIPS.


Armazenamento dos Resultados

Etapa similar a de busca de operandos.I Mas no sentido inverso.I i.e., ao inves de ler valores, estes sao armazenados em local apropriado.

Este “local” pode ser um registrador ou algum endereco da MP.I Assim como ocorre na busca de operandos, opcode e formato da instrucao determinam o

local.Tambem de forma similar, pode ser necessario realizar “processamento” para determinarexatamente este local.

I i.e., algum tipo de conta.I Exemplo classico: instrucoes de transferencia para a MP do MIPS.

F Soma de registrador com imediato.


Armazenamento dos Resultados

Note ainda que certas instrucoes nao geram dados a serem armazenados.I Ao menos nao na MP ou em registradores de proposito geral.

I e.g., instrucoes de desvio.I Unica (possıvel) escrita e no PC.


Introducao ao Conceito de Pipeline


Ciclos de CPU vs. Instrucoes

Processadores operam em ciclos.Duracao de um ciclo do processador e determinada pela frequencia do seu clock.

I Clock de 1 GHz → 1 bilhao de ciclos por segundo.Pergunta: quantas instrucoes um processador operando a 1 GHz de clock executapor segundo?

I Resposta: depende!I Pode ser exatamente 1 bilhao.I Pode ser menos.I Pode ser mais.


Ciclos de CPU vs. Instrucoes

Por que depende?I E possıvel projetar um processador que execute exatamente uma instrucao a cada ciclo.

F O que veremos nas proximas aulas.I Mas ha vantagens em quebrar a execucao de uma instrucao em varios ciclos de clock.

F Reutilizacao de componentes.F Permitir que instrucoes mais simples levem menos tempo.F Permitir paralelismo.

Voltaremos a este ponto em aulas posteriores.I Mas por hora, o foco sera no ultimo ponto.


Pipeline: Uma Analogia

Vamos usar uma analogia1para entender o conceito de Pipeline (Patterson):I Suponha uma republica de estudantes com 4 pessoas: Ann, Brian, Cathy, Dave.I Toda segunda-feira a noite, eles lavam roupa.I Cada um possui um conjunto de roupas sujas.

F Aproximadamente a mesma quantidade de roupas.I Processo composto por 4 etapas:

F Maquina de lavar: 30 minutos.

F Secador/passar roupas: 30 minutos.

F Dobrar roupas: 30 minutos.

F Guardar roupas: 30 minutos.

1Adaptado de http://www.cs.berkeley.edu/˜pattrsn/61CS99/lectures/lec25-pipeline.pdfFernanda Passos (UFF) Ciclo de Execucao; Intro. ao Pipeline FAC 28 / 43

http://www.cs.berkeley.edu/~pattrsn/61CS99/lectures/lec25-pipeline.pdf

Pipeline: Uma Analogia (II)

Solucao sequencial:I Cada pessoa aguarda a conclusao da anterior.

30

B

C

D

ATime

3030 3030 30 3030 3030 3030 3030 3030

6 PM 7 8 9 10 11 12 1 2 AM

Ordem

das

Tarefas


Pipeline: Uma Analogia (III)

Solucao alternativa:I A medida que uma pessoa termina uma fase, a seguinte inicia aquela fase do seu conjunto de

roupas.

12 2 AM6 PM 7 8 9 10 11 1

Time

B

C

D

A

303030 3030 30 30

Ordem

das

Tarefas


Pipeline: Uma Analogia (IV)

Na solucao original, cada pessoa demora 4× 30 = 120 minutos para lavar sua roupa.Na solucao alternativa tambem.Mas o tempo total na solucao alternativa e muito menor:

I 210 minutos, contra 480 minutos.Em outras palavras:

I O tempo de resposta para uma unica tarefa (pessoa) nao mudou.I Mas a vazao do sistema (pessoas atendidas por unidade de tempo) aumentou 118%.

Maior eficiencia vem do uso de pipeline.I i.e., executar etapas de tarefas diferentes em paralelo.I Evita que recursos fiquem ociosos.


Ciclo de Execucao de Instrucao e Pipeline

Podemos aplicar a mesma tecnica para a execucao de instrucoes em uma CPU?I Sim, desde que possamos quebrar a tarefa de execucao das instrucoes em sub-tarefas

independentes.Podemos, por exemplo, considerar as subtarefas como as etapas do ciclo de execucao deuma instrucao.

I Busca da instrucao.I Decodificacao.I Busca dos operandos.I Execucao.I Armazenamento do Resultado.

Assumindo, e claro, que nao haja dependencia entre as etapas de instrucoessubsequentes.


Ciclo de Execucao de Instrucao e Pipeline: Eficiencia

No jargao de arquitetura de computadores, cada “subtarefa” e chamada de estagio dopipeline.Considerando um pipeline com 5 estagios, o estado do pipeline ao longo do tempo:

S1:

S2:

S3:

S4:

S5:

1 2 3 4 5 7 86

Tempo

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7

1 2 3 4 5 6

1 2 3 4 5

1 2 3 4

...

Quantas instrucoes sao executadas por ciclo de clock?


Ciclo de Execucao de Instrucao e Pipeline: Eficiencia (II)

Com 5 estagios, primeira instrucao demora 5 ciclos de clock.Apos este tempo, a cada 1 ciclo, temos mais uma instrucao sendo concluıda.Para executar n instrucoes, precisamos de t = 5 + n − 1 = n + 4 ciclos.

I Logo, processador executa nn+4 instrucoes por ciclo de clock.

I Para n grande, isso e praticamente 1.Eficiencia nao e perfeita porque os k primeiros ciclos sao gastos enchendo o pipeline.

I Onde k e o numero de estagios.


Pipeline vs. Monociclo

Na conta anterior, verificamos que com o pipeline quase conseguimos atingir umainstrucao por ciclo.

I Entao qual e a vantagem de usar um pipeline com varios estagios ao inves de uma solucaoque faz tudo em um ciclo so?

A vantagem esta na duracao do ciclo.I Como, individualmente, cada estagio do pipeline faz algo “simples”, a duracao de um ciclo

pode ser curta.I Na implementacao monociclo, cada ciclo e mais complexo, longo.

Exemplo: o que e melhor?I Quase uma tarefa por ciclo, com ciclo de 1 ns.I Exatamente uma tarefa por ciclo, com ciclo de 5 ns.


Pipeline vs. Monociclo: Exercıcio Resolvido

Suponha que vao ser executadas 100 instrucoes.Deseja-se saber o tempo de execucao delas em uma maquina monocıclica e outra compipeline.Maquina monociclo:

I 1 ciclo de relogio tem duracao de 45 ns.I Tempo = duracao ciclo × CPI × I = 45× 1× 100 = 4500 ns

Maquina ideal com pipeline:I 1 ciclo de relogio tem duracao de 10 ns.I Com 5 estagios de pipeline.I Cada estagio de pipeline utiliza um ciclo de relogio.I Tempo = 5× duracao ciclo + (duracao ciclo × (100− 1)) = 5× 10 + 99× 10 = 1040 nsI ou Tempo = (n + k − 1)× duracao ciclo = (100 + 5− 1)× 10 = 1040 ns


Pipeline e Desvios

A tecnica de pipeline e efetiva, desde que mantenhamos o pipeline cheio.I i.e., quando uma instrucao esta no estagio i , a proxima esta no estagio i + 1.

Mas como o processador sabe qual e a proxima instrucao?I A princıpio, uma tarefa facil.I Programas sao sequencias de instrucoes armazenadas em memoria.

F Tambem de forma sequencial.Mas ha um caso especial: as instrucoes de desvio.

I Proxima instrucao pode estar em alguma posicao diferente.


Pipeline e Desvios (II)

Suponha que uma instrucao de desvio chegue ao ultimo estagio do pipeline.Neste ponto, a CPU descobre que sera realizado um desvio (ao inves da execucaosequencial).O que fazer?

I Outras instrucoes ja estao no pipeline.I Elas nao deveriam ser executadas.I Solucao: flush do pipeline.

F Esvaziamos o pipeline, nao permitindo a conclusao das demais instrucoes.F Recomecamos com o pipeline vazio a partir do endereco do desvio.F Resulta em uma penalidade de acordo com a quantidade de instrucoes removidas.


Pipeline e Desvios (III)

S1:

S2:

S3:

S4:

S5:

1 2 3 4 5 7 86

Tempo

1 2 3 4 5 6 11 12

1 2 3 4 5 11

1 2 3 4

1 2 3

1 2

...

Flush


Pipeline e Desvios (IV)

O flush em um pipeline impede que executemos instrucoes erradas.I Mas desempenho e prejudicado.I Enfrentamos novamente o custo inicial de encher o pipeline.

Lembre-se: ha dois tipos de desvios diferentes.I Desvios condicionais.I Desvios incondicionais.

No caso de desvios incondicionais, podemos amenizar o problema:I Se conseguirmos detectar o desvio cedo, precisamos descartar apenas um subconjunto das

instrucoes ja executadas.I O pipeline ainda ficara “meio cheio”.


Pipeline e Desvios (V)

Mas e para desvios condicionais?I Se soubessemos cedo o resultado da condicao, poderıamos usar a mesma estrategia dos

desvios incondicionais.I Mas isso geralmente nao e possıvel.

F Desvios condicionais sao mais complexos.F Precisam chegar a estagios finais do pipeline para sabermos seu resultado.

Nao ha solucao, entao?


Predicao de Desvios

Processadores modernos geralmente possuem um branch predictor.I Preditor de desvios.I Tenta “adivinhar” o resultado de uma instrucao de desvio condicional.I Baseado em historico.

Quando CPU detecta (cedo) a execucao de uma instrucao de desvio condicional:I Preditor preve se desvio ocorrera ou nao.I Se preditor diz que desvio nao ocorrera, proxima instrucao e colocada no pipeline.I Caso contrario, instrucao do endereco de destino e utilizada.

Se o preditor acerta, pipeline continua cheio.Se o preditor erra, temos que fazer um flush.

I E pagar a penalidade de desempenho.


Exercıcio

Suponha um processador com pipeline de 5 estagios.I Em instrucoes de desvio condicional, o preditor sempre preve que o salto nao ocorrera.I Assuma que ao final do quarto estagio a CPU e capaz de determinar o resultado de

instrucoes de desvio condicional.I Caso o desvio seja tomado, e preciso dar um flush nas tres instrucoes nos estagios anteriores.I Caso contrario, o pipeline continua cheio.

Determine o numero medio de instrucoes executadas por ciclo de clock considerando:I 20% das instrucoes sao de desvio condicional.I 30% destes desvios ocorrem.I Nao ha nenhuma outra fonte de ineficiencia do pipeline.


Aula 15: Ciclo de Execução e Introdução ao Pipelinefernanda/2016-1/FAC/aulas/aula15.pdf · I...

Documents

Transcript of Aula 15: Ciclo de Execução e Introdução ao Pipelinefernanda/2016-1/FAC/aulas/aula15.pdf · I...