Esercizio 24pipeline MIPS senza forwarding, numero di cicli

Regola per contare gli stalli

Pipeline a 5 stadi: IF, ID (lettura dei registri), EX, MEM, WB (scrittura dei registri). Senza forwarding un'istruzione che legge un registro scritto da una precedente deve avere il proprio ID nello stesso ciclo del WB della produttrice, o dopo (il WB scrive nella prima metà del ciclo e l'ID legge nella seconda). Se la produttrice ha IF al ciclo $t$, il suo WB è al ciclo $t + 4$ (senza stalli propri), quindi il consumatore, che a regime avrebbe ID al ciclo $t + 1 + d$ ($d$ = distanza in istruzioni), deve aspettare:

Durante lo stallo l'istruzione resta in ID e quella dopo resta in IF. Gli stalli si sommano perché ciascuno ritarda tutte le istruzioni successive. Numero di cicli: $\text{istruzioni} + 4 + \text{stalli}$ ($7 + 4 +$ stalli).

Individuare le dipendenze

Per ogni istruzione i registri letti (R) e quello scritto (W):

Per l'istruzione 6 le due attese avvengono in parallelo (si aspetta che entrambi i registri siano pronti): si prende il massimo, non la somma. Gli stalli totali sono $2 + 2 + 2 = 6$.

Diagramma

• Istruzione 3: $2 è scritto da SUB nel WB del ciclo 6 → l'ID di LW va dal 4 al 6 e l'EX parte al 7.
• Istruzione 4: $3 è scritto da LW $3 nel WB del ciclo 9 → l'ID di SUBI finisce al 9, EX al 10.
• Istruzione 5: $2 viene letto in ID al ciclo 10, dopo il WB di SUB (ciclo 6): nessuna attesa.
• Istruzione 6: $2 da ADDI (WB al ciclo 13) e $3 da SUBI (WB al ciclo 12) → ID fino al 13, EX al 14.
• Istruzione 7: nessuna attesa; l'ID viene però ritardato dall'attesa dell'istruzione davanti (stalli propagati), e WB al ciclo 17.

Totale: $7 + 4 + 6 = \mathbf{17}$ cicli → risposta d.

Versione 2015-16. Le dipendenze hanno la stessa forma (ADD → LW, LW → SUBI, ADDI e SUBI → SW; SUB finale non dipende da nulla di vicino): stessi 6 stalli, 17 cicli, che non è tra le opzioni a) 13, b) 15, c) 19, d) 14 → risposta e (nessuna delle precedenti). Le altre opzioni non corrispondono a un conteggio corretto: sono distrattori (chi ignora gli stalli di una delle dipendenze, o ne conta meno per istruzione).

Verifica con un programma

import re

def cicli(codice):
    """Pipeline MIPS a 5 stadi: scrittura WB nella prima metà del ciclo e lettura ID nella seconda."""
    ins = []
    for riga in codice:
        op, resto = riga.split(None, 1)
        args = [a.strip() for a in resto.split(",")]
        if op in ("LW", "SW"):
            base = re.search(r"\((\$\d+)\)", args[1]).group(1)
            scrive = args[0] if op == "LW" else None
            legge = [base] + ([args[0]] if op == "SW" else [])
        else:
            scrive, legge = args[0], [a for a in args[1:] if a.startswith("$")]
        ins.append((op, scrive, legge))
    ex, id_first, if_first = [], [], []
    for i, (op, scrive, legge) in enumerate(ins):
        ifc = 1 if i == 0 else id_first[i - 1]            # entra in IF quando la precedente lascia IF
        idc = ifc + 1 if i == 0 else max(ifc + 1, ex[i - 1])  # entra in ID quando la precedente passa a EX
        e = idc + 1
        for r in legge:
            for p in range(i - 1, -1, -1):
                if ins[p][1] == r:
                    wb = ex[p] + 2
                    e = max(e, wb + 1)                     # ID (ciclo e-1) nel ciclo del WB o dopo
                    break
        if_first.append(ifc); id_first.append(idc); ex.append(e)
    return ex[-1] + 2

codice_1415 = ["LW $5, 80($0)", "SUB $2, $0, $3", "LW $3, 800($2)", "SUBI $3, $3, 3",
               "ADDI $2, $2, 4", "SW $3, 108($2)", "SUB $4, $5, $3"]
codice_1516 = ["SW $3, 80($0)", "ADD $2, $3, $1", "LW $1, 800($2)", "SUBI $1, $1, 3",
               "ADDI $2, $2, 4", "SW $1, 108($2)", "SUB $4, $3, $1"]
print(cicli(codice_1415), cicli(codice_1516))      # 17 17

Errori comuni

• Contare uno stallo solo per il caso "istruzione immediatamente successiva": con $d = 2$ c'è ancora 1 stallo.
• Sommare gli stalli dei due operandi della stessa istruzione (SW) invece di prendere il massimo.
• Dimenticare di ritardare anche le istruzioni successive (la pipeline è in ordine).
• Usare le regole del forwarding quando il testo dice "senza data-forwarding" (e viceversa).
• Dimenticare la possibilità di scrittura e lettura nello stesso ciclo: senza di essa $d=1$ costerebbe 3 stalli.