# Personal computer/Linguaggio Macchina/DLX/DLX pipeline

Personal computer
* Storia dei calcolatoriPersonal computer/Storia
* Architettura del calcolatorePersonal computer/Architettura
** CPUPersonal computer/Architettura/CPU
** MemoriaPersonal computer/Architettura/Memoria
** Input/OutputPersonal computer/Architettura/IO
* Linguaggio MacchinaPersonal computer/Linguaggio Macchina
** DLXPersonal computer/Linguaggio Macchina/DLX
*** Operazioni DLXPersonal computer/Linguaggio Macchina/DLX/Operazioni
*** DLX sequenzialePersonal computer/Linguaggio Macchina/DLX/DLX_sequenziale
*** DLX in pipelinePersonal computer/Linguaggio Macchina/DLX/DLX_pipeline
** 8086-8088Personal computer/Linguaggio Macchina/8086
* Mapping di Memorie ed InterfaccePersonal computer/Mapping
** Integrati NotevoliPersonal computer/Mapping#Caratteristiche_e_funzionamento_degli_integrati_notevoli
*** DriverPersonal computer/Mapping/Driver
*** CPUPersonal computer/Mapping/CPU
*** Memoria PrincipalePersonal computer/Mapping/Memorie
*** Interfacce I/OPersonal computer/Mapping/Interfacce
** Gestione delle interfacce tramite programmaPersonal computer/Mapping#Gestione_delle_interfacce_tramite_programma
* Standard alla base di un personal computerPersonal computer/Standard
* Appendici e RiassuntoPersonal computer/Appendici
Modifica il sommario

## DLX pipeline

Nei 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:
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

Dato 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
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

I conflitti tra dati si verificano quando vi è una dipendenza tra le istruzioni inserite nella pipeline.
Il seguente spezzone di codice presenta una dipendenza:
Eseguendo le operazioni in pipeline
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
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
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
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
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
con a,b,c,d,e,f word in memoria, il codice è
questo codice presenta due situazioni di stallo per conflitto tra dati ( ADD e SUB dopo un LW ), riorganizzando il codice in questo modo
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

I 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
Una possibile soluzione, detta di Always Stall è quella di inserire degli stalli finché il PC non viene aggiornato
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à
$CPI=1+S=1+3*0,25=1,75$
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
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à
$CPI=1+S=1+3*0,25*0,65=1,48$
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

Consideriamo un semplice programma, che scritto in un linguaggio ad alto livello è
con A,B,C e Z delle variabili in memoria, il programma tradotto in linguaggio macchina DLX risulta
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
Considerando la più semplice pipeline, senza forwarding unit l'esecuzione del programma è
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
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
Riducendo a 15 il numero di clock necessari per eseguire il programma si ottiene
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
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