Pipelining
Ana Cristina Alves de Oliveira
[email protected]
Arquitetura de Computadores
Mestrado em Ciências da Computação
Depto. de Sistemas e Computação – UFCG
Roteiro
Introdução
 Visão Geral sobre Pipelining
 Pipeline Superescalar
 Pipeline Dinâmico
 Exemplos
 Resumo
 Conclusões
 Referências

Introdução






Pipeline é uma técnica que explora o paralelismo
entre as instruções, considerando um fluxo de
execução sequencial
É invisível ao programador
O pipeline começa uma instrução a cada ciclo de
clock
Não reduz o tempo gasto para completar uma
instrução
Aumenta a vazão das instruções iniciadas e
terminadas na unidade de tempo
Estamos considerando o processador deste
trabalho como sendo o MIPS
Tempo entre Instruções (Ti)

Tipipeline = Tinão-pipeline / nº de estágios
Classe
Busca
Leit.
Reg
Op. ULA
Aces.
Dado
Escr.
Reg
Tempo
Total
Load word
(lw)
2 ns
1 ns
2 ns
2 ns
1 ns
8 ns
Store word
(sw)
2 ns
1 ns
2 ns
2 ns
Add, sub,
and, or, slt
2 ns
1 ns
2 ns
beq
2 ns
1 ns
2 ns
7 ns
1 ns
6 ns
5 ns
Conflitos do Pipeline: Estruturais e
de Controle

Conflitos estruturais
– O hardware não pode suportar a combinação de
instruções no mesmo ciclo de clock
– Exemplo: Suponha que exista apenas uma memória
para dados e instruções. Ocorrerá este conflito se
uma instrução acessar um dado na memória (lw),
enquanto outra tenta escrever na memória (sw)
simultaneamente

Conflitos de controle
– Necessidade de tomar uma decisão com base nos
resultados de uma instrução, enquanto outras estão
sendo executadas
Conflitos do Pipeline: Soluções para o
Conflito de Controle (1)

Parada do Pipeline: conhecida como “bolha”
– Execução sequencial com a inserção de uma instrução de nop
após um desvio condicional
– Degrada o desempenho consideravelmente

Predição
– Em geral, é adotada para tratar os desvios condicionais
executados em pipeline
– Não retarda o pipeline se a previsão for correta
– Esquema simples: sempre predizer que a condição vai falhar
– Preditores dinâmicos em hardware fazem predições dependendo
do comportamento anterior de cada desvio
Conflitos do Pipeline: Soluções para o
Conflito de Controle (2)

Decisão retardada: conhecida como
“desvio retardado” (delayed branch)
– Sempre executa a instrução seguinte à
instrução de desvio, cuidando para que a
escolha seja uma instrução não afetada pela
decisão do desvio
– Tipicamente, os compiladores preenchem
cerca de 50% dos slots que seguem o desvio
condicional com instruções úteis
– Utilizada no processador MIPS
Conflitos do Pipeline: Conflitos por
Dados

Conflitos por dados
– A execução de uma instrução depende do
resultado de outra, que ainda está no pipeline
– Não é preciso esperar o término da instrução
para tentar resolver este conflito
– Solução
 Adiantamento ou bypass: obtenção antecipada de
determinado item faltante a uma operação, a partir
de recursos internos da máquina
Conflitos do Pipeline: Reordenação
do Código para Evitar Paradas

Encontre o conflito deste código:
lw $t0, 0($t1)
lw $t2, 4($t1)
sw $t2, 0($t1)
sw $t0, 4($t1)

#
#
#
#
#
reg $t1 possui o end. de v[k]
reg $t0 (temp) = v[k]
reg $t2 = v[k+1]
v[k] = reg $t2
v[k+1] = reg $t0 (temp)
Reordene as instruções de modo a evitar
parada do pipeline em função do conflito
Conflitos do Pipeline: Reordenação
do Código para Evitar Paradas

Código reordenado deste código:
lw $t0, 0($t1)
lw $t2, 4($t1)
sw $t0, 4($t1)
sw $t2, 0($t1)

#
#
#
#
#
reg $t1 possui o end. de v[k]
reg $t0 (temp) = v[k]
reg $t2 = v[k+1]
v[k+1] = reg $t0 (temp)
v[k] = reg $t2
A troca de lugar das 2 instruções de store
elimina a possibilidade do conflito
Código em C para a Função
swap(int v[], int k) {
int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}
Pipeline Superescalar
Replicação dos componentes internos do
processador para que ele possa colocar várias
instruções em cada estágio do pipeline
 Permite que a taxa de instruções prontas na
unidade de tempo exceda à taxa do clock
 Exemplo: um processador de 1000Mhz,
superescalar, com 4 instruções simultâneas pode
operar em uma taxa de pico de 4 bilhões de
instruções por segundo
 Desvantagem: trabalho extra de manutenção

Pipeline Dinâmico
Ou Escalonamento Dinâmico do Pipeline
 Executado pelo hardware para evitar
conflitos no pipeline

– É normalmente associado a recursos extras
de hardware
– As instruções posteriores podem prosseguir
em paralelo

O modelo de execução de instruções é
bem mais complexo
Exemplo 1: Implementação Simples de
Pipeline
Especificações : É como o MIPS, exceto por:
•Não modifica a ordem de execução (sem desvio retardado e sem
reescalonamento por software)
•Registradores não podem ser lidos e escritos em um mesmo ciclo de
clock
•Após um desvio, não se pode fazer uma busca por nova instrução
até que a comparação seja feita
•Sem adiantamento
Complete os estágios do pipeline a seguir ==>
and $4, $6, $5
sub $8, $6, $5
Or $7, $4, $8
bne $5, $5, exit
sw $3, 4($4)
lw $10, 4 ($4)
add$12, $10, $11
IF
ID
IF
AL
ID
IF
MR
AL
n
WB
MR
n
WB
n
ID
IF
AL
ID
MR
AL MR
IF
WB
ID
Exemplo 2: Implementação de
pipeline para MIPS
10
lw
r1, r2(35)
14
addI r2, r2, 3
20
sub
r3, r4, r5
24
beq
r6, r7, 100
30
ori
r8, r9, 17
34
add
r10, r11, r12
100
and
r13, r14, 15
Estes endereços estão em octal
Desvio atrasado é tarefa do compilador:
‘ori’ será uma tarefa fora da ordem
Início: Busca10
n
WB
Ctrl
A
Exec
im
Reg
File
Mem
Ctrl
rs rt
S
M
=
PC
10
D
Mem
Acces
s
Data
Mem
B
Next PC
IR
n
Reg.
File
n
Decode
Inst. Mem
n
IF 10
lw
r1, r2(35)
14
addI r2, r2, 3
20
sub
r3, r4, r5
24
beq
r6, r7, 100
30
ori
r8, r9, 17
34
add
r10, r11, r12
100 and
r13, r14, 15
n
n
WB
Ctrl
Mem
Ctrl
A
S
M
Reg.
File
im
Exec
rt
Reg
File
2
=
PC
14
D
Mem
Acces
s
Data
Mem
B
Next PC
IR
n
Decode
lw r1, r2(35)
Inst. Mem
Busca 14, Decodifica 10
ID 10
lw
r1, r2(35)
IF 14
addI r2, r2, 3
20
sub
r3, r4, r5
24
beq
r6, r7, 100
30
ori
r8, r9, 17
34
add
r10, r11, r12
100 and
r13, r14, 15
n
WB
Ctrl
S
M
Reg.
File
r2
n
Mem
Ctrl
Exec
35
Reg
File
lw r1
rt
2
=
PC
20
D
Mem
Acces
s
Data
Mem
B
Next PC
IR
Decode
addI r2, r2, 3
Inst. Mem
Busca 20, Decodifica 14, Exec 10
EX 10
lw
ID 14
addI r2, r2, 3
IF 20
sub
r3, r4, r5
24
beq
r6, r7, 100
30
ori
r8, r9, 17
34
add
r10, r11, r12
100 and
r1, r2(35)
r13, r14, 15
n
WB
Ctrl
D
Reg.
File
M
Mem
Acces
s
Data
Mem
Mem
Ctrl
r2+35
Exec
3
Reg
File
r2
lw r1
addI r2, r2, 3
5
4
B
PC
24
=
Next PC
IR
Decode
sub r3, r4, r5
Inst. Mem
Busca 24, Decod. 20, Exec 14, Mem 10
M 10
lw
EX 14
addI r2, r2, 3
ID 20
sub
r3, r4, r5
24
beq
r6, r7, 100
30
ori
r8, r9, 17
34
add
r10, r11, r12
IF
100 and
r1, r2(35)
r13, r14, 15
M[r2+35]
D
PC
Next PC
Mem
Acces
s
Data
Mem
=
WB
Ctrl
Reg.
File
r2+3
Exec
Reg
File
IR
Mem
Ctrl
lw r1
addI r2
Decode
Inst. Mem
Busca 30, Dcd 24, Ex 20, Mem 14, WB 10
WB 10
M 14
lw
r1, r2(35)
addI r2, r2, 3
EX 20
ID 24
sub
r3, r4, r5
beq
r6, r7, 100
IF 30
ori
r8, r9, 17
add
r10, r11, r12
34
100 and
r13, r14, 15
M[r2+35]
D
Mem
Acces
s
Data
Mem
Mem
Ctrl
lw r1
addI r2
r2+3
sub r3
sub
Exec
WB
Ctrl
7
r4
Reg.
File
6
Reg
File
IR
Decode
beq r6, r7 100
Inst. Mem
Busca 30, Dcd 24, Ex 20, Mem 14, WB 10
r5
30
WB 10
M 14
lw
r1, r2(35)
addI r2, r2, 3
EX 20
ID 24
sub
r3, r4, r5
beq
r6, r7, 100
IF 30
ori
r8, r9, 17
add
r10, r11, r12
PC
Next PC
=
Note que o desvio retardado: sempre executa ori após beq
34
100 and
r13, r14, 15
WB
Ctrl
r1=M[r2+35]
x
x
x
Mem
Ctrl
Reg.
File
x
x
x
Exec
x
x
x
Reg
File
IR
x
Decode
Inst. Mem
Busca 34, Dcd 30, Ex 24, Mem 20, WB 14
=
34
PC
Next PC
D
Take the branch – r6-r7 = 0
Mem
Acces
s
Data
Mem
x
10
WB 14
M 20
lw
r1, r2(35)
addI r2, r2, 3
sub
r3, r4, r5
EX 24
ID 30
beq
r6, r7, 100
ori
r8, r9, 17
34
add
r10, r11, r12
IF 100 and r13, r14, 15
r1=M[r2+35]
WB
Ctrl
Reg.
File
addI r2
Mem
Ctrl
r2+3
sub r3
r4-r5
r6
9
Exec
100
beq
xx
Reg
File
IR
Decode
ori r8, r9 17
=0
PC
34
D
Take the branch – r6-r7 = 0
Mem
Acces
s
Data
Mem
r7
Next PC
Inst. Mem
Busca 34, Dcd 30, Ex 24, Mem 20, WB 14
10
WB 14
M 20
lw
r1, r2(35)
addI r2, r2, 3
sub
r3, r4, r5
EX 24
ID 30
beq
r6, r7, 100
ori
r8, r9, 17
34
add
r10, r11, r12
IF 100 and r13, r14, 15
WB
Ctrl
Reg.
File
sub r3
Mem
Ctrl
r4-r5
Exec
beq
ori r8
17
r9
or
xxx
Decode
IR
11 12
Reg
File
add r10, r11, r12
Inst. Mem
Busca 100, Dcd 34, Ex 30, Mem 24, WB 20
r1=M[r2+35]
r2 = r2+3
100
PC
Next PC
D
Problema?
Mem
Acces
s
Data
Mem
x
10
lw
r1, r2(35)
14
addI r2, r2, 3
20
sub
r3, r4, r5
24
beq
r6, r7, 100
30
ori
r8, r9, 17
34
add
r10, r11, r12
100 and
r13, r14, 15
WB
Ctrl
Reg.
File
sub r3
Mem
Ctrl
r4-r5
beq
xxx
ori r8
17
r9
or
Exec
Decode
IR
11 12
Reg
File
add r10, r11, r12
Inst. Mem
Busca 100, Dcd 34, Ex 30, Mem 24, WB 20
r1=M[r2+35]
r2 = r2+3
100
PC
Next PC
D
Apenas 1 instrução deveria estar atrasada
Mem
Acces
s
Data
Mem
x
10
lw
r1, r2(35)
14
addI r2, r2, 3
20
sub
r3, r4, r5
24
beq
r6, r7, 100
30
ori
r8, r9, 17
34
add
r10, r11, r12
100 and
r13, r14, 15
Busca 104, Dcd 100, Ex 34, Mem 30, WB 24
WB
Ctrl
Reg.
File
beq
xxx
D
Mem
Acces
s
Data
Mem
ori r8
add r10
xx
Mem
Ctrl
r9 | 17
Decode
r11
add
Exec
IR
14 15
Reg
File
and r13, r14, r15
Inst. Mem
n
r1=M[r2+35]
r2 = r2+3
r3 = r4-r5
104
PC
Next PC
r12
Destrói a instrução extra
10
lw
r1, r2(35)
14
addI r2, r2, 3
20
sub
r3, r4, r5
24
beq
r6, r7, 100
30
ori
r8, r9, 17
34
add
r10, r11, r12
100 and
r13, r14, 15
Busca 108, Dcd 104, Ex 100, Mem 34, WB 30
ori r8
add r10
and r13
Mem
Ctrl
WB
Ctrl
PC
108
D
Reg.
File
r9 | 17
Mem
Acces
s
Data
Mem
r15
r11+r12
Exec
r14
Next PC
IR
Reg
File
xx
Decode
Inst. Mem
n
r1=M[r2+35]
r2 = r2+3
r3 = r4-r5
10
lw
r1, r2(35)
14
addI r2, r2, 3
20
sub
r3, r4, r5
24
beq
r6, r7, 100
30
ori
r8, r9, 17
34
add
r10, r11, r12
100 and
r13, r14, 15
Busca 112, Dcd 108, Ex 104, Mem 100, WB 34
114
PC
Next PC
D
NO WB
NO Ovflow
WB
Ctrl
Reg.
File
add r10
r11+r12
Mem
Ctrl
Mem
Acces
s
Data
Mem
and r13
r14 & R15
Exec
IR
Reg
File
Decode
Inst. Mem
n
r1=M[r2+35]
r2 = r2+3
r3 = r4-r5
r8 = r9 | 17
10
lw
r1, r2(35)
14
addI r2, r2, 3
20
sub
r3, r4, r5
24
beq
r6, r7, 100
30
ori
r8, r9, 17
34
add
r10, r11, r12
100 and
r13, r14, 15
Destrói a instrução extra
Resumo

O que o torna fácil o pipeline?
– Todas as instruções têm o mesmo tamanho
– Poucos formatos para a instrução
– Operandos da memória aparecem apenas em loads e
stores

O que o torna fácil o pipeline?
– Conflitos estruturais: caso exista apenas 1 memória
para instruções e dados
– Conflitos de controle: preocupação com instruções de
desvio
– Conflitos de dados: instruções que depedem de
instruções anteriores
Resumo
5
Estágios:
– Busca: busca instruções na memória
– Decodificação: pega o valor do registrador e decodifica as
informações de controle
– Execução: executa operações aritméticas/cálculo de endereços
– Memória: faz operações da mémoria (load e store)
– Escreve no registrador: escreve resultados de volta nos
registradores
 Pipelines
passam o controle da informação pelo pipe assim
como os dados se movem no pipe
 Balancear o tamanho das instruções torna o pipeline mais
suave
 Aumentar o tamanho do pipeline, aumenta o impacto de
conflitos
Conclusões



O pipeline melhora o throughput, mas não altera o
tempo de execução de uma instrução
A latência introduz dificuldades devido às dependências
nos programas
Redução do custo das dependências com:
– Hardware para adiantamento de dados
– Predição de desvios


Processamento superescalar e escalonamento dinâmico
tem melhorado cerca de 60% ao ano o desempenho dos
processadores desde 1986
Com os avanços na tecnologia de processamento, o
sistema de memória é que passa a ser o gargalo (lei de
Amdahl)
Referências




Patterson, D. A.; Hennessy, J. L. Organização e projeto
de computadores: A interface HARDWARE/SOFTWARE.
Rio de Janeiro, LTC, 2ª ed., 2000.
Programmed Introdution to MIPS Assembly Language.
http://chortle.ccsu.edu/AssemblyTutorial/TutorialContent
s.html.
SPIM - A MIPS32 Simulator.
http://www.cs.wisc.edu/~larus/spim.html
Aplicações Avançadas de Microprocessadores:
Colectânea de Problemas.
http://tahoe.inesc.pt/~aml/ist/aam98/problemas/proble
mas.html
Contato

Ana Cristina A. de Oliveira
– [email protected]
– www.dsc.ufcg.edu.br/~cristina

Projeto Failure Spotter
– www.spotter.lsd.ufcg.edu.br