Pipeline

L'idea

Una pipeline non rende più veloce la singola istruzione: aumenta il numero di istruzioni completate per unità di tempo (throughput). Come in una catena di montaggio, il lavoro è diviso in fasi e ogni stadio lavora contemporaneamente su un'istruzione diversa.

Confronto con la replicazione: $n$ esecutori completi in parallelo producono un lavoro ogni $T/n$ ma ognuno ha bisogno di tutti gli strumenti; nella catena di montaggio ogni esecutore è specializzato in una fase e gli strumenti non vanno replicati.

Pipeline a 5 stadi (stile MIPS)

Diagramma (ogni riga un'istruzione, ogni colonna un ciclo):

Controllo utile negli esercizi: in una colonna non può comparire due volte lo stesso stadio.

Registri di pipeline (IF/ID, ID/EX, EX/MEM, MEM/WB) tra uno stadio e il successivo conservano l'istruzione, i dati e i segnali di controllo che servono agli stadi successivi.

Conflitto sul banco dei registri: WB di un'istruzione e ID di un'altra lo usano nello stesso ciclo. Si risolve scrivendo nella prima metà del ciclo e leggendo nella seconda. Il conflitto sulla memoria tra IF e MEM si risolve con cache separate per istruzioni e dati (vedi Memoria cacheBlocchi, linee ed etichette; scomposizione dell'indirizzo; associazione diretta, completamente associativa e associativa a insiemi con calcolo dei campi; politiche di rimpiazzo (LRU, FIFO, casuale); politiche di scrittura (write-through, write-back con bit sporco, write-allocate); dimensione del blocco; cache multilivello e separate; come ridurre i miss; quesiti sui campi dell'indirizzo.Memoria cache →).

Prestazioni

Tempo di ciclo: lo stadio più lento più il ritardo dei registri di pipeline $d$:

$$\tau = \max_i \tau_i + d$$

Tempo per eseguire $n$ istruzioni con $k$ stadi, senza stalli: la prima istruzione esce dopo $k$ cicli, poi ne esce una per ciclo:

$$T_k = (k + n - 1)\,\tau$$

Esempio: 9 istruzioni, 6 stadi → $6 + 9 - 1 = 14$ cicli invece di $9 \cdot 6 = 54$.

Speedup rispetto all'esecuzione senza pipeline (che richiede $k\tau$ per istruzione):

$$S_k = \frac{n\,k\,\tau}{(k + n - 1)\,\tau} = \frac{nk}{k + n - 1} \xrightarrow{n \to \infty} k$$

Con $k = 5$ e $n = 100$: $S = 500/104 \approx 4{,}8$.

Esempio con stadi sbilanciati: stadi da 200, 100, 200, 200, 100 ps, $d = 20$ ps → $\tau = 220$ ps. Senza pipeline un'istruzione dura $800$ ps; a regime la pipeline ne completa una ogni 220 ps: speedup $800/220 \approx 3{,}6$, non 5. Lo stadio più lento detta il passo.

Con stalli (vedi Hazard nella pipelineHazard strutturali, sui dati e sul controllo; dipendenze RAW, WAR e WAW; stalli e bolle con diagrammi; data forwarding (bypass) e caso load-use; riordino delle istruzioni da parte del compilatore e dell'hardware; costo dei salti.Hazard nella pipeline →), a regime:

$$S = \frac{k}{1 + \text{frazione di cicli di stallo per istruzione}}$$

Limiti

• Stadi sbilanciati: il clock si adegua al più lento.
• Overhead dei registri di pipeline: con stadi troppo corti $d$ diventa una parte rilevante di $\tau$.
• Hazard: dipendenze tra istruzioni vicine che costringono a fermare la pipeline (dati, controllo, risorse).

Più stadi (pipeline profonde, oltre 15–20) permettono clock più alti ma rendono più costosi gli stalli, soprattutto dopo un salto sbagliato (vedi Branch predictionTecniche per gli hazard sul controllo: stallo, flussi multipli, prelievo anticipato del bersaglio, loop buffer, salto ritardato; predizione statica e dinamica con bit di storia, predittore a 1 e a 2 bit con esempio su un ciclo, tabella dei bersagli (BTB); costo di una predizione errata.Branch prediction →).

Errori tipici

• Calcolare il tempo di $n$ istruzioni come $n \cdot \tau$ dimenticando il riempimento iniziale ($k - 1$ cicli).
• Pensare che la latenza della singola istruzione diminuisca: aumenta leggermente (per $d$ e per lo sbilanciamento).