Esercitazione Architettura degli elaboratori

EX WB

IF IF ID tutto OK

SW $1, 108($2) IF ID

SUB $4, $3, $1 si accorge di RAW su $2, risolvibile con forward

mem[108+[R2]] <- [R1] di EX/MEM.AluOutput verso TopAluInput

ma c’è un’altra RAW su $1: l’esecuzione di SW

SW in fase ID deve anche leggere $1=IF/ID.IR[rt] e non può procedere

propagarlo nei registri di pipeline fino alla fase MEM ma -> stallo

il valore corretto di $1 sarà scritto in fase WB di SUBI

16 8

19/06/2020

Sequenza 2

… 5 6 7 8 9 10 11 12 13

LW $3, 80 ($0) WB

ADD $2, $3, $1 MEM WB

EX

LW $1, 800($2) EX MEM WB

ID

SUBI $1, $1, 3 MEM WB

IF ID ID EX

ADDI $2, $2, 4 MEM

EX WB

IF IF ID

SW $1, 108($2) MEM WB

IF ID ID EX

SUB $4, $3, $1 lo stallo ripete la fase ID:

• nella prima metà del ciclo SUBI scrive $1

• nella seconda metà del ciclo SW può leggere $1

e risolve RAW su $2, con forward di

MEM/WB.AluOutput verso TopAluInput

17 Sequenza 2

… 5 6 7 8 9 10 11 12 13 14

LW $3, 80 ($0) WB

ADD $2, $3, $1 MEM WB

EX

LW $1, 800($2) EX ME WB

ID M

SUBI $1, $1, 3 ME WB

IF ID ID EX

ADDI $2, $2, 4 M ME

EX WB

IF IF ID

SW $1, 108($2) M

SUB $4, $3, $1 MEM WB

IF ID ID EX MEM WB

EX

IF IF ID

tutto ok: sia SUB che SW fanno lettura di $1

18 9

19/06/2020

Pipeline SENZA data forward

1 2 3 4 5 6 7 8 9 10 11

IF ID EX MEM WB

lw $3 80($0) IF ID ID ID EX MEM WB

add $2 $3 $1 ID ID EX MEM WB

lw $1 38($2) IF IF IF ID

subi $1 $1 3 IF IF IF ID

addi $2 $2 4

sw $1 11($2)

sub $4 $3 $1

19 Pipeline SENZA data forward

5 6 7 8 9 10 11 12 13 14 15

WB

lw $3 80($0) ID EX MEM WB

add $2 $3 $1 IF ID ID ID EX ME WB

lw $1 38($2) M

IF IF IF ID ID ID EX MEM WB

subi $1 $1 3 IF IF IF ID EX MEM WB

addi $2 $2 4

sw $1 11($2)

sub $4 $3 $1

20 10

19/06/2020

Pipeline SENZA data forward

9 10 11 12 13 14 15 16 17 18 19

lw $3 80($0)

add $2 $3 $1 EX MEM WB

lw $1 38($2) ID ID ID EX MEM WB

subi $1 $1 3 IF IF IF ID EX MEM WB

addi $2 $2 4 IF ID ID ID EX MEM WB

sw $1 11($2) IF IF IF ID EX MEM WB

sub $4 $3 $1

21 Sequenza 2: Riordino?

legge il contenuto di $3, che è definito

LW $3, 80 ($0) nell’istruzione precedente, quindi non si può

anticipare

ADD $2, $3, $1 legge il contenuto di $2, definito nella ADD

LW $1, 800($2) precedente, quindi non si può anticipare

SUBI $1, $1, 3 leggere il contenuto di $1, definito nella LW

precedente, quindi non si può anticipare

ADDI $2, $2, 4

SW $1, 108($2) si può anticipare prima di SUBI, ma non

prima di LW perche’ questa ADDI modifica $2

SUB $4, $3, $1 legge il contenuto di $2, definito nella ADDI

precedente, quindi deve stare dopo ADDI

basta sche stia dopo la SUBI che e legge $1, definito in SUBI, quindi anche

definisce il contenuto di $1, nota che dopo SUBI

SW legge $1

22 11

19/06/2020

Sequenza 2: Riordino?

LW $3, 80 ($0) LW $3, 80 ($0)

ADD $2, $3, $1 ADD $2, $3, $1

LW $1, 800($2) LW $1, 800($2)

SUBI $1, $1, 3 ADDI $2, $2, 4

ADDI $2, $2, 4 SUBI $1, $1, 3

SW $1, 108($2) SW $1, 108($2)

SUB $4, $3, $1 SUB $4, $3, $1

basta sche stia dopo la SUBI che deve leggere $1 in fase ID, ma

definisce il contenuto di $1, nota che $1 è scritto in fase WB di SUBI

SW legge $1 quindi peggiora la situazione!

23 Sequenza 3

lw $1 0 ($2)

add $2 $3 $1

sw $2 21 ($1)

beq $2 $1 11

add $3 $2 $2

add $1 $1 $3

sw $3 0 ($1)

24 12

19/06/2020

Pipeline CON data forward

1 2 3 4 5 6 7 8 9 10 11

lw $1 0 ($2) IF ID EX MEM WB

add $2 $3 $1 MEM

IF ID ID EX WB

sw $2 21 ($1)

beq $2 $1 11

add $3 $2 $2

add $1 $1 $3

sw $3 0 ($1)

2

istruzione 1 stallo e forward:

MEM/WB.LMD BottomALUInput



IF/ID.IR[rt] = ID/EX.IR[rt] RAW $1



25 Pipeline CON data forward

1 2 3 4 5 6 7 8 9 10 11

lw $1 0 ($2) IF ID EX MEM WB

add $2 $3 $1 MEM

IF ID ID EX WB

sw $2 21 ($1) MEM

IF IF ID ID ID EX WB

beq $2 $1 11

add $3 $2 $2

add $1 $1 $3

sw $3 0 ($1)

istruzione 3 deve leggere $2 in fase ID

quindi 2 stalli e lettura in seconda

IF/ID.IR[rs] = MEM/WB.IR[rt] RAW $1

 meta’ di ciclo

cosi’ si risolve anche RAW $1

IF/ID.IR[rt] = ID/EX.IR[rd] RAW $2



26 13

19/06/2020

Pipeline CON data forward

1 2 3 4 5 6 7 8 9 10 11

lw $1 0 ($2) IF ID EX MEM WB

add $2 $3 $1 MEM

IF ID ID EX WB

sw $2 21 ($1) MEM

IF IF ID ID ID EX WB

beq $2 $1 11 MEM

IF IF IF ID EX WB

add $3 $2 $2

add $1 $1 $3

sw $3 0 ($1)

istruzione 4 in ciclo 10 usa la

condizione di salto.

beq legge sia $2 che $1, che erano scritte da Supponiamo sia falsa

istruzioni 2 e 1, ma al ciclo 8 sono gia’ completate

27 Pipeline CON data forward

1 2 3 4 5 6 7 8 9 10 11

lw $1 0 ($2) IF ID EX MEM WB

add $2 $3 $1 MEM

IF ID ID EX WB

sw $2 21 ($1) MEM

IF IF ID ID ID EX WB

beq $2 $1 11 MEM

IF IF IF ID EX WB

add $3 $2 $2 ..

IF ID EX

add $1 $1 $3

sw $3 0 ($1)

istruzione 5

tutto ok

28 14

19/06/2020

Pipeline CON data forward

5 6 7 8 9 10 11 12 13 14

lw $1 0 ($2) WB

add $2 $3 $1 MEM

EX WB

sw $2 21 ($1) MEM

ID ID ID EX WB

beq $2 $1 11 MEM

IF IF IF ID EX WB

add $3 $2 $2 ME

IF ID EX WB

M

add $1 $1 $3 MEM

IF ID EX WB

sw $3 0 ($1)

istruzione 6

IF/ID.IR[rt] = ID/EX.IR[rd] RAW $3

 si risolve con forward:

EX/MEM.ALUOutput BottomALUInput



29 Pipeline CON data forward

5 6 7 8 9 10 11 12 13 14 15

lw $1 0 ($2) WB

add $2 $3 $1 MEM

EX WB

sw $2 21 ($1) MEM

ID ID ID EX WB

beq $2 $1 11 MEM

IF IF IF ID EX WB

add $3 $2 $2 MEM

IF ID EX WB

add $1 $1 $3 MEM WB

IF ID EX

sw $3 0 ($1) MEM WB

IF ID ID EX

istruzione 7 deve leggere $3 in fase ID

IF/ID.IR[rs] = ID/EX.IR[rd] RAW $1

 quindi 1 stalli e r/w in ciclo 12

piu’ forward:

IF/ID.IR[rt] = EX/MEM.IR[rd] RAW $3

 MEM/WB.AluOutput TopAluInput

30 15

19/06/2020

Sequenza con branch

LW $2, 0 ($1) assumiamo:

Label1: BEQ $2, $0, Label2 preso solo la prima volta

LW $3, 0 ($2)

BEQ $3, $0, Label1 preso sempre

ADD $1, $3, $1

Label2: SW $1, 0 ($2)

per semplicità

• usiamo Label al posto del campo Imm (esteso a 32 bit) da usare come offset

per calcolare l’indirizzo del salto:

beq $1, $2, Imm if ([R1]-[R2]==0) then PC=NPC+(Imm<<2)

• non assumiamo alcuna tecnica di predizione dei salti

• in fase EX di istruzione beq calcola la condizione e il target, ma è in fase MEM

che decide se saltare, cioè usa la condizione per decidere il valore di PC

31 Segnali di controllo in fase MEM decide come

aggiornare il PC a seconda

di salto preso o no

32 16

19/06/2020

Sequenza con branch

1 2 3 4 5 6 7 8

IF ID EX MEM WB

LW $2, 0 ($1) MEM WB

IF ID ID EX

L1:BEQ $2, $0, L2

LW $3, 0 ($2)

BEQ $3, $0, L1 si accorge che il registro di lettura IF/ID.IR[rs]

è uguale al registro di scrittura ID/EX.IR[rt] => RAW

ADD $1, $3, $1

L2:SW $1, 0 ($2) LW determina il valore da scrivere in $2 in fase MEM

quindi serve 1 stallo + data forward:

MEM/WB.LMD inviato a TopAluInput

I rs rt

codop address/const

BEQ/LW

33 Sequenza con branch

qui decide che salta

1 2 3 4 5 6 7 8 9 10 11

IF ID EX MEM WB

LW $2, 0 ($1) MEM WB

L1:BEQ $2, $0, L2 IF ID ID EX

LW $3, 0 ($2) IF IF ID EX

BEQ $3, $0, L1 IF ID

ADD $1, $3, $1 IF

L2:SW $1, 0 ($2) MEM WB

IF ID EX

scarta il contenuto della pipeline e

inizia IF dell’istruzione in L2

nessun problema di dipendenza

branch penalty = n. di cicli in cui non conclude nessuna istruzione = 3

34 17

19/06/2020

Sequenza con branch

se decide che NON salta

1 2 3 4 5 6 7 8 9 10

IF ID EX MEM WB

LW $2, 0 ($1) MEM WB

L1:BEQ $2, $0, L2 IF ID ID EX

LW $3, 0 ($2) MEM WB

IF IF ID EX

BEQ $3, $0, L1 MEM WB

IF ID ID EX

ADD $1, $3, $1 IF IF ID EX

L2:SW $1, 0 ($2) IF ID

tutto ok: no RAW su $2 poiche’ LW legge $2 in

seconda metà di ciclo 5, e in prima metà di ciclo 5

LW completa la scrittura

RAW su $3: come prima stallo più forward

35 Sequenza con branch

se decide che NON salta

1 2 3 4 5 6 7 8 9 10

IF ID EX MEM WB

LW $2, 0 ($1) decide che salta

MEM WB

L1:BEQ $2, $0, L2 IF ID ID EX

LW $3, 0 ($2) MEM WB

IF IF ID EX

BEQ $3, $0, L1 MEM WB

IF ID ID EX

ADD $1, $3, $1 IF IF ID EX

L2:SW $1, 0 ($2) IF ID IF

scarta le istruzioni e ricomincia con IF di L1

36 18

19/06/2020

Sequenza con branch

se decide che NON salta

1 2 3 4 5 6 7 8 9 10

IF ID EX MEM WB

LW $2, 0 ($1) decide che NON salta

MEM WB

L1:BEQ $2, $0, L2 IF ID ID EX

LW $3, 0 ($2) MEM WB

IF IF ID EX

BEQ $3, $0, L1 MEM WB

IF ID ID EX

ADD $1, $3, $1 IF IF ID EX

L2:SW $1, 0 ($2) IF ID

si accorge che c’è RAW su $1:

SW in fase ID deve leggere $1 e propagarlo nei registri

di pipeline fino alla fase MEM ma il valore corretto di $1

sarà scritto in fase WB di ADD

non c’è forward verso fase ID, quindi 2 stalli

37 Sequenza con branch

se decide che NON salta

… 6 7 8 9 10 11 12 13 14

LW $2, 0 ($1) decide che NON salta

MEM WB

L1:BEQ $2, $0, L2 MEM WB

EX

LW $3, 0 ($2) ME WB

ID ID EX

BEQ $3, $0, L1 M

ADD $1, $3, $1 ME WB

IF IF ID EX M

L2:SW $1, 0 ($2) EX MEM WB

IF ID ID ID

ripete la fase ID:

• nella prima metà del ciclo ADD scrive $1

• nella seconda metà del ciclo SW può leggere $1

38 19

Nome e Cognome: Matricola:

Corso di

Architettura degli Elaboratori

Anno Accademico 2019/2020

Esempio di compitino Seconda Parte

Istruzioni

• Scrivere Nome, Cognome e Matricola su ogni foglio (solo pagine dispari).

• Scrivere la risposta nello spazio bianco al di sotto della domanda; Non è possibile allegare fogli

aggiuntivi, quindi cercate di essere chiari e non prolissi.

• In caso di errori indicate chiaramente quale parte della risposta deve essere considerata; annullate

le parti non pertinenti.

• Assicurarsi che non manchi alcun foglio al momento della consegna.

1

Nome e Cognome: Matricola: Pagina 2

Domande a risposta multipla

es1

Quante volte la CPU deve accedere alla memoria quando preleva ed esegue un’istruzione che ha due

operandi, uno con modo di indirizzamento registro indiretto e uno con mod