(5 pontos) Considere o seguinte trecho de código
  1. Iw t0, 0(s0)
  2. add s0,s2, $t0
  3. Iw t1, 40(s6)
  4. sub s6,t1, $s2
  5. or s3,s6, $zero
  6. sw s3, 50(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.

Passo 1

O enunciado nos dá um trecho de 6 instruções MIPS e pede para analisar o pipeline de 5 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 2 ciclos de stall.
Dependências:
  • entre I 1 (lw \to t\(0) e I 2 (add usa)t 0): 2 stalls
  • entre I 3 (lw \to t\(1) e I 4 (sub usa)t 1): 2 stalls
  • entre I 4 (sub \to s\(6) e I 5 (or usa)s 6): 2 stalls
  • entre I 5 (or \to s\(3) e I 6 (sw usa)s 3 em ID): 2 stalls
Sem stalls o programa levaria 6 + 4 = 10 ciclos. Há 4 dependências \to 4 \times 2 = 8 ciclos de stall. Total = 10 + 8 = 18 ciclos.
Diagrama (“s” = stall):
Ciclo
Instr 123456789101112131415161718
I 1 lw IF ID EX MEM WB
I 2 add IF ID s s EX MEM WB
I 3 lw IF ID EX MEM WB
I 4 sub IF ID s s EX MEM WB
I 5 or IF ID EX MEM WB
I 6 sw IF ID EX MEM WB

Passo 3

(ii) Pipeline com forwarding
Com forwarding, ALU-ALU não geram stall, mas o caso load-use ainda precisa de 1 stall porque o dado só sai no final de MEM. Dependências que provocam 1 stall cada:
  • I 1\toI 2 (load-use de $t 0)
  • I 3\toI 4 (load-use de $t 1)
    As demais (sub \toor e or \tosw) são resolvidas por forwarding ou escrita no primeiro meio-ciclo de ciclo.
    Total de stalls =2, total de ciclos = 10 + 2 = 12.
Diagrama (“s” =1 ciclo de stall):
Ciclo
Instr 123456789101112
I 1 lw IF ID EX MEM WB
I 2 add IF ID s EX MEM WB
I 3 lw IF ID EX MEM WB
I 4 sub IF ID s EX MEM WB
I 5 or IF ID EX MEM WB
I 6 sw IF ID EX MEM WB

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:
1. lw t\(0, 0()s 0)
2. lw t\(1, 40()s 6)
3. add s\(0,)s 2, t\(04. sub)s 6, t\(1,)s 25. or s\(3,)s 6, $zero
6. sw s\(3, 50()s 1)
Agora cada uso de carga está a 2 instruções de distância, e com forwarding não há mais stalls.

Resposta

(i) 18 ciclos
(ii) 12 ciclos
(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\))

Exercícios relacionados