Parte 7
Pipeline: Conceitos básicos, implementação
e ganho de desempenho
1
Melhorando o Desempenho com Pipelining
Baseado nas anotações do Livro do Hennessey &
Patterson e no material do Prof. José Luís Güntzel
[www.ufpel.edu.br/~guntzel/AOC2/AOC2.html]
2
O que é um Pipeline?
•
•
•
A técnica de pipelining é usada por todos os processadores
atuais para melhorar o desempenho pela superposição da
execução de instruções.
A analogia mais commum para um pipeline é uma linha de
montagem. Supondo 3 fases da linha:
1. Montagem
2. Pintura
3. Polimento
Assuma, por exemplo, que cada fase gaste 1 hora para ser
concluída
3
O que é um Pipeline?
• Se uma pessoa trabalha na linha de produção, ela levará 3
horas para produzir 1 produto.
• Se existem 3 pessoas, 1 pessoa poderia se ocupar de cada
estágio e cada vez que terminassem sua parte na produção,
poderiam passar seus produtos para a próxima pessoa
(estágio), sem nenhum tempo de espera.
• Desta maneira, seria possível produzir 1 produto por hora
assumindo que a linha de montagem está preenchida.
4
O que é um pipeline: Analogia Lavanderia
5
O que é um pipeline: Analogia Lavanderia
6
Pensando em termos de instruções MIPS
•
•
Considere os tempos de resposta de cada um dos componentes da
via de dados e os tempos para execução das instruções conforme a
tabela abaixo.
Podemos estimar que o período de clock será igual a 8ns para uma
CPU MIPS na sua versão monociclo.
• Pensando na execução de 3 loads (instrução mais lenta)
7
Execução sem e com pipeline
8
Características do Pipelining
• Se os estágios do pipeline não estiverem balanceados e um
dos estágios for mais lento que os outros, a vazão do pipeline
será afetada como um todo.
• Idealmente, cada estágio é balanceado (todos os estágios
estão prontos para iniciar ao mesmo tempo e levam a mesma
quantidade de tempo para serem concluídos).
• Assim, o tempo de execução por instrução no pipeline seria
definido por:
9
Características do Pipelining
• A expressão anterior corresponde ao ganho ideal (máximo).
– Existe um overhead para preencher o pipeline e os
estágios podem não estar perfeitamente balanceados…
• Em termos de uma CPU, a implementação do pipeline tem
efeito de reduzir o tempo médio por instrução e, portanto, o
valor médio do CPI.
– Ex: Se cada instrução num microprocessador leva 5 ciclos
de clock (sem pipelined) e se houver um pipeline de 4
estágios, o CPI ideal teórico seria 1.25
10
Voltando ao exemplo dos 3 loads...
• Sem pipeline: o tempo decorrido entre o início da primeira
instrução e o início da quarta instrução é 3x8 = 24 ns
• Com pipeline: o tempo decorrido entre o início da primeira
instrução e o início da quarta instrução é 3x2 = 6 ns
• Melhora de desempenho com pipeline = 24/6 = 4 vezes!
– Mas o ganho máximo teórico não deveria ser 5x, já que
esse é o número de estágio do pipeline?
– Onde está a diferença no exemplo?
• E se agora fossem realizadas 1.000.003 instruções load? Qual
o tempo total de execução com e sem pipeline? E o ganho
Sem pipeline: 1.000.003x8 = 8.000.024 ns
Com pipeline: 8 + 1.000.003x2= 2.000.014 ns
Ganho  4.0
11
RISC Instruction Set (Hennessey & Patterson)
•
Propriedades da arquitetura MIPS:
– Todos os operandos estão em registradores (32-bits).
– Acesso à Memória somente por operações load /store
– Instruções de tamanho único (32 bits)
– Poucos formatos de instruções, sempre com o registrador-fonte
localizado na mesma posição
– Operandos do MIPS alinhados na memória
•
Conjunto de instruções pensado para o pipeline!!!
•
Instruções aritméticas (ULA), acesso a memória e mudança de fluxo
de controle (desvios)
12
Tipos de Instruções MIPS
• ULA (ou tipo R)
– Aritméticas com 2 registradores ou 1 registrador e um imediato
como operandos. Resultado escrito num registrador destino
• Load/store
– Um registrador (base) e um operando 16-bits como valor
imediato. A soma deles define o endereço efetivo para o
acesso à memória.
– Um segundo registrador: destino para a operação de load e
dado a ser armazenado na operação de stored.
• Branches e Jumps
– Mudanças de fluxo de controle. Um branch resulta na soma de
um valor imediato ao valor atual do PC.
13
5 passos para execução de instruções MIPS
• Assume-se que qualquer instrução MIPS pode ser
executada em no máximo 5 ciclos de clock:
1. Busca da instrução na memória (BI/IF)
2. Leitura dos registradores, enquanto a instrução
é decodificada (ID/DI)
3. Execução de uma operação ou cálculo de um
endereço (EX)
4. Acesso a um operando na memória (MEM)
5. Escrita do resultado em um registrador (EM/WB)
14
Pensando em ciclos de clock
•
Resumo dos ciclos para executar instruções numa CPU não pipeline:
• Branch - 2 clocks
• Store - 4 clocks
• Outras - 5 clocks
•
EX: Assumindo que as instruções de desvio correspondem a 12% de
todas as instruções e que stores a 10%, qual o CPI médio da CPU?
CPImédio = 0.12*2+0.10*4+0.78*5 = 4.54
15
Pipeline RISC de 5 estágios
• Implementação clássica do conceito de pipeline proposta por
Hennessy e Patterson para o DLX (MIPS)
• Para o caso ideal, o pipeline deveria começar uma nova
instrução a cada novo ciclo de clock.
• Infelizmente isso nem sempre é possível:
– Um ADD não gasta o mesmo tempo de ULA que um MULT
– Dependências de dados entre instruções
– …
• Mas cada estágio pode ser tratado de forma independente e
assim as fases de execução podem ser “superpostas”
16
Representação Gráfica do Pipeline de Instrução
17
Lembram-se dos possíveis
caminhos para os dados na
via de dados da CPU?
18
Alguns Problemas à vista…
1. A memória é acessada 2x durante cada ciclo de clock.
– Separar memória de dados e de instruções
– Importante: o período do clock é o mesmo para a CPU
com pipeline e sem pipeline… Com isso, a memória
deve trabalhar 5x mais rápido.
2. Registradores acessados 2x por ciclo
– Para tentar evitar o conflito por recurso, realizar a
escrita na 1a metade do ciclo e a leitura na 2a metade
do ciclo de clock.
– Escreve-se primeiro porque o resultado de uma escrita
(dado) pode ser usado por outra instrução com execução
mais adiantada no pipeline
19
Alguns Problemas à vista…
3. Interação entre o PC e o pipeline ao fim da fase IF/BI. Se
a decodificação identifica uma instrução de desvio que
modifica o PC, como isso afeta o pipeline?
– O uso de registradores específicos para o pipeline
fornecem à CPU uma memória temporária que permite
armazenar estados intermediários da execução das
instruções no pipeline.
20
Conflitos de Pipeline (Pipeline “Hazards”)
• O ganho de desempenho porque é possível se iniciar a
execução de uma nova instrução a cada ciclo de clock. Porém,
em um cenário realista, isso nem sempre é possível…
• Os chamados conflitos de pipeline (“pipeline hazards”) atrasam
a execução da próxima instrução por alguns ciclos de clock, até
que haja tempo para que sejam solucionados...
– Usaremos hazard = conflito (hazard: azar, risco, acaso, …)
• Três tipos:
– Estruturais
– De controle
– De dados
21
1. Conflitos Estruturais (Structural Hazards)
• O hardware (do datapath) não tem recursos
suficientes para atender às solicitações da
execução sobreposta das instruções no pipeline
em um dado ciclo de clock
• O conjunto de instruções do MIPS foi projetado
para executar em pipeline (é muito fácil evitar esses
conflitos no design)
• Uma possível solução é a parada do pipeline
(“bolha”), isto é interromper a progressão das
instruções pelo pipeline.
22
1. Conflitos Estruturais (Structural Hazards)
• Se na CPU multiciclo vista anteriormente fosse mantida
apenas uma memória única para dados e instruções,
ocorreria um conflito estrutural quando uma instrução estiver
sendo buscada ao mesmo tempo que um dado é escrito na
memória (estágios BI e MEM)
• Outro problema aconteceria se considerarmos que o banco
de registradores só puder ser ou escrito ou lido num mesmo
ciclo (estágios DI e ER)
23
Conflito estrutural (Acesso
duplo à memória)
Conflito estrutural (Leitura e
escrita dos registradores)
24
2. Conflitos de Controle (Control Hazards)
• Interação PC – pipeline: conflitos se originam da
necessidade de se tomar uma decisão para o valor
de PC baseada nos resultados de uma instrução, a
qual ainda não foi concluída.
• Muito comuns em instruções de salto condicional
(beq, no caso do MIPs reduzido)
25
Parada do pipeline num conflito de controle
•
Assumir que um hardware extra foi adicionado para permitir testar
registradores, calcular o endereço de desvio condicional e atualizar
o PC, tudo isso no segundo estágio (decodificação). Isso é uma
solução comum para minimizar o efeito desse tipo de conflito.
26
Parada do pipeline num conflito de controle
•
Se for necessário resolver o desvio condicional em um estágio
posterior ao segundo (o que é o ocorre na maioria das CPUs reais),
ocorrerá uma perda maior de desempenho em função da
necessidade de encher novamente o pipeline
27
Outra solução para conflito de controle
• Predição estática: esquema muito usado em CPUs reais
• Simples: assumir que os desvios condicionais
sempre irão falhar (teste gera FALSO)
• Se acertar, o pipeline prossegue com velocidade máxima
• Se errar, será necessário atrasar o pipeline
• Mais sofisticado: assumir que parte dos desvios
ocorrem e outros não ocorrem
• Desvios para endereços anteriores supostamente falham
(instruções tipo if-then-else)
• Desvios para endereços posteriores supostamente são
feitos (última instrução de um loop)
28
Pipeline com predição de desvio
29
Mais uma solução para conflito de controle
• Predição dinâmica: realizada em função do
comportamento anterior (histórico) de cada desvio
• Podem mudar a predição para um mesmo ponto de
desvio com o decorrer da execução do programa
• Um esquema comum é manter uma história para
cada desvio realizado ou não-realizado
• Preditores dinâmicos são implementados em
hardware e apresentam até 90% de acerto
Qualquer que seja o esquema de predição, quando o palpite
(previsão) estiver errado(a), o controle do pipeline precisa
assegurar que as instruções seguintes ao desvio não terão
influência na execução das instruções futuras.
30
Mais uma solução para conflito de controle
• O esquema de retardar a decisão (delayed branch)
consiste em encaixar uma instrução “útil” para ser
executada logo após a instrução de desvio, de modo
a manter o pipeline preenchido, evitando a parada
• Isto é um trabalho para o Compilador!
– Lembrem-se que o compilador tem papel fundamental para
o desempenho de máquinas RISC
31
Solução para conflito de controle: delayed branch
32
Soluções similares ao delayed branch
33
3. Conflitos de Dados (Data Hazards)
• Ocorre quando uma instrução depende de dados resultantes
da execução de outra que ainda está no pipeline
34
Uma solução para conflito de dados
• Passar para o compilador a solução deste tipo de conflito é
inviável, pois ele é muito frequente
• Adiantamento (forwarding ou bypass): tão logo a ULA calcule
o resultado da operação, ele pode ser disponibilizado como
operando para as instruções que vem logo a seguir.
– Necessidade de um hardware de roteamento para detectar
a dependência entre dados de instruções subsequentes.
• Supondo a sequência de execução anterior:
35
Solução do conflito por adiantamento
•
Solução: conexão entre a saída da ULA e a entrada da própria ULA
Não haverá mais bolha no pipeline!
36
Outro exemplo de adiantamento
•
O adiantamento para uma instrução lw seguida de uma instrução que
usa o valor que acaba de ser buscado na memória:
Sempre haverá uma bolha no pipeline nesses casos! Inevitável!
37
Solução por reordenação de código
•
•
O compilador reordena as instruções de forma a evitar os possíveis
conflitos de dados.
Ex: o código do procedimento swap abaixo exibe um conflito.
lw
lw
sw
sw
$t0,
$t2,
$t2,
$t0,
0($t1)
4($t1)
0($t1)
4($t1)
#
#
#
#
#
reg $t1 possui o endereco de v[k]
reg $t0 (temp) = v[k]
reg $t2 = v[k+1]
v[k] = reg $t2
v[k+1] = reg $t0 (temp)
38
Solução por reordenação de código
•
Solução: trocar a 2ª e a 3ª linhas de posição: Código sem conflito
lw
lw
sw
sw
$t0,
$t2,
$t0,
$t2,
0($t1)
4($t1)
4($t1)
0($t1)
#
#
#
#
#
reg $t1 possui o endereco de v[k]
reg $t0 (temp) = v[k]
reg $t2 = v[k+1]
v[k+1] = reg $t0 (temp)
v[k] = reg $t2
39
Conflitos provocam a parada do pipeline
• Com os conflitos, algumas expressões envolvendo ganhos
mais realistas de pipeline em termos de CPI poderiam ser
calculados da seguinte forma:
Speedup = CPI unpipelined / CPI pipelined
= No estágios / (1 + paradas por instrução)
= Tmédio por Inst unpipelined / Tmédio por Inst pipelined
OBS: Assume-se que o período de clock é o mesmo para as implementação
com ou sem pipeline.
40
Conflitos provocam a parada do pipeline
•
Pode-se pensar no desempenho em termos de um ciclo de clock
mais rápido para a CPU pipelined da seguinte forma:
Speedup =
Tempo Ciclo Clock unpipelined
CPI unpipelined
x
Tempo Ciclo_Clock_pipelined
CPI pipelined
Tempo Ciclo_Clock_pipelined =
Tempo Ciclo Clock unpipelined
No estágios
1
Speedup =
x No estágios
1 + Paradas do pipeline por Instrução
41
Speedup x conflitos
• A solução básica para conflitos é a inserção de uma parada
ou bolha no pipeline. O efeito é o retardamento da execução
da próxima instrução de 1 ciclo a cada bolha inserida.
– Obviamente, isso aumenta o CPI, piorando o desempenho!
• Ex: Considere a comparação entre 2 CPUs. Uma delas tem
conflito estrutural que ocorre 40% do tempo, causando uma
bolha, mas com isso, trabalha com uma taxa de clock 1.05x
mais alta que a CPU sem conflito. Quanto a CPU com conflito
é mais rápida do que a sem conflito?
42
Speedup x conflitos
CPI sem_conflito
Speedup =
T ciclo_clock sem_conflito
x
T ciclo_clock com_conflito
CPI com_conflito
1
1
x
Speedup =
1+0.4*1
1/1.05
Speedup = 0.75
Note que:
(1) Apesar da taxa de clock do processador com conflito ser um pouco maior, o speedup é um
pouco menor que 1 (perde desempenho, mas não muito…) e
(2) Não cuidar do conflito poderia ser uma solução adotada por conta de custos envolvendo as
alterações na via de dados, aliada à baixa probabilidade de ocorrência deste conflito
43
Pipeline não resolve sozinho o desempenho
•
•
Precisaremos de buffers entre estágios do pipeline
– Armazenar os estados intermediários da execução de cada um
das instruções que está momentaneamente no pipeline
– Detecção de dependências
Além dos conflitos, ainda existem outros problemas a serem
resolvidos...
– Instruções com tempos diferentes por estágio (Adição x
multiplicação, ponto flutuante x inteiros)
– Múltiplos pipelines em arquiteturas superescalares
– Paralelismo em nível de instrução x compiladores paralelos
– Predição de desvio por hardware
44
Operações com múltiplos clocks
•
Algumas aplicações não serão completadas em apenas 1 clock.
Exemplos:
• Multiplicação Floating Point
• Divisão Floating Point
• Soma Floating Point
•
•
Pode se supor que existe um hardware específico para executar esse
tipo de instrução.
Em geral, Multiplicação e soma FP são totalmente pipelined, mas a
divisão é não pipelined.
45
Múltiplos estágios de execução na via de dados
46
Estágios de execução (EX) pipelined
47
Previsão de desvio via hardware
48