Esercizio Pipeline MIPS

Soluzione

Considerando la pipeline MIPS vista a lezione, si consideri il seguente frammento di codice:

loop:	LW	R1, 0(R2)	R1← mem[0+[R2]]
	ADDI	R1,R1,#1	R1← [R1] + 1
	SW	R1, 0(R2)	mem[0+[R2]] ← [R1]
	ADDI	R2, R2, #4	R2← [R2] + 4
	SUB	R4, R3, R2	R4← [R3] - [R2]
	BENZ	R4, loop	if([R4] != 0) PC ← indirizzo(loop)

assumendo che il valore iniziale di R3 sia R2+396.

a) si individuino e discutano le dipendenze dovute ai dati

Soluzione:

DIPENDENZE [dipendenza dati (senza considerare limiti architettura MIPS)]
[dipendenza dati considerando i limiti della architettura MIPS]

R1 in ADDI R1,R1,#1
dipende da

LW R1, 0(R2)
[input EXE_ADDI ha bisogno di output da MEM_LW]
[ID_ADDI deve legge R1 aggiornato da WB_LW (stesso ciclo clock)]

R1 in SW R1,0(R2)
dipende da

LW R1, 0(R2)
[input MEM_SW ha bisogno di output da MEM_LW]
[ID_SW deve legge R1 aggiornato da WB_LW (stesso ciclo clock)]

R1 in SW R1,0(R2)
dipende da

ADDI R1,R1,#1
[input MEM_SW ha bisogno di output da EXE_ADDI]
[ID_SW deve legge R1 aggiornato da WB_ADDI (stesso ciclo clock)]

R2 in SUB R4, R3, R2
dipende da

ADDI R2,R2,#4
[input EXE_SUB ha bisogno di output da EXE_ADDI]
[ID_SUB deve legge R2 aggiornato da WB_ADDI (stesso ciclo clock)]

R4 in BENZ R4, loop
dipende da

SUB R4, R3, R2
[input EXE_BENZ ha bisogno di output da EXE_SUB]
[ID_BENZ deve legge R4 aggiornato da WB_SUB (stesso ciclo clock)]

b) mostrare come evolve la pipeline durante l'esecuzione del codice per le prime 6 istruzioni eseguite, assumendo:

possibilità di forwarding, così come visto a lezione per la pipeline MIPS;
che il salto condizionale (BENZ) sia trattato con stallo della pipeline fino al calcolo dell'indirizzo target.

Si calcoli inoltre il numero totale di cicli di clock necessari per portare a termine l'esecuzione completa del codice.

Soluzione:

Evoluzione pipeline per le prime 6 istruzioni eseguite

1 2 3 4 5 6 7 8 9 10 11

l: LW R1,0(R2) IF ID EXE MEM WB

ADDI R1,R1,#1 IF ID ID EXE MEM WB

SW R1, 0(R2) IF IF ID EXE MEM WB

ADDI R2,R2,#4 IF ID EXE MEM WB

SUB R2,R3,R2 IF ID EXE MEM WB

BENZ R4, l IF ID EXE MEM WB

non preso/preso IF IF IF (preso: LW R1,0(R2) ID

Il numero totale di cicli è calcolato come segue:

numero di iterazioni del ciclo = (396/4) + 1 = 99 + 1 = 100

numero cicli di clock per eseguire il codice = 99 * 9 (si sovrappone MEM_BENZ della iterazione i con IF_LW della iterazione i+1) + 1*11 = 902

Se si considera che lo stadio WB di BENZ in effetti non fa nulla, i cicli sono 901.

DIPENDENZE	[dipendenza dati (senza considerare limiti architettura MIPS)] [dipendenza dati considerando i limiti della architettura MIPS]
R1 in ADDI R1,R1,#1 dipende da LW R1, 0(R2)	[input EXE_ADDI ha bisogno di output da MEM_LW] [ID_ADDI deve legge R1 aggiornato da WB_LW (stesso ciclo clock)]
R1 in SW R1,0(R2) dipende da LW R1, 0(R2)	[input MEM_SW ha bisogno di output da MEM_LW] [ID_SW deve legge R1 aggiornato da WB_LW (stesso ciclo clock)]
R1 in SW R1,0(R2) dipende da ADDI R1,R1,#1	[input MEM_SW ha bisogno di output da EXE_ADDI] [ID_SW deve legge R1 aggiornato da WB_ADDI (stesso ciclo clock)]
R2 in SUB R4, R3, R2 dipende da ADDI R2,R2,#4	[input EXE_SUB ha bisogno di output da EXE_ADDI] [ID_SUB deve legge R2 aggiornato da WB_ADDI (stesso ciclo clock)]
R4 in BENZ R4, loop dipende da SUB R4, R3, R2	[input EXE_BENZ ha bisogno di output da EXE_SUB] [ID_BENZ deve legge R4 aggiornato da WB_SUB (stesso ciclo clock)]