Esercizio 8ritardo del sommatore e prestazioni di una pipeline (temi d'esame 2004, novembre 2020 e febbraio 2023)

---

Teoria usata: ALU - sommatore, overflow, carry look-ahead e shiftL'ALU è un insieme di celle a 1 bit (full adder + selettori) collegate in parallelo: somma, sottrae ($A-B=A+\overline B+1$: si inverte $B$ e si porta il riporto iniziale a 1), fa AND/OR. Il ritardo è dominato dal riporto: nel ripple-carry cresce linearmente con i bit; col carry look-aheadtecnica che calcola in anticipo i riporti da generazione e propagazione, riducendo il ritardo i riporti si calcolano da generazione $g_i=A_iB_i$ e propagazione $p_i=A_i+B_i$ in pochi livelli di logica. L'overflow è $V=C_{in,n-1}\oplus C_{out,n-1}$. Gli shift logici inseriscono 0, gli aritmetici estendono il segno; il barrel shiftercircuito che sposta una parola di un numero qualsiasi di posizioni in un solo ciclo sposta di $m$ posti in un ciclo.ALU - sommatore, overflow, carry look-ahead e shift →, Pipeline - accelerazione e conflittiLa pipeline divide l'esecuzione in $n$ stadi (fetch, decodifica, lettura, esecuzione, scrittura) che lavorano contemporaneamente su istruzioni diverse. Il clock è dettato dallo stadio più lento; a regime si completa un'istruzione per ciclo. Per $N$ istruzioni servono $(n+N-1),T_{clk}$: l'accelerazione rispetto al multiciclo tende a $n$ ma è sempre minore (riempimento, conflitti). I conflitti sono strutturali (stessa risorsa), sui dati (RAW...) e di controllo (salti): si risolvono con stalli (interlocking), bypass, sovrapposizione, riordino, salti ritardati. La latenza di una singola istruzione non diminuisce.Pipeline - accelerazione e conflitti →, 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 →.

(i) Ripple carry e CLA

Nel ripple carry ogni cella introduce $2\tau$ sul riporto (due livelli di logica: un AND e un OR): per $n=8$ celle $8\cdot2\tau=16\tau$, più $\tau$ per formare l'ultimo bit di somma: 17 ns. Nel CLA a blocchi da 4: la generazione dei riporti dentro un blocco richiede 3 livelli di logica, tra i due blocchi altri 2: $3+2=5\tau$ per i riporti, più $\tau$ per l'ultima somma: 6 ns. Il CLA è circa 3 volte più veloce già a 8 bit (e 5-6 volte a 16 bit: $3+2=5\tau$ contro $32\tau$).

(ii) Pipeline a 3 stadi

• Tempo di completamento di una istruzione (latenza): $3\cdot50=\mathbf{150\ ns}$.
• A regime una istruzione per ciclo: $\frac1{50\text{ ns}}=\mathbf{20\cdot10^6}$ istruzioni al secondo.
• Un salto incondizionato gestito con stalli (interlocking) svuota la pipeline: le istruzioni già caricate sono scartate e il regime si ripristina dopo il tempo di riempimento: 150 ns (3 cicli) di ritardo tra il completamento dell'istruzione corrente e quello della successiva.

(iii) Ciclo singolo, multiciclo, pipeline

• Ciclo singolo: clock = somma di tutte le fasi $=5+3+5+2+5=20$ ns; 100 istruzioni: $100\cdot20=2000$ ns.
• Multiciclo: clock = fase più lenta = 5 ns; 5 cicli per istruzione = 25 ns; 100 istruzioni: $2500$ ns.
• Pipeline a $n=5$ stadi, clock 5 ns: $(n+N-1)T_{clk}=(5+99)\cdot5=520$ ns.
• Accelerazione: rispetto al multiciclo $\frac{2500}{520}=\mathbf{4{,}81}$ (limite 5 per $N\to\infty$; per $N=5$ sarebbe $\frac{5\cdot5}{5+4}=2{,}78$); rispetto al ciclo singolo $\frac{2000}{520}=3{,}85$. La latenza di una istruzione nella pipeline resta $5\cdot5=25$ ns (uguale al multiciclo): migliora solo la frequenza di completamento.

(iv) Conflitti con bypass

Le istruzioni: (1) $r_1=r_2+r_3=2+2=4$; (2) $r_3=r_2+r_3=2+2=4$; (3) $r_1=r_1+r_1=4+4=8$; (4) $r_3=r_2+r_3=2+4=6$; (5) $r_1=r_2+r_1=2+8=10$. I conflitti sui dati (lettura di un registro non ancora aggiornato) sono: (3) legge $r_1$ scritto da (1), distanza 2 istruzioni; (4) legge $r_3$ scritto da (2), distanza 2; (5) legge $r_1$ scritto da (3), distanza 2. Con il bypass tra il modulo di esecuzione e quello di lettura il dato è inoltrato in tempo: risolvibili senza stalli. Valore finale $r_1=\mathbf{0x000A}$ ($=10$). Numero di cicli supponendo la pipeline già a regime: 5 (una istruzione per ciclo, nessuno stallo).

(v) Vero o falso

• a. Vero: la pipeline, a parità di clock e stadi, completa più istruzioni per unità di tempo.
• b. Falso: la latenza di una istruzione non diminuisce (anzi, con le registrazioni intermedie può crescere).
• c. Falso: l'accelerazione ideale è al massimo pari al numero di stadi ($S\le n$) ma non cresce linearmente, per via di riempimento e conflitti.
• d. Vero: più stadi, più istruzioni in volo contemporaneamente, quindi più probabili i conflitti sui dati e più costosi gli stalli.
• e. Falso: esistono il bypass (internal forwarding), la sovrapposizione e il riordino del codice.
• f. Falso: gli ARM7 hanno 3 stadi, altre famiglie più stadi.

Confronto con il mix di istruzioni

Per il mix 24% load, 12% store, 44% ALU, 20% salti (Pipeline - accelerazione e conflittiLa pipeline divide l'esecuzione in $n$ stadi (fetch, decodifica, lettura, esecuzione, scrittura) che lavorano contemporaneamente su istruzioni diverse. Il clock è dettato dallo stadio più lento; a regime si completa un'istruzione per ciclo. Per $N$ istruzioni servono $(n+N-1),T_{clk}$: l'accelerazione rispetto al multiciclo tende a $n$ ma è sempre minore (riempimento, conflitti). I conflitti sono strutturali (stessa risorsa), sui dati (RAW...) e di controllo (salti): si risolvono con stalli (interlocking), bypass, sovrapposizione, riordino, salti ritardati. La latenza di una singola istruzione non diminuisce.Pipeline - accelerazione e conflitti →) il numero medio di cicli per istruzione è 3,16 nel multiciclo e 1,32 nella pipeline a 4 stadi con le penalità indicate: accelerazione $3{,}16/1{,}32=2{,}4$.

Errori comuni

• Dire che la pipeline riduce il tempo di una singola istruzione.
• Sommare i tempi di tutte le unità per il clock della pipeline: il clock è dato dallo stadio più lento.
• Dimenticare il tempo di riempimento: $N$ istruzioni richiedono $(n+N-1)$ cicli, non $N$.
• Considerare conflitto il caso in cui il bypass risolve il problema.