Esercizio 25pipeline MIPS con forwarding, stalli e bypass

Il modello della pipeline

• Stadi: IF (prelievo), ID (decodifica e lettura dei registri), EX (ALU o calcolo dell'indirizzo), MEM (accesso alla memoria dati), WB (scrittura del registro). Il banco registri si scrive nella prima metà del ciclo e si legge nella seconda: se il WB di una istruzione e l'ID di un'altra cadono nello stesso ciclo, la seconda legge già il valore nuovo.
• Forwarding (bypass): il risultato viene portato direttamente all'ingresso della ALU (stadio EX) dell'istruzione che lo usa:
  • dall'uscita della ALU di un'istruzione aritmetica, tramite il registro EX/MEM.ALUOutput, all'EX dell'istruzione subito dopo (distanza 1);
  • dal registro MEM/WB (ALUOutput per le aritmetiche, LMD, il dato letto dalla memoria, per una LW) all'EX dell'istruzione a distanza 2.
• Una LW produce il dato solo alla fine del suo MEM: l'istruzione successiva che lo usa in EX deve aspettare 1 ciclo (load-use), anche con il forwarding.
• Come nelle soluzioni dei temi, non è previsto un bypass verso lo stadio MEM: il dato che una SW scrive in memoria (il primo registro, rt) si legge solo dal banco registri nello stadio ID, quindi la SW deve avere l'ID nello stesso ciclo del WB della produttrice, o dopo. Il registro base dell'indirizzo, invece, serve in EX e può arrivare dal forwarding.

Dipendenze sui dati (RAW)

(SUB e SUBI scrivono entrambi $9: è una dipendenza WAW, senza effetti in una pipeline in ordine; ogni lettura di $9 si riferisce alla scrittura più recente che la precede.)

Evoluzione della pipeline

Commento ai cicli.

• Ciclo 4. LW è in EX con $9 ottenuto dall'uscita della ALU di ADD (registro EX/MEM): bypass EX.ALUOutput di ADD → ingresso superiore della ALU di LW.
• Cicli 4-5: stallo. SUB ha bisogno di $1, che LW produce al ciclo 5 (fine del suo MEM). SUB resta in ID per un ciclo (il secondo ID) e la SW dietro resta in IF. Al ciclo 6 SUB va in EX e riceve $1 dal registro MEM/WB.LMD: bypass MEM.LMD di LW → ALU di SUB.
• Ciclo 6. SW $3, 73($1) ha l'ID nel ciclo del WB di LW (6): legge $1 dal banco registri, senza bypass.
• Ciclo 9. SW $7, 78($9) è in EX con $9 da SUBI (che è in MEM): bypass EX.ALUOutput di SUBI → ALU della SW.
• Cicli 9-10: stallo. L'ultima SW deve scrivere in memoria $9, scritto da SUBI, che fa il WB al ciclo 10. Il suo ID (secondo ID) cade nel ciclo 10, la SW legge $9 dal banco registri e va in EX al ciclo 11.

Totale: $7$ istruzioni $+ 4 +$ 2 stalli = 13 cicli (l'ultimo WB è al ciclo 13).

Un'altra istanza (esempio di compito a.a. 2014-15)

SUB $2,$7,$5; LW $1,7($2); ADD $2,$1,$8; SW $3,73($1); SUBI $2,$3,4; ADDI $7,$3,8; ADD $1,$7,$2. Con lo stesso modello: 12 cicli, 1 solo stallo (il load-use di ADD $2,$1,$8), e i bypass sono quelli indicati nella soluzione allegata al testo: EX.ALUOutput di SUB → ALU di LW; MEM.LMD di LW → ALU di ADD; MEM.ALUOutput di SUBI → secondo ingresso della ALU dell'ultima ADD; EX.ALUOutput di ADDI → primo ingresso della ALU dell'ultima ADD.

Verifica con un programma

import re

def pipeline(codice):
    """Pipeline MIPS a 5 stadi con forwarding verso EX, nessun bypass verso MEM per il dato di una store.
    Restituisce (cicli totali, stalli per istruzione)."""
    ins = []
    for riga in codice:
        op, resto = riga.split(None, 1)
        a = [x.strip() for x in resto.split(",")]
        if op in ("LW", "SW"):
            base = re.search(r"\((\$\d+)\)", a[1]).group(1)
            ins.append((op, a[0] if op == "LW" else None, [base], [a[0]] if op == "SW" else []))
        else:
            ins.append((op, a[0], [x for x in a[1:] if x.startswith("$")], []))
    ex, idc, stalli = [], [], []
    for i, (op, scrive, per_ex, per_mem) in enumerate(ins):
        if i == 0:
            ifc, id_i = 1, 2
        else:
            ifc = idc[i - 1]
            id_i = max(ifc + 1, ex[i - 1])
        e = id_i + 1
        for r in per_ex + per_mem:
            for p in range(i - 1, -1, -1):
                if ins[p][1] == r:
                    if r in per_mem:                           # dato della store: banco registri, dopo il WB
                        e = max(e, ex[p] + 2 + 1)
                    else:                                       # operando della ALU: forwarding
                        e = max(e, ex[p] + (2 if ins[p][0] == "LW" else 1))
                    break
        idc.append(id_i); ex.append(e); stalli.append(e - id_i - 1)
    return ex[-1] + 2, stalli

codice = ["ADD $9, $7, $5", "LW $1, 7($9)", "SUB $9, $1, $8", "SW $3, 73($1)",
          "SUBI $9, $3, 4", "SW $7, 78($9)", "SW $9, A($7)"]
print(pipeline(codice))                  # (13, [0, 0, 1, 0, 0, 0, 1])

altro = ["SUB $2, $7, $5", "LW $1, 7($2)", "ADD $2, $1, $8", "SW $3, 73($1)",
         "SUBI $2, $3, 4", "ADDI $7, $3, 8", "ADD $1, $7, $2"]
print(pipeline(altro))                   # (12, [0, 0, 1, 0, 0, 0, 0])

Errori comuni

• Dimenticare lo stallo del load-use: con la LW il forwarding non basta, resta 1 ciclo.
• Dimenticare che una SW ha due registri letti con ruoli diversi: la base (necessaria in EX, può avere il bypass) e il dato da scrivere (letto in ID, senza bypass nel modello del corso).
• Usare come produttrice la scrittura sbagliata di $9 (non la più recente).
• Indicare il bypass dal registro sbagliato: distanza 1 → EX/MEM, distanza 2 → MEM/WB, e per le load il dato è nel LMD, non nell'ALUOutput.
• Dimenticare che durante lo stallo l'istruzione resta in ID e quella dopo resta in IF.