Personal computer/Linguaggio Macchina/DLX/DLX pipeline
DLX pipeline
modificaNei paragrafi precedenti abbiamo visto come le istruzioni DLX siano tutti divisibili in cinque blocchi funzionali:
- IF: prelievo dell'istruzione,
- ID: decodifica dell'istruzione,
- EX: esecuzione e calcolo dell'indirizzo,
- MEM: accesso alla memoria,
- WB: scrittura del risultato.
Assegnando le cinque operazioni a blocchi distinti, è possibile svolgere più istruzioni contemporneamente:
Clock 1 2 3 4 5 6 7 8 9 Istruzione i IF ID EX MEM WB Istruzione i+1 IF ID EX MEM WB Istruzione i+2 IF ID EX MEM WB Istruzione i+3 IF ID EX MEM WB Istruzione i+4 IF ID EX MEM WB
questo comporta, con pipeline piena, la scrittura del risultato di un'operazione ad ogni ciclo di clock, ovvero un CPI ideale di 1, nonostante il tempo per eseguire un'operazione ( latenza ) resti invariato .
Il CPI reale della pipeline dipende da più fattori, primo fra tutti l'effettiva durata del clock, se tra gli stadi di pipeline bisogna aggiungere degli elementi di memoria il tempo di un ciclo di clock aumenta di un fattore pari alla somma tra il setup time (tempo per memorizzare il valore) e il delay time (ritardo di propagazione). Ben più influente è la necessità di bilanciare la pipeline, se infatti lo stadio di MEM richiede più cicli di clock, è necessario che tutti gli stadi della pipeline abbiano la durata massima per consentirne l'esecuzione.
Sono quindi determinanti gli elementi di memoria, per questo motivo si utilizzano le memorie cache, ovvero memorie integrate nella CPU con tempi di accesso della durata di un clock.
Ovviamente la pipeline è possibile soltanto se la sovrapposizione delle istruzioni non sovraccarichi le risorse, è ad esempio impossibile richiedere alla ALU di eseguire un'operazione qualsiasi mentre un'altra istruzione vuole calcolare un indirizzo effettivo (incremento del program counter), vanno quindi apportate alcune modifiche al normale funzionamento della CPU sequenziale:
- Il PC deve essere incrementato durante la fase di IF con un incrementatore addizionale per lasciare libera la ALU allo stadio di EX
- Ad ogni ciclo di clock deve essere prelevata una nuova istruzione (stadio IF)
- Sono necessari due MDR (Registro di accesso alla memoria) per gestire il caso di una LOAD seguita da una STORE, i due registri verranno indicati con MDR e SMDR (Store MDR)
- In ogni ciclo di clock vanno eseguiti due accessi alla memoria, IF e MEM, per cui sono necessarie due cache separate per dati ed istruzioni
- Occorrono elementi di memoria per conservare i valori da usare negli stadi successivi della pipeline, ma che possono essere modificati dall'istruzione successiva, ovvero l'istruzione, il risultato ALU il prossimo valore del PC.
Nonostante questi accorgimenti, una pipeline così costruita funzionerebbe bene se le istruzioni fossero tutte tra di loro indipendenti, qualora non lo fossero si verificherebbero delle alee o conflitti (in inglese Hazard), che possono essere di tre tipi:
- Conflitti strutturali che derivano da problemi nell'uso delle risorse
- Conflitti tra dati che si verificano quando un'istruzione dipende dai risultati dell'istruzione precedente
- Conflitti di controllo che sono legati alle diramazioni e alle istruzioni che modificano il PC
Un'alea nella pipeline rende necessario l'arresto della stessa, ovvero uno 'stallo. Uno stallo richede che alcune istruzioni possano proseguire per consentire di risolvere il conflitto, mentre altre debbano essere sospese, questo ovviamente comporta un peggioramento delle prestazioni, ovvero il CPI di un'istruzione sarà il CPI ideale ( 1 ) più il numero di stalli necessari per risolvere il conflitto.
Conflitti strutturali
modificaDato che l'esecuzione delle istruzioni non è più lineare, ma sovrapposta, per rendere possibili le diverse combinazioni di istruzioni da eseguire contemporaneamente sono necessari dei collegamenti tra i diversi stadi della pipeline. Se mancano alcuni collegamenti, ovvero alcune combinazioni non sono possibili, si dice che la macchina presenta conflitti strutturali.
Per esempio una macchina potrebbe disporre di un'unica memoria per dati ed istruzioni, ciò comporta uno stallo ogni volta che viene eseguita un'istruzione con riferimento ai dati in memoria perché la macchina non può eseguire l'operazione di IF che comporta la lettura in memoria dell'istruzione da eseguire
Istruzione di caricamento IF ID EX MEM WB Istruzione i+1 IF ID EX MEM WB Istruzione i+2 IF ID EX MEM WB Istruzione i+3 stallo IF ID EX MEM WB
L'istruzione i+3 non può iniziare finché l'istruzione di caricamento non libera l'unica porta di memoria disponibile.
I conflitti strutturali comportano un CPI inferiore e sono sempre risolvibili aumentando la complessità, e quindi i costi, della macchina. La realizzazione di una pipeline completa (senza conflitti strutturali) comporta, inoltre, un aumento dei tempi di latenza delle operazioni che in alcuni casi si può trasformare in un peggioramento delle prestazioni
Conflitti tra dati
modificaI conflitti tra dati si verificano quando vi è una dipendenza tra le istruzioni inserite nella pipeline.
Il seguente spezzone di codice presenta una dipendenza:
ADD R1, R2, R3 SUB R4, R1, R5
Eseguendo le operazioni in pipeline
Cicli di clock 1 2 3 4 5 6 Istruzione ADD IF ID EX MEM WB Istruzione SUB IF ID EX MEM WB
Il risultato della prima istruzione è disponibile sul banco dei registri dopo lo stadio WB e quindi al clock 5, mentre la seconda operazione legge il valore in R1 nello stadio ID, al clock 3, in anticipo.
Tuttavia l'istruzione ADD calcola il valore di R1 già alla fine dello stadio di EX, una soluzione per questo tipo di conflitti è una unità di anticipazione o forwarding unit (FU). La FU consiste nel retroazionare il risultato dell'ALU agli elementi di memoria posti in ingresso all'ALU. Se la FU rileva che l'operazione ALU in corso richiede come ingresso l'uscita dell'operazione immediatamente precedente, la logica di controllo seleziona come ingresso il valore retroazionato invece del valore letto nel banco dei registri.
Occorre, inoltre, passare i risultati non solo all'istruzione che segue immediatamente, ma anche alle successive, ad esempio
ADD R1, R2, R3 IF ID EX MEM WB SUB R4, R1, R5 IF ID EX MEM WB AND R6, R1, R7 IF ID EX MEM WB OR R8, R1, R9 IF ID EX MEM WB XOR R10,R1, R11 IF ID EX MEM WB
In grassetto sono indicati tutti gli stadi per i quali è richiesta una forwarding unit, l'XOR non ne ha bisogno dato che al momento dell'ID il valore di R1 è già stato scritto dalla prima istruzione. Si può ridurre il numero di istruzioni da anticipare considerando che il banco dei registri può essere usato due volte in un solo ciclo di clock. Eseguendo le letture nella seconda metà di ID e le scritture nella prima metà di WB l'istruzione OR non necessita di FU.
Ridurre il livello di cortocircuitazione richiede un elemento di memoria e una rete logica che decide se l'istruzione condivide il registro sorgente o destinazione con una adiacente.
Per le operazioni ALU, usando le forwarding unit, si riescono ad eliminare tutti i conflitti tra dati.
Il concetto di anticipazione può essere anche esteso a unità funzionali diverse, ad esempio
ADD R1, R2, R3 SW 25(R1), R1
richiede che l'uscita dell'ALU sia anticipata di nuovo sull'ALU per poter essere calcolato l'indirizzo effettivo, ma anche sull'MDR per poter essere memorizzato senza stalli.
I possibili conflitti di dati tra un'istruzione i e la successiva j sono:
- RAW (Read After Write, lettura dopo scrittura) l'istruzione j tenta di leggere una sorgente prima ancora che i l'abbia scritta.
- WAR (Write After Read, scrittura dopo lettura) j tenta di scrivere una destinazione prima che sia stata letta da i. Questo tipo di conflitto non è possibile nel DLX dato che per qualsiasi operazione la lettura precede (in ID) la scrittura (in WB). Questo conflitto si verificherebbe con istruzioni che scrivono risultati nei primi stadi della pipeline.
- WAW (Write After Write, scrittura dopo scrittura) j tenta di scrivere un operando prima che sia stato scritto da i, il risultato scritto corrisponderebbe erroneamente a quello di i. Anche questo conflitto non è possibile nel DLX.
Il caso RAR non è un conflitto. Il primo esempio considerato in questo paragrafo è un conflitto RAW.
Non tutti i conflitti sui dati si possono risolvere senza conseguenze sulle prestazioni, ad esempio
LW R1, 20(R2) IF ID EX MEM WB ADD R3, R1, R4 IF ID EX MEM WB
Il valore della prima istruzione sarà disponibile soltanto dopo lo stadio di MEM, mentre l'istruzione ALU successiva ha bisogno di quel valore nello stadio EX, ovvero all'inizio dello stesso ciclo di clock. In questo caso non è possibile realizzare un'unità anticipatrice, ma il conflitto tra i dati può essere risolto soltanto con uno stallo
LW R1, 20(R2) IF ID EX MEM WB ADD R3, R1, R4 IF ID stallo EX MEM WB
In questo caso si è rappresentato lo stallo dopo la fase EX, in realtà, per quanto riguarda la pipeline del DLX, tutti i conflitti possono essere rilevati già durante la fase di ID, un'istruzione si dice avviata quando passa dallo stadio di decodifica (ID) a quello di esecuzione (EX); se esiste un conflitto tra dati l'istruzione viene sospesa prima di essere avviata.
Esiste anche una tecnica, detta di scheduling della pipeline, che permette di ridurre il numero di stalli riordinando il codice per eliminare i conflitti. Questo compito è affidato al compilatore.
Se ad esempio se si vogliono eseguire le operazioni
a = b + c d = e - f
con a,b,c,d,e,f word in memoria, il codice è
LW R1, b LW R2, c ADD R3, R1, R2 SW a, R3 LW R4, e LW R5, f SUB R6, R4, R5 SW d, R6
questo codice presenta due situazioni di stallo per conflitto tra dati ( ADD e SUB dopo un LW ), riorganizzando il codice in questo modo
LW R1, b LW R2, c LW R4, e ;scambio ADD con la LW successiva in modo da evitare lo stallo ADD R3, R1, R2 ;questa ADD non dipende dall'istruzione immediatamente precedente LW R5, f SW a, R3 ;ritardo la SW per risolvere il secondo conflitto tra dati SUB R6, R4, R5 SW d, R6
Il codice riscritto non presenta stalli.
La tecnica della schedulazione può essere impossibile da realizzare, in questo caso viene inserita una operazione nulla (NOP, No-OPeration) tra le due in conflitto. Questa modifica, per quanto riguarda il CPI, è del tutto equivalente ad uno stallo, ma permette di gestire soltanto tramite la schedulazione i conflitti tra dati, semplificando la realizzazione della CPU
Conflitti di controllo
modificaI conflitti di controllo influiscono pesantemente sulle prestazioni della CPU in pipeline, infatti, osservando il datapath per le istruzioni di salto si nota che il valore del program counter modificato è disponibile soltanto alla fine dello stadio MEM (quarto stadio). Fintanto che il PC non viene modificato le istruzioni inserite nella pipeline sono quelle immediatamente successive all'istruzione di salto.
Conflitto di controllo
Salto all'istruzione 8 IF ID EX MEM WB
Istruzione 2 IF ID EX MEM WB
Istruzione 3 IF ID EX MEM WB
Istruzione 4 IF ID EX MEM WB
;a questo punto il PC è stato incrementato e viene fatto il Fetch dell'istruzione 8
;tuttavia vengono eseguite anche le istruzioni 2-3-4
...
Istruzione 8 IF ID EX MEM WB
Una possibile soluzione, detta di Always Stall è quella di inserire degli stalli finché il PC non viene aggiornato
Salto all'istruzione 8 IF ID EX MEM WB
Istruzione 2 stallo stallo stallo
Istruzione 3 stallo stallo
Istruzione 4 stallo
;a questo punto il PC è stato incrementato e viene fatto il Fetch dell'istruzione corretta
...
Istruzione 8 IF ID EX MEM WB
Similmente al caso delle LOAD, alcune CPU RISC affidano completamente la soluzione delle alee di controllo al software che inserirà tre NOP dopo ogni operazione di BRANCH
Nonostante sia la soluzione più semplice comporta un notevole peggioramento delle prestazioni rispetto al caso ideale, se ad esempio il programma contiene il 25% di istruzioni di tipo Branch, il CPI in pipeline sarà
Una soluzione più performante è quella di Predict Not Taken, la CPU prevede che il branch sia not taken e che quindi il flusso del programma sia quello normale del PC, qualora poi il branch si dimostrasse taken nello stadio di MEM verrebbe inviato un segnale di Flush alla pipeline, ovvero verrebbe svuotata la pipeline senza portare a termine le istruzioni ancora presenti in essa, trasformandole quindi in delle NOP
Salto all'istruzione 8 IF ID EX MEM WB
Istruzione 2 IF ID EX flush
Istruzione 3 IF ID flush
Istruzione 4 IF flush
;le istruzioni 2-3-4 diventano delle NOP
;il PC è stato incrementato e viene fatto riprendere il programma dall'istruzione 8
...
Istruzione 8 IF ID EX MEM WB
Questa soluzione permette di stallare la CPU soltanto in caso di branch taken. Se il programma contiene il 25% di istruzioni di tipo Branch, di cui il 65% Taken il CPI in pipeline sarà
Esistono anche tecniche più sofisticate che permettono ulteriormente di ridurre il CPI e si basano su predizioni dinamiche dei Branch
Prestazioni del DLX in pipeline
modificaConsideriamo un semplice programma, che scritto in un linguaggio ad alto livello è
Z = A + B - C
con A,B,C e Z delle variabili in memoria, il programma tradotto in linguaggio macchina DLX risulta
LW R1, A(R0) LW R2, B(R0) LW R3, C(R0) ADD R1, R2, R1 SUB R1, R1, R3 SW Z(R0), R1
Ipotizzando che ogni accesso in memoria sia completato in un ciclo di clock l'esecuzione di questo programma non i pipeline richiede 34 clock (4 operazioni di caricamento ognuna da 6 clock e due operazioni ALU da 5 clock) per un
CPI medio non in pipeline 5,67
Considerando la più semplice pipeline, senza forwarding unit l'esecuzione del programma è
clk 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 LW A IF ID EX MEM WB LW B IF ID EX MEM WB LW C IF ID EX MEM WB ADD IF S S ID EX MEM WB SUB IF S S S ID EX MEM WB SW Z IF S S S ID EX MEM WB
La prima istruzione di ADD ha bisogno, nella fase di decodifica, del valore di R2 che, in assenza di forwarding unit è disponibile soltanto alla fine dello stadio di WB della seconda istruzione (clock 6). L'istruzione di SUB richiede poi il valore calcolato nella precedente istruzione che sarà disponibile a partire da clock 11. La penultima istruzione terminerà il calcolo A + B - C nel clock 14 e quindi l'istruzione di SW può effettuare la decodifica soltanto nel clock 15. L'intero programma richiede 18 cicli di clock per un
CPI medio senza forwarding unit 3
Sempre in assenza di forwarding unit e ipotizzando che il Register File ritorni immediatamente il proprio contenuto in caso di lettura/scrittura dallo stesso registro, ovvero che il valore di un registro sia disponibile direttamente nella fase MEM (quando ormai tale valore necessita soltanto di essere scritto in WB), è possibile eliminare tre stalli
clk 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 LW A IF ID EX MEM WB LW B IF ID EX MEM WB LW C IF ID EX MEM WB ADD IF S ID EX MEM WB SUB IF S S ID EX MEM WB SW Z IF S S ID EX MEM WB
Riducendo a 15 il numero di clock necessari per eseguire il programma si ottiene
CPI medio senza FU con ritorno immediato di RF 2,5
Aggiungendo anche un forwarding unit sullo stato EX che permette quindi la propagazione all'indietro su EX del risultato di una MEM od una EX precedente, si ottiene
clk 1 2 3 4 5 6 7 8 9 10 LW A IF ID EX MEM WB LW B IF ID EX MEM WB LW C IF ID EX MEM WB ADD IF ID EX MEM WB SUB IF ID EX MEM WB SW Z IF ID EX MEM WB
In rosso il forwarding di R2 da MEM all' EX dell'operazione ADD. In blu il forwarding di R3 da MEM all' EX dell'operazione SUB. In grassetto il forwarding di R1 tra gli stati di EX delle istruzioni ADD, SUB e SW.
Il programma con forwarding unit viene eseguito in 10 clock senza stalli
CPI medio con forwarding unit 1,67