Contenuto della lezione - STLAB · G. Bucci - Calcolatori Elettronici. 13/09/2013 48. Come si...

13/09/2013G. Bucci - Calcolatori Elettronici 1

La Pipeline

• Contenuto della lezione– Studio del funzionamento di una CPU in pipeline– Prestazioni– Conflitti– Soluzione dei conflitti– Tecniche per la predizione delle diramazioni


Schema della Pipeline


Pipeline • Modello di riferimento: pipeline a 5 stadi

IF: Prelievo istruzioneID: Decodifica istruzione e fetch registriEX: Esecuzione codice operazioneME: Accesso alla memoriaWB: Scrittura registro destinazione

Esempi commerciali


Esecuzione istruzioni


Esempio esecuzione (ADD)

• Facciamo riferimento alle istruzioni aritmetiche (per esempio ADD R1,R6,R9)

• (Solo gli elementi essenziali)


… Esempio esecuzione (ADD)

Primo periodo di clock: IF• Il registro IF/ID contiene l'istruzione precedente. Lo

stadio IF legge l'istruzione dalla memoria. • Al termine della fase IF (fronte finale del clock) la

codifica dell'istruzione viene copiata su IF/ID.



Secondo periodo di clock: ID• Lo stadio ID decodifica il contenuto del registro IF/ID.

Al termine della fase ID il risultato della decodifica viene copiato in ID/EX. Nel dettaglio:– La rappresentazione del codice di operazione

della ALU (OPALU = fALU = ADD).– l'identità (TAG) del registro di destinazione in cui dovrà

scrivere lo stadio WB. Il campo viene denominato RW– un bit (R_Write = 1) che indica che l'istruzione prevede la

scrittura di un registro di destinazione. – copia del contenuto dei due registri sorgente (selezionati

attraverso in campi Rs1 e Rs2). I campi relativi sono A e B.

(RW e R_Write dovranno essere propagati fino a ME/WB)



Terzo periodo di clock: EX• Su EX/ME viene trasferito:

– il risultato dell'addizione calcolato dalla ALU– il contenuto del campo RW di ID/EX – il contenuto del campo (bit) R_Write di ID/EX



Quarto periodo: ME• Niente da fare, eccetto il

trasferimento da EX/ME a ME/WB di: RW, R_Write e D

Quinto periodo: WB• Lo stadio WB (essendo Rwrite

asserito) scrive nel regostro di destinazione selezionato da RW il contenuto del campo D


PrestazioniTempo richiesto dal generico stadio

Tempo di latch

Periodo di clock in multiciclo

Periodo di clock in pipeline

Periodo di clock in monociclo


Esempio

Tempo di latch:

Pipeline a 4 stadi con i seguenti tempi:

=


Profili di esecuzione


….Esempio

• I tempi di permanenza di un’istruzione e numero di istruzioni per unità di tempo sono:

– 300 1/300

– 360 1/360

– 400 4/400 = 1/100

con un guadagno di 3 e 3,6 rispettivamente


Indici delle prestazioni

Tasso di esecuzione : Num istruz. Per unità di tempo



Tasso di esecuzione : Num istruz. per unità di tempo

Per completare n istruzioni partendo dalla pipe vuota occorrono[k+(n-1)] cicli ci clock

Tasso di esecuzione medio

Si osservi che per



• Efficienza (utilizzazione): percentuale di tempo in cui la CPU è occupata, ovvero rapporto tra tasso medio e tasso ideale

• Tende a 1 per n che tende a infinito



• Accelerazione: Rapporto tra la velocità di un processore con pipeline rispetto ad un processore multiciclo (ovvero tra i loro tassi di esecuzione)


Pipeline lineari/parallele

• Eliminazione di un collo di bottiglia

Originale

Parallela

Lineare


Esecuzione

• In fase ID vengono asseriti i tre campi EX, ME, WB di ID/EX con i comandi relativi ai corrispondenti stadi


Propagazione (segnali di controllo)• Ingresso a UC:

UC.OPCODE = IF/ID.OPUC.f = IF/ID.fALU

• Verso ID/EXID/EX.WB <- UC.WBID/EX.ME <- UC.MEID/EX.EX <- UC.EXID/EX.RW <- IF/ID.Rd oppure IF/ID.Rsd

• Verso EX/MEEX/ME.WB <- ID/EX.WBEX/ME.ME <- ID/EX.MEEX/ME.RW <- ID/EX.RW

• Verso ME/WBME/WB.WB <- EX/ME.WBME/WB.RW <- EX/ME.RW

C’è da fare la “lista della spesa”, cioè vedere quanto valgono i campi e se ne servono altri.


Istr. aritmetiche


...Istr. aritmetiche

• Fase IFPC <- PC+4IF/ID.IR <- MI[PC]

• Fase ID

ID/EX.EX.OPALU <- UC.OPALUID/EX.WB.RWrite <- 1 ID/EX.EX.ALUMux <- UC.ALUMux ;(ALU.B = RF.B)ID/EX.WB.MemToReg <- 0ID/EX.RW <- IF/ID.Rd

ID/EX.A <- RF.AID/EX.B <- RF.B

Dati

Selettori

Valide per tutte le istruzioni.(nel seguito non sono indicate)

L’effettivo aggiornamento può essere diverso (salti)

Comandi


...Istr. aritmetiche• Fase EX

EX/ME.WB <- ID/EX.WBEX/ME.RW <- ID/EX.RWEX/ME.ALUOut <- ALU.ALUOut

• Fase MEME/WB.WB <- EX/ME.WBME/WB.RW <- EX/ME.RWME/WB.ALUOut <- EX/ME.ALUOut

• Fase WB– ME/WB.Rwrite (vale 1) determina la scrittura nel registro

selezionato da ME/WB.RW– MemToReg (vale 0) seleziona ME/WB.ALUOut come

sorgente del dato da scrivere nel registro selezionato


Istr. Load


Istr. Store


..LD/ST Fase ID

• Comuni a LD e STID/EX.A <- RF.AID/EX.IMM <- IF/ID.OFFSET

• Specifiche LDID/EX.ME.M_Read <- 1ID/EX.WB.R_RWrite <- 1

ID/EX.WB.MemToReg <- 1

ID/EX.RW <- IF/ID.Rsd

• Specifiche STID/EX.WB.M_MWrite <- 1ID/EX.B <- RF.B


Istr. Salto condizionato


..Salto condizionato

• IFIF/ID.PC <- PC+4 ; serve dopo

• IDID/EX.A <- RF.A

ID/EX.B <- RF.B

ID/EX.IMM <- IF/ID.PC+IF/ID.OFFSET

• EXZero (JE) e Segno (JZ) determinano l’ingresso a PC tramite PCMux


.. Istruzioni JMP/ JR

• IF

• IDID/EX.IMM <- IF/ID.IND ;Per il JMP

ID/EX.IMM <- RF.B ;Per JR

• EXPCMux a selezionare ID/EX.IMM

– Nota: si potrebbe fare a meno di passare IND / B per ID/EX.IMM trasferendolo direttamente a PC, in modo da concludere l’istruzione in ID e risparmiare un clock


...JAL

• Fase IF• Fase ID

ID/EX.IMM <- IF/ID.INDID/EX.WB.RWrite <- 1 ID/EX.WB.MemToReg <- 0ID/EX.RW <- 31ID/EX.PC <- IF/ID.PC ;per salvarlo

•

Fase EXPCMux a selezionare ID/EX.IMM

•

Fasi ME , WB Solo propagazione dei segnali (che in WB determinano la scrittura in R31)


Sintesi Campi Fine della lista della spesa


Sintesi comandi….

• Campo WB– R_Write ; scrittura del registro di destinazione– MemToReg ; seleziona ALUOut o MEMDAT

• Campo ME – M_ Read ; lettura in memoria;– M_Write ; scrittura in memoria;


…. (segue) Sintesi comandi

• Campo EX – OPALU seleziona l'operazione ALU;– ALUMux seleziona l'ingresso B alla ALU;– JE istruzione JE;– JS istruzione JS;– JMP istruzione JMP;– JAL istruzione JAL;– JR istruzione JR.


.. Inoltre

• IMMux ;per selezionare l’ingresso a ID/EX.IMM tra» IF/ID.OFFSET (LD/ST) » IF/ID.IND (JMP, JAL)» IF/ID.PC+IF/ID.OFFSET (JE, JS)» RF.B (JR)

• RWMux ; per selezionare l’ingresso a ID/EX.RW tra» Rd (ARITM)» Rsd (LD)» 31 (JAL)

• PCMux ; per selezionare l’ingresso a PC; Unico a non nascere da UC

2 bit


UC


Unità di controllo – Esempio: Stadio IF

Determinato dai codici di salto e dalle condizioni

Superfluo


PCMux

• Asserito su– JMP– JAL– JR– JE and Zero– JS and Segno


Come sarebbe?

Se il set di istruzioni prevedesse anche • l’accesso al byte tramite le istruzioni LDB/STB e

l’accesso alle semiparole tramite le istruzioni LDH/STH ??

• Ci vorrebbero due ulteriori segnali di controllo– ENW , ENH ; Veder i due lucidi seguenti


LD

(NB: Little endian)

Lo schema è per il caso generale:

LDW

LDB

LDH


ST

(NB: Little endian)

Lo schema è per il caso generale:

STW

STB

STH


Conflitti

• Conflitti strutturali: insorgono per l'uso della stessa risorsa.

• Conflitti dati: insorgono quando un'istruzione dipende dai risultati di una precedente.

• Conflitti di controllo: derivano dalla presenza di diramazioni e da altre istruzioni che modificano il contatore di programma.


Conflitti strutturali

• Una sola porta di memoria (memoria unica)


Soluzione


CONFLITTI DATI

Date due istruzioni i e j , con i precede j • RAW (Read After Write): j tenta di leggere un dato

scritto da i prima che i abbia effettivamente scritto.• WAR (Write After Read ): j tenta di scrivere in una

destinazione letta i da prima che sia effettivamente letta da i. – impossibile nel nostro modello di pipeline: tutte le letture

precedono (in ID) tutte le scritture (in WB).

• WAW ( Write After Write ): j tenta di scrivere un operando prima che questo sia stato scritto da i. – Si tratta di un conflitto che può verificarsi in pipeline che

consentono alle istruzioni di avanzare anche quando un'istruzione precedente sospesa. Neanche questo conflitto è possibile nel nostro modello pipeline


Riconoscimento conflitti dati

ADD R1,R6,R9 LD R1,100(R3) ADD R1,R6,R9SUB R4,R1,R7 MUL R4,R1,R7 ST 200(R3),R1

Conflitto su R1

• I registri vengono letti in ID e aggiornati in WB (la ST non aggiorna i registri)

• Se accade che l'istruzione in EX, o quella in ME, o quella in WB prevede la scrittura su uno dei registri sorgente dell'istruzione in ID si ha un conflitto RAW (l’istruzione in ID legge prima che il dato sia scritto)


Condizioni

• Wa• Wb

S1= ARITM + LD + ST + JE + JS S2= ARITM + ST + JE + JS + JR

• Xa• Xb

• Ma• Mb


Riconoscimento


Come si comanda lo stallo

• Si usa la linea Confl per stallare la pipeline in ID– In modo simile a quello dello stallo per IF– Quando Confl è asserito PC non viene fatto avanzare

• Ovvero viene silenziato il clock a PC• In ID/EX viene inserito il codice NOP determinando una bolla

– Esempio: ADD r1,r10,r11 ;Ipotesi: SUB r2,r1,r16 ; in ID al clock i

• Clock i: Xa => SUB stallata in ID; ID/EX.OP <- NOP• Clock i+1: Ma => SUB stallata in ID; ID/EX.OP <- NOP• Clock i+2: Wa => SUB stallata in ID; ID/EX.OP <- NOP• Clock i+3: -- => SUB decodificata; ID/EX.OP <- SUB


Stallo


Stallo e altro

• Lo stallo è la peggiore di tutte le soluzioni !

• Ci sono tecniche per evitare di pagare la penalizzazione dello stallo.– Anticipazione (Forwarding o by-passing)– Sovrapposizione (Clock halving)– Riordinamento (scheduling)

• Le prime evitano lo stallo in modo “trasparente” (in hardware) al programmatore

• La terza è una tecnica al tempo di compilazione (riordinamento statico) con la quale si aggiusta l’ordine delle istruzioni nel testo del programma


Sovrapposizione (clock halving)

• Si guadagna un clock se ID legge nella seconda parte del clock e WB scrive nella prima


Semplifichiamo

• Se c’è la sovrapposizione le due condizioni Wa e WB non sussistono. Dunque la condizione di conflitto è data da

• Nel seguito assumeremo che ci sia la sovrapposizione

Confl = Xa+Xb+Ma+Mb


Anticipazione

• Prelevare il dato lungo la pipeline, quando non è ancora stato scritto nel reg di destinazione, bypassando la parte di pipeline che segue il punto di prelievo

Criteri• Riconoscere il conflitto quando l’istruzione è in ID• In caso di conflitto multiplo selezionare il dato più

recente


Conflitto ID-EX

1. L’istruzione in ID usa il dato in EXa) L’istruzione in EX produce il dato in EX: forward di

EX/ME.ALUout verso ALU al clock seguenteb) L’istruzione in EX produce il dato in ME (è un LD): stallo

inevitabile. Al clock seguente si effettua il forward del dato da ME/WB alla ALU

2. L’istruzione in ID usa il dato in ME – Può essere solo la ST. Lo stallo è comunque evitato con il

forward da ME/WB a ME al clock successivo.


..Conflitto ID - EX

a) L’istruzione in ID usa il dato in EX, l’istruzione in EX produce il dato in EX: (non può essere ST)

add r2,r5,r6sub r1,r2,r3


..Conflitto ID - EX

• L’istruzione in ID usa il dato in EX, l’struzione in EX produce il dato in EX:

add r2,r5,r6sub r1,r2,r3

Forward da ME a EX al clock successivo


..Conflitto ID - EXb) L’istruzione in ID usa il dato in EX, l’istruzione in EX

produce il dato in ME (non può che essere LD)

Forward da WB a EX 2 clock dopo (con uno stallo di ID e IF sul primo clock)

bolla ld r2,x(r7)sub r1,r2,r3


..Conflitto ID - EX

2. L’istruzione ID usa il dato in ME (solo ST)

Forward da WB a ME, dopo 2 clock

ST y(r2),r1 ***


Conflitto ID-ME

• Con il nostro repertorio in ME può esserci solo il LD1. L’istruzione in ID usa il dato in EX: forward da WB

a EX al clock successivo2. L’istruzione in ID usa il dato in ME (può essere

solo ST): forward da WB a ME al clock successivo

•


Conflitto ID – ME (in ME c’è LD !)

1. L’istruzione in ID usa il dato in EX

Forward da WB a EX

ADD r7,r1,r1 LD r1, z(r2)


Conflitto ID – ME (in ME c’è LD !)

2. L’istruzione in ID usa il dato in ME (è la ST)

Forward da WB a ME (via EX)

ST x(r7),r1 LD r1, z(r2)


Ci vogliono altri campi (per propagare i selettori aggiuntivi)

FwBMux: – Il valore è determinato dalla condizione di conflitto– Asserito da UC (stadio ID): dunque occorre estendere il

campo ID/EX.EX, in modo che ID/EX.EX.FwBMux <- UC.FwBMux

Analogamente per FwAMux e per il Mux alla Memoria


Sintesi


Riordinamento (statico/tempo di compilazione)

Sequenza data (Fortran, C,..) a= b+c;d= e+f;

Possibile traduzione “uno a uno” Ipotesi: la macchina ha la sovrapposizione e il bypass

LD R1,B(R0) LD R2,C(R0)ADD R3,R1,R2ST A(R0),R3

LD R1,E(R0) LD R2,F(R0)ADD R3,R1,R2ST D(R0),R3


Riordinamento (statico/tempo di compilazione)

Sequenza data (Fortran, C,..) a= b+c;d= e+f;

Possibile traduzione “uno a uno” Ipotesi: la macchina ha la sovrapposizione e il bypass

I bypass evitano tutti gli stalli eccetto quelli dovuto al LOAD Ci sarebbero 2 stalli




Riordinamento (statico)

Come fare

LD R1,B(R0) LD R2,C(R0)LD R4,E(R0)ADD R3,R1,R2LD R2,F(R0)ST A(R0),R3ADD R3,R4,R2ST D(R0),R3

2. Portare questo ST prima del II ADD

1. Usare R4 invece di R1 e portare l’istruzione prima del I ADD



I due stalli sono evitati


…Riordinamento (statico)Ipotesi: la macchina ha la sovrapposizione ma NON il bypass

Che

succede

con la soluzione

precedente?

Totale

8 stalli.

Richiede

2 stalli

(per R3)

Richiede

2 stalli

(per R2)

Richiede

2 stalli

(per R3)

Richiede

2 stalli

(per R2)




..la soluzione precedente

Si guadagnano 3 clock

Richiede

1 stallo

(per R2)

Richiede

2 stalli

(per R3)

Richiede

1 stallo

(per R3)

Richiede

1 stallo

(per R2)



..la soluzione precedente


BELLO, ma attenzione alla compatibilità !!!!

Problema generale: In quali casi si può ricorrere al riordino?

Si guadagnano 3 clock


Conflitti per salti incondizionatiIpotesi: nel caso di salto incondizionato

PC viene aggiornato in EX

• Le statistiche indicano che i salti incondizionati compaiono nel mix di istruzioni in percentuali dal 2% all’8%

• Meglio evitare di pagare la penalizzazione.• Ciò può essere fatto attraverso il compilatore


Salto ritardato

• Ovviamente la macchina deve operare in modo congruente (nel caso specifico non deve introdurre stalli in presenza di salto).

LD R1,100(R3)ADD R2,R2,R3SUB R4,R5,R6JMP DaQualcheParte::I1::I2

LD R1,100(R3)JMP DaQualcheParteADD R2,R2,R3SUB R4,R5,R6::I1::I2

• Soluzione statica: Il compilatore può riordinare le istruzioni in modo da riempire le bolle, evitando lo stallo


Diramazioni (Salti condizionati)

• Bisogna attendere il risultato del test per sapere se la diramazione è o no effettiva, nel qual caso occorre introdurre una bolla.

• Funzionamento (hardware)– all'apparire di un'istruzione di diramazione la pipeline continua a

prelevare le istruzioni successive– se la verifica della condizione indica diramazione effettiva, la

pipeline viene svuotata delle istruzioni che seguono e viene alimentata a partire dall'indirizzo di destinazione, introducendo un bolla lunga quanto il numero di cicli persi

– se la verifica della condizione di diramazione indica che la diramazione non è effettiva, tutto procede come se si trattasse di una normale istruzione senza effetto sul PC (senza alcuna penalizzazione)


Soluzione compilativa: Riordinamento

Dest ADD R2,R1,R3JE R1,R3,DestSUB R4,R2,R1XX

• Lo slot dietro JE è stato riempito con la SUB: l’effetto dell’esecuzione è identico e il fetch di XX viene fatto solo a fine ciclo.

• Il riordino si è potuto fare perché il test non dipendeva dall’istruzione precedente: se fosse stato SUB R1,R2,R1 il SUB avrebbe dovuto precedere JE comunque.

Ipotesi per i casi seguenti (trasp 74-78): penalizzazione di uno solo clock

Dest ADD R2,R1,R3SUB R4,R2,R1JE R1,R3,DestXX


...Soluzione compilativa (con dipendenza)

ADD R7,R1,R3Dest ..altre istruzioni

SUB R4,R2,R1JE R4,R8,DestADD R7,R1,R3MUL R5,R2,R1

Dest ADD R7,R1,R3..altre istruzioniSUB R4,R2,R1JE R4,R8,DestMUL R5,R2,R1

Si può portare la ADD dietro a JE.Il codice deve essere ristrutturato come sotto





• Il riordino non deve aver effetto pratico sulla logica del programma





Se a Dest

si arriva per altra via con un salto occorre mettere anche sul relativo percorso l’istruzione ADD R7,R1,R3

R7 viene comunque modificato (anche se la diramazione non ha luogo) contro la logica del programma. Si può accettare se nel seguito non c’è

uso di R7 come sorgente

• Il riordino non deve aver effetto pratico sulla logica del programma


… Soluzione compilativa



Dest ADD R7,R1,R3..altre istruzioniSUB R4,R2,R1JE R4,R8,DestMUL R5,R7,R1

• Questa trasformazione introduce un errore (la volta che la diramazione non viene presa) perché R7 viene usato da MUL.

il compilatore deve garantire che se la diramazione non ha luogo, l'aver eseguito l'istruzione successiva alla diramazione non ha effetto sulla logica del programma


Dati sperimentali

(da Hennessy & Patterson, “Computer architecture, a quantitative approach”)

ProbabilitàP(SS) = 97% Che un successo segua un successo

P(NS) = 61% Che un successo segua un fallimento

P(SN) = 54% Che un fallimento segua un successo

P(NN) = 11% Che un fallimento segua un fallimento

• Come sarebbe trattare le diramazioni in hardware, predicendo come si comporteranno e agendo di conseguenza ?


Predizione dinamica (hardware)

• A carico della logica di CPU:1. Predire prima possibile (parte iniziale della pipe) ed agire

conseguentemente (modificare PC)2. Verificare (in EX) se la predizione è stata corretta ed

eventualmente aggiustare quel che è stato fatto

• Si basa sul valore del funzionale F(x_1, x_2, ...)– F: probabilità che una diramazione sia effettiva– x_1, x_2, ... parametri che influenzano F. – Se F > 0.5: predizione di successo; F < 0.5: predizione di fallimento.

• I parametri rappresentano la storia della diramazione• Dalla storia degli esiti di una specifica diramazione si hanno utili

indicazioni circa la probabilità che la la sua prossima esecuzione produca o no una effettiva diramazione.


Forma semplificata

• Si tiene conto dell'esito dell'ultima diramazione incontrata e si predice lo stesso comportamento per la successiva.

• X parametro (un bit per tutto il sistema) che tiene conto dell’esito dell’ultima diramazione eseguita

• F(X) = X• Tecnica di predizione molto rozza:

– Tutte le diramazioni trattate allo stesso modo, indipendentemente dalla probabilità che hanno le singole diramazioni di essere eseguite.

– Meglio tenere una statistica delle singole diramazioni (una storia individuale)


Predittore a 2 bit (statistica)

• Contatore a saturazione tenuto per ogni diramazione di cui si tiene traccia

Esistono anche predittori più complessi


Tabella di predizione (BPB)

Cache associativa

Il campo di sinistra ha funzione di TAG

Per come è gestita possono esserci solo gli indirizzi di diramazioni


Cosa teniamo in BPB

• Stabiliamo che le diramazioni che si presentano la prima volta vengono trattate come se per esse valesse una predizione di fallimento– Ovvero non si fa alcuna predizione– Quando l’istruzione giunge in EX si verifica se la

diramazione viene presa o meno• Se la diramazione ha luogo il relativo indirizzo viene inserito in

BPB con statistica = 10 (in modo che nel futuro dia predizione di successo)

• Se la diramazione non ha luogo non viene messa in BPB, se si ripresenta è come se fosse nuova

• In EX occorre avere l’indirizzo della diramazione per metterla BPB. Inoltre occorre avere l’esito della previsione (se questa c’è stata)


Come si attua (1: previsione)

Quando una generica istruzione è in IFA. Se il suo indirizzo è contenuto in BPB:

– si tratta di una diramazione già eseguita– la predizione (Successo/Fallimento – S/F) viene copiata in IF/ID

B. Se il suo indirizzo non è in BPB– non si sa se è o meno una diramazione– in IF/ID viene scritta la predizione di fallimento (F) (Equivale a dire

che per le diramazioni che si presentano per la prima volta o che comunque non sono in BPB si prevede fallimento, vedi trasp precedente)

• Assieme alla previsione occorre anche scrivere in IF/ID se questa è stata effettivamente effettuata (A) o no (B) (ovvero se l’istruzione è presente o no in BPB)


Come si attua (2: modifica PC)

Al clock successivo l’istruzione è in ID• Se l’istruzione non è una diramazione:

– L’istruzione viene trattata normalmente• Se l’istruzione è una diramazione:

– Se la previsione è S:• L’indirizzo di destinazione (calcolato in ID) viene trasmesso a

PC (PC viene quindi modificato da ID e non da EX, salvando un clock)

• Viene eliminata l’istruzione in IF (nasce una bolla)

• Se la previsione è F :• L’istruzione viene trattata normalmente (non viene modificato PC)

• (ovviamente la Previsione e l’indicatore di Presenza vengono propagati verso EX)


Come si attua (3: verifica)

Al clock successivo l’istruzione è in EX• Viene valutata la condizione • Se si tratta di una diramazione viene fatto il confronto con la previsione; si

hanno questi casi:a) Previsione = S & Condizione = V (indovinato !)

Aggiornamento del contatore a saturazioneb) Previsione = S & Condizione = F

Inserimento bolla in IF (in ID c’è la bolla precedente)

Modifica di PC con l’indirizzo dell’istruzione successiva nel testo del programma

Aggiornamento del contatore a saturazionec) Previsione = F & Presenza = V & Condizione = V

Inserimento bolla in IF e ID

Modifica di PC con l’indirizzo di destinazione

Aggiornamento del contatore a saturazioned) Previsione = F & Presenza = V & Condizione = F (indovinato !)

Aggiornamento del contatore a saturazionee) Previsione = F & Presenza = F & Condizione = V



Inserimento in BPB (tag e contatore) f) Previsione = F & Presenza = F & Condizione = F (assunzione giusta)

Niente

(Z AND JE) OR (S AND JS)

ID/EX.Presenza

ID/EX.Previsione


Come si attua (3: verifica)

Al clock successivo l’istruzione è in EX• Viene valutata la condizione • Se si tratta di una diramazione viene fatto il confronto con la previsione; si

hanno questi casi:a) Previsione = S & Condizione = V (indovinato !)

Aggiornamento del contatore a saturazioneb) Previsione = S & Condizione = F

Inserimento bolla in IF (in ID c’è la bolla precedente)

Modifica di PC con l’indirizzo dell’istruzione successiva nel testo del programma

Aggiornamento del contatore a saturazionec) Previsione = F & Presenza = V & Condizione = V



Aggiornamento del contatore a saturazioned) Previsione = F & Presenza = V & Condizione = F (indovinato !)

Aggiornamento del contatore a saturazionee) Previsione = F & Presenza = F & Condizione = V



Inserimento in BPB (tag e contatore) f) Previsione = F & Presenza = F & Condizione = F (assunzione giusta)

Niente


Prestazioni BPB

Riassunto delle considerazioni precedenti


Branch Target Buffer (BTB)

• Migliora le prestazioni anticipando l’eventuale cambiamento di PC alla fase IF.

• Formato del buffer


Come si attua

• Per le istruzioni che non sono in BTB tutto avviene come prima

• Per le istruzioni in BTB si è in grado di prelevare l’indirizzo di destinazione e di trasmetterlo subito a PC se la predizione è di successo– In tal modo in fase ID non si introduce la bolla in IF,

risparmiando il relativo ciclo di penalizzazione. – Per il resto tutto procede come nel caso del BPB


Predizione con BTB


Predizione con BTB (come si legge)

Vuol dire che mentre la diramazione è in ID lo stadio IF sta già leggendo

dall’indirizzo di diramazione


Prestazioni BTB

• Ma ne valeva la pena per salvare un solo ciclo ??– Se si considera che la nostra pipe è molto corta e che nel caso

reale tra IF, ID e EX possono esserci altri stadi intermedi– E’ tanto più conveniente quanto più la pipeline è lunga


Nota su BPB e BTB

• In EX occorre avere: – L’indirizzo della diramazione (PC) per accedere alla cache – L’indirizzo dell’istruzione che segue la diramazione (PC+4)

nel caso ci sia bisogno di tornare indietro

• Si può prevedere– Di avere due campi distinti per PC e PC+4 in pipeline– uno dei due tra PC e PC+4 e prevedere uno specifico

sommatore/sottrattore per trovare l’altro– Nel caso della nostra pipeline sui latch è già stato previsto

PC+4 (quindi ci vuole un sottrattore per accedere alla cache)


Cache BPM/BTP

• Ovviamente non è di dimensioni illimitate– Di solito associativa a più vie (negli schemi precedenti era

puramente associativa)– È possibile che ci sia un miss anche se la diramazione è già

stata trattata in precedenza• In tal caso la diramazione è “nuova” e, in base al nostro criterio,

trova posto in cache solo se ha successo


BTB Pentium

000001

000002

111110

111111

TAG (6-31)

0-5

Destinazione2 Bit predizione

E’ una cache a 4 vie


E i salti incondizionati ??

• In precedenza abbiamo trattato solo salti condizionati• Niente toglie che in BTB ci stiano pure i salti

incondizionati– E’ implicito che la previsione è sempre vera– La prima volta che appaiono, PC viene modificato da ID

(JMP e JAL) e vanno in BTB (con previsione di successo (10) e indirizzo di destinazione)

– Finché sono in BTB, PC viene direttamente aggiornato da IF, senza alcuna penalizzazione.


Interruzioni

• Con la pipeline la gestione delle interruzioni si complica di molto: in pipeline ci sono più istruzioni– Si fanno concludere o si eliminano? e quali si elimina?– Le eccezioni si manifestano rispetto all’istruzione (allo

stadio) che le determina: • Eliminare l’istruzione che la determina e quelle che la seguono

– Le interruzioni esterne sono asincrone• Eliminare solo l’istruzione in IF e far concludere le altre?

– Se a un’eccezione o a un’interruzione esterna segue un’eccezione da parte di un’istruzione ancora in pipeline (non eliminata) occorre che il trattamento di questa abbia precedenza => c’è una priorità naturale


Eccezioni - Priorità

• Nota: Non è possibile che un’eccezione si manifesti in WB

Nome Tipo Causa Stadio

MadErr E Tentativo di Scritt/Lett dato nonallineato

ME

Div0 E Tentativo di divisione per zero EXSys T System call IDRI E Codice non definito IDFadErr E Tentativo di Lettura istr. non

allineataIF

INTR E Evento esterno Tutti


Priorità

• La priorità serve nel caso di eccez. Contemporanee.• Eccezioni NON contemporanee: la più prioritaria

passa avanti

2a. Bolla determinata dall’Eccezione in IF

1. Eccezione in IF (FAdErr)

2b. Eccezione in ME

2c. IF della prima istruz. Rout Serv Eccezione IF

3a. Bolla per Eccezione in ME

2c. IF della prima istruz. Rout Serv Eccezione ME

Contenuto della lezione - STLAB · G. Bucci - Calcolatori Elettronici. 13/09/2013 48. Come si...

Documents

Transcript of Contenuto della lezione - STLAB · G. Bucci - Calcolatori Elettronici. 13/09/2013 48. Come si...