La Pipeline

(1)

13/09/2013

G. 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

(2)

Schema della Pipeline

(3)

13/09/2013

Pipeline

• Modello di riferimento: pipeline a 5 stadi

IF: Prelievo istruzione

ID: Decodifica istruzione e fetch registri EX: Esecuzione codice operazione

ME: Accesso alla memoria

WB: Scrittura registro destinazione

Esempi commerciali

(4)

Esecuzione istruzioni

(5)

13/09/2013

Esempio esecuzione (ADD)

• Facciamo riferimento alle istruzioni aritmetiche ^(per

esempio ADD R1,R6,R9)

• (Solo gli elementi essenziali)

(6)

… 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.

(7)

13/09/2013

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)

(8)

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

(9)

13/09/2013

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

(10)

Prestazioni

Tempo richiesto dal generico stadio Tempo di latch

Periodo di clock in multiciclo Periodo di clock in pipeline Periodo di clock in monociclo

(11)

13/09/2013

Esempio

Tempo di latch:

Pipeline a 4 stadi con i seguenti tempi:

=

(12)

Profili di esecuzione

(13)

13/09/2013

….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

(14)

Indici delle prestazioni

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

(15)

13/09/2013

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

(16)

• 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

(17)

13/09/2013

• Accelerazione: Rapporto tra la velocità di un

processore con pipeline rispetto ad un processore multiciclo (ovvero tra i loro tassi di esecuzione)

(18)

Pipeline lineari/parallele

• Eliminazione di un collo di bottiglia

Originale

Parallela Lineare

(19)

13/09/2013

Esecuzione

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

(20)

Propagazione (segnali di controllo)

• Ingresso a UC:

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

• Verso ID/EX

ID/EX.WB <- UC.WB ID/EX.ME <- UC.ME ID/EX.EX <- UC.EX

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

• Verso EX/ME

EX/ME.WB <- ID/EX.WB EX/ME.ME <- ID/EX.ME EX/ME.RW <- ID/EX.RW

• Verso ME/WB

ME/WB.WB <- EX/ME.WB

C’è da fare la “lista della spesa”, cioè vedere quanto

valgono i campi e se ne servono altri.

(21)

13/09/2013

Istr. aritmetiche

(22)

...Istr. aritmetiche

• Fase IF

PC <- PC+4

IF/ID.IR <- MI[PC]

• Fase ID

ID/EX.EX.OPALU <- UC.OPALU ID/EX.WB.RWrite <- 1

ID/EX.EX.ALUMux <- UC.ALUMux ;(ALU.B = RF.B) ID/EX.WB.MemToReg <- 0

ID/EX.RW <- IF/ID.Rd ID/EX.A <- RF.A

ID/EX.B <- RF.B Dati

Selettori

Valide per tutte le istruzioni.

(nel seguito non sono indicate)

L’effettivo aggiornamento può essere diverso (salti)

Comandi

(23)

13/09/2013

...Istr. aritmetiche

• Fase EX

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

• Fase ME

ME/WB.WB <- EX/ME.WB ME/WB.RW <- EX/ME.RW

ME/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

(24)

Istr. Load

(25)

13/09/2013

Istr. Store

(26)

..LD/ST Fase ID

• Comuni a LD e ST

ID/EX.A <- RF.A

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

• Specifiche LD

ID/EX.ME.M_Read <- 1 ID/EX.WB.R_RWrite <- 1 ID/EX.WB.MemToReg <- 1

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

• Specifiche ST

ID/EX.WB.M_MWrite <- 1 ID/EX.B <- RF.B

(27)

13/09/2013

Istr. Salto condizionato

(28)

..Salto condizionato

• IF

IF/ID.PC <- PC+4 ; serve dopo

• ID

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

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

• EX

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

(29)

13/09/2013

.. Istruzioni JMP/ JR

• IF

• ID

ID/EX.IMM <- IF/ID.IND ;Per il JMP ID/EX.IMM <- RF.B ;Per JR

• EX

PCMux 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

(30)

...JAL

• Fase IF

• Fase ID

ID/EX.IMM <- IF/ID.IND ID/EX.WB.RWrite <- 1 ID/EX.WB.MemToReg <- 0 ID/EX.RW <- 31

ID/EX.PC <- IF/ID.PC ;per salvarlo

• Fase EX

PCMux a selezionare ID/EX.IMM

• Fasi ME , WB

Solo propagazione dei segnali

(che in WB determinano la scrittura in R31)

(31)

13/09/2013

Sintesi Campi Fine della lista della spesa

(32)

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;

(33)

13/09/2013

…. (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.

(34)

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

(35)

13/09/2013

UC

(36)

Unità di controllo – Esempio: Stadio IF

Superfluo

(37)

13/09/2013

PCMux

• Asserito su

– JMP – JAL – JR

– JE and Zero – JS and Segno

(38)

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

(39)

13/09/2013

LD

(NB: Little endian)

Lo schema è per il caso generale:

LDW LDB LDH

(40)

ST

(NB: Little endian)

Lo schema è per il caso generale:

STW STB STH

(41)

13/09/2013

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.

(42)

Conflitti strutturali

• Una sola porta di memoria (memoria unica)

(43)

13/09/2013

Soluzione

(44)

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

(45)

13/09/2013

Riconoscimento conflitti dati

ADD R1,R6,R9 LD R1,100(R3) ADD R1,R6,R9 SUB 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)

(46)

Condizioni

• Wa

• Wb

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

• Xa

• Xb

• Ma

• Mb

(47)

13/09/2013

Riconoscimento

(48)

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

(49)

13/09/2013

Stallo

(50)

Stallo

(51)

13/09/2013

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

(52)

Sovrapposizione (clock halving)

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

(53)

13/09/2013

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

(54)

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

(55)

13/09/2013

Conflitto ID-EX

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

a) L’istruzione in EX produce il dato in EX: forward di EX/ME.ALUout verso ALU al clock seguente

b) 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.

(56)

..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,r6 sub r1,r2,r3

(57)

13/09/2013

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

add r2,r5,r6 sub r1,r2,r3

Forward da ME a EX al clock successivo

(58)

b) 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

(59)

13/09/2013

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

Forward da WB a ME, dopo 2 clock

ST y(r2),r1 ***

(60)

Conflitto ID-ME

• Con il nostro repertorio in ME può esserci solo il LD

1. L’istruzione in ID usa il dato in EX: forward da WB a EX al clock successivo

2. L’istruzione in ID usa il dato in ME (può essere solo ST): forward da WB a ME al clock

(61)

13/09/2013

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)

(62)

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)

(63)

13/09/2013

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

(64)

Sintesi

(65)

13/09/2013

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,R2 ST A(R0),R3 LD R1,E(R0) LD R2,F(R0) ADD R3,R1,R2 ST D(R0),R3

(66)

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

LD R1,B(R0) LD R2,C(R0) ADD R3,R1,R2 ST A(R0),R3 LD R1,E(R0) LD R2,F(R0) ADD R3,R1,R2

(67)

13/09/2013

Riordinamento (statico)

Come fare

LD R1,B(R0) LD R2,C(R0) LD R4,E(R0) ADD R3,R1,R2 LD R2,F(R0) ST A(R0),R3 ADD R3,R4,R2 ST 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

(68)

…Riordinamento (statico)

Ipotesi: la macchina ha la sovrapposizione ma NON il bypass

Totale 8 stalli.

Richiede 2 stalli (per R3) Richiede 2 stalli (per R2)

(69)

13/09/2013

..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)

(70)

..la soluzione precedente

BELLO, ma attenzione alla compatibilità !!!!

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

Si guadagnano 3 clock

(71)

13/09/2013

Conflitti per salti incondizionati

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

(72)

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,R3 SUB R4,R5,R6

JMP DaQualcheParte ::I1

::I2

LD R1,100(R3)

JMP DaQualcheParte ADD R2,R2,R3

SUB R4,R5,R6 ::I1

::I2

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

(73)

13/09/2013

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)

(74)

Soluzione compilativa: Riordinamento

Dest ADD R2,R1,R3 JE R1,R3,Dest SUB R4,R2,R1 XX

• 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,R3 SUB R4,R2,R1 JE R1,R3,Dest XX

(75)

13/09/2013

...Soluzione compilativa (con dipendenza)

ADD R7,R1,R3 Dest ..altre istruzioni

SUB R4,R2,R1 JE R4,R8,Dest ADD R7,R1,R3 MUL R5,R2,R1 Dest ADD R7,R1,R3

..altre istruzioni SUB R4,R2,R1 JE R4,R8,Dest MUL R5,R2,R1

Si può portare la ADD dietro a JE.

Il codice deve essere ristrutturato come sotto

(76)

SUB R4,R2,R1 JE R4,R8,Dest ADD R7,R1,R3

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

(77)

13/09/2013

SUB R4,R2,R1 JE R4,R8,Dest ADD R7,R1,R3 MUL R5,R2,R1 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

(78)

… Soluzione compilativa

SUB R4,R2,R1 JE R4,R8,Dest ADD R7,R1,R3 MUL R5,R7,R1 Dest ADD R7,R1,R3

..altre istruzioni SUB R4,R2,R1 JE R4,R8,Dest MUL 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

(79)

13/09/2013

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 ?

(80)

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.

(81)

13/09/2013

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)

(82)

Predittore a 2 bit (statistica)

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

(83)

13/09/2013

Tabella di predizione (BPB)

Cache associativa

Il campo di sinistra ha funzione di TAG

Per come è gestita possono esserci solo gli indirizzi di diramazioni

(84)

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)

(85)

13/09/2013

Come si attua (1: previsione)

Quando una generica istruzione è in IF A. 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)

(86)

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)

(87)

13/09/2013

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 saturazione b) 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 saturazione

c) Previsione = F & Presenza = V & Condizione = V

 Inserimento bolla in IF e ID

 Modifica di PC con l’indirizzo di destinazione

d) Previsione = F & Presenza = V & Condizione = F (indovinato !)

e) 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

(88)

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 saturazione b) 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

c) Previsione = F & Presenza = V & Condizione = V

d) Previsione = F & Presenza = V & Condizione = F (indovinato !)

e) Previsione = F & Presenza = F & Condizione = V

 Inserimento in BPB (tag e contatore)

f) Previsione = F & Presenza = F & Condizione = F (assunzione giusta)

 Niente

(89)

13/09/2013

Prestazioni BPB

Riassunto delle considerazioni precedenti

(90)

Branch Target Buffer (BTB)

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

• Formato del buffer

(91)

13/09/2013

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

(92)

Predizione con BTB

(93)

13/09/2013

Predizione con BTB (come si legge)

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

dall’indirizzo di diramazione

(94)

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

(95)

13/09/2013

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)

(96)

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

(97)

13/09/2013

BTB Pentium

000001 000002

111110 111111

TAG (6-31) 0-5

Destinazione

2 Bit predizione

E’ una cache a 4 vie

(98)

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.

(99)

13/09/2013

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

(100)

Eccezioni - Priorità

Nome Tipo Causa Stadio

MadErr E Tentativo di Scritt/Lett dato non allineato

ME Div0 E Tentativo di divisione per zero EX

Sys T System call ID

RI E Codice non definito ID

FadErr E Tentativo di Lettura istr. non allineata

IF

INTR E Evento esterno Tutti

(101)

13/09/2013

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