Pipeline, hazard e architetture RISC e CISC

Nel computer a ciclo singolo il periodo di clock è la somma dei ritardi di tutti i blocchi (Un semplice microprocessore - istruzioni, ciclo singolo e cicli multipliIstruzioni a 16 bit: opcode (7 bit) + DR, SA, SB/OP (3 bit ciascuno) oppure formato di salto con offset a 6 bit (AD sinistro + AD destro, relativo al PC e con estensione di segno). Insieme di istruzioni load/store (solo LD e ST accedono ai dati): MOVA, INC, ADD, SUB, ..., LDI, ADI, LD, ST, BRZ, BRN, JMP. Nel computer a ciclo singolo (due memorie separate) il decoder combinatorio ricava MB, MD, RW, MW, PL, JB, BC dai bit 15, 14, 13, 9 dell'istruzione e $FS$ dai bit 12–9; il periodo di clock è la somma dei ritardi lungo il cammino peggiore (9,8 ns nell'esempio). Nel computer a cicli multipli (memoria unica) servono IR, registri interni R8–R15 e un decoder sequenziale: fetch (INF) + uno o più stati di esecuzione.Un semplice microprocessore - istruzioni, ciclo singolo e cicli multipli →): la velocità massima è bassa, e si riduce ancora aggiungendo il ritardo della unità di controllo. Si possono però identificare fasi precise dell'elaborazione, separarle con registri ed eseguirle in periodi di clock diversi: è la pipeline. Il quadro generale di architettura è in PipelineIdea della catena di montaggio; pipeline a 5 stadi IF, ID, EX, MEM, WB; tempo di ciclo, tempo per n istruzioni in una pipeline a k stadi e speedup con esempi svolti; registri di pipeline; scrittura e lettura dei registri nello stesso ciclo; limiti (stadi sbilanciati, hazard).Pipeline →, 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 →, 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 →, Architetture RISC e CISCMotivazioni del CISC (divario semantico) e dati sull'esecuzione dei programmi; caratteristiche delle architetture RISC; finestre di registri; allocazione dei registri con colorazione di un grafo; confronto e situazione attuale (MIPS, ARM, x86).Architetture RISC e CISC →.

Idea della pipeline

Più che una "conduttura" è una linea di produzione: ogni fase di lavorazione è separata dalle altre e più fasi sono attive in parallelo, ciascuna su un'istruzione diversa. Fasi tipiche del datapath: OF (operand fetch: lettura dei registri), EX (execute: unità funzionale), WB (write back: scrittura del risultato). Con la unità di controllo si hanno quattro stadi: IF (instruction fetch: l'istruzione è letta dalla memoria), DOF (decode and operand fetch: decodifica e lettura degli operandi), EX, WB.

Definizione (latenza e throughput)

• Latenza: durata totale di una istruzione: non cambia (anzi cresce un poco) con la pipeline.
• Throughput (resa): numero di istruzioni completate nell'unità di tempo: aumenta di un fattore circa uguale al numero di stadi.

Esempio. Con $3$ stadi da $1{,}0$ ns la latenza è $3\cdot1{,}0=3{,}0$ ns, ma a regime si completa una istruzione ogni $1{,}0$ ns (throughput $1$ GHz).

Esempio numerico: latenza e throughput

Datapath a ritardi (ns): lettura register file $0{,}6$, MUX B $0{,}2$, unità funzionale $0{,}8$, MUX D $0{,}2$, scrittura register file $0{,}6$.

• Senza pipeline: periodo $=0{,}6+0{,}2+0{,}8+0{,}2+0{,}6=2{,}4$ ns, cioè $417$ MHz.
• Pipeline a 3 stadi (setup dei FF supposto 0, ritardo dei registri di pipeline $0{,}2$ ns):
  • stadio 1 (OF): $0{,}6+0{,}2=0{,}8$ ns;
  • stadio 2 (EX): $0{,}2+0{,}8=1{,}0$ ns;
  • stadio 3 (WB): $0{,}2+0{,}2+0{,}6=1{,}0$ ns;
  • clock limitato dallo stadio più lento: $T=1{,}0$ ns, cioè 1 GHz.

Il miglioramento non è un fattore 3 (il numero di stadi) ma meno: $2{,}4/1{,}0=2{,}4$, per due motivi: i ritardi dei flip-flop dei registri di pipeline e il fatto che la frequenza è limitata dallo stadio più lento. Per $N$ istruzioni: senza pipeline $2{,}4N$ ns, con pipeline $(3+N-1)\cdot1{,}0$ ns; per $N=1000$ sono $2400$ ns contro $1002$ ns (speedup $\approx2{,}4$), per $N=1$ la pipeline è più lenta ($3$ ns contro $2{,}4$).

Schema di esecuzione

Con $k$ stadi, ogni istruzione occupa uno stadio per ciclo e la successiva parte un ciclo dopo. Per 4 stadi:

Formula (cicli per eseguire $N$ istruzioni). Nei primi $k-1$ cicli non tutti gli stadi sono attivi (la pipeline si riempie, filling), analogamente alla fine (si svuota, emptying). Per $N$ istruzioni servono $k+N-1$ cicli: con 7 istruzioni su 4 stadi, $10$ cicli. Un programma di una sola istruzione su una pipeline a 6 stadi richiede 6 cicli (la latenza). A regime si completa 1 istruzione per ciclo, con al più $k$ istruzioni in volo contemporaneamente (una per stadio): una pipeline a 4 stadi esegue "al massimo 4 istruzioni per ciclo" nel senso che 4 sono contemporaneamente in lavorazione, mai di più (e meno durante il riempimento).

Esempio. $k=4$ stadi e $N=7$ istruzioni: $k+N-1=4+7-1=10$ cicli.

Architettura RISC

Definizione (architettura RISC). Un RISC (Reduced Instruction Set Computer) è ottimizzato per istruzioni semplici: hardware più semplice e veloce; ai compilatori è lasciato il compito di realizzare operazioni complesse combinando istruzioni semplici. Caratteristiche:

• accesso alla memoria load/store;
• modi di indirizzamento semplici e limitati (quattro): registro, registro indiretto (solo per load/store), immediato, relativo (branch e jump);
• unica lunghezza di istruzione;
• istruzioni con operazioni elementari, eseguibili con un solo passaggio nella pipeline.

Esempio. Con 32 registri bastano $5$ bit per indicare un registro; con un opcode di $7$ bit si hanno $2^7=128$ operazioni.

Registri RISC: 32 registri, molti perché tutte le operazioni usano solo operandi nei registri: così si evitano troppi load/store (che richiedono più cicli). R0 è speciale: vale $0$ se usato come sorgente e scarta il risultato se usato come destinazione.

Formato (32 bit): opcode da 7 bit (128 operazioni), SA e SB registri sorgente, DR destinazione, per i salti target address = PC + offset (complemento a 2); tre tipi: tre registri, due registri + immediato, branch. Molte operazioni con operando immediato (con zero fill o sign extension del bit 14) per ridurre gli accessi alla memoria.

Datapath della CPU RISC con pipeline. Rispetto al computer a ciclo singolo: register file $32\times32$ con $R_0$; il register file non è più edge-triggered ma usa latch che permettono la scrittura nella prima metà del ciclo e la lettura nella seconda; unità funzionale con ALU a 32 bit e barrel shifter al posto dello shifter a un bit. Un barrel shifter a 32 bit realizza sia lo shift a destra sia a sinistra di $p$ posizioni con uno shift (rotazione) a destra, anteponendo zeri all'operando (a destra: $p$ posizioni; a sinistra: $64-p$ posizioni su un operando esteso a 64 bit).

Hazard

Definizione (hazard). Un hazard è un problema, nei dati o nel controllo, che impedisce di eseguire normalmente l'istruzione successiva nel ciclo successivo.

• Hazard di dato: l'istruzione successiva cerca di usare il risultato di un'istruzione precedente o un operando prima che sia disponibile.
• Hazard di controllo: il programma salta a una posizione diversa dalla successiva, ma la pipeline ha già caricato le istruzioni seguenti.

Esempio. Se l'istruzione 3 legge $R_4$ nel ciclo 4 ma l'istruzione 2 lo scrive solo nel ciclo 5, c'è un hazard di dato.

Hazard di dato: esempio

Pipeline a 4 stadi IF, DOF, EX, WB, istruzioni:

1. $R_5\leftarrow R_1+R_2$
2. $R_4\leftarrow R_3$
3. $R_6\leftarrow R_4+R_5$

L'istruzione 3 legge $R_4$ e $R_5$ nel suo DOF, al ciclo 4. $R_5$ è scritto dall'istruzione 1 nel ciclo 4, nella prima metà (la lettura avviene nella seconda): disponibile. $R_4$ invece è scritto dall'istruzione 2 solo nel suo WB, al ciclo 5: al ciclo 4 il valore letto è quello vecchio. C'è quindi un data hazard solo al ciclo 4 (due istruzioni distanti 1 sola posizione, dipendenza su $R_4$).

Proprietà (rimedi ai data hazard). Rimedi.

• NOP inseriti dal compilatore: istruzioni "nessuna operazione" tra le due per ritardare l'esecuzione della seconda.
• Stall hardware (pipeline stalled, bubble): l'hardware stesso inserisce NOP e blocca IF/DOF finché il dato non è pronto. Una logica confronta i registri sorgente e destinazione delle istruzioni in volo (segnale DHS, Data Hazard Stall): si sprecano cicli di clock.
• Forwarding (data forwarding): se il risultato che serve è già calcolato (all'uscita dello stadio EX) lo si manda avanti direttamente allo stadio che lo richiede, senza aspettare la scrittura: nessun ciclo sprecato.

Esempio. Nel caso di $R_4$ lo stall ritarda l'istruzione 3 di un ciclo (DOF al ciclo 5, quando $R_4$ è stato scritto); con il forwarding non si perde nessun ciclo.

Hazard di controllo e predizione dei salti

Proprietà (hazard di controllo e predizione dei salti). In un salto (branch) il PC cambia, ma nei due cicli successivi la pipeline ha già caricato istruzioni che non dovrebbero essere eseguite. Soluzioni: inserire NOP in attesa del salto (si perdono due cicli di clock) o prevedere il salto: si assume che il salto non sia preso e si prosegue; se invece è preso, si annullano le istruzioni caricate disabilitando $RW$ (nessuna scrittura nei registri), $BS$ (nessun salto) e $MW$ (nessuna scrittura in memoria): è come inserire una bolla (bubble) nella pipeline. In sintesi: il branch prediction evita (o riduce) le perdite dovute ai control hazard, non i data hazard, e non aumenta la frequenza del clock.

Esempio. Inserendo NOP si perdono $2$ cicli per ogni salto; con la predizione "salto non preso" non si perde nessun ciclo se il salto non è preso, altrimenti le $2$ istruzioni caricate diventano bolle.

Architettura CISC

Definizione (architettura CISC). Un CISC (Complex Instruction Set Computer) ha istruzioni complesse, molto difficili o impossibili da eseguire con un unico ciclo o un solo passaggio nella pipeline. Caratteristiche: più modi di indirizzamento, istruzioni di lunghezza variabile, istruzioni di salto più sofisticate.

Esempio. Il load con doppio accesso alla memoria $R[DR]\leftarrow M[M[R[SA]]]$ è tipico di un CISC: non entra in un solo passaggio della pipeline.

Organizzazione combinata CISC–RISC: un nucleo RISC per le istruzioni semplici e un controllo microprogrammato per quelle complesse, con registri temporanei. Il controllo microprogrammato è una macchina a stati la cui logica combinatoria è realizzata con una ROM (microprogramma): un'istruzione complessa è una sequenza di microistruzioni, quindi richiede più cicli di clock. Ad esempio un'unità di decodifica microprogrammata "permette di realizzare istruzioni che richiedono più cicli di clock", non istruzioni di qualsiasi complessità in un solo ciclo.

Modifiche rispetto al RISC: formato di branch con confronto tra due registri; codici condizionali ($>$, $\ge$, ...) usati dai branch, con un registro di stato (condition code register); partizionamento dei registri con registri temporanei; unità costante ampliata (segnale CS, costante CA dal microprogramma); segnali di stall sul PC e su IR; un MUX per scegliere tra istruzioni semplici e microprogrammate.

Errori comuni

• Dire che la pipeline riduce il tempo di una singola istruzione: riduce il tempo medio per istruzione, non la latenza.
• Calcolare lo speedup come il numero di stadi: bisogna considerare i ritardi dei FF e lo stadio più lento.
• Confondere hazard di dato (operando non pronto) e di controllo (salto).
• Dire che la branch prediction evita i data hazard.
• Dimenticare riempimento e svuotamento nel conteggio dei cicli ($k+N-1$).