Pipeline - accelerazione e conflitti

La pipeline ("catena di montaggio") è una particolare organizzazione della CPU, tipica dei processori ad alte prestazioni e oggi presente anche in molti µC RISC e nei DSP, con livelli di complessità inferiori a quelli dei PC. Consiste in una catena di stadi che eseguono in successione temporale le azioni necessarie all'esecuzione delle istruzioni, lavorando insieme su istruzioni diverse. Aumenta le istruzioni completate nell'unità di tempo, ma può rendere più difficile ottimizzare il codice.

Il principio

L'esecuzione di Add R1, num ($[R_1]\leftarrow[R_1]+M[num]$) richiede cinque fasi: fetch (F), decodifica (D), lettura operandi (R), esecuzione (E), scrittura risultati (W). Supponiamo unità separate con questi tempi: F 5 ns, D 3 ns, R 5 ns, E 2 ns, W 5 ns.

• Ciclo singolo: il clock deve contenere tutte le fasi: $5+3+5+2+5=20$ ns.
• Multiciclo: ogni fase occupa almeno un ciclo; il ciclo è fissato dalla fase più lenta (5 ns), quindi $5\times5=25$ ns per istruzione.
• Pipeline: ogni fase è uno stadio; il clock è 5 ns (lo stadio più lento) e a regime a ogni ciclo di clock una istruzione esce dalla catena. Tra gli stadile sezioni della catena della pipeline: ognuna esegue una fase delle istruzioni ci sono registri buffer (ingresso e uscita di ciascuno); in situazioni di conflittosituazione in cui la pipeline non può proseguire normalmente (risorsa occupata, dato non pronto, salto) si possono usare percorsi tra stadi non consecutivi (internal forwarding), quindi il controllo può diventare complesso.

Nel multiciclo e nel ciclo singolo le unità lavorano solo per una frazione del tempo di esecuzione: la pipeline interviene proprio su questa inefficienza.

Accelerazione

Con $n$ stadi e un clock $T_{clk}$:

• una singola istruzione impiega comunque $n\,T_{clk}$ (la latenza non diminuisce);
• il tempo di riempimentotempo che serve a riempire la pipeline: finché non è piena non esce un'istruzione per ciclo della pipeline è $n\,T_{clk}$: solo dopo questo tempo si comincia a completare un'istruzione per ciclo;
• $N$ istruzioni richiedono $(n+N-1)\,T_{clk}$, quindi il numero medio di istruzioni completate nell'unità di tempo è $\dfrac{N}{(n+N-1)T_{clk}}$, che tende a $\dfrac1{T_{clk}}$ solo per $N\gg n$.

L'accelerazione è il rapporto tra le istruzioni per unità di tempo della pipeline e quelle di un'organizzazione multiciclo con le stesse unità e lo stesso clock: $$S=\frac{N\,n\,T_{clk}}{(n+N-1)T_{clk}}=\frac{N\,n}{n+N-1}\ \le\ n .$$ Esempio (5 stadi da 5 ns): per $N=100$ istruzioni la pipeline impiega $(5+99)\cdot5=520$ ns; il multiciclo $100\cdot25=2500$ ns; il ciclo singolo $100\cdot20=2000$ ns. Accelerazionerapporto tra le prestazioni della pipeline e quelle di una organizzazione multiciclo con lo stesso clock rispetto al multiciclo $2500/520=4{,}81$ (limite $5$), rispetto al ciclo singolo $3{,}85$. Per $N=5$ solo $2{,}78$.

In pratica il valore è inferiore a $n$ per il riempimento e per i conflitti. Nei µC e DSP il numero di stadi è di solito tre (fetch, decodifica, esecuzione) come nei processori ARM; esistono DSP con 5 stadi (TMS320C54x). Un esempio con $T_{clk}=50$ ns e 3 stadi: tempo di completamento di una istruzione $3\cdot50=150$ ns; istruzioni completate in un secondo, a regime, $1/50\text{ ns}=20\cdot10^6$; dopo uno svuotamento (per esempio un salto incondizionato gestito con stalli) il regime si raggiunge dopo 150 ns.

Conflitti (hazard)

Conflitti strutturali. Due istruzioni richiedono lo stesso stadio (la stessa unità funzionale) nello stesso ciclo, per esempio una memoria sola per istruzioni e dati. L'unica soluzione definitiva è hardware (unità duplicate: memorie separate per dati e istruzioni), ma oltre un certo livello il costo diventa eccessivo: si accetta un compromesso e il conflitto resta possibile. Per gestirlo si introducono stalli (cicli vuoti, {{NOP|istruzione che non fa nulla, usata per riempire un ciclo}}): tecnica di interlocking.

Conflitti sui dati. Un'istruzione $j$ usa il risultato di una precedente $i$ che non è ancora conclusa. Casi: $j$ legge un dato prodotto da $i$ prima che $i$ lo scriva (RAWRead After Write: una istruzione legge un dato prima che la precedente lo abbia scritto); $j$ scrive un dato che $i$ non ha ancora letto; $j$ scrive nella stessa posizione di $i$ prima che $i$ sia conclusa. Sono pericolosi perché danno risultati sbagliati senza errore. Esempio:

add R1, num   ; R1 = R1 + M[num]
add R2, R1    ; R2 = R2 + R1   (legge R1 prima che sia stato aggiornato!)

Il controllore deve riconoscerli: ogni volta che abilita la lettura operandi, controlla se istruzioni negli stadi E o W stanno per scrivere su quell'operando. La risoluzione:

• interlocking: si ritarda la lettura dell'operando (stalli);
• bypass (internal forwarding): il dato richiesto è prelevato appena disponibile, prima ancora della sua scrittura nel registro;
• sovrapposizione: nello stesso ciclo, diviso a metà, prima si scrive e poi si legge;
• riordinamento: il compilatore o il programmatore altera la sequenza per evitare il conflitto. Esempi con add R3,R4; sub R1,R3: conflitto risolvibile per sovrapposizionescrittura nella prima metà del ciclo e lettura nella seconda, per far vedere il dato appena scritto (se la scrittura precede la lettura) o con interlockingtecnica che ritarda una istruzione con cicli vuoti (stalli) finché il conflitto è risolto.

Conflitti di controllo. Un salto (jump) o una diramazione (branch) fa scartare le istruzioni già caricate nella pipeline: si crea una bollagruppo di cicli in cui la pipeline non completa alcuna istruzione (cicli perduti). Soluzioni: stallo (interlocking), salto ritardatosalto in cui le istruzioni successive già entrate nella pipeline vengono comunque eseguite (delayed jump: le istruzioni successive al salto, già entrate, vengono comunque eseguite, e il programmatore le deve scrivere in quell'ordine: complica l'assembly) o, per i salti condizionati, predizione dell'esito con meccanismi statistici rudimentali. Un caso particolare è l'interruzione: il passaggio alla routine di servizio agisce come un salto e allunga la latenzatempo che una singola istruzione impiega per attraversare la pipeline (Sistemi di interruzioni - latenza, nesting e sostenibilitàCon $N$ sorgenti, ciascuna ISR $i$ ha durata $T_{d,i}$ (spesso già comprensiva della latenza intrinseca $T_{LI}$ e dell'istruzione in corso) e periodo minimo $T_{p,i}$. Condizione necessaria: $\sum_iT_{d,i}/T_{p,i}<1$ (la percentuale di impegno della CPU è la somma). Condizione di intervallo per ogni $i$ (priorità 1 = massima): $T_{d,i}+\sum_{k<i}n_k,T_{d,k};[+\max(T_{RC},\max_{j>i}T_{d,j})\text{ senza nesting}]\le T_{p,i}$, con $n_k=\lceil T_{p,i}/T_{p,k}\rceil$. Latenza massima della priorità $n$: con nesting $T_{LI}+\sum_{i<n}T_{ex,i}$; senza nesting si aggiunge $\max_{j>n}T_{ex,j}$.Sistemi di interruzioni - latenza, nesting e sostenibilità →). I µC e DSP più semplici gestiscono i salti sempre con interlocking (un salto costa più cicli); alcuni DSP usano solo salti ritardati.

Confronto numerico pipeline e multiciclo

Con il mix 24% load, 12% store, 44% operazioni ALU, 20% salti, un multiciclo a 4 segmenti ha $NC=3{,}16$ (Unità di controllo - cablata, microprogrammata, singolo ciclo e multicicloL'unità di controllo preleva (fetch), decodifica ed esegue le istruzioni generando i segnali che attivano registri, ALU e memoria. Può essere cablata (logica dedicata, veloce, poco flessibile, oggi la norma) o microprogrammata (una piccola CPU con ROM di microcodice: flessibile ma lenta e grande). Con un solo bus le operazioni vanno distribuite su più segmenti di clock (multiciclo: il clock è dettato dall'unità più lenta); con memorie e ALU separate si può fare singolo ciclo (il clock è dettato dall'istruzione più lenta). Il tempo medio per istruzione dipende dal mix di istruzioni: $NC=\sum f_i,NC_i$.Unità di controllo - cablata, microprogrammata, singolo ciclo e multiciclo →). Con una pipeline a 4 stadi che gestisce senza interlocking la metà dei load (penalità 1 ciclo per l'altra metà) e la metà dei salti (penalità 2 cicli per l'altra metà):

• load: $0{,}5\cdot1+0{,}5\cdot2=1{,}5$ cicli; salti: $0{,}5\cdot1+0{,}5\cdot3=2$ cicli;
• $NC=1{,}5\cdot0{,}24+1\cdot(0{,}12+0{,}44)+2\cdot0{,}2=1{,}32$ cicli per istruzione. Il tempo di esecuzione si riduce di quasi il 60% e l'accelerazione è $3{,}16/1{,}32=2{,}4$.

Fattori che limitano l'accelerazione: i conflitti sui dati (con più stadi uno stallo costa di più), il rallentamento dei salti (cresce con $n$), la complessità del controllo che costringe a ridurre la frequenza di clock.

Pipeline nei processori ARM

Gli ARM7 hanno una pipeline a 3 stadi (Fetch, Decode, Execute). Nel caso ideale (istruzioni solo su registri) ogni istruzione si completa in un ciclo. Un salto incondizionato fa perdere 2 cicli (due istruzioni già caricate vanno scartate); una lettura dalla memoria (LDR) costa un ciclo in più (due cicli macchina). Non tutti gli ARM hanno la stessa profondità (non è vero che "tutti" abbiano 5 stadi).

Superscalare e VLIW

I DSP di ultima generazione usano architetture superscalari: più unità funzionali replicate (fattore 2-4) per eseguire molte istruzioni in parallelo, con pipeline dinamicapipeline che può eseguire le istruzioni fuori ordine per evitare le bolle (esecuzione fuori ordine: unità di fetch e decode, unità di esecuzione e unità di write-back che scrive solo i risultati assestati), predizione dei salti e cache. Costano molto e consumano molto: non sono adatti ai controllori embedded. I VLIW hanno pipeline statica, poco parallelismo hardware e istruzioni larghe (Architettura del repertorio di istruzioni - RISC, CISC, VLIW e indirizzamentoL'architettura è l'insieme delle risorse visibili al programmatore (istruzioni, modi di indirizzamento). RISC: poche istruzioni semplici, di uguale lunghezza, decodifica cablata, quasi tutte a 1 ciclo; CISC: molte istruzioni complesse, decodifica microprogrammata, più cicli. I DSP sono RISC "potenziati" (MAC, saturazione, barrel shifter, arrotondamento, VLIW, SIMD); i modi di indirizzamento tipici sono immediato, a registro, diretto, indiretto, con auto-incremento, circolare e a bit rovesciati (per la FFT).Architettura del repertorio di istruzioni - RISC, CISC, VLIW e indirizzamento →).

Errori comuni

• Credere che la pipeline riduca il tempo di una istruzione: aumenta il throughput, la latenza resta $n\,T_{clk}$.
• Dire che l'accelerazione cresce linearmente con $n$: è limitata superiormente da $n$ e in pratica da conflitti e dal clock; la probabilità di conflitti sui dati aumenta con $n$.
• Dire che i conflitti sui dati si risolvono sempre con stalli: esistono bypasspercorso che porta il risultato di uno stadio direttamente a uno stadio precedente, senza passare dal registro, sovrapposizione, riordino.