Il pipelining: criticità sui dati Il pipelining: criticità sui dati

(1)

Il pipelining: criticità sui dati Il pipelining: criticità sui dati

Lucidi fatti in collaborazione con l’Ing. Valeria Cardellini

(2)

Codice iniziale con criticità

sub $2, $1, $3 and $12, $2, $5 or $13, $6, $2 add $14, $2, $2 sw $15,100($2)

Criticità sui dati (1° esempio)

(3)

Criticità sui dati (1°esempio) Criticità sui dati (1°esempio)

Presenza conflitto strutturale banco- registri

SOLUZ. con NOP Codice iniziale

con criticità

sub $2, $1, $3 and $12, $2, $5 or $13, $6, $2 add $14, $2, $2 sw $15,100($2)

(4)

Criticità sui dati (1° esempio) Criticità sui dati (1° esempio)

Codice con nop ipotizzando che ci sia conflitto strutturale sul banco-registri

sub $2, $1, $3 nop, nop, nop and $12, $2, $5 or $13, $6, $2 add $14, $2, $2 sw $15,100($2) Codice iniziale

con criticità

sub $2, $1, $3 and $12, $2, $5 or $13, $6, $2 add $14, $2, $2 sw $15,100($2)

(5)

Criticità sui dati (1° esempio) Criticità sui dati (1° esempio)

sub $2, $1, $3 nop, nop, nop and $12, $2, $5 or $13, $6, $2 add $14, $2, $2 sw $15,100($2)

Codice con nop ipotizzando che NON ci sia

conflitto

strutturale sul banco-registri Codice iniziale

con criticità

sub $2, $1, $3 and $12, $2, $5 or $13, $6, $2 add $14, $2, $2 sw $15,100($2)

(6)

sub $2, $1, $3 nop, nop, nop and $12, $2, $5 or $13, $6, $2 add $14, $2, $2 sw $15,100($2)

Codice con nop ipotizzando che NON ci sia

conflitto

strutturale sul banco-registri

sub $2, $1, $3 nop, nop

and $12, $2, $5 or $13, $6, $2 add $14, $2, $2 sw $15,100($2) Codice iniziale

con criticità

sub $2, $1, $3 and $12, $2, $5 or $13, $6, $2 add $14, $2, $2 sw $15,100($2)

Criticità sui dati (1° esempio)

(7)

Criticità sui dati (2°esempio) Criticità sui dati (2°esempio)

sub $2, $1, $3 and $12, $7, $5 or $13, $6, $2 add $14, $2, $2 sw $15,100($13)

SOLUZ. con NOP

SOLUZ. con

riordino istruzioni, uso minimo di nop Presenza conflitto strut. banco-reg.

(8)

Criticità sui dati (2°esempio) Criticità sui dati (2°esempio)

sub $2, $1, $3 and $12, $7, $5 or $13, $6, $2 add $14, $2, $2 sw $15,100($13)

SOLUZ. con NOP

sub $2, $1, $3 and $12, $7, $5 nop, nop

or $13, $6, $2 add $14, $2, $2 nop, nop

sw $15,100($13)

VERIFICA se possibie usare SOLUZ. con

riordino istruzioni, uso minimo di nop Presenza conflitto strut. banco-reg.

sub $2, $1, $3 and $12, $7, $5 nop, nop

or $13, $6, $2 add $14, $2, $2 nop, nop

sw $15,100($13) Non c’è alcuna istruzione che si può spostare

(9)

Altro esempio

sub $2, $1, $3 and $12, $7, $5 or $13, $6, $2 add $14, $2, $2

sw $15,100($16) /* istruz.

differente rispetto a prima*/

SOLUZ. con riordino

istruzioni, uso min di nop Presenza conflitto strut.

banco-reg

(10)

Altro esempio

SOLUZ. con riordino

istruzioni, uso min di nop Presenza conflitto strut.

banco-reg sub $2, $1, $3 and $12, $7, $5 sw $15,100($16) nop

or $13, $6, $2 add $14, $12, $2 Codice iniziale con criticità

sub $2, $1, $3 and $12, $7, $5 or $13, $6, $2 add $14, $2, $2

sw $15,100($16) /* istruz.

modificata rispetto a prima*/

(11)

Soluzione hardware Soluzione hardware

criticità sui dati con propagazione in avanti

(12)

(13)

13

Criticità sui dati Criticità sui dati

• Consideriamo una sequenza di 5 istruzioni

2 criticità sui dati risolvibili mediante propagazione allo stadio EX

(14)

14

Soluzione con propagazione Soluzione con propagazione

propagazione

ottimizz. banco dei registri

(15)

propagazione

ottimizz.

banco dei registri

(16)

16

Soluzione con propagazione (2) Soluzione con propagazione (2)

• Consideriamo la prima criticità (EX):

sub $2, $1, $3 e and $12, $2, $5

– Il dato prodotto dall’istruzione sub è disponibile alla fine dello stadio EX (CC 3)

– Il dato è richiesto dall’istruzione and all’inizio dello stadio EX (CC 4) – La criticità può essere rilevata quando l’istruzione and si trova nello

stadio EX e l’istruzione sub si trova nello stadio MEM

• Consideriamo la seconda criticità (MEM):

sub $2, $1, $3 e or $13, $6, $2

– Il dato prodotto dall’istruzione sub è disponibile alla fine dello stadio EX (CC 3)

– Il dato è richiesto dall’istruzione or all’inizio dello stadio EX (CC 5) – La criticità può essere rilevata quando l’istruzione or si trova nello

stadio EX e l’istruzione sub si trova nello stadio WB

(17)

17

Propagazione dai registri di pipeline Propagazione dai registri di pipeline

• Gli ingressi alla ALU sono forniti dal registro di pipeline d’avanti anziché dal registro di pipeline di dietro

– In questo modo le dipendenze sono in avanti nel tempo

Da EX/MEM

Da MEM/WB

(18)

soluzione per la propagazione soluzione per la propagazione

• struttura modificata:

i dati all’ALU vengono forniti da più registri di pipeline

• struttura di base

rt rd

Alla

Forwarding

unit servono gli identificativi dei registri

sorgenti (istr.

seguente) che quelli destin (istruz.

Success)

(19)

(20)

20

Progetto unità di propagazione:

Riconoscimento della criticità sui dati Riconoscimento della criticità sui dati

• Condizioni che generano la criticità sui dati:

– Reg. destin. istr. preced

non conclusa = Reg. sorg. istr. nella fase di fetch

• Notazione:

– NomeRegistroPipeline.CampoRegistro 1a. EX/MEM.RegisterRd = ID/EX.RegisterRs 1b. EX/MEM.RegisterRd = ID/EX.RegisterRt 2a. MEM/WB.RegisterRd = ID/EX.RegisterRs 2b. MEM/WB.RegisterRd = ID/EX.RegisterRt

(21)

•Consideriamo la prima criticità (EX):

sub $2, $1, $3 e and $12, $2, $5

–E’ verificata la condizione 1a

EX/MEM.RegisterRd = ID/EX.RegisterRs = $2

•Consideriamo la seconda criticità (MEM):

sub $2, $1, $3 e or $13, $6, $2

–E’ verificata la condizione 2b

MEM/WB.RegisterRd = ID/EX.RegisterRt = $2

Progetto unità di propagazione:

Riconoscimento della criticità sui dati

(22)

22

Riconoscimento della criticità sui dati (2) Riconoscimento della criticità sui dati (2)

• Per evitare propagazioni inutili raffiniamo le condizioni

– Non tutte le istruzioni scrivono un registro

• Controlliamo se RegWrite è asserito

– Nel MIPS il contenuto del registro $0 quando letto deve sempre essere pari a 0, pertanto se è il registro destinazione non si richiede propagazione

• Aggiungiamo EX/MEM.RegisterRd0 e MEM/WB.RegisterRd0

• Quindi le condizioni divengono:

1a. EX/MEM.RegWrite and (EX/MEM.RegisterRd  0) and (EX/MEM.RegisterRd = ID/EX.RegisterRs)

1b. EX/MEM.RegWrite and (EX/MEM.RegisterRd  0) and (EX/MEM.RegisterRd = ID/EX.RegisterRt)

2a. MEM/WB.RegWrite and (MEM/WB.RegisterRd  0) and

(MEM/WB.RegisterRd = ID/EX.RegisterRs)

2b. MEM/WB.RegWrite and (MEM/WB.RegisterRd  0) and

(MEM/WB.RegisterRd = ID/EX.RegisterRt)

(23)

23

Hardware per la propagazione Hardware per la propagazione

• ALU e registri di pipeline senza propagazione

• ALU e registri di pipeline con propagazione

- Unità di propagazione (forwarding unit): assegna un valore ai segnali di

controllo ForwardA e ForwardB per i due mux davanti alla ALU

rt rd

(24)

(25)

25

Segnali di controllo per la propagazione Segnali di controllo per la propagazione

Controllo MUX Sorgente Significato

ForwardA = 00 ID/EX Primo operando della ALU dal banco dei registri

ForwardA = 10 EX/MEM Primo operando della ALU propagato dal precedente risultato della ALU

ForwardA = 01 MEM/WB Primo operando della ALU propagato dalla memoria dati o da un precedente risultato della ALU

ForwardB = 00 ID/EX Secondo operando della ALU dal banco dei registri

ForwardB = 10 EX/MEM Secondo operando della ALU propagato dal precedente risultato della ALU

ForwardB = 01 MEM/WB Secondo operando della ALU propagato dalla memoria dati o da un precedente risultato della ALU

(26)

26

Condizioni e segnali di controllo Condizioni e segnali di controllo

• Criticità EX

if (EX/MEM.RegWrite

and (EX/MEM.RegisterRd  0)

and (EX/MEM.RegisterRd = ID/EX.RegisterRs)) ForwardA = 10

if (EX/MEM.RegWrite

and (EX/MEM.RegisterRd = ID/EX.RegisterRt)) ForwardB = 10

(27)

27

Condizioni e segnali di controllo (2) Condizioni e segnali di controllo (2)

• Criticità MEM

if (MEM/WB.RegWrite

and (MEM/WB.RegisterRd  0)

and (MEM/WB.RegisterRd = ID/EX.RegisterRs)) ForwardA = 01

if (MEM/WB.RegWrite

and (MEM/WB.RegisterRd  0)

and (MEM/WB.RegisterRd = ID/EX.RegisterRt)) ForwardB = 01

(28)

28

Doppio conflitto con stesso “registro”

• Potenziale criticità tra risultato dell’istruzione nello stadio WB, risultato dell’istruzione nello stadio MEM e operando sorgente dell’istruzione nello stadio EX

– Esempio

add $1, $1, $2

add $1, $1, $3 criticità EX con prima istruzione

add $1, $1, $4 criticità MEM con prima, EX con seconda, deve vincere criticità EX

– Cioè se inizialmente $1 =0, $2 =5, $3 =6, $4 =7 , allora vorremmo che:

add $1, $1, $2 ($1 =5) add $1, $1, $3 ($1 =11) add $1, $1, $4 ($1 =18)

N.B. se vincesse la criticità MEM avremmo che $1 =12

(29)

Condizioni e segnali di controllo (4) Condizioni e segnali di controllo (4)

Quindi, le condizioni per la criticità MEM diventano:

if (MEM/WB.RegWrite

and (EX/MEM.RegisterRd  ID/EX.RegisterRs) and (MEM/WB.RegisterRd  0)

and (MEM/WB.RegisterRd = ID/EX.RegisterRs)) ForwardA = 01

if (MEM/WB.RegWrite

and (EX/MEM.RegisterRd  ID/EX.RegisterRt) and (MEM/WB.RegisterRd  0)

and (MEM/WB.RegisterRd = ID/EX.RegisterRt)) ForwardB = 01

(30)

30

Unità di elaborazione dati con forwarding

(31)

Esercizio: progetto dell’unità di forwarding Esercizio: progetto dell’unità di forwarding

• Per esempio progettare parte dell’unità che controlla - Criticità EX

if (EX/MEM.RegWrite

and (EX/MEM.RegisterRd = ID/EX.RegisterRs)) ForwardA = 10

(32)

32

Esempio Esempio

• Consideriamo la sequenza di istruzioni MIPS

sub $2, $1, $3 and $4, $2, $5 or $4, $4, $2 add $9, $4, $2

• Analizziamo l’esecuzione della sequenza nei cicli di clock da 3 a 6

– Ciclo 3: sub in EX – Ciclo 4: and in EX – Ciclo 5: or in EX – Ciclo 6: add in EX

• Nota: l’istruzione or ha una doppia criticità sui dati

(33)

33

Esempio: cicli di clock 3 e 4 Esempio: cicli di clock 3 e 4

• or: entra nella pipeline

• Nessuna criticità

• and: in ID/EX vengono scritti $2, $5, 2, 5, e 4 (numeri dei registri)

• add: entra nella pipeline

• Criticità tra and e sub su $2

• and: $2 da EX/MEM, $5 da ID/EX

or $4, $4, $2 and $4, $2, $5

(34)

34

Esempio: cicli di clock 5 e 6 Esempio: cicli di clock 5 e 6

• sub: termina l’esecuzione scrivendo nella prima metà del ciclo di clock $2 nel banco dei registri (no

criticità tra add e sub su $2)

• Criticità tra or e and su $4 e tra or e sub su $2

• or: $4 da EX/MEM, $2 da MEM/WB

• and: termina l’esecuzione

• Criticità tra add e or su $4

• add: $4 da EX/MEM, $2 da ID/EX

(35)

35

Modifica per calcolare indirizzo di memoria Modifica per calcolare indirizzo di memoria

(dato alla somma del contenuto di un registro con indirizzo di 16 bit esteso a 32) (dato alla somma del contenuto di un registro con indirizzo di 16 bit esteso a 32)

• Si aggiunge un MUX per scegliere come secondo operando

sorgente della ALU anche il valore immediato (esteso in segno a 32 bit) per istruzioni load e store

(36)

36

Esercizio Esercizio

• Considerare la sequenza di istruzioni MIPS

add $1, $1, $3 add $4, $2, $1 and $5, $4, $1

• Analizzare l’esecuzione della sequenza nei cicli di

clock da 3 a 5

(37)

37

Criticità

Criticità load/use : propagazione e stallo : propagazione e stallo

• La propagazione non basta per risolvere una criticità sui dati determinata da un’istruzione che ha letto il registro che ancora non è stato aggiornato dalla precedente istruzione lw, in questo caso il dato è disponibile solo alla fine del periodo di clock e nel frattempo l’ALU ha già finito di lavorare.

– Occorre individuare la criticità ed inserire uno stallo della pipeline

Criticità sui dati non risolvibile mediante la sola propagazione

(38)

38

Condizione per la criticità load/use Condizione per la criticità load/use

• Condizione per individuare la criticità sui dati di tipo load/use

– Controllare se istruzione lw è nello stadio EX

– Controllare se il registro da caricare con lw è usato come operando dall’istruzione corrente nello stadio ID

– In caso affermativo, bloccare la pipeline per un ciclo di clock if (ID/EX.MemRead and

and ((ID/EX.RegisterRt = IF/ID.RegisterRs) or (ID/EX.RegisterRt = IF/ID.RegisterRt)))

then metti bolla/stallo

• Condizione implementata dall’unità di rilevamento di

criticità (hazard detection unit)

(39)

39

Implementazione di uno stallo Implementazione di uno stallo

• Per un ciclo di clock

– Non aggiornare il PC (PCWrite = 0)

– Mantenere il contenuto del registro IF/ID (IF/IDWrite = 0)

– Mettere le 9 linee di controllo negli stadi EX, MEM e WB pari a 0, micro-comandi relativi alla “nop”

and $4, $2, $5

Da MEM/WB L’istruz. and

diventa nop

(40)

40

Unità di elaborazione

(41)

41

Esempio Esempio

• Consideriamo la sequenza di istruzioni MIPS

lw $2, 20($1) and $4, $2, $5 or $4, $4, $2 add $9, $4, $2

• Simile all’esempio del lucido 13 ad eccezione della prima istruzione

• Analizziamo l’esecuzione della sequenza nei cicli di

clock da 2 a 7

(42)

42

Esempio: cicli di clock 2 e 3 Esempio: cicli di clock 2 e 3

• and: entra nella pipeline

• Nessuna criticità

• lw: In ID/EX vengono scritti

$1, 1 e 2 (numeri dei registri)

• or: entra nella pipeline

• and: dovrebbe leggere il valore scritto in $2 da lw.

L’unità di rilevamento di criticità blocca

l’avanzamento delle istruzioni and e or:

PCWrite=0 e IF/ID.Write=0

(43)

43

Esempio: cicli di clock 4 e 5 Esempio: cicli di clock 4 e 5

• Viene inserito lo stallo

• and e or possono

riprendere l’esecuzione

• and: $2 da MEM/WB, $4 da ID/EX

(44)

44

Esempio: cicli di clock 6 e 7 Esempio: cicli di clock 6 e 7

• Lo stallo ha consentito a lw di scrivere nel quinto ciclo:

nel sesto ciclo non occorre la propagazione da

MEM/WB per or

• or: $4 da EX/MEM e $2 da ID/EX

• Criticità tra add e or su $4

• add: $4 da EX/MEM e $2 da ID/EX

(45)

45

Esercizio Esercizio

• Considerare la sequenza di istruzioni MIPS

lw $2, 20($1) add $4, $5, $2 sub $4, $4, $2

• Analizzare l’esecuzione della sequenza nei cicli di

clock da 3 a 6

(46)