(5 pontos) Considere o seguinte trecho de código
- Iw
s0)
- add
s2, $t0
- Iw
s6)
- sub
t1, $s2
- or
s6, $zero
- sw
s1)
i) Assuma um pipeline MIPS de 5 estágios sem forwarding, e que cada estágio demora 1 ciclo. Qual o tempo de execução (em ciclos) do programa inteiro? Faça o diagrama da execução das instruções em pipeline.
ii) Assuma um pipeline MIPS de 5 estágio com forwarding. Faça o diagrama da execução das instruções em pipeline.
iii) Faça o reordenamento de código para eliminar as dependências de dados, quando for possível.
ii) Assuma um pipeline MIPS de 5 estágio com forwarding. Faça o diagrama da execução das instruções em pipeline.
iii) Faça o reordenamento de código para eliminar as dependências de dados, quando for possível.
Passo 1
O enunciado nos dá um trecho de
instruções MIPS e pede para analisar o pipeline de
estágios (IF, ID, EX, MEM, WB) nas duas situações: sem forwarding e com forwarding, além de reordenar o código para remover dependências. Vamos precisar contar ciclos, identificar dependências RAW e inserir bolhas (stalls) quando o dado não estiver disponível a tempo.
Passo 2
(i) Pipeline sem forwarding
Sem forwarding, qualquer dependência RAW força a instrução que usa o dado a aguardar até que o valor seja escrito no registrador (fim do estágio WB). Cada RAW entre duas instruções consecutivas insere ciclos de stall.
Dependências:
Sem forwarding, qualquer dependência RAW força a instrução que usa o dado a aguardar até que o valor seja escrito no registrador (fim do estágio WB). Cada RAW entre duas instruções consecutivas insere
Dependências:
- entre I
(lw ) e I (add usa)t ): stalls - entre I
(lw ) e I (sub usa)t ): stalls - entre I
(sub ) e I (or usa)s ): stalls - entre I
(or ) e I (sw usa)s em ID): stalls
Sem stalls o programa levaria
ciclos. Há
dependências
ciclos de stall. Total
ciclos.
Diagrama (“s”
stall):
Ciclo
Instr
I lw IF ID EX MEM WB
I add IF ID s s EX MEM WB
I lw IF ID EX MEM WB
I sub IF ID s s EX MEM WB
I or IF ID EX MEM WB
I sw IF ID EX MEM WB
Ciclo
Instr
I
I
I
I
I
I
Passo 3
(ii) Pipeline com forwarding
Com forwarding, ALU-ALU não geram stall, mas o caso load-use ainda precisa de stall porque o dado só sai no final de MEM. Dependências que provocam
stall cada:
Com forwarding, ALU-ALU não geram stall, mas o caso load-use ainda precisa de
- I
I (load-use de $t ) - I
I (load-use de $t )
As demais (subor e or sw) são resolvidas por forwarding ou escrita no primeiro meio-ciclo de ciclo.
Total de stalls, total de ciclos .
Diagrama (“s”
ciclo de stall):
Ciclo
Instr
I lw IF ID EX MEM WB
I add IF ID s EX MEM WB
I lw IF ID EX MEM WB
I sub IF ID s EX MEM WB
I or IF ID EX MEM WB
I sw IF ID EX MEM WB
Ciclo
Instr
I
I
I
I
I
I
Passo 4
(iii) Reordenamento para eliminar dependências (assumindo uso de forwarding)
Queremos evitar load-use em sequência, então após cada lw colocamos uma instrução independente. Uma solução:
. lw
,
()s
)
. lw
,
()s
)
. add
,)s
,
. sub)s
,
,)s
. or
,)s
, $zero
. sw
,
()s
)
Queremos evitar load-use em sequência, então após cada lw colocamos uma instrução independente. Uma solução:
Agora cada uso de carga está a
instruções de distância, e com forwarding não há mais stalls.
Resposta
(i)
ciclos
(ii) ciclos
(iii) Código reordenado:
(ii)
(iii) Código reordenado:
lw \(t\(0\), \(0\)(\)s\(0\))
lw \(t\(1\), \(40\)(\)s\(6\))
add \(s\(0\),\)s\(2\), $t\(0\)
sub \(s\(6\),\)t\(1\), $s\(2\)
or \(s\(3\),\)s\(6\), $zero
sw \(s\(3\), \(50\)(\)s\(1\))