Esercizio 27pipeline MIPS, dipendenze e cicli totali di un ciclo

Quante volte gira il ciclo

$2 cresce di 4 a ogni iterazione e $3 vale all'inizio $2 + 396. BENZ ripete finché la differenza $4 = $3 - $2 è diversa da zero, cioè finché $2 non ha raggiunto $3: $396 / 4 = 99$ iterazioni.

a) Dipendenze sui dati

(La SW legge anche $2 come base, scritto dalla ADDI $2 precedente, ma quella ADDI è dopo la SW nel programma: nell'iterazione corrente la SW usa il $2 dell'iterazione precedente, già nel banco registri.)

b) Evoluzione delle prime istruzioni

Il salto è risolto alla fine di EX e la pipeline ferma il prelievo finché non si conosce l'indirizzo: l'istruzione successiva (il LW della iterazione dopo) viene prelevata nel ciclo in cui BENZ è in MEM.

Commento.

• Cicli 3-4. ADDI $1,$1,1 entra in EX al ciclo 5, non 4: LW produce $1 solo alla fine del suo MEM (ciclo 4), 1 stallo.
• Cicli 5-7. SW $1,0($2) aspetta il WB di ADDI $1 (ciclo 7): ID ai cicli 5, 6, 7 e EX al ciclo 8 (2 stalli; la ADDI $2 dietro è ferma in IF).
• Ciclo 10. SUB è in EX e riceve $2 dall'uscita ALU di ADDI $2 (ora in MEM) tramite EX/MEM: nessuno stallo.
• Ciclo 11. BENZ valuta la condizione in EX con $4 appena calcolato da SUB (ora in MEM).
• Ciclo 12. BENZ è in MEM: l'indirizzo target è noto e al ciclo 12 viene prelevato il LW della iterazione successiva. Il salto fa sovrapporre il MEM di BENZ con l'IF del LW seguente: un'iterazione dura 11 cicli (dal ciclo 1 al ciclo 12 il prossimo IF).

Numero totale di cicli

• Le prime 98 iterazioni hanno ciascuna 11 cicli "di passo": il LW di ogni iterazione inizia 11 cicli dopo quello precedente: $98 \times 11 = 1078$.
• L'ultima iterazione (la 99ª) non ha un successore: dal suo IF al WB di BENZ passano 13 cicli (come nel diagramma: IF di LW al ciclo 1, WB di BENZ al ciclo 13).

$$98 \cdot 11 + 13 = 1091 \text{ cicli di clock.}$$

Convenzione usata: si conta anche lo stadio WB di BENZ, perché ogni istruzione attraversa tutti e 5 gli stadi e l'esecuzione finisce quando l'ultima ha completato il WB: 1091 cicli, valore della soluzione allegata al testo. Se invece si considera che il WB di BENZ non fa nulla e non si conta, il totale è 1090.

Confronto: senza stalli (CPI ideale = 1) servirebbero $99 \times 6 + 4 = 598$ cicli. Il codice costa quasi il doppio per gli stalli del load-use, della SW e del salto.

Verifica con un simulatore

import re

def parse(riga):
    riga = riga.strip()
    op, resto = riga.split(None, 1)
    a = [x.strip() for x in resto.split(",")]
    if op == "LW":
        return dict(op=op, dst=a[0], ex=[re.search(r"\((\$\d+)\)", a[1]).group(1)], mem=[], tipo="load")
    if op == "SW":
        return dict(op=op, dst=None, ex=[re.search(r"\((\$\d+)\)", a[1]).group(1)], mem=[a[0]], tipo="store")
    if op == "BENZ":
        return dict(op=op, dst=None, ex=[a[0]], mem=[], tipo="salto")
    return dict(op=op, dst=a[0], ex=[x for x in a[1:] if x.startswith("$")], mem=[], tipo="alu")

def cicli_totali(corpo, iterazioni):
    ins = [parse(r) for r in corpo] * iterazioni
    ex, idc, ifc = [], [], []
    for i, c in enumerate(ins):
        if i == 0:
            f, d = 1, 2
        else:
            f = ex[i - 1] + 1 if ins[i - 1]["tipo"] == "salto" else idc[i - 1]   # salto: si preleva con il salto in MEM
            d = max(f + 1, ex[i - 1])                                              # in ID quando la precedente è in EX
        e = d + 1
        for r in c["ex"] + c["mem"]:
            for p in range(i - 1, -1, -1):
                if ins[p]["dst"] == r:
                    if r in c["mem"]:
                        e = max(e, ex[p] + 3)                                      # dato della store: dopo il WB
                    else:
                        e = max(e, ex[p] + (2 if ins[p]["tipo"] == "load" else 1))  # forwarding verso EX
                    break
        ifc.append(f); idc.append(d); ex.append(e)
    return ex[-1] + 2, ifc

corpo = ["LW $1, 0($2)", "ADDI $1, $1, 1", "SW $1, 0($2)", "ADDI $2, $2, 4", "SUB $4, $3, $2", "BENZ $4, loop"]
print(cicli_totali(corpo, 1)[0], cicli_totali(corpo, 2)[0])      # 13 24: 13 per una iterazione, +11 per ogni altra
tot, ifc = cicli_totali(corpo, 99)
print(tot)                                                       # 1091
print(ifc[6] - ifc[0])                                           # 11: passo tra una iterazione e la successiva
print(99 * 6 + 4)                                                # 598: tempo senza stalli

Il simulatore riproduce i numeri della soluzione allegata al testo (11 cicli per iterazione, 1091 in totale).

Errori comuni

• Moltiplicare $99 \times 13$ (1287): le iterazioni si sovrappongono di 2 cicli (il MEM e il WB di BENZ con l'IF e l'ID del LW successivo) e il passo è 11.
• Non contare le 99 iterazioni (396/4) ma 100 o 396.
• Dimenticare che LW → ADDI costa uno stallo anche con forwarding (load-use).
• Dimenticare il vincolo della SW (dato da scrivere letto in ID, nel ciclo del WB della produttrice).
• Far partire l'IF dell'istruzione successiva a un salto prima che l'indirizzo target sia noto (qui: quando BENZ è in MEM).