Conflitos
Aula 9
31 de Março de 2005
1
Estrutura desta aula
z
z
z
z
z
z
z
Taxonomia dos conflitos
Dependências entre instruções
Conflitos num pipeline
Conflitos estruturais
Conflitos de dados
Conflitos de controlo
Ref: Hennessy e Patterson, A2, A4
Patterson e Hennessy, 6.4-6.6
31 de Março de 2005
Arquitectura de Computadores 2004/05
2 - Aula 9
Taxonomia dos conflitos
z
3 diferentes tipos de conflitos (“hazards”) podem atrasar
a execução das instruções no pipeline:
• Conflitos estruturais: uma instrução no pipeline necessita
•
•
de um recurso que está a ser usado por outra instrução no
pipeline
Conflitos de dados: uma instrução no pipeline tem a sua
execução dependente dos resultados de outras instruções
anteriores que estão no pipeline => dependência de
instruções que podem ou não gerar conflitos de dados
Conflitos de controlo: alterações ao fluxo normal do
programa só conhecidas em andares posteriores do pipeline
e o fetch de uma instrução é feito no primeiro andar
•
por exemplo, BEQ R1,R2,offset só faz o teste à igualdade ou
desigualdade entre R1 e R2 no andar EX do pipeline
31 de Março de 2005
Arquitectura de Computadores 2004/05
3 - Aula 9
Conflitos estruturais (1)
z
z
z
Conflito estrutural quando duas ou mais instruções no
pipeline querem utilizar o mesmo recurso de hardware no
mesmo ciclo de relógio
Exemplos:
•
•
•
Um único somador serve para os Branches e para a ALU
Múltiplos acessos a uma Memória única
Múltiplos acessos à Register File
Soluções
•
Provocar uma bolha (stall) no pipeline (veremos à frente
como implementar uma bolha)
•
•
A bolha atrasa a instrução que se segue no pipeline e todas as
instruções posteriores (mais à frente no programa)
Replicar os recursos de hardware envolvidos no conflito
31 de Março de 2005
Arquitectura de Computadores 2004/05
4 - Aula 9
Conflitos estruturais (2)
z
Exemplo 1:
31 de Março de 2005
Sem o ADDER#2, o cálculo do endereço e o
processamento aritmético precisariam do
acesso À ALU no mesmo ciclo de relógio
=> obviamente impossível !
Arquitectura de Computadores 2004/05
5 - Aula 9
Conflitos estruturais (3)
z
Exemplo 2: Duas instruções precisam de aceder à
memória no mesmo ciclo de relógio
•
O conflito apenas existe se a memória for única, como
indica o acetato a seguir
31 de Março de 2005
Arquitectura de Computadores 2004/05
6 - Aula 9
Conflitos estruturais (4)
DSUB R5,R6,R7
DADD R10,R11,R12
DADD R12,R10,R11
31 de Março de 2005
R
M
Ciclo 7
M
R
R
M
R
M
R
M
R
M
R
ALU
M
Ciclo 5 Ciclo 6
ALU
Ciclo 1 Ciclo 2 Ciclo 3 Ciclo 4
ALU
LW R2,10(R4)
Tempo
ALU
Execução do
programa
M
Arquitectura de Computadores 2004/05
Ciclo 8
R
7 - Aula 9
Conflitos estruturais (5)
z
Solução 1:
•
•
•
Inserir uma bolha (fazer o stall do pipeline durante 1 ciclo
de relógio)
Atrasa a instrução que entra no pipeline e todas as que se
lhe seguem no programa
Pode ser implementada com uma instrução NOP
31 de Março de 2005
Arquitectura de Computadores 2004/05
8 - Aula 9
Conflitos estruturais (6)
DSUB R5,R6,R7
DADD R10,R11,R12
STALL (NOP)
DADD R12,R10,R11
31 de Março de 2005
R
M
Ciclo 8
M
R
R
M
R
M
R
M
R
bubble
bubble
bubble
bubble
bubble
M
R
ALU
M
Ciclo 5 Ciclo 6 Ciclo 7
ALU
Ciclo 1 Ciclo 2 Ciclo 3 Ciclo 4
ALU
LW R2,10(R4)
Tempo
ALU
Execução do
programa
M
Arquitectura de Computadores 2004/05
9 - Aula 9
Conflitos estruturais (7)
z
Solução 2:
•
•
Replicar o recurso
Esta é a razão pela qual se usam, em geral, duas memórias
separadas, uma Memória de Instruções (IM) e uma Memória
de Dados (DM)
31 de Março de 2005
Arquitectura de Computadores 2004/05
10 - Aula 9
Conflitos estruturais (8)
z
Exemplo 3: a Register File é pretendida por duas
instruções no pipeline
Escrita na Register File em R1
DADD R1,R2,R3
. . .
. . .
SW R2,500(R5)
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
WB
IF
ID
EX
MEM
IF
ID
?
WB
?
Leitura de R5 da Register File
31 de Março de 2005
Arquitectura de Computadores 2004/05
11 - Aula 9
?
Conflitos estruturais (9)
z
Solução 2:
•
•
•
“Replicar” o recurso
Usar uma Register File que permita escritas na primeira
metade do período de relógio e leituras na segunda metade
•
Fácil de fazer se utilizarmos
flip-flops edge-triggered
Daqui para a frente, admitiremos que temos sempre esta
situação
31 de Março de 2005
Arquitectura de Computadores 2004/05
12 - Aula 9
Conflitos estruturais (10)
SW
R2,500(R5)
M
M
R
R
M
R
M
R
M
R
M
R
ALU
...
R
ALU
...
M
ALU
DADD R1,R2,R3
Ciclo 5 Ciclo 6 Ciclo 7
ALU
Ciclo 1 Ciclo 2 Ciclo 3 Ciclo 4
M
Ciclo 8
R
Não há conflito
estrutural
31 de Março de 2005
Arquitectura de Computadores 2004/05
13 - Aula 9
Dependências de dados - RAW
z
Conflitos
Read After Write (RAW)
A InstrJ tenta ler um operando antes de a InstrI o escrever
I:
J:
z
z
daddi
daddi
R1,R0,10
R4,R1,17
I
RAW R1
J
Estas dependências são inerentes ao programa, representando o
seu fluxo de instruções => dependências verdadeiras
Se as instruções forem suficientemente próximas por forma a
coexistirem no pipeline, e se nada for feito, existe um conflito
de dados que conduz à incorrecta execução da InstrJ
31 de Março de 2005
Arquitectura de Computadores 2004/05
14 - Aula 9
RAW – Outro exemplo (2)
OR
R8,R1,R9
XOR
R10,R1,R11
R
Há RAW
R
M
R
M
R
M
R
M
R
M
R
M
R
ALU
R6,R1,R7
M
M
ALU
AND
R
ALU
DSUB R4,R1,R3
M
Ciclo 8
ALU
DADD R1,R2,R3
Ciclo 5 Ciclo 6 Ciclo 7
ALU
Ciclo 1 Ciclo 2 Ciclo 3 Ciclo 4
M
Não há RAW
Reparar como só há RAW se a seta estiver “para trás” no tempo
31 de Março de 2005
Arquitectura de Computadores 2004/05
15 - Aula 9
Dependências de nome
z
z
z
Dependências que não exigem a produção de resultados
Apenas devem preservar a ordem
•
•
Antidependências
Dependências de saída
Não são dependências verdadeiras, por isso também se
designam por dependências falsas
31 de Março de 2005
Arquitectura de Computadores 2004/05
16 - Aula 9
Antidependências – WAR (1)
z
z
Conflitos Write After Read (WAR)
A InstrI deve ler um operando antes de a InstrJ o
actualizar
I:
daddi
R2,R1,10
I
J:
daddi
R1,R4,17
J
WAR R1
Conflitos WAR só podem ocorrer em pipelines em que os
andares de escrita (em registos ou em memória)
antecedem um andar de leitura do mesmo recurso
31 de Março de 2005
Arquitectura de Computadores 2004/05
17 - Aula 9
Antidependências – WAR (2)
z
O pipeline do MIPS, com 5 andares, não pode gerar um
conflito WAR porque
•
•
•
Todas as instruções usam os 5 andares para serem
executadas (mesmo as que só necessitam de 3 ou 4 ciclos
de relógio)
As leituras só ocorrem no andar 2, ID
As escritas são sempre no andar 5, WB
31 de Março de 2005
Arquitectura de Computadores 2004/05
18 - Aula 9
Dependências de saída – WAW (1)
z
Conflitos Write After Write (WAW)
A InstrI deve escrever um resultado antes de a InstrJ o
actualizar
z
I:
daddi
R1,R2,10
I
J:
daddi
R1,R4,17
J
WAW R1
Conflitos WAW só podem ocorrer em pipelines que
escrevem (em registos ou memória) em mais do que um
andar
•
O pipeline do MIPS não gera conflitos deste tipo
31 de Março de 2005
Arquitectura de Computadores 2004/05
19 - Aula 9
Dependências de saída – WAW (2)
z
O pipeline do MIPS, com 5 andares, não pode gerar um
conflito WAR porque
•
•
z
z
z
Todas as instruções usam os 5 andares para serem
executadas (mesmo as que só necessitam de 3 ou 4 ciclos
de relógio)
As escritas são sempre no andar 5, WB
Veremos mais à frente no curso que os conflitos WAR e
WAW ocorrem em pipelines mais complexos, quando
existir execução fora de ordem
O objectivo, nesses casos, é melhorar o CPI
O pipeline do MIPS apenas admite execução em ordem
31 de Março de 2005
Arquitectura de Computadores 2004/05
20 - Aula 9
RAR?
z
E RAR?
•
RAR não é uma dependência, logo não é geradora de
conflitos
31 de Março de 2005
Arquitectura de Computadores 2004/05
21 - Aula 9
Dependências RAW (1)
R4 <--- R1 ...
I:
J:
31 de Março de 2005
daddi
daddi
R1 <--- ...
R1,R0,10
R4,R1,17
Arquitectura de Computadores 2004/05
22 - Aula 9
Dependências RAW (2)
. . .
IF ID EX MEM WB
DADDI R1,R0,10
IF ID
EX
DADDI R4,R1,17
IF
ID
EX
MEM
IF
ID
EX
IF
ID
. . .
. . .
MEM WB
MEM WB
EX
Dependência RAW
31 de Março de 2005
Arquitectura de Computadores 2004/05
23 - Aula 9
Soluções para as dependências RAW
z
z
z
z
Solução 1: Bloqueio (stall) dos andares do pipeline,
até que o dado correcto esteja disponível (este bloqueio
também é designado por interlocking)
Solução 2: Se o dado correcto existir algures no pipeline,
estabelece-se um bypass para o andar correcto (esta
técnica também é conhecida por forwarding)
Solução 3: o forwarding nem sempre resolve os conflitos
RAW, como veremos mais tarde. Nesses casos tem que
se usar bloqueio e forwarding
Solução 4: escalonar (ordenar) as instruções
•
•
Escalonamento estático – pelo compilador
Escalonamento dinâmico – pelo hardware
31 de Março de 2005
Arquitectura de Computadores 2004/05
24 - Aula 9
Bloqueio do pipeline (1)
z
z
z
z
z
Vamos ver como bloquear o pipeline e, em seguida, vamos
passar aos conflitos de controlo
O forwarding será estudado mais tarde, para podermos
ter uma visão global dos problemas do pipeline típico com
5 andares que estamos a analisar
Para que o bloqueio funcione, é necessário que a
instrução no andar i+1 possa ser completada sem
interferência das instruções nos andares 1 a i
Bloqueia-se o pipeline no andar ID inserindo um NOP
nesse andar
O NOP vai-se propagar no pipeline até ao fim
31 de Março de 2005
Arquitectura de Computadores 2004/05
25 - Aula 9
Bloqueio do pipeline (2)
. . .
IF ID EX MEM WB
DADDI R1,R0,10
IF ID
DADDI R4,R1,17
IF
. . .
. . .
EX
MEM WB
stall
stall stall ID EX MEM
stall
stall stall IF
ID
EX
stall stall stall IF
ID
Iremos ver já a seguir como é que o NOP (stall) é
inserido no pipeline em ID e se propaga até ao fim
31 de Março de 2005
Arquitectura de Computadores 2004/05
26 - Aula 9
Bloqueio do pipeline (3)
z
O princípio é o seguinte:
•
Detecta-se a dependência e gera-se feedback para os
andares anteriores do pipeline, por forma a fazer o bloqueio
das instruções que se encontram nesses andares
31 de Março de 2005
Arquitectura de Computadores 2004/05
27 - Aula 9
Bloqueio do pipeline (4)
Inserção do NOP no andar ID
Bloqueio da actualização do PC
Bloqueio da instrução no andar ID
31 de Março de 2005
Arquitectura de Computadores 2004/05
28 - Aula 9
Bloqueio do pipeline (5)
I1: DADDI R1,R0,10
I2: DADDI R4,R1,17
I3:
I4:
I5:
Utilização dos
recursos
31 de Março de 2005
Arquitectura de Computadores 2004/05
29 - Aula 9
Bloqueio do pipeline (6)
Comparam-se os registos fonte da instrução no andar ID
com o registo destino da instrução que está a fazer o WB.
Só no WB? E para todas as instruções?
31 de Março de 2005
Arquitectura de Computadores 2004/05
30 - Aula 9
Bloqueio do pipeline (7)
z
Comparação dos registos fonte e destino para todas as
instruções?
•
•
Nem todas as instruções escrevem num reg. destino Î
Nem todas as instruções usam registos fonte Î
we
re
Registo destino no andar WB
. . .
IF ID EX MEM WB
DADDI R1,R0,10
IF ID
DADDI R4,R1,17
IF
. . .
. . . fonte no andar ID
Registo
31 de Março de 2005
EX
MEM WB
stall
stall stall ID EX MEM
stall
stall stall IF
ID
EX
stall stall stall IF
ID
Arquitectura de Computadores 2004/05
31 - Aula 9
Bloqueio do pipeline (8)
Só fazemos bloqueio nestas condições
31 de Março de 2005
Arquitectura de Computadores 2004/05
32 - Aula 9
Bloqueio do pipeline (9)
31 de Março de 2005
Arquitectura de Computadores 2004/05
33 - Aula 9
Bloqueio do pipeline (10)
Apenas parte
do problema !
31 de Março de 2005
Arquitectura de Computadores 2004/05
34 - Aula 9
Bloqueio do pipeline (11)
z
z
Vamos ver o que se passa com os Loads e Stores
Por exemplo, a sequência de instruções
SD R2,7(R1)
LD R4,5(R3)
z
gera uma dependência de dados se R1+7 = R3+5 (isto é, se os
endereços forem iguais)
Contudo, não existe conflito RAW se a Memória de Dados
completar as operações de escrita num único ciclo
•
para já, este é o modelo (simplificado) que estamos a usar para a
Memória de Dados e de Instruções Æ mas mais à frente no curso
iremos ter que que usar um modelo muito mais complexo, quando
falarmos em Memória Virtual e caches
31 de Março de 2005
Arquitectura de Computadores 2004/05
35 - Aula 9
Cálculo do CPI com bloqueios
z
z
Começar com o CPI de base
Adicionar bloqueios (stalls)
CPI = CPI base + CPI stall
CPI stall = STALLtype −1 × freqtype −1 + STALLtype − 2 × freqtype − 2
z
z
Suponhamos:
•
•
•
•
CPIbase=1
Freqbranch=20%, freqload=30%
Os Branches causam sempre 1 ciclo de stall
Os Loads causam um stall com 100 ciclos 1% das vezes
Então: CPI = 1 + (1×0.20) + (100 × 0.30×0.01) = 1.5
31 de Março de 2005
Arquitectura de Computadores 2004/05
36 - Aula 9
Conflitos de controlo (1)
304
Um Jump elimina (não bloqueia)
a instrução que se segue
Como?
31 de Março de 2005
Arquitectura de Computadores 2004/05
37 - Aula 9
Conflitos de controlo (2)
31 de Março de 2005
Arquitectura de Computadores 2004/05
38 - Aula 9
Conflitos de controlo (3)
31 de Março de 2005
Arquitectura de Computadores 2004/05
39 - Aula 9
Conflitos de controlo (4)
z
E os branches?
A condição do branch só é
conhecida no andar EX.
Que acção tomar no andar ID?
31 de Março de 2005
Arquitectura de Computadores 2004/05
40 - Aula 9
Conflitos de controlo (5)
31 de Março de 2005
Arquitectura de Computadores 2004/05
41 - Aula 9
Conflitos de controlo (6)
br
31 de Março de 2005
304
200
PC de I3 = 104
Arquitectura de Computadores 2004/05
42 - Aula 9
Conflitos de controlo (7)
z
O sinal de stall tem de vir modificado por causa dos
branches que saltam para o endereço alvo
Não fazer o stall se o branch se efectuar para o endereço alvo. Porquê?
A instrução no andar ID não é válida num BEQZ que salta.
Queremos eliminá-la
Mas é uma instrução válida no caso de um conflito RAW.
Neste caso, queremos apenas bloqueá-la (stall)
31 de Março de 2005
Arquitectura de Computadores 2004/05
43 - Aula 9
Conflitos de controlo (8)
• Equações de controlo
dos muxs
Dar prioridade à
instrução mais antiga,
a que se encontra no
andar EX, sobre a que
está no andar ID
31 de Março de 2005
Arquitectura de Computadores 2004/05
44 - Aula 9
Conflitos de controlo (9)
31 de Março de 2005
Arquitectura de Computadores 2004/05
45 - Aula 9
Conflitos de controlo (10)
z
z
Podemos remover uma bolha se usarmos um comparador
suplementar no andar ID
Nesse caso, o diagrama do pipeline fica igual ao dos
Jumps
31 de Março de 2005
Arquitectura de Computadores 2004/05
46 - Aula 9
Conflitos de controlo (11)
z
z
Podemos resolver os conflitos de controlo deixando-os
para o compilador
Muda-se o fluxo de instruções do programa, de modo a
que a instrução que se segue a um Jump ou a um Branch
é sempre executada
•
z
O compilador deve escolher a instrução a colocar no slot de
atraso, substituindo a bolha que o hardware lá colocaria
O slot de atraso vem prenchido
com uma instrução que é executada
independentemente do resultado
do Branch
Outra técnica usa Predição de Saltos (Branch Prediction),
que pode reduzir significativamente a penalização
associada aos Branches Î para mais tarde no curso
31 de Março de 2005
Arquitectura de Computadores 2004/05
47 - Aula 9
Forwarding para conflitos RAW (1)
z
Retomemos um exemplo anterior:
DADD R1,R2,R3
DSUB R4,R1,R3
31 de Março de 2005
AND
R6,R1,R7
OR
R8,R1,R9
XOR
R10,R1,R11
Arquitectura de Computadores 2004/05
48 - Aula 9
Forwarding para conflitos RAW (2)
OR
R8,R1,R9
XOR
R10,R1,R11
31 de Março de 2005
R
Há RAW
R
M
R
M
R
M
R
M
R
M
R
M
R
ALU
R6,R1,R7
M
M
ALU
AND
R
ALU
DSUB R4,R1,R3
M
Ciclo 8
ALU
DADD R1,R2,R3
Ciclo 5 Ciclo 6 Ciclo 7
ALU
Ciclo 1 Ciclo 2 Ciclo 3 Ciclo 4
M
Arquitectura de Computadores 2004/05
Não há RAW
49 - Aula 9
Forwarding para conflitos RAW (3)
OR
R8,R1,R9
XOR
R10,R1,R11
31 de Março de 2005
R
Há RAW
R
M
R
M
R
M
R
M
R
M
R
M
R
ALU
R6,R1,R7
M
M
ALU
AND
R
ALU
DSUB R4,R1,R3
M
Ciclo 8
ALU
DADD R1,R2,R3
Ciclo 5 Ciclo 6 Ciclo 7
ALU
Ciclo 1 Ciclo 2 Ciclo 3 Ciclo 4
M
Arquitectura de Computadores 2004/05
50 - Aula 9
OR
R8,R1,R9
XOR
R10,R1,R11
31 de Março de 2005
R
Já não há RAW
R
M
R
M
R
M
R
M
R
M
R
M
R
ALU
R6,R1,R7
M
M
ALU
AND
R
ALU
DSUB R4,R1,R3
M
ALU
DADD R1,R2,R3
ALU
Forwarding para conflitos RAW (4)
M
Arquitectura de Computadores 2004/05
51 - Aula 9
Bypassing (1)
Cada bloqueio (stall) ou eliminação (kill) introduz uma bolha no pipeline
Î CPI > 1
Uma modificação do datapath, designado por bypass ou forwarding,
pode obter o resultado à saída da ALU e colocá-lo à sua entrada
(não precisa de esperar pelo WB)
31 de Março de 2005
Arquitectura de Computadores 2004/05
52 - Aula 9
Bypassing (2)
z
Acrescentando um bypass
31 de Março de 2005
Arquitectura de Computadores 2004/05
53 - Aula 9
Bypassing (3)
z
Em que situações é que o bypass ajuda?
DADDI R1,R0,10
DADDI R4,R1,17
31 de Março de 2005
Sim
Arquitectura de Computadores 2004/05
54 - Aula 9
Bypassing (4)
z
Em que situações é que o bypass ajuda?
LD
R1,10(R0)
DADDI R4,R1,17
31 de Março de 2005
Não
Arquitectura de Computadores 2004/05
55 - Aula 9
Bypassing (5)
z
Em que situações é que o bypass ajuda?
JAL
500
DADDI R4,R31,17
31 de Março de 2005
Não
Arquitectura de Computadores 2004/05
56 - Aula 9
Bypassing (6)
z
Obtenção do sinal de bypass a partir do sinal de stall
Estará correcto ?
Não, porque apenas as instruções ALU e ALUI podem beneficiar
deste bypass (apenas consideramos, para já, bypasses provenientes
da ALU)
Solução: partir weE em dois componentes, we-bypass e we-stall
31 de Março de 2005
Arquitectura de Computadores 2004/05
57 - Aula 9
Bypassing (7)
z
Partir weE em dois componentes: we-bypass e we-stall
31 de Março de 2005
Arquitectura de Computadores 2004/05
58 - Aula 9
Bypassing (8)
z
Datapath completo com bypass
•
Vamos agora considerar bypasses com origem nos andares
MEM e WB, para além do andar EX (o bypass anterior)
31 de Março de 2005
Arquitectura de Computadores 2004/05
59 - Aula 9
Bypassing (9)
z
Datapath completo com bypass
31 de Março de 2005
Arquitectura de Computadores 2004/05
60 - Aula 9
Bypassing (10)
z
z
z
E o sinal de stall?
Reduz-se a:
Ainda temos de fazer stalls por causa dos Loads (ver 2
acetatos à frente)
31 de Março de 2005
Arquitectura de Computadores 2004/05
61 - Aula 9
Bypassing (11)
z
z
Porque é que não conseguimos fazer sair para o exterior
do pipeline (“dispatch”) uma instrução em cada ciclo de
relógio? Ou seja,
Porque é que não conseguimos um CPI = 1 ?
•
O bypass completo pode ser muito dispendioso
•
•
•
Tipicamente, apenas se incluem os caminhos de bypass mais
frequentes
Alguns caminhos de bypass pouco frequentes podem aumentar a
duração do ciclo de relógio, e desta forma diminuir realmente o
benefício pretendido da redução do CPI
Os Branches podem causar bolhas
•
•
Temos de eliminar a instrução (ou as duas instruções) que se
segue(m) ao Branch, no caso de se efectivar o salto
As alternativas são os slots de atraso ou a predição de saltos
31 de Março de 2005
Arquitectura de Computadores 2004/05
62 - Aula 9
Bypassing (12)
z
Porque é que não conseguimos um CPI = 1 ?
•
Mesmo com bypass, os Loads têm uma latência igual a 2
ciclos
•
A instrução depois de um Load não pode utilizar o resultado do
Load, como vimos atrás
31 de Março de 2005
Arquitectura de Computadores 2004/05
63 - Aula 9
Conflito de dados, mesmo com forwarding
A instrução que se segue a um Load não pode utilizar o
resultado do Load, mesmo com bypass
R
M
R
AND
R6,R1,R7
M
OR
R8,R1,R9
Com forwarding
não há RAW
31 de Março de 2005
M
Há RAW
R
Não precisa de
forwarding
M
R
R
M
R
M
R
ALU
DSUB R4,R1,R3
M
ALU
R1,0(R2)
ALU
LD
ALU
z
M
Arquitectura de Computadores 2004/05
R
64 - Aula 9
Próxima aula
z
z
Excepções
Arquitecturas multi-ciclo
31 de Março de 2005
Arquitectura de Computadores 2004/05
65 - Aula 9