Pipeline
É possível obter maior desempenho computacional com:
• tecnologias mais avançadas, tais como circuitos mais rápidos;
• melhor organização da CPU, tais como o uso de múltiplos
registradores e memória cache;
• pipeline de instruções.
A idéia básica num pipeline de instruções é a de novas entradas
serem aceitas, antes que as entradas aceitas previamente tenham
terminado. Este conceito assume que uma instrução tem vários
estágios.
Arquitetura de Computadores
Profa Luiza Mourelle
Seqüência de eventos num ciclo de instrução:
início
busca de instrução;
decodificação da instrução;
cálculo de endereço de operando;
busca de operando;
execução da instrução;
cálculo de endereço do resultado;
verificação de interrupção;
se interrupção então tratamento de interrupção;
cálculo de endereço da próxima instrução;
volta para busca de instrução;
end.
Arquitetura de Computadores
Profa Luiza Mourelle
Ao invés da execução seqüencial do algoritmo, poderíamos associar
cada etapa a um estágio do pipeline.
novo endereço
espera
instrução
busca
instrução
espera
resultado
execução
descarte
O primeiro estágio busca a instrução e a armazena em uma área de
armazenamento temporário.
Quando o segundo estágio está livre, o primeiro passa para ele a
instrução armazenada.
Enquanto o segundo estágio está executando essa instrução, o
primeiro tira proveito de ciclos de memória que não são usados para
buscar e armazenar a próxima instrução.
Arquitetura de Computadores
Profa Luiza Mourelle
A busca antecipada de instrução (instruction prefetch) ou
superposição de busca (fetch overlap) consiste em buscar a próxima
instrução, enquanto a atual está sendo executada.
O aumento da taxa de execução de instruções, no exemplo anterior,
pode não ser possível pois:
• o tempo de execução é geralmente maior que o de busca (o
estágio de busca pode ter que esperar antes que possa esvaziar a
área de armazenamento temporário);
• instruções de desvio condicional fazem com que o endereço da
próxima instrução seja desconhecido (o estágio de busca teria de
esperar pelo endereço da próxima instrução e o estágio de
execução teria que esperar enquanto a próxima instrução é
buscada).
Arquitetura de Computadores
Profa Luiza Mourelle
Para conseguir maior desempenho, o pipeline deve ter o maior
número de estágios possível.
Exemplo: Considere um pipeline com
duração:
•
•
•
•
•
•
6 estágios de mesma
busca de instrução (BI);
decodificação de instrução (DI);
cálculo de operandos (CO);
busca de operandos (BO);
execução de instrução (EI);
escrita de operando (EO).
Arquitetura de Computadores
Profa Luiza Mourelle
Pipeline com seis estágios:
tempo
1 2
3
4
5
6
EI
BO
CO
DI
BI
EO
EI
BO
CO
DI
BI
7
8
9
10 11 12 13 14
instrução
1
2
3
4
5
6
7
8
9
BI DI CO BO
BI DI CO
BI DI
BI
Arquitetura de Computadores
EO
EI
BO
CO
DI
BI
EO
EI
BO
CO
DI
BI
Profa Luiza Mourelle
EO
EI
BO
CO
DI
BI
EO
EI
BO
CO
DI
EO
EI EO
BO EI EO
CO BO EI EO
Consideramos que cada instrução passa por todos os estágios do
pipeline (o que nem sempre é necessário), simplificando o hardware.
Consideramos que todos os estágios podem ser executados em
paralelo, não havendo conflito, por exemplo, nos acesso à memória
(o dado pode estar no cache ou alguns estágios, que requerem acesso
à memória, não estão sendo usados).
Se os seis estágios não têm duração igual, existe certa espera
envolvida em vários estágios.
Uma instrução de desvio condicional pode invalidar diversas buscas
de instrução. Da mesma forma, a ocorrência de interrupção.
Arquitetura de Computadores
Profa Luiza Mourelle
Exemplo: Suponha que a instrução 3 seja um desvio condicional
para a instrução 15.
tempo
1 2
3
4
5
6
EI
BO
CO
DI
BI
EO
EI
BO
CO
DI
BI
7
8
9
10 11 12 13 14
instrução
1
2
3
4
5
6
7
15
16
BI DI CO BO
BI DI CO
BI DI
BI
Arquitetura de Computadores
EO
EI EO
BO
CO
DI
BI
BI DI CO BO EI EO
BI DI CO BO EI EO
Profa Luiza Mourelle
Dizer que uma máquina A é n vezes mais rápida que uma máquina
B significa que:
tempo de e xecução B
 n
tempo de e xecução A
Desempenho é definido como o inverso do tempo de execução:
1
tempo de e xecução B
desempenho B
desempenho A
n


1
tempo de e xecução A
desempenho B
desempenho A
Arquitetura de Computadores
Profa Luiza Mourelle
A lei de Amdahl define o speedup (S), que consiste do ganho em
desempenho que pode ser obtido ao melhorar determinada
característica do computador:
S 
desempenho
desempenho
S 
de toda a operação usando a melhoria
de toda a operação sem usar a melhoria
tempo de execução de toda a operação sem usar a melhoria
tempo de execução de toda a operação usando a melhoria
Arquitetura de Computadores
Profa Luiza Mourelle
O tempo de ciclo  de um pipeline de instrução é o tempo requerido
para avançar um conjunto de instruções um estágio.
O tempo de ciclo pode ser determinado da seguinte maneira:
 = max[i] + d = m + d, 1  i  k
onde:
m = atraso máximo de estágio
k = número de estágios do pipeline de instrução
d = tempo necessário para propagar sinais e dados de um
estágio para o próximo
Em geral, d é equivalente ao pulso de um relógio e m  d.
Arquitetura de Computadores
Profa Luiza Mourelle
Exemplo: Suponha que sejam processadas n instruções, sem que
ocorra desvio.
Tk = [k+(n-1)]  ,
tempo total de execução
O speedup para a execução com o pipeline de instruções em relação
à execução sem o uso do pipeline é:
T1
nk 
nk
Sk 


T k [ k  ( n  1)] k  ( n  1)
Arquitetura de Computadores
Profa Luiza Mourelle
Em função do número de instruções executadas sem desvio, no
limite (n  ), o fator de aceleração é igual a k.
Em função do número de estágios, o fator de aceleração se aproxima
do número de instruções que podem ser introduzidas no pipeline
sem desvio.
Quanto maior o número de estágios do pipeline, maior o speedup.
No entanto, o ganho diminui devido:
•
•
•
ao aumento no custo da implementação;
aos atrasos entre estágios;
aos atrasos no processo de esvaziamento do pipeline quando
ocorre instrução de desvio.
Um número de estágios entre 6 e 9 parece ser mais adequado.
Arquitetura de Computadores
Profa Luiza Mourelle
Speedup
Speedup para execução com pipeline
de instruções em relação à execução
sem pipeline
14
12
10
8
6
4
2
0
k=6
k=9
k = 12
1
10
100
1000
10000
Número de instruções
Arquitetura de Computadores
Profa Luiza Mourelle
Speedup
Speedup para execução com pipeline
de instruções em relação à execução
sem pipeline
20
16
12
8
4
0
n = 10
n = 20
n = 30
0
5
10 15 20 25 30 35
Número de estágios
Arquitetura de Computadores
Profa Luiza Mourelle
Considere a arquitetura do processador DLX, sem pipeline:
• 32 registradores de 32 bits (R0 a R31);
• 31 registradores de ponto flutuante (F0 a F30);
• endereçamento de dados é imediato ou deslocamento;
• endereçamento de byte, com endereço de 32 bits;
• instruções de carga e armazenamento;
• instruções aritméticas e lógicas;
• instruções de desvio.
Arquitetura de Computadores
Profa Luiza Mourelle
Todas as instruções são de 32 bits, com 6 bits para código de
operação e 16 bits para endereçamento por deslocamento,
constantes imediatas e endereços de desvio relativos ao contador
de programas (PC):
• instrução do tipo I:
• instrução do tipo R:
• instrução do tipo J:
opcod rs1
5
6
rd
5
opcod rs1
6
5
rs2 rd
5
5
opcod
6
imediato
16
função
11
deslocamento somado ao PC
26
Há quatro classes de instruções: cargas e armazenamentos,
operações com a ALU, desvios e operações de ponto flutuante.
Arquitetura de Computadores
Profa Luiza Mourelle
Todas as instruções levam, no máximo, cinco ciclos de clock para
serem executadas:
1 – ciclo de busca de instrução (IF):
IR  mem[PC];
NPC  PC + 4
2 – ciclo de decodificação de instrução/busca de registrador (ID):
A  regs[IR6 .. 10];
B  regs[IR11 .. 15];
Imm  (IR16 .. 31);
Arquitetura de Computadores
Profa Luiza Mourelle
3 – ciclo de execução/endereço efetivo (EX):
ALUoutput  A + Imm; endereçamento de memória
ALUoutput  A op B; operação entre registradores
ALUoutput  A op Imm; operação entre registrador e
imediato
ALUoutput  NPC + Imm; cálculo do endereço de desvio
Cond  (A op 0); operação de comparação dependendo
do código de operação (i.e., ==)
Arquitetura de Computadores
Profa Luiza Mourelle
4 – ciclo de acesso à memória/complemento de desvio (MEM):
LMD  mem[ALUoutput] ou
mem[ALUoutput]  B; endereçamento de memória
if (cond)
then PC  ALUoutput
else PC  NPC; desvio condicional
5 – ciclo de escrita (WB):
regs[IR16 .. 20]  ALUoutput;
regs[IR11 .. 15]  ALUoutput;
regs[IR11 .. 15]  LMD
Arquitetura de Computadores
Profa Luiza Mourelle
ID
IF
EX
MEM
WB
mux
4
soma
PC
.
memória
de
instrução
NPC
IR
.
zero
.
.
.
A
regs
B
.
mux
ALU
mux
Imm
Arquitetura de Computadores
cond
Profa Luiza Mourelle
aluoutput
.
memória
de dados
LMD
mux
Ao término de cada ciclo de clock, cada valor computado durante
aquele ciclo e requerido num ciclo mais tarde (quer seja para esta
instrução ou a próxima) é escrito em um meio de armazenamento,
que pode ser a memória, um registrador de propósito geral, o PC
ou um registrador temporário (LMD, Imm, A, B, IR, NPC,
ALUoutput ou Cond).
Esses registadores temporários armazenam valores entre ciclos de
clock para uma instrução, enquanto os outros meios de
armazenamento são elementos do estado da arquitetura e guardam
valores entre instruções sucessivas.
Nesta arquitetura, instruções de desvio requerem quatro ciclos de
clock e todas as outras requerem cinco ciclos de clock.
Arquitetura de Computadores
Profa Luiza Mourelle
Pode-se implementar pipeline nesta arquitetura começando uma
nova instrução a cada ciclo de clock e associando um estágio do
pipeline a cada ciclo da arquitetura descrita.
ciclos de clock
instrução 1
i
i+1
2
3
4
IF ID EX MEM
IF
i+2
i+3
i+4
Arquitetura de Computadores
5
6
7
8
9
WB
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
IF
ID
EX
Profa Luiza Mourelle
WB
MEM WB
ID/EX
IF/ID
4
.
PC
.
zero
mux
soma
memória
de
instrução
IR
.
.
IR6 .. 10
IR11 .. 15
MEM/WB.IR
regs
.
desvio
mux
ALU
mux
.
Arquitetura de Computadores
MEM/WB
EX/MEM
Profa Luiza Mourelle
.
memória
de dados
mux
Os registradores do pipeline armazenam tanto dados quanto
controle de um estágio do pipeline para o próximo. Qualquer valor
necessário em um estágio adiante deve ser posto em um desses
registradores e copiado de um registrador para outro, até não ser
mais requerido.
Por exemplo, o campo de um operando usado em uma escrita ou
numa operação da ALU é fornecido pelo registrador do estágio
MEM/WB, ao invés do registrador do estágio IF/ID. Isto porque o
estágio IF/ID está, no momento, associado a outra instrução que
não aquela correspondente à operação no estágio MEM/WB.
Qualquer instrução está ativa em exatamente um estágio do
pipeline de cada vez.
Arquitetura de Computadores
Profa Luiza Mourelle
Estágio
Qualquer instrução
IF
IF/ID.IRmem[PC]; IF/ID.NPC,PC(se EX/MEM.cond então (EX/MEM.NPC) senão (PC+4);
ID
ID/EX.Aregs[IF/ID.IR6 .. 10]; ID/EX.Bregs[IF/ID.IR11 .. 15]; ID/EX.NPCIF/ID.NPC; ID/EX.IRIF/ID.IR;
ID/EX.ImmIR16 .. 31;
EX
Instrução para ALU
Carga ou armazenamento
Desvio
EX/MEM.IRID/EX.IR;
EX/MEM.ALUoutput
ID.EX.A op ID/EX.B; ou
EX/MEM.IRID/EX.IR;
EX/MEM/ALUoutputID/EX.Imm;
EX/MEM.cond0;
EX/MEM.BID/EX.B;
EX/MEM.ALUoutputID/EX.NPC+ID/EX.Imm;
EX/MEM.cond(ID/EX.A op 0);
EX/MEM.ALUoutput
ID/EX.A op ID/EX.Imm;
EX/MEM.cond0;
MEM
MEM/WB.IREX/MEM.IR;
MEM/WB.ALUoutput
EX/MEM.ALUoutput;
MEM/WB.IREX/MEM.IR;
MEM/WB.LMD
mem[EX/MEM.ALUoutput]; ou
mem[EX/MEM.ALUoutput] EX/MEM.B;
WB
Regs[MEM/WB.IR16 .. 20]
MEM/WB.ALUoutput; ou
Regs[MEM/WB.IR11 .. 15]MEM/WB.LMD;
Regs[MEM/WB.IR11 .. 15]
MEM/WB.ALUoutput
Arquitetura de Computadores
Profa Luiza Mourelle
Se a instrução i for um desvio a ser tomado, então o PC será
modificado ao final do estágio MEM, após o complemento do
cálculo do endereço e comparação.
O método mais simples de tratar com desvios é parar o pipeline,
assim que um desvio é detetado, até chegar ao estágio MEM, que
vai determinar o próximo PC.
Neste caso, a parada do pipeline só ocorre após o estágio ID,
quando se identifica que a instrução é um desvio.
Arquitetura de Computadores
Profa Luiza Mourelle
Um desvio causa uma parada de três ciclos no pipeline. A instrução
depois do desvio é buscada, mas é ignorada.
ciclos de clock
instrução
1
2
i (desvio) IF ID
i+1
3
4
EX
5
7
8
9
10
MEM WB
IF parada parada
IF
i+2
ID EX MEM
IF
i+3
i+4
i+5
Arquitetura de Computadores
6
Profa Luiza Mourelle
WB
ID
EX
MEM
WB
IF
ID
EX
MEM
IF
ID
EX
IF
ID
O número de ciclos de clock numa parada por desvio pode ser
reduzido através de duas ações:
1 – identificar mais cedo se o desvio deve ser tomado ou não;
2 – computar mais cedo o endereço alvo de desvio.
Na arquitetura do DLX, é possível completar o teste da condição
de desvio ao final do estágio ID.
Para tirar vantagem do teste da condição nesse estágio, os valores
possíveis do PC já devem estar computados.
Arquitetura de Computadores
Profa Luiza Mourelle
4
.
PC
.
memória
de
instrução
IR
MEM/WB
soma
mux
soma
EX/MEM
ID/EX
IF/ID
zero
.
IR6 .. 10
.
IR11 .. 15
MEM/WB.IR
regs
.
..
Arquitetura de Computadores
Profa Luiza Mourelle
ALU
mux
.
memória
de dados
mux
Uma vez que o desvio é feito ao final do estágio ID, os estágio EX,
MEM e WB não são utilizados durante um desvio.
Estágio Instrução de desvio
IF
IF/ID.IRmem[PC];
IF/ID.NPC,PC(se EX/MEM.cond então (EX/MEM.NPC) senão (PC+4);
ID
ID/EX.Aregs[IF/ID.IR6 .. 10]; ID/EX.Bregs[IF/ID.IR11 .. 15];
ID/EX.NPCIF/ID.NPC + IR16 .. 31;
ID/EX.IRIF/ID.IR; ID/EX.cond(regs[IF/ID.IR6 .. 10] op 0];
ID/EX.ImmIR16 .. 31;
EX
MEM
WB
Arquitetura de Computadores
Profa Luiza Mourelle
Tratamento com Desvios
Múltiplos fluxos consiste em duplicar os estágios iniciais do
pipeline para permitir a busca de ambas as instruções, usando dois
fluxos de instruções. Problemas:
• o uso de múltiplos pipelines introduz atrasos devidos à contenção
de acesso a registradores e à memória;
• pode ocorrer a entrada de instruções de desvio adicionais na
pipeline, antes que seja tomada a decisão sobre o desvio original.
Arquitetura de Computadores
Profa Luiza Mourelle
Busca antecipada da instrução-alvo do desvio consiste em buscar
antecipadamente tanto a instrução-alvo do desvio quanto a instrução
consecutiva ao desvio, no instante em que a instrução de desvio
condicional é reconhecida. A instrução-alvo é armazenada em um
registrador, até que a instrução de desvio seja executada.
Memória de laço consiste em usar uma pequena memória de alta
velocidade (memória de laço de repetição ou loop buffer), mantida
pelo estágio de busca de instrução, para guardar as n instruções
buscadas mais recentemente, em seqüência.
Arquitetura de Computadores
Profa Luiza Mourelle
Vantagens:
• com o uso de busca antecipada, a memória de laço conterá certo
número de instruções que estão à frente da instrução corrente;
• se ocorrer um desvio para alguma posição adiante do endereço da
instrução de desvio, essa posição já estará na memória de laço
(útil em instruções do tipo IF-THEN-ELSE);
• particularmente adequada para lidar com laços de repetição ou
iterações (se a memória for grande o suficiente para conter as
instruções de uma iteração, estas terão que ser buscadas da
memória apenas uma vez, para a primeira iteração).
Arquitetura de Computadores
Profa Luiza Mourelle
Exemplo: Considere uma memória de laço com 256 bytes e
endereçamento de byte.
endereço de desvio
8
memória de laço
de 256 bytes
Arquitetura de Computadores
Profa Luiza Mourelle
comparação dos bits mais
significativos do endereço para
determinar se a instrução está
na memória de laço
Previsão de desvio pode ser feita de várias formas:
• prever que o desvio nunca será tomado:
abordagem simples e estática, isto é, não depende do histórico das
instruções até o momento em que ocorre a instrução de desvio
condicional; continua buscando instruções na seqüência em que
ocorrem no programa.
• prever que o desvio sempre será tomado:
abordagem simples e estática, isto é, não depende do histórico das
instruções até o momento em que ocorre a instrução de desvio
condicional; busca sempre as próximas instruções a partir do
endereço-alvo do desvio.
Arquitetura de Computadores
Profa Luiza Mourelle
• prever se o desvio será tomado ou não conforme o código de
operação:
abordagem simples e estática.
• prever o desvio com base em chaves de desvio tomado e de
desvio não tomado:
abordagem dinâmica,isto é, depende do histórico de execução.
• prever o desvio com base em uma tabela de histórico de desvios:
abordagem dinâmica.
Arquitetura de Computadores
Profa Luiza Mourelle
Se a busca da instrução consecutiva à instrução de desvio causar
uma falta de página ou uma violação de proteção, o processador
interromperá a busca antecipada da instrução, até que tenha certeza
de que essa instrução deve ser mesmo buscada.
Análises de comportamento de programas mostram que desvios
condicionais são tomados em mais de 50% das vezes.
Se o custo da busca antecipada de instruções for o mesmo em
qualquer caminho, o resultado obtido deverá ser melhor se a busca
antecipada de instruções for sempre efetuada a partir do endereçoalvo do desvio.
Arquitetura de Computadores
Profa Luiza Mourelle
Entretanto, em uma máquina que usa paginação, a busca antecipada
de instruções, a partir do endereço de desvio, tem maior
probabilidade de causar uma falta de página do que a busca de
instruções consecutivas à instrução de desvio.
A previsão de desvio com base no código de operação da instrução
de desvio pressupõe que para determinados códigos o desvio é
sempre tomado e para outros não, havendo um aproveitamento de
75%.
Estratégias dinâmicas de previsão de desvio mantêm um histórico
sobre as instruções de desvio condicional, i.e. um ou mais bits
(chaves de desvio tomado ou de desvio não tomado) são associados
a cada instrução de desvio condicional.
Arquitetura de Computadores
Profa Luiza Mourelle
Utilizando-se somente um bit de histórico, pode-se registrar se a
última execução da instrução resultou em desvio ou não.
Uma desvantagem neste caso ocorre quando o desvio é quase
sempre tomado, tal como em instruções de desvio usadas para
implementar laços de repetição. Sempre ocorrerão dois erros de
previsão de desvio, cada vez que o laço de repetição for executado:
uma vez na entrada e outra na saída.
Atraso de desvio consiste em reordenar as instruções, de modo que
as instruções de desvio ocorram mais tarde.
Arquitetura de Computadores
Profa Luiza Mourelle