AULA 06 - MIPS
PIPELINE
1998 Morgan Kaufmann Publishers
1
IMPLEMENTAÇÃO DO MIPS MONOCICLO
RegDst
MemtoReg
Zero
ALUSrc
RegWrite
MemRead
Control
Branch
MemWrite
ALUControl
ALUOp
1998 Morgan Kaufmann Publishers
2
1998 Morgan Kaufmann Publishers
3
PC
R
I
A
B
ALUOut
M
D
R
1998 Morgan Kaufmann Publishers
4
PASSOS relativos ao MIPS Multiciclo
Aritmética
reg-reg
Branch
Step 3
1998 Morgan Kaufmann Publishers
5
PASSOS (CICLOS)
Passo 1: Busca da instrução (Instruction Fetch)
Passo 2: Decod. da Instrução e Busca de Registradores
Passo 3 (dependente da instrução)
Referência à memória: ALUOut = A + sign-extend(IR[15-0]);
Aritmética Reg-Reg: ALUOut = A op B;
Aritmética Reg-Imm: ALUOut = A op Imm;
Branch: se (A==B) PC = ALUOut;
Passo 4 (Aritmética ou acesso à memória)
Acesso à memória através de loads e stores
MDR = Memory[ALUOut]; ou Memory[ALUOut] = B;
Fim das instruções R-type: Reg[IR[15-11]] = ALUOut;
Passo 5 (Write-back, para instrução load)
Reg[IR[20-16]]= MDR;
1998 Morgan Kaufmann Publishers
6
MULTICICLO x PIPELINE
• Multiciclo: a instrução é executada em vários estágios (S) sequenciais.
S2
Latch
Latch
Latch
S1
Sk
Estágio ATIVO no ciclo 2
Apenas uma instrução por vez.
• Pipeline: vários estágios funcionam juntos para instruções diferentes.
instrução i
S2
instrução i - 1
Latch
Latch
Latch
S1
Sk
instrução i – (k -1)
k instruções por vez.
1998 Morgan Kaufmann Publishers
7
Pipeline: é natural!
• Exemplo de Lavanderia
• Tem-se os volumes A, B, C e D de
roupas para lavar, secar e passar
• A lavadora leva 30 minutos
• A secadora leva 40 minutos
• “Passadeira” leva 20 minutos
A
B
C
D
1998 Morgan Kaufmann Publishers
8
Lavanderia Sequencial
6
7
8
9
10
11 Meia noite
Tempo
30 40 20 30 40 20 30 40 20 30 40 20
T
a
s
k
A
B
O
r
d
e
r
C
D
• A lavanderia sequencial leva 6 horas para 4 volumes
• Se usarem o “pipeline”, quanto tempo levaria?
1998 Morgan Kaufmann Publishers
9
Lavanderia em Pipeline
6
7
8
9
10
11 Meia noite
Tempo
30 40
o
r
d
e
m
40
40
40 20
A
B
C
D
• Lavanderia em Pipeline leva 3.5 horas
1998 Morgan Kaufmann Publishers
10
Lições sobre o Pipeline
6
7
8
30 40
A
B
C
D
40
40
O Pipeline ajuda melhorar o
throughput de um trabalho por
completo
•
A taxa do Pipeline é limitada
pelo estágio mais lento
•
Speedup ideal = Número de
estágios
•
Comprimentos desbalanceados
dos estágios do pipeline
reduzem o speedup
•
O tempo para “preencher” o
pipeline e o tempo para
“limpar” o pipeline reduzem o
speedup
9
Tempo
o
r
d
e
m
•
40 20
1998 Morgan Kaufmann Publishers
11
Pipelines em Computadores
• Executa bilhões de instruções, tal que o importante seja o throughput
• Fatores desejados:
– todas as instruções tenham o mesmo comprimento,
– os campos de registradores sejam localizados numa mesma posição
no formato de instrução,
– referências à memória somente através de instruções loads ou stores
• Speedup: para um programa de n instruções, num computador pipeline de k estágios,
relativo a um computador multiciclo de k ciclos, considerando mesmo tempo de ciclo.
Tempo do multiciclo = n . k .tempociclo
Tempo do pipeline = (k + n-1).tempociclo
Speedup = tempo do multiciclo/tempo do pipeline = n.k/ (k + n - 1)
Para n grande, speedup ~ k
1998 Morgan Kaufmann Publishers
12
Pipeline no MIPS
multiciclo
pipeline
1998 Morgan Kaufmann Publishers
13
Implementação do Pipeline
•
O que facilita:
– Todas as instruções com mesmo comprimento
– Somente poucos formatos de instruções
– Os operandos de memória aparecem somente em loads e stores
•
O que difículta:
– conflitos estruturais: supor que temos somente uma memória
– conflitos de controle: preocupar com instruções de branch
– conflitos de dados: uma instrução depende de uma instrução
prévia
– Manipulação de exceções
– Melhorar o desempenho com execução fora-de-ordem, etc.
1998 Morgan Kaufmann Publishers
14
Idéia Básica
SOMADOR
REGS.
SOMADOR
MEM.
INSTR.
ALU
MEM.
DADOS
1998 Morgan Kaufmann Publishers
15
Fluxo de dados com latch’s entre os estágios
IF/ID
somador
ID/EX
EX/MEM
somador
MEM/WB
Regist.
PC
ALU
Mem.
Instr.
Mem.
dados
1998 Morgan Kaufmann Publishers
16
Pipelines representados graficamente
Time (in clock cycles)
Program
execution
order
(in instructions)
lw $10, 20($1)
sub $11, $2, $3
CC 1
CC 2
CC 3
CC 4
CC 5
IM
Reg
ALU
DM
Reg
IM
Reg
ALU
DM
CC 6
Reg
1998 Morgan Kaufmann Publishers
17
CONTROLE DO PIPELINE
PCSrc
Branch
RegWrite
Regs.
Mem
Read
ALUSrc
PC
Mem
toReg
ALU
Mem.
Inst.
ALUOp
Mem. Mem
dados Write
RegDst
1998 Morgan Kaufmann Publishers
18
Controle do Pipeline
•
O que necessita ser controlado em cada estágio?
–
–
–
–
–
•
Busca de Instrução e Incremento do PC
Decodificação da Instrução / Busca de Registradores
Execução
Estágio de Memória
Write Back
Cada estágio deve funcionar para uma determinada instrução,
simultaneamente a outros estágios.
1998 Morgan Kaufmann Publishers
19
Os sinais são repassados pelos estágios
Controle do Pipeline
como os dados
Execution/Address Calculation Memory access stage
control lines
stage control lines
Mem Mem
Reg ALU ALU ALU
Src Branch Read Write
Op0
Op1
Instruction Dst
0
0
0
0
0
1
1
R-format
lw
0
1
0
1
0
0
0
sw
1
0
0
1
0
0
X
beq
0
0
1
0
1
0
X
IF/ID
ID/EX
EX/MEM
Write-back
stage control
lines
Reg Mem to
write Reg
0
1
1
1
X
0
X
0
MEM/WB
1998 Morgan Kaufmann Publishers
20
Fluxo de dados e controle
PCSrc
MemtoReg
MemRead
Branch
RegWrite
ALUOp
MemWrite
RegDst
1998 Morgan Kaufmann Publishers
21
Dependências de dados
•
•
Pode ocorrer iniciando uma instrução antes de terminar a anterior
dependências que “vão retroceder no tempo” são conflitos de dados
Time (in clock cycles)
CC 1
Value of
register $2: 10
CC 2
CC 3
CC 4
CC 5
CC 6
CC 7
CC 8
CC 9
10
10
10
10/– 20
– 20
– 20
– 20
– 20
DM
Reg
Program
execution
order
(in instructions)
sub $2, $1, $3
and $12, $2, $5
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)
IM
Reg
IM
DM
Reg
IM
DM
Reg
IM
Reg
DM
Reg
IM
Reg
Reg
Reg
DM
Reg
1998 Morgan Kaufmann Publishers
22
Solução por Antecipação – usar os resultados
temporários, sem esperar que eles sejam escritos
- Atuar no caminho do banco de registr. p/ substituir o valor de leit/escrita de registrador
- Antecipação da ALU
Time (in clock cycles)
CC 1
Value of register $2 : 10
Value of EX/MEM : X
Value of MEM/WB : X
CC 2
CC 3
CC 4
CC 5
CC 6
CC 7
CC 8
CC 9
10
X
X
10
X
X
10
– 20
X
10/– 20
X
– 20
– 20
X
X
– 20
X
X
– 20
X
X
– 20
X
X
DM
Reg
Program
execution order
(in instructions)
sub $2, $1, $3
and $12, $2, $5
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)
IM
Reg
IM
Reg
IM
DM
Reg
IM
Reg
DM
Reg
IM
Reg
DM
Reg
Reg
DM
Reg
1998 Morgan Kaufmann Publishers
what if this $2 was $13?
23
Solução por Antecipação
Unidade de antecipação
1998 Morgan Kaufmann Publishers
24
Antecipação do estágio EX/MEM
sub $2,$1,$3
Seleciona MUX
do lado A
da ALU para
antecipação
EX/MEMRegWrite
$5
Rt
Rs
$2
EX/MEMRegisterRd
$2
RegWrite
and $12,$2,$5
Seleciona MUX
do lado B
da ALU para
antecipação
1998 Morgan Kaufmann Publishers
25
Antecipação do estágio MEM/WB
Seleciona MUX
do lado A
da ALU para
antecipação
$2
MEM/WBRegWrite
$2
Rt
Rs
$6
MEM/WBRegisterRd
sub $2,$1,$3
RegWrite
or $13,$6,$2
Seleciona MUX
do lado B
da ALU para
antecipação
1998 Morgan Kaufmann Publishers
26
=
=
MUX A
SA1
MUX A
SA0
SELEÇÃO DO
MUX A
MEM/WBRegWrite
Rt
MEM/WBRegisterRd
10
EX/MEMRegWrite
Rs
01
Rs
00
MUX B
10
Rt
01
EX/MEMRegisterRd
00
MUX A
CIRCUITO DE ANTECIPAÇÃO (FORWARDING UNIT)
=
=
MUX B
SB0
MUX B
SB1
SELEÇÃO DO
MUX B
1998 Morgan Kaufmann Publishers
27
Nem sempre é possível solucionar por antecipação (Fazer
o Load de uma palavra pode causar um conflito)
- Se uma instrução tenta ler um registrador seguindo uma instrução de
load word que escreve no mesmo registrador.
Time (in clock cycles)
Program
CC 1
execution
order
(in instructions)
lw $2, 20($1)
and $4, $2, $5
or $8, $2, $6
add $9, $4, $2
slt $1, $6, $7
•
IM
CC 2
CC 3
Reg
IM
CC 4
CC 5
DM
Reg
Reg
IM
DM
Reg
IM
CC 6
CC 8
CC 9
Reg
DM
Reg
IM
CC 7
Reg
DM
Reg
Reg
DM
Reg
Portanto, necessitamos que a unidade de detecção de conflitos
1998 Morgan Kaufmann Publishers 28
paralize, em um ciclo, as instruções seguintes ao load word
Parada (Stall)
manter instruções nos mesmos estágios
1998 Morgan Kaufmann Publishers
29
Parada com inserção de nop a partir do estágio EX
lw $2,20($1)
IM
Reg
DM
DM
nop
and $4,$2,$5
or $8, $2, $8
add $9, $4, $2
slt $1, $6, $7
Reg
IM
Reg
Reg
IM
IM
Reg
DM
Reg
IM
Reg
DM
Reg
IM
Reg
DM
Reg
Reg
DM
Reg
1998 Morgan Kaufmann Publishers
30
Unidade de detecção de conflitos
• A parada faz com que uma instrução que não faz nada (nop) prossiga
1998 Morgan Kaufmann Publishers
31
Exemplo de inserção de parada
sinais 0
1998 Morgan Kaufmann Publishers
32
Conflitos de Desvio (Branch)
•
Quando é decidido pelo branch, outras instruções estão em pipeline!
Time (in clock cycles)
Program
execution
CC 1
CC 2
order
(in instructions)
40 beq $1, $3, 7
44 and $12, $2, $5
48 or $13, $6, $2
52 add $14, $2, $2
72 lw $4, 50($7)
•
IM
CC 3
Reg
IM
CC 4
CC 5
DM
Reg
Reg
IM
DM
Reg
IM
CC 6
CC 8
CC 9
Reg
DM
Reg
IM
CC 7
Reg
DM
Reg
Reg
DM
Reg
O pipeline equivale a previsão de “não ocorrer branch”
– Solução: hardware para desprezar as instruções posteriores
1998 Morgan Kaufmann Publishers 33
caso haja branch
Controle para limpar as instruções posteriores
além de antecipar o cálculo da condição
IFFlush
1998 Morgan Kaufmann Publishers
34
Exemplo de beq e atualização do PC
44
and $12,$2,$5
40
beq $1,$3,7
endereço 72
lw $4, 50($7)
Resulta em NOP
1998 Morgan Kaufmann Publishers
35
RESULTADO DO CONTROLE DE DESVIO
Necessidade de limpar apenas uma instrução
1998 Morgan Kaufmann Publishers
36
Melhorando o desempenho
•
Tentar evitar paradas! P.ex., reordenar essas instruções:
lw
lw
sw
sw
•
$t0,
$t2,
$t2,
$t0,
0($t1)
4($t1)
0($t1)
4($t1)
Adicionar um “branch delay slot”
– permitindo que a próxima instrução seguida do branch seja
sempre executada
– Confiar no compilador para preencher o slot com algo útil
•
Processador Superescalar: iniciar mais que uma instrução no
mesmo ciclo
1998 Morgan Kaufmann Publishers
37
MIPS superescalar
1998 Morgan Kaufmann Publishers
38
MIPS superescalar
Tipo de
instrução
Estágios do pipeline
R ou desvio
IF
ID
EX MEM WB
Load/store
IF
ID
EX MEM WB
R ou desvio
IF
ID
EX
MEM WB
Load/store
IF
ID
EX
MEM WB
R ou desvio
IF
ID
EX
MEM WB
Load/store
IF
ID
EX
MEM WB
R ou desvio
IF
ID
EX
MEM WB
Load/store
IF
ID
EX
MEM WB
1998 Morgan Kaufmann Publishers
39
EXEMPLO
O código:
loop: lw
add
sw
addi
bne
$t0, 0 ($s1)
$t0, $t0,$s2
$t0, 0($s1)
$s1, $s1, -4
$s1, $zero, loop
# t0 = elemento de array
# soma o elemento do array a um valor escalar em $s2
# armazena o resultado
# decrementa o ponteiro
# desvia para loop se $s1 diferente de 0
pode ser escalonado para o MIPS superescalar da seguinte forma:
R ou desvio
loop:
Load/store
Ciclo de clock
lw
1
$t0, 0($s1)
addi $s1, $s1,-4
2
add $t0 , $t0, $s2
3
bne $s1, $zero, loop sw
$t0, 4($s1)
4
5 instruções em 4 ciclos
1998 Morgan Kaufmann Publishers
40
Desdobramento de laço (loop unrolling)
loop:
R ou desvio
Load/store
Ciclo
de clock
Observações
addi $s1, $s1, -16
lw $t0, 0 ($s1)
1
$s1 inicial
lw $t1, 12($s1)
2
$s1 = $s1 - 16
add $t0, $t0, $s2
lw $t2, 8($s1)
3
add $t1, $t1, $s2
lw $t3, 4($s1)
4
add $t2, $t2, $s2
sw $t0, 16($s1) 5
add $t3, $t3, $s2
sw $t1, 12($s1) 6
16($s1) =
$s1 inicial
sw $t2, 8($s1) 7
bne $s1, $zero, loop sw $t3, 4($s1) 8
14 instruções em 8 ciclos
1998 Morgan Kaufmann Publishers
41
Escalação Dinâmica
•
O hardware realiza a “escalação”
– O hardware tenta encontrar instruções para executar
– É possível execução fora de ordem
– Execução especulativa e previsão dinâmica de desvio (branch)
– DEC Alpha 21264: tem 9 estágios pipeline, 6 instruções
simultâneas
– PowerPC e Pentium: tabela de história de desvio
– É importante a tecnologia do compilador
1998 Morgan Kaufmann Publishers
42
Escalação Dinâmica
Despacho em ordem
Unidades
funcionais
Execução
fora de ordem
Unidade de Comprometimento:
escrita final do resultado
em ordem
43
1998 Morgan Kaufmann Publishers
A microarquitetura do Pentium 4
1998 Morgan Kaufmann Publishers
44
Multiprocessadores
•
criar computadores potentes conectando muitos computadores pequenos
Processor
Processor
Processor
Cache
Cache
Cache
Processor
Processor
Processor
Cache
Cache
Cache
Memory
Memory
Memory
Single bus
Memory
I/O
Network
Multiprocessador de memória
compartilhada centralizada
Multiprocessador de memória
distribuída
1998 Morgan Kaufmann Publishers
45
CPU de um único thread
•
Thread é uma seqüência de instruções de um programa
RAM - Diferentes cores = quatro
diferentes programas em
execução na memória
Front end – busca até
4 instruções
7 Pipelines, sendo apenas
o programa de cor vermelha
em execução
Nota-se os espaços
em branco dos estágios
pipeline ociosos
1998 Morgan Kaufmann Publishers
46
Single Threaded SMP (Symmetric Multiprocessor)
Os diferentes programas
são executados em CPUs
distintos para não deixar
muitos programas em
espera.
Programa vermelho
numa CPU
amarelo em outra
1998 Morgan Kaufmann Publishers
47
Superthreading ou multithreading
• CPU com capacidade para
executar mais de um thread
simultaneamente,
porém, cada estágio do
pipeline deve conter
instruções de apenas um
thread
•
Não se pode emitir
instruções de threads
distintos num mesmo
instante
1998 Morgan Kaufmann Publishers
48
Hyper-threading (HT)
Simultaneous multithreading (SMT)
•
Não existe restrição de
emissão de instruções
para threads diferentes
em cada clock.
•
Compara-se ao singlethreaded SMP
Single-threaded SMP
1998 Morgan Kaufmann Publishers
49
Formas de Execução dos Threads
Superscalar
Multithreading
Simultaneous
Multithreading
Clock cycles
Empty
Thread 1
Thread 2
Thread 3
Thread 4
Issue slots
1998 Morgan Kaufmann Publishers
50
Chips de um único CORE
Superescalar
SMT
1998 Morgan Kaufmann Publishers
51
Processadores Multi-Core
•
Um único chip com múltiplos cores
(CPUs), cada um executando
threads distintos como em singlethreaded SMP
•
Compatível em softare a uma
arquitetura SMT porém
tecnologicamente mais interessante,
pois usando tecnologia que
consome menos energia pode ser
usado, e o desempenho aumenta
com o número de CORES.
1998 Morgan Kaufmann Publishers
52
REFERÊNCIAS SOBRE SMT E MULTICORE
• http://arstechnica.com/articles/paedia/cpu/hyperthreading.ars
•
http://www.intel.com/cd/ids/developer/asmo-na/eng/211198.htm?page=1
1998 Morgan Kaufmann Publishers
53