Introdução

Arquitectura com unidade de controlo uniciclo
Unidade de controlo
Load / INC
Controlo de
saltos
PC
Memória de
programa
Memória de dados
Descodificador
de Endereços
Leitura/Escrita
Tipo
de salto
Descodificador
de Instruções
Palavra de Controlo
Datapath
Bits de estado (flags)
1
Introdução
A mesma ideia, posta de uma forma diferente...
M
U
X
End. salto
Controlo de
saltos
Tipo salto
Inc
Const
P
C
Memória
de
instruções
Banco
de
registos
M
U
X
ALU

Memória
de dados
M
U
X
2
Introdução
Descodificação
M
U
X
Execução
Controlo de
saltos
Const
P
C
Memória
de
instruções
Write
back
End. salto
Tipo salto
Inc
Acesso à
memória
Banco
de
registos
M
U
X
ALU
Fetch
Memória
de dados
M
U
X
3
Introdução

Por cada instrução tem-se a sequência
Fetch
Descodificação
Execução
Memória
Write-back
IF
ID
EXE
MEM
WB

Fetch (IF) – ler a instrução localizada no endereço dado por PC

Descodificação (ID) – obter o opcode e operandos; ler os
registos fonte

Execução (EXE) – operações na ALU e controlo dos saltos

Memória (MEM) – aceder à memória para escrever ou ler dados

Write-back (WB) – escrever o resultado no registo de destino
4
Funcionamento em pipeline

Estrutura de um pipeline
IF
ID
EXE
MEM
WB
Clock

Separam-se as várias etapas por registos (buffers)

E sincronizam-se esses registos com um sinal de relógio
comum…
Obtém-se um pipeline
5
Funcionamento em pipeline
Com mais detalhe...
M
U
X
End. salto
Controlo de
saltos
Tipo salto
Inc
Const
P
C
Memória
de
instruções
Banco
de
registos
M
U
X
ALU

Memória
de dados
M
U
X
6
Funcionamento em pipeline

Ideia semelhante a uma linha de montagem:

Por cada impulso de relógio é realizada uma etapa de
uma instrução

Se o pipeline tem N etapas, então N instruções
podem estar simultaneamente dentro do pipeline

Uma instrução em cada etapa
Inst. i+4
Inst. i+3
Inst. i+2
Inst. i+1
Inst. i
IF
ID
EXE
MEM
WB
Clock
7
Funcionamento em pipeline

Ilustração do funcionamento
Inst. 1
Inst. 2
Inst. 3
Inst. 4
Inst. 5
Inst. 6
…
IF
Programa a correr
ID
EXE
MEM
WB
Clock
8
Funcionamento em pipeline

Ilustração do funcionamento
Inst. 1
Inst. 2
Inst. 3
Inst. 4
Inst. 5
Inst. 6
…
Programa a correr
Inst. 1
IF
ID
EXE
MEM
WB
Clock
9
Funcionamento em pipeline

Ilustração do funcionamento
Inst. 1
Inst. 2
Inst. 3
Inst. 4
Inst. 5
Inst. 6
…
Programa a correr
Inst. 2
Inst. 1
IF
ID
EXE
MEM
WB
Clock
10
Funcionamento em pipeline

Ilustração do funcionamento
Inst. 1
Inst. 2
Inst. 3
Inst. 4
Inst. 5
Inst. 6
…
Programa a correr
Inst. 3
Inst. 2
Inst. 1
IF
ID
EXE
MEM
WB
Clock
11
Funcionamento em pipeline

Ilustração do funcionamento
Inst. 1
Inst. 2
Inst. 3
Inst. 4
Inst. 5
Inst. 6
…
Programa a correr
Inst. 4
Inst. 3
Inst. 2
Inst. 1
IF
ID
EXE
MEM
WB
Clock
12
Funcionamento em pipeline

Ilustração do funcionamento
Inst. 1
Inst. 2
Inst. 3
Inst. 4
Inst. 5
Inst. 6
…
Programa a correr
Inst. 5
Inst. 4
Inst. 3
Inst. 2
Inst. 1
IF
ID
EXE
MEM
WB
Clock
13
Funcionamento em pipeline

Ilustração do funcionamento
Inst. 1
Inst. 2
Inst. 3
Inst. 4
Inst. 5
Inst. 6
…
Programa a correr
Inst. 6
Inst. 5
Inst. 4
Inst. 3
Inst. 2
IF
ID
EXE
MEM
WB
Clock
14
Funcionamento em pipeline

Outra maneira de ver..
Ciclos de relógio
inst 1
inst 2
inst 3
inst 4
inst 5
inst 6
...
1º
2º
3º
4º
5º
6º
7º
8º
9º
10º
IF
ID
EXE
MEM
WB
IF
ID
EXE
MEM
WB
IF
ID
EXE
MEM
WB
IF
ID
EXE
MEM
WB
IF
ID
EXE
MEM
WB
IF
ID
EXE
MEM
WB
...
....
....
...
11º
...
Por exemplo, no 5º ciclo de relógio, a instrução 1 está na fase WB, a instrução 2 na fase
MEM, a instrução 3 na fase EXE, a inst. 4 está na fase ID e a inst. 5 na fase IF.
15
Desempenho ideal

Em condições ideais

O pipeline está “equilibrado”


todas as etapas demoram o mesmo tempo
O pipeline encontra-se sempre cheio

tem-se sempre uma instrução em cada etapa
Tnew  Tetapa

Told

Netapas
CPIideal  1
Ganho (ideal) face a uma versão sem pipeline:
Ganhoideal  Netapas
16
Conflitos

Mas num pipeline nem tudo são rosas...


Existem situações em que

Instruções em fases diferentes tentam aceder ao mesmo
recurso (e.g. à memória)

O resultado de uma instrução depende de outra que ainda
não terminou a execução
Essas situações designam-se por conflitos
(ou pipeline hazards)

A existência de conflitos reduzem significativamente o ganho
de um pipeline...
17
Conflitos

Tipos de conflitos

Conflitos de dados
ocorrem quando existem dependências de dados entre
instruções que se encontram dentro do pipeline

Conflitos estruturais
ocorrem quando duas instruções em fases diferentes tentam
aceder ao mesmo recurso

Conflitos de controlo
ocorrem em instruções de salto, quando o salto depende de um
resultado que ainda não foi calculado
18
Conflitos de dados

Conflito RAW (Read after Write)

Para ilustrar a ocorrência destes conflitos vamos considerar que
temos duas instruções: instrução 1 e instrução 2



A instrução 2 vai ser executada depois da instrução 1
Vamos supor que a instrução 2 lê dados que são o resultado da
instrução 1 – existe uma dependência entre as instruções

O conflito ocorre se a instrução 2 tentar ler os dados antes da
instrução 1 os ter escrito

A instrução 2 iria ler um valor desactualizado...
Exemplo:
...
inst. 1:
ADD R0, R1, R2
# R0 ← R1 + R2
inst. 2:
SUB R5, R0, R4
# R5 ← R0 – R4
...
19
Conflitos de dados

Conflito RAW (cont.)
...
ADD R0, R1, R2
SUB R5, R0, R4
...
k
k+1
k+2
k+3
k+4
k+5
...
...
...
...
IF
ID
IF
k+6
EXE
MEM
WB
ID
EXE
MEM
WB
...
...
...
...
k+7
...
CONFLITO !
A instrução SUB está a utilizar o valor de R0 antes de tempo, pois a
instrução ADD ainda não escreveu o resultado (Write-back)...
20
Conflitos de dados

Resolução básica de conflitos


Detecta-se o conflito

Introduzem-se bolhas no pipeline

Uma bolha é basicamente uma palavra de controlo que
manda “não fazer nada” (nop)

Cada bolha faz com que seja desperdiçado um ciclo de
relógio
Contudo existem alternativas mais eficientes para
resolver cada tipo de conflito

Inserir bolhas, só mesmo se não houver uma alternativa...
21
Conflitos de dados

Para o caso anterior, resolve-se o conflito introduzindo 2
bolhas após detectado o conflito

O conflito pode ser detectado quando é feita a descodificação do SUB

Depois atrasa-se o SUB dois ciclos, de forma a dar tempo para fazer o
WB do ADD
k
k+1
k+2
k+3
...
...
...
...
...
ADD R0, R1, R2
IF
ID
EXE
MEM
WB
IF
ID
B
...
SUB R5, R0, R4
…
Conflito
detectado
k+4
k+5
k+6
k+7
B
EXE
MEM
WB
...
...
...
...
Conflito
resolvido
22
Conflitos de dados

Outra maneira de ver o problema:
SUB R5,R0,R4
IF
ADD R0,R1,R2
…
ID
EXE
MEM
WB
Clock
23
Conflitos de dados

Outra maneira de ver o problema:
…
IF
SUB R5,R0,R4
ADD R0,R1,R2
ID
EXE
…
MEM
WB
Clock
24
Conflitos de dados

Outra maneira de ver o problema:
…
IF
SUB R5,R0,R4
B
ADD R0,R1,R2
ID
EXE
MEM
…
WB
Clock
25
Conflitos de dados

Outra maneira de ver o problema:
…
IF
SUB R5,R0,R4
B
B
ID
EXE
MEM
ADD R0,R1,R2
WB
Clock
26
Conflitos de dados

Outra maneira de ver o problema:
…
IF
…
SUB R5,R0,R4
ID
EXE
B
MEM
B
WB
Clock
27
Conflitos de dados

Resolução mais eficiente de conflitos RAW

Utiliza-se uma técnica chamada forwarding

A ideia consiste em disponibilizar resultados nas
entradas da unidade funcional (fase EXE)…

…ainda antes de ser feito o write-back

Quando são detectados conflitos, utilizam-se esses
resultados em vez do que foi lido dos registos
28
Conflitos de dados
Utilização de forwarding
M
U
X
M
U
X
ALU

M
U
X
Memória
de dados
M
U
X
29
Conflitos de dados

Outros conflitos de dados

Conflito WAW (Write after Write)



Conflito WAR (Write after Read)



Ambas as instruções são de escrita e o resultado vai ser
escrito no mesmo local
O conflito ocorre quando se a instrução 2 tentar escrever
antes da instrução 1
A instrução 1 lê dados do local onde a instrução 2 escreve
O conflito ocorre se a instrução 2 tentar escrever antes da
instrução 1 ler
Ocorrem em pipelines mais complexos, com várias
fases onde podem ser feitas leituras e escritas e nos
registos
30
Conflitos estruturais

Duas (ou mais) instruções tentam aceder
simultaneamente ao mesmo recurso

Situação típica:


Quando se usa uma única memória para dados e programa, não se
pode fazer o fetch (IF) ao mesmo tempo que uma instrução acede à
memória para ler/escrever dados
Situações menos típicas

Tentar escrever no mesmo registo em simultâneo (só ocorre em
processadores com mais do que uma fase de write-back)

Tentar ler ou escrever dados em simultâneo na mesma memória (só
ocorre em processadores com mais do que uma fase de acesso à
memória)
31
Conflitos estruturais

Exemplo de um conflito estrutural
k
k+1
k+2
k+3
...
...
...
...
...
LOAD R1, a
IF
ID
EXE
MEM
WB
IF
ID
EXE
MEM
WB
IF
ID
EXE
MEM
WB
IF
ID
EXE
MEM
ADD R3,R4,R5
SUB R6,R6,R7
XOR R1,R4,R5
k+4
k+5
k+6
k+7
WB
...
CONFLITO !
Não pode ser feito o fetch ao mesmo tempo que se acede à memória para
ler dados (o LOAD)...
32
Conflitos estruturais

Resolução do conflito

Introdução de uma bolha antes do fetch...
k
k+1
k+2
k+3
...
...
...
...
...
LOAD R1, a
IF
ID
EXE
MEM
WB
IF
ID
EXE
MEM
WB
IF
ID
EXE
MEM
WB
B
IF
ID
...
ADD R3,R4,R5
SUB R6,R6,R7
XOR R1,R4,R5
...
k+4
k+5
k+6
k+7
k+8
EXE
MEM
WB
...
...
...
Conflito resolvido
33
Conflitos estruturais

Resoluções mais eficientes

Memórias de dados e de instruções separadas


Tipicamente este esquema é implementado usando uma
memória cache para dados e outra para instruções
Instruction pre-fetching

É feito antecipadamente o fetch de várias instruções, que
ficam guardadas numa memória interna (buffer de instruções)

Quando o buffer fica vazio vão-se buscar mais instruções à
memória.
34
Conflitos de controlo

Ocorrem quando aparecem saltos


Saltos incondicionais

O processador só fica a saber que é uma instrução de salto
na fase ID (descodificação)...

... mas nessa altura a instrução na posição que se segue à de
salto já se encontra na fase IF (fetch)
Saltos condicionais

Para além do que acontece com os saltos incondicionais, não
se sabe antecipadamente se vai ou não ocorrer o salto

Tipicamente só se sabe a ocorrência (ou não) do salto após a
verificação da condição do salto (tipicamente associada à
fase EXE)
35
Conflitos de controlo
Só aqui se sabe
que é um salto...
End. salto
Controlo de
saltos
Tipo salto
Inc
Const
P
C
Memória
de
instruções
Banco
de
registos
M
U
X
ALU
M
U
X
Nos saltos condicionais, só aqui se sabe
se o salto vai ser tomado ou não...
Memória
de dados
M
U
X
36
Conflitos de controlo

Exemplo (salto incondicional)
...
LBL1: ADD R1, R4, R5
...
STORE a, R1
JUMP LBL1
LBL2: LOAD R1, a
...
37
Conflitos de controlo

Ilustração do problema (salto incondicional):
k
k+1
k+2
k+3
...
...
...
...
...
JUMP LBL1
IF
ID
EXE
MEM
WB
IF
B
B
B
B
IF
ID
EXE
MEM
WB
...
...
...
...
LOAD R1, a
ADD R1, R4, R5
...
k+4
k+5
k+6
k+7
k+8
k+9
Perde-se 1 ciclo, pois é feito um fetch inútil da instrução que se
segue à de salto
38
Conflitos de controlo

Exemplo (salto condicional)
...
DEC R1, R1
JZER END
Umas vezes há salto,
outras não...
ADD R0, R1, R2
STORE a, R0
...
END:
LOAD R1, a
...
39
Conflitos de controlo

supondo que o salto ocorre:
k
k+1
k+2
k+3
...
...
...
...
...
DEC R1, R1
IF
ID
EXE
MEM
WB
IF
ID
EXE
MEM
WB
IF
ID
B
B
B
IF
B
B
B
B
IF
ID
EXE
MEM
JZER END
ADD R0, R1, R2
STORE a, R4
LOAD R1, a
k+4
k+5
k+6
k+7
k+8
k+9
WB
...
Perdem-se 2 ciclos, pois só se irá actualizar o valor de PC depois do
salto concluir a fase EXE (só aí se sabe que o salto se vai verificar ou
não)...
40
Conflitos de controlo

Minorar a introdução de bolhas:
Previsão de saltos (branch prediction)



Previsão estática

Assume-se que o salto é sempre tomado (predict-taken)

Ou se assume que o salto nunca é tomado (predict-not-taken)
Previsão dinâmica

A previsão depende do que se passou em saltos anteriores

Muito usada actualmente
Nos casos em que a previsão está errada vão-se perder ciclos
de processamento

A anular o efeito das instruções que entretanto entraram
41