Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Pipeline ArqCompAv - Luan, Marco, Rebecca

Seminário sobre pipeline realizado por alunos da graduação do CEFET/RJ cursando bacharelado em ciência da computação em jul/2013. Baseado no livro: J. L. Hennessy, D. A. Patterson, Computer Architecture: A Quantitative Approach
by

Rebecca Pontes Salles

on 1 December 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Pipeline ArqCompAv - Luan, Marco, Rebecca

z9
Pipeline
Luan Moraes, Marco Lúcio, Rebecca Pontes Salles
Principal obstáculo do pipelining
Hazards (ou perigos)

Problemas que impedem a execução das instruções
Implementação
Armadilhas
Avaliar um escalonador em tempo de compilação com base em código não-otimizado.
Arquiteturas Avançadas de Computadores
"A linha de montagem de instruções."
Lavanderia sequencial leva 6 horas para terminar!
Lavanderia com pipelining leva 3 horas e 50 minutos!
ID
EX
WB
1. Ciclo de busca de instrução (IF)
IR <- Mem[PC];
NPC <- PC + 4;
3. Ciclo de execução/endereço efetivo (EX):
Referência de memória:
ULAOutput <- A + Imm;

Instrução de registrador-registrador da ULA:
ULAOutput <- A função B;

Instrução de registrador-imediato da ULA:
ULAOutput <- A op Imm;

Desvio:
ULAOutput <- NPC + (Imm << 2);
Cond <- (A == 0)

2. Ciclo de decodificação de instrução/busca de registrador (ID):
A <- Regs[rs];
B <- Regs[rt];
Imm <- campo imediato de IR estendido com sinal;

4. Ciclo de acesso à memória/conclusão de desvio (MEM):
PC <- NPC;

Referência à memória:
LMD <- Mem[ULAOutput] ou
Mem[ULAOutput] <- B;

Desvio:
If (cond) PC <- ULAOutput

MEM
5. Ciclo de write-back (WB):
Instrução de registrador-registrador da ULA:
Regs[rd] <- ULAOutput;

Instrução de registrador-imediato da ULA:
Regs[rt] <- ULAOutput;

Instrução de carga:
Regs[rt] <- LMD

IF
Uma implementação simples de MIPS
Um pipeline básico para MIPS
Iniciando uma nova instrução em cada ciclo de clock, todas as operações em uma fase do canal devem se completar em 1 ciclo de clock;
Os registradores de pipeline transportam dados e controle de uma fase de pipeline para a seguinte.
Os registradores temporários guardam valores entre ciclos de clock relativos a uma instrução.
Definições
Ciclo do Processador
= 1 ou 2 ciclos de clock
Throughput
(Rendimento)
= frequência com que uma instrução sai do pipeline
Fase de Canal
= etapas da linha de montagem
Desafio
Equilibrar o tempo de cada fase
Aceleração
Tempo por instrução em máquina sem pipeline
Número de fases do canal
RISC
Operações sobre dados se aplicam a dados nos registradores(32 ou 64 bits)
Instruções de acesso à memória
- LOAD e STORE
Entre registrador e memória
Podem envolver parte do registrador
Tamanho das Instruções
- Geralmente, possuem tamanho único
MIPS
Formatos de Instruções
O Nintendo 64 usou um processador central
NEC VR4300 baseado nos MIPS low-cost R4300i
MIPS64
(Microprocessor without Interlocked Pipeline Stages)
Versão 64 bits do conjunto de instruções MIPS
- "D" no ínicio ou no final das instruções(ex:DADD)
32 registradores com 64 bits cada
R0 = zero
Instruções com 32 bits
MIPS64
Classes de Instruções
ULA
Sufixo I para instruções com valores imediatos de 16 bits
DADD, DSUB, OR, AND, DADDI, DADDIU
Sufixo U para instruções de representação sem sinal
- Não geram exceções de estouro(overflow)
Instruções de Carga e Armazenamento
LOAD e STORE
Entre registrador e memória
Desvios e Saltos
Endereço efetivo
LD(Load Word) e SD(Store Word)
base(registrador) + offset(imediato de 16 bits)
- Movem 64 bits entre o registrador e a memória
Condicional(Branch)
- Comparação entre o registrador e zero
- Destino: deslocamento de 16b, com sinal, somado ao PC
Incondicional(Jump)
- Destino: diversas formas de endereçamento com PC
Controle para o pipeline MIPS
Todos os perigos de dados podem ser verificados durante a fase ID do pipeline.
Como outra alternativa, podemos detectar o perigo ou fazer o encaminhamento no início de um ciclo de clock que utilize um operando (EX e MEM para esse pipeline).
Com a instrução de origem sendo uma carga, a instrução de carga estará na fase EX quando uma instrução que necessitar dos dados estiver na ID.
Perigo RAW (Read After Write)
Uma vez que um perigo é detectado, a unidade de controle deve inserir a parada de pipeline e impedir que as instruções das fases IF e ID avancem.
A implementação da lógica de encaminhamento é semelhante. O destino do resultado encaminhado é uma entrada da ULA para a instrução que se encontra atualmente em EX.
Como lidar com desvios no pipeline
BEQZ e BNEZ
Será possível completar essa decisão no final do ciclo de ID.
Ambos os PCs (seguido e não-seguido) devem ser calculados antecipadamente.
A parada de perigos de desvio pode ser reduzida.

A primeira mudança é mover tanto o cálculo do endereço de destino de desvio quanto a decisão da condição de desvio para o ciclo de ID.

A segunda mudança é gravar o PC da instrução na fase IF.

A seleção do PC sequencial ou do PC de destino de desvio ainda ocorre durante IF, mas agora utiliza valores do registrador ID/EX. Essa mudança reduz a penalidade de desvio em 2 ciclos.
Como estender o pipeline MIPS para manipular operações de vários ciclos
As instruções de ponto flutuante têm o mesmo pipeline das instruções de inteiros, com duas mudanças importantes:

O ciclo de EX pode ser repetido tantas vezes quantas forem necessárias para concluir a operação.
Pode haver várias unidades funcionais de ponto flutuante.

Como EX não tem pipeline, nenhuma outra instrução que utilize essa unidade funcional poderá emitir enquanto a instrução anterior não deixar EX.
Bloqueio de carga
Perigos em pipelines de latência mais longa
Possíveis perigos
Podem ocorrer perigos estruturais.
O número de gravações de registradores exigidas em um ciclo pode ser maior que 1.
Perigos WAW (Write After Write) são possíveis.
As instruções podem se completar em uma ordem diferente daquela em que foram emitidas, causando problemas com exceções.
As paradas relativas a perigos RAW serão mais frequentes.
Perigos 1 e 2
Unidade de divisão
Porta de gravação no arquivo de registradores.
Perigos estruturais com relação a:
Perigo 3
Os perigos WAW só ocorrem quando uma instrução inútil é executada?
Não. Às vezes ocorrem em código razoável.
Por sorte, essa sequência de código será muito rara

Solução simples: Não emitir a segunda instrução para EX.
Existem duas alternativas diferentes para implementar esse bloqueio:

Controlar o uso da porta de gravação na fase ID.

Desdobrar uma instrução conflitante quando ela tentar entrar na fase MEM ou WB.
Desvantagem: Complica o controle do pipeline.
Perigo 4
Perigo 5
O impacto potencial dos perigos RAW:
Verificações
Detecção de perigos
Existem três verificações que devem ser executadas antes de uma instrução poder emitir:

Verificação de perigos estruturais;

Verificar um perigo de dados RAW;

Verificar um perigo de dados WAW.
Implementação Simples
IF
Instruction Fetch
Leitura de instrução na memória usando o PC como endereço.
ID
Instruction Decoder/ Register Fetch
Fixed-field decoding
Decodifica instrução, leitura de registradores, extensão de sinal de imediatos e offsets
no caso de desvios: teste, cálculo do endereço destino
**implementações de alta performance: concluir a execução de instruções de desvio neste ciclo
EX
MEM
WB
Operações distintas para instruções distintas
ALU: realiza operação espeficada no opcode (reg/reg, reg/imm)
Load/Store: calcula endereço efetivo (registrador + offset)
Execution/Effective Address
1
PC = PC+4
2
3
Load/Store: realiza acesso utilizando endereço efetivo
Memory Acess
4
Write Back
Atualiza registrador com o resultado de operação ALU ou com o valor lido por Load
5
Sem Pipeline
Avaliação
Número de ciclos por classe de instrução
Desvios Condicionais = 2 (20%)
ULA = 5 (40%)
LOAD = 5 (30%)
Store = 4 (10%)
1ns x (0,2) x 2 + (0,4) x 5 + (0,3) x 5 + (0,1) x 4 = 4,3 CPI
Pipeline
1
2
3
4
5
6
7
8
9
i+1
i
i+2
i+3
i+4
CPI = 1
Instruções diferentes em cada estágio
Solução: Armazene os resultados necessários para executar o próximo
ciclo de cada instrução
Performance da memória...
Solução: cache para poder manter a frequência alta
Conflito entre leitura de dados e instruções
Solução: um cache para dados outro para instruções
PC para a leitura da próxima instrução
Ok, resolvido. PC atualizado no primeiro estágio
Leitura e Escrita de registradores no mesmo ciclo
Não é um problema...
E os desvios?
Questões Gerais
Escalonamento dinâmico com um placar
Registrador
r
Como manter exceções precisas
DIV.D F0, F2, F4
ADD.D F10, F10, F8
SUB.D F12, F12, F14
Não existe nenhuma dependência. Porém, surge um problema:
Conclusão fora de ordem e, consequentemente, possíveis exceções imprecisas.
Ignorar o problema e se conformar com exceções imprecisas.

Bufferizar os resultados de uma operação até todas as operações que foram emitidas antes se completarem.

Permitir que as exceções se tornem um tanto imprecisas, mas manter informações.
Dificuldade: O tratador deve executar as instruções corretamente.
Simplificação: Limitar o número de instruções de ponto flutuante cuja execução pode ser sobreposta.

Esquema híbrido: Permite que a emissão de instruções só continue se houver certeza de que todas as instruções anteriores se completarão sem causar uma exceção.
Há quatro abordagens possíveis para lidar com a conclusão fora de ordem:
Conjuntos de instruções RISC e eficiência de pipelining
Os conjuntos de instruções simples oferecem outra vantagem: Facilitam o escalonamento de execução do código.
Pipelines dinamicamente escalonados
Para superar perdas de desempenho o compilador pode tentar escalonar instruções a fim de evitar perigo (escalonamento estático).

Processadores anteriores usavam escalonamento dinâmico - O hardware reorganiza a execução de instruções.

Queremos que as instruções iniciem sua execução logo que seus operandos de dados se tornem disponíveis. Desse modo, o pipeline fará a execução fora de ordem, o que implica conclusão fora de ordem.
Dividir a fase ID do canal em duas fases.

Emissão – Decodificar instruções, verificar perigos estruturais.


Leitura de operandos – Esperar até não haver perigos de dados, depois ler operandos.


Distinguir quando uma instrução inicia a execução e quando ela completa a execução.
Para implementar a execução fora de ordem:
Existem três tipos de perigos:
Estruturais
Dados
Controle
Perigos estruturais (Structural hazards)
Perigos de dados (Data hazards)
Perigos de controle (Control hazards)
Instrução usa dados da instrução anterior
Quando os desvios podem vir a alterar o PC
Processador com pipeline tem perigo estrutural
=
Instrução não acomodada por causa de conflito de recurso
Exemplo:
Solução:
O pipeline quer executar duas gravações em um ciclo de clock quando o processador possui apenas uma porta de gravação de arquivo.
Quando uma instrução encontra esse perigo, o pipeline é desdobrado por 1 ciclo de clock
Implementação
O que é ?
A marcação no placar é uma técnica que permite e execução de instruções fora de ordem.

O objetivo de um placar é manter uma velocidade de execução de uma instrução por ciclo de clock executando uma instrução o mais cedo possível.

Os placares fazem sentido principalmente na unidade de ponto flutuante.
Como funciona ?
Toda instrução passa pelo placar, onde é construído um registro das dependências de dados;
Em seguida, o placar determina quando a instrução pode ler seus operandos e iniciar a execução.
Ele irá monitorar toda a mudança no hardware e decidir quando a instrução pode ser executada.
O placar também controla quando uma instrução pode gravar seu resultado no registrador de destino.
Toda a detecção e resolução de perigos é centralizada no placar.
Há uma pequena complicação: As fases de gravação de resultados e leitura de operandos não podem se sobrepor.
O CDC 6600 resolveu esse problema reunindo as unidades funcionais em quatro grupos. Somente uma unidade em um grupo poderia ler seus operandos ou gravar seu resultado durante um clock.
Etapas de execução que substituem as etapas ID, EX e WB:
Fase ID
Etapa
- Emissão

-Leitura de operandos
Etapa
Fase EX
Etapa
- Execução
Fase WB
Etapa
- Gravação de resultado
Outra visão
o pipeline MIPS R4300
Uma instrução não pode ter permissão para gravar seus resultados quando:

Existe uma instrução que não leu seus operandos e que precede, em ordem de emissão, a instrução que está sendo concluída.

Um dos operandos é o mesmo registrador que resulta da instrução que está se completando.

Comentários finais
Supercomputador
Mainframe
Tianhe-2
O placar tem três partes:

1. Status de instrução
2. Status de unidade funcional
3. Status de resultado de registrador
Minicomputador
O nível de paralelismo disponível entre as instruções

O número de entradas do placar

O número e os tipos da unidades funcionais

A presença de antidependências e de dependência de saída

Data General Nova
Na eliminação das paradas, um placar é limitado por diversos fatores:
Os perigos WAW e WAR se tornam mais importantes em processadores dinamicamente escalonados.
Nintendo 64 CPU
Sequências de execução inesperadas podem causar perigos inesperados.
O pipelining extensivo pode causar impacto sobre outros aspectos de um projeto, levando a um custo-desempenho global pior.
Performance
Latência
–Tempo de execução de uma instrução
– Ligeiramente maior que na implementação multiciclo devido ao hardware de controle da pipeline.
– Entretanto, programas executam mais rapidamente..
Limites para performance da pipeline
– Aumento da latência de instrução limita o número de estágios da pipeline
– Dificuldades em dividir em estágios de igual duração
– Latência de registradores de pipeline e tempo de setup
– Desvio máximo das transições de relógio entre os
registradores de pipeline
Comparação
Instruções executadas
- Desvios condicionais: 2 (20%)
- ALU: 5 (40%)
- Load: 5 (30%)
- Store: 4 (10%)
Implementação sem Pipeline
- Ciclo do relógio = 1 ns
- Tempo médio por instrução = 4,3 ns
Implementação Pipeline
- Ciclo do relógio = 1,2 ns
(clock skew e setup time)
4,3/1,2 = 3,8
O que torna o pipeline difícil de implementar?
Situações excepcionais
Como lidar?
Sobreposição de instruções = perigo
Executada fragmento por fragmento
Certas exceções cancelam instruções
Exceções e requisitos
Terminologia das exceções varia
Nomes longos = classe particular de exceções
ex: interrupção de E/S
exceção de ponto flutuante
erro de página
Exceção engloba todos os eventos
Seus requisitos são:
Solicitado vs. forçado
Mascarável vs. não-mascarável
Retomar vs. encerrar
Dentro da instrução vs. entre a instrução
Sincronos vs. assíncronos
Evento com mesmo lugar, dados e memória
Evento causado por dispositivo externo
Sincronos
Assíncronos
Evento pode ser desabilitado pelo usuário
Evento pode ser desabilitado pelo hardware
Mascarável
Não-mascarável
Evento for síncrono
Evento for assíncrono
Dentro
Entre
Evento continua depois de interrompido
Evento pára depois de interrompido
Retomar
Encerrar
Evento é solicitado diretamente pelo usuário
Não é solicitado diretamente pelo usuário ou é soliticado pelo hardware
Solicitado
Forçado
Exceções problemáticas no MIPS
Ocorrem, pois existem várias instruções em execução.
Podemos notar no exemplo que ocorrerá um erro de página de dados e uma exceção aritmética ao mesmo tempo.

É possível tratar o erro de página e depois reiniciar a execução. Quando a segunda exceção ocorrer, o outro erro será tratado independentemente.

O pipeline sempre tratará a exceção da primeira instrução.

Desvio alterar PC = desvio seguido
Desvio não altera PC = desvio não-seguido
O que são?
Hardware é necessário para várias instruções
Quando ocorrem?
Reg A <- int i
int i+1 <- Reg A
int i+1 -> execute / int i -> write-back ?
Essa é a situação Read After Write (RAW)
Exemplo:
Quando ocorrem?
Quando ocorrem?
Aumento da Latência
Atraso de Desvio + Atraso de Carga
Família de Processadores MIPS R4000
Inclui MIPS R4400
Implementa o MIPS 64
Possui pipeline mais profundo, chamado Superpipeline
Fases do Superpipeline
IF
ID/RF
DF
TC
IS
EX
DS
WB
1º metade da busca de instruções
Seleção do PC
Início do acesso à cache de instruções
2ª metade da busca de instruções
Encerra o acesso a cache
Decodificação da instrução
Busca de Registradores
Verificação de perigos(Hazards)
Detecção de acerto da cache
Cálculo do Effective Address
Operações da ULA
Computação do destino de desvios
Avaliação de Condições
Busca de dados
1ª metade do acesso à cache de dados
2ª metade do acesso à cache
Concluí o acesso
Verificação de Tags
Determina se o acesso à cache de dados foi um acerto
Write back para cargas e operações reg-reg
Instrução de carga seguida de uso imediato causando um atraso de 2 ciclos.
Encaminhamento
Atraso de Desvio
Atraso de desvio básico de 3 ciclos
Desvios não seguidos possuem um slot de atraso
Desvios seguidos possuem um slot de atraso + dois ciclos ociosos
No pipeline simples o encaminhamento de instruções reg-reg era feito em ULA/MEM ou no MEM/WB.
No Superpipeline ele pode ser feito em EX/DF, DF/DS, DS/TC ou em TC/WB
O Pipeline FP
Possui:
1 somador float point
1 multiplicador float point
1 divisor float point
Operações FP de precisão dupla demoram de dois ciclos(negação) até 112 ciclos(raiz quadrada)
Unidades Funcionais
Possuem 8 fases diferentes. Que compoem as operações FP.
Paradas
MULT + ADD
ADD + MULT
DIV + ADD
ADD+DIV
Desempenho do R4000
O CPI varia entre 1,2 a 2,8
IBM 7030 Stretch
1961
Primeiro processador com pipeline de uso geral
O plano era obter um aperfeiçoamento de 1,6x a partir da sobreposição de operações de busca, decodificação e execução.
Utilizava pipeline de 4 fases
Circuitos do IBM 7030
1964
CDC 6600
Introduziu o uso de tags
Processadores periféricos que usam multithreading
Escalonador de execução de instruções para compiladores FORTRAN
Os componentes fundamentais da arquitetura do CDC são:
- um processador
- uma memória principal,
- 10 processadores periféricos múltiplos
- 12 canais de E/S.
Final de 70 - Início de 80
Uma série de descrições gerais forneceram grande parte da terminologia e a maioria das técnicas básicas usadas em pipeline simples
Look Ahead Processors Keller, R.M.
[1975]
Pipeline Architecture
Ramamoorthy, C.D. and H.F. Li
[1977]
Overlap and parallel processing
Chen, T.C.
[1980]
The Architecture of
Pipeline Computers
Kooge, P.M.
[1981]
Alpha 21064 processor
1992
História
1991
MIPS R4000
Um dos primeiros microprocessadores com pipeline profundo
Conjunto de instruções e estrutura de pipeline de inteiros semelhante ao MIPS R4000, com mais pipelining na unidade FP
As primeiras CPUs com pipeline
É necessário buscar a instrução seguinte dos desvios, sendo que o primeiro IF é uma parada.
Sem erros, o pipeline continuaria a toda velocidade.
Full transcript