Pipeline

Enquanto um lw lê memória, outra instrução pode calcular na ALU e uma terceira pode ser descodificada. Uma pipeline sobrepõe fases de instruções diferentes. Aumenta a taxa de conclusão; cada instrução continua a atravessar vários ciclos.

Usamos cinco fases, emissão de uma instrução por ciclo e memórias I/D separadas. Os atalhos e a regra temporal do banco de registos serão indicados em cada traço.

Fases, período e latência

Fase	Trabalho
IF	Obter a instrução pelo PC
ID	Descodificar e ler os operandos
EX	Calcular resultado, endereço ou condição de salto
MEM	Ler/escrever dados; no modelo básico, redirecionar o salto
WB	Escrever resultado no registo, se a instrução o fizer

As fases sem trabalho útil ainda ocupam a posição temporal do modelo. Um sw não escreve um registo em WB, por isso não acrescentes uma escrita fictícia.

Considera atrasos de 200, 100, 150, 250 e 100 ps, sem custo adicional dos registos entre fases. O período precisa de acomodar a fase mais lenta:

$$T=\max(200,100,150,250,100)=250\ \mathrm{ps}.$$

Uma instrução atravessa cinco períodos: a latência é $5\times250=1250$ ps. Em ciclo único, o caminho de um load soma os atrasos e demora 800 ps.

Para 20 instruções sem paragens, a primeira termina no ciclo 5 e as outras 19 terminam nos 19 ciclos seguintes:

$$T_{\rm pipeline}=(5+19)\times250=6000\ \mathrm{ps}.$$

Em ciclo único, as 20 instruções ocupam $20\times800=16000$ ps. A rapidez relativa do conjunto é $16000/6000\approx2,667$. A latência individual aumentou, mas o conjunto termina mais cedo porque as fases se sobrepõem.

Dividir uma fase e pagar os registos

Acelerar uma fase só reduz o período quando diminui o maior atraso. Se IF, EX e MEM demoram 200 ps, reduzir EX para 150 ps deixa o período em 200 ps: as outras duas continuam a limitá-lo.

Para atrasos [300,400,350,500,100] ps, MEM limita a pipeline a 500 ps. Se for possível dividir MEM em duas fases de 250 ps, passam a existir seis fases e ID, de 400 ps, determina o novo período. Não continues a usar cinco fases depois da divisão.

Os registos entre fases também introduzem atraso. Usa $\tau$ para o custo comum por fase, incluindo os tempos exigidos para guardar e disponibilizar os sinais. Se esse custo não estiver já incluído nos atrasos:

$$T=\max_i t_i+\tau.$$

Com $\tau=150$ ps, compara sequências independentes, sem paragens:

Organização	Fases	Período	Uma instrução	Dez instruções
Original	5	650 ps	3250 ps	9100 ps
MEM dividida	6	550 ps	3300 ps	8250 ps

A versão dividida tem débito em regime de uma instrução a cada 550 ps, mas demora mais a completar uma instrução isolada. Para dez, o enchimento adicional já compensa: $14\times650=9100$ ps contra $15\times550=8250$ ps. O custo do registo entra uma vez no período, e cada instrução paga tantos períodos quantas as fases. Somá-lo uma única vez à latência total perderia os restantes registos.

Esta comparação ideal conserva dependências e penalidades. Numa implementação real, deslocar o instante em que um load ou branch produz informação pode alterar paragens; a redução do período, sozinha, não determina o ganho.

Conflitos estruturais e de dados

Um conflito estrutural existe quando operações simultâneas requerem um recurso que não as suporta. Uma única memória com um porto não pode servir IF e um load em MEM no mesmo ciclo. Para resolver isso, bloqueia IF ou disponibiliza recursos separados. Inserir um NOP também requer obter uma instrução, logo não cria um segundo porto.

Uma dependência RAW existe quando uma instrução precisa do valor escrito por uma anterior. Torna-se conflito se esse valor não estiver disponível na fase que o usa. Não basta procurar registos repetidos: identifica leituras, escritas e o instante de uso.

Atalhos para a ALU

add t0,t1,t2
sub t3,t0,t4
and t5,t0,t6

O resultado do add está pronto no fim de EX. A sub pode recebê-lo de EX/MEM no seu EX; a and, de MEM/WB. Não precisam de esperar que o banco seja escrito.

O comparador de forwarding verifica RegWrite, destino diferente de zero e igualdade com a origem. Se EX/MEM e MEM/WB oferecem o mesmo registo, escolhe EX/MEM, o resultado mais recente. Não encaminhes de EX/MEM o resultado de um load como se fosse o dado carregado: nesse momento é apenas o endereço.

Load-use com uma bolha

lw t0,0(a0)
add t1,t0,t2

O add fica em ID nos ciclos 3 e 4; a instrução seguinte fica em IF. No ciclo 4, EX recebe uma bolha. Congelar PC e IF/ID evita perder ou repetir instruções; zerar o controlo de ID/EX evita executar o add com dado antigo.

Sem forwarding, e com escrita WB na primeira metade e leitura ID na segunda metade, o consumidor pode ler em ID no ciclo 5: duas paragens, não três. Se o banco tiver outra regra temporal, adapta a conta.

O operando de um store

sw t0,0(a0) usa a0 para endereço em EX e t0 como dado em MEM. São usos diferentes. Um load seguido de store do seu resultado pode dispensar paragem se houver atalho do dado para MEM. Se só existem atalhos ALU–ALU, o store pode precisar de esperar em ID ou usar outro caminho. Não transfiras automaticamente a regra load-use da ALU para este caso.

Contar e reduzir paragens

Traço finito completo com duas iterações de um fragmento repetido, com forwarding completo para EX e memórias I/D separadas:

add a0, t0, a1
lw t0, 0(a0)

Dentro de uma iteração, add para lw usa o atalho ALU para EX e não precisa de paragem. Entre iterações, o lw da iteração anterior produz t0 para o add seguinte e impõe uma bolha load-use. Para add1, lw1, add2, lw2:

Ciclo	1	2	3	4	5	6	7	8	9
add1	IF	ID	EX	MEM	WB
lw1		IF	ID	EX	MEM	WB
add2			IF	ID	ID	EX	MEM	WB
lw2				IF	IF	ID	EX	MEM	WB

Só há uma aresta lw para add dentro desta janela: lw1 para add2. A segunda aresta (lw2 para um add3 fora da janela) não se conta no traço finito. Logo $B = 1$, $C = N + 4 + B = 4 + 4 + 1 = 9$ ciclos até WB de lw2, e o CPI finito é $9/4 = 2{,}25$.

Em regime com muitas iterações, cada grupo de 2 instruções paga 1 paragem, logo o CPI tende para $3/2 = 1{,}5$. Não leias 1,5 no traço de 4 instruções. O valor 1,5 é o limite com muitas repetições, não o quociente 9/4.

Para $N$ instruções em 5 fases, conta até à última chegar a WB:

$$C=N+4+B,$$

com $B$ bolhas efetivas. Se o pedido é o instante de uma escrita final em memória, identifica MEM desse store; o seu WB não faz uma nova escrita. Conta as bolhas de dependências e controlo sem cobrar duas vezes uma espera que resolve ambos os conflitos.

Dois loads imediatamente seguidos de consumidores ALU, sem outras dependências, dão $B=2$. Para 10 instruções, são 16 ciclos.

Mover uma instrução independente entre load e consumidor pode ocultar essa paragem:

lw t0,0(a0)
addi a1,a1,4
add t1,t0,t2

É válido se a atualização de a1 não alterar o significado nem o endereço de outros acessos e puder ocorrer antes do add. Reordenar exige conservar dependências de registos e memória, não só reduzir bolhas.

Para um ciclo repetido muitas vezes, $CPI\approx(n+B_{\rm iter})/n$, incluindo dependências entre iterações. Uma carga na última instrução pode alimentar a primeira da iteração seguinte.

Saltos e período de relógio

Um salto introduz incerteza no PC. Neste modelo básico, a comparação começa em EX e o PC é redirecionado em MEM. Há até três instruções mais novas no caminho errado. Os casos de predição e decisão antecipada estão em Predição de saltos.

Forwarding também tem custo de hardware. Se uma versão precisa de 9 ciclos a 300 ps e outra de 7 ciclos a 400 ps, os tempos são 2700 e 2800 ps. A segunda tem menos ciclos, mas a rapidez relativa é 0,964, ou seja, é mais lenta.