Cognome e Nome: Matricola:
Ho gi`a superato il Modulo 1 con Voto
Architettura degli Elaboratori - mod 2 (1
aprova parziale)
(17 Aprile 2019)Esercizio 1
Per l’esecuzione del seguente codice:
1. add $t0, $a0, $s0
2. lw $t1, 0($t0)
3. addi $t1, $t1, 50
4. sw $t1, 0($t0)
5. addi $s0, $s0, 4 6. bne $s0, $t1, loop
si consideri un’architettura pipeline a 5 stadi (con delayed branch e anticipo allo stadio ID del completamento delle branch).
In particolare : (a) un’architettura pipeline senza forwarding e con il register file speciale che scrive un registro nella prima parte del ciclo e legge una coppia di registri nella seconda parte del ciclo: (b) architettura con forwarding e register file speciale.
1. Individuare le dipendenze RAW (Read After Write) nel codice, facendo riferimenti ai numeri che ideantificano le varie istruzioni e al registro che causa ciascuna dipendenza;
2. Disegnare il diagramma temporale per il caso (a);
3. Disegnare il diagramma temporale per il caso (b) evidenzando i forwarding necessari per risolvere le dipen- denze RAW (da quale registro intermedio a quale unit`a funzionale);
4. Modificare l’ordine delle istruzioni per ridurre gli stalli nel caso (b) (opzionale).
Soluzione
1 -> 2 ($t0) 1 -> 4 ($t0) 2 -> 3 ($t1) 3 -> 4 ($t1) 3 -> 6 ($t1) 5 -> 6 ($s0)
Caso a:
--- add $t0, $a0, $s0 | IF | ID | EX | ME | WB |
--- lw $t1, 0($t0) | IF | ID |<ID>|<ID>| EX | ME | WB |
--- addi $t1, $t1, 50 | IF |<IF>|<IF>| ID |<ID>|<ID>| EX | ME | WB |
--- sw $t1, 0($t0) | IF |<IF>|<IF>| ID |<ID>|<ID>| EX | ME | WB |
---
addi $s0, $s0, 4 | IF |<IF>|<IF>| ID | EX | ME | WB |
---
bne $s0, $t1, loop | IF | ID |<ID>|<ID>| EX | ME | WB |
---
nop | IF |<IF>|<IF>| ID | EX | ME | WB |
---
Caso b:
--- 1. add $t0, $a0, $s0 | IF | ID | EX | ME | WB |
--- 2. lw $t1, 0($t0) | IF | ID | EX | ME | WB |
--- 3. addi $t1, $t1, 50 | IF | ID |<ID>| EX | ME | WB |
--- 4. sw $t1, 0($t0) | IF |<IF>| ID | EX | ME | WB |
---
5. addi $s0, $s0, 4 | IF | ID | EX | ME | WB |
---
6. bne $s0, $t1, loop | IF | ID |<ID>| EX | ME | WB |
---
nop | IF |<IF>| ID | EX | ME | WB |
---
Le dipendenze RAW vengono risolte come segue:
• 1->2 ($t0): forwarding dal registro EX/ME allo stadio EX
• 1->4 ($t0): lo stadio ID di 4 eseguito quando 1 `e gi`a completato
• 2->3 ($t1): forwarding dal registro ME/WB allo stadio EX
• 3->4 ($t1): forwarding dal registro EX/ME allo stadio EX
• 3->6 ($t1): dipendenza risolta dal register file speciale
• 5->6 ($s0): forwarding dal registro EX/ME allo stadio ID (che conclude l’esecuzione di bne)
Infine modifichiamo l’ordine delle istruzioni per ridurre gli stalli. In particolare, poniamo anche un’istruzione indipendente nel delay slot dell’istruzione bne.
--- 1. add $t0, $a0, $s0 | IF | ID | EX | ME | WB |
--- 2. lw $t1, 0($t0) | IF | ID | EX | ME | WB |
--- 5. addi $s0, $s0, 4 | IF | ID | EX | ME | WB |
---
3. addi $t1, $t1, 50 | IF | ID | EX | ME | WB |
--- 6. bne $s0, $t1, loop | IF | ID |<ID>| EX | ME | WB |
---
4. sw $t1, 0($t0) | IF |<IF>| ID | EX | ME | WB |
---
Si noti come l’ordine stabilito dalle dipendenze 1->2, 1->4, 2->3, 3->4, 3->6 e 5->6 continui ad essere rispettato nel codice in cui le istruzioni sono state riordinate.
Esercizio 2
Supporre di avere una memoria indirizzabile al byte, acceduta con un indirizzo fisico di 32 b. Supporre inoltre che la CPU invii una serie di indirizzi come segue: 0x00000419, 0x0000041B, 0x00000423, 0x00000428, 0x0000042B, 0x0000041E, 0x0000041F, 0x00000433.
La cache contiene solo 4 blocchi ed `e inizialmente vuota. Rispondere ai seguenti quesiti:
• Cache direct-mapped, composta da 4 blocchi grandi da 1 word (4 B): determinare se ogni accesso `e un hit o un miss, e mostrare il contenuto finale della cache, con la TAG associata ad ogni blocco.
• Cache 2-way set associative, composta da 2 insiemi con blocchi da 2 word (8 B): determinare se ogni accesso
`
e un hit o un miss, e mostrare il contenuto finale della cache, con la TAG associata ad ogni blocco.
• Cache fully associative, composta da 4 blocchi da 2 word (8 B): determinare se ogni accesso `e un hit o un miss, e mostrare il contenuto finale della cache, con la TAG associata ad ogni blocco.
Soluzione
• se la cache ha 4 blocchi ed `e diretta, allora INDEX = log 4 = 2 b. Anche l’OFFSET `e di 2 bit, poich´e il blocco `e di 4 B. Infine TAG = 32 - 2 -2 = 28 b. Per la sequenza di accesso della cache abbiamo:
0x419: TAG=41 INDEX+OFFSET = 10+01 → miss 0x41B: TAG=41 INDEX+OFFSET = 10+11 → hit 0x423: TAG=42 INDEX+OFFSET = 00+11 → miss
0x428: TAG=42 INDEX+OFFSET = 10+00 → miss + conflict 0x42B: TAG=42 INDEX+OFFSET = 10+11 → hit
0x41E: TAG=41 INDEX+OFFSET = 11+10 → miss 0x41F: TAG=41 INDEX+OFFSET = 11+11 → hit
0x433: TAG=43 INDEX+OFFSET = 00+11 → miss + conflict ---
Set no. 00: | TAG = 43 |
Set no. 01: | |
Set no. 10: | TAG = 42 | Set no. 11: | TAG = 41 | ---
• se la cache ha 2 insiemi, allora INDEX = log 2 = 1 b. L’OFFSET `e di log 8=3 bit (blocco da 8 B), mentre TAG = 32 - 1 - 3 = 28 b. Per la sequenza di accesso della cache abbiamo:
0x419: TAG=41 INDEX+OFFSET = 1+001 → miss 0x41B: TAG=41 INDEX+OFFSET = 1+011 → hit 0x423: TAG=42 INDEX+OFFSET = 0+011 → miss 0x428: TAG=42 INDEX+OFFSET = 1+000 → miss 0x42B: TAG=41 INDEX+OFFSET = 1+011 → hit 0x41E: TAG=41 INDEX+OFFSET = 1+110 → hit 0x41F: TAG=41 INDEX+OFFSET = 1+111 → hit 0x433: TAG=43 INDEX+OFFSET = 0+011 → miss
via 0 via 1
--- Set no. 0: | TAG = 42 | TAG = 43 | Set no. 1: | TAG = 41 | TAG = 42 | ---
• per la cache completamente associativa, abbiamo un solo insieme, con INDEX = log 1 = 0 b. L’OFFSET `e sempre di log 8 = 3 bit (blocco da 8 B), mentre TAG = 32 - 3 = 29 b. Per la sequenza di accesso della cache abbiamo:
0x419: TAG=0x41+1 OFFSET = 001 → miss 0x41B: TAG=0x41+1 OFFSET = 011 → hit 0x423: TAG=0x42+0 OFFSET = 011 → miss 0x428: TAG=0x42+1 OFFSET = 000 → miss 0x42B: TAG=0x41+1 OFFSET = 011 → hit 0x41E: TAG=0x41+1 OFFSET = 110 → hit 0x41F: TAG=0x41+1 OFFSET = 111 → hit 0x433: TAG=0x43+0 OFFSET = 011 → miss
---
| TAG = 41+1 | TAG = 42+0 | TAG = 42+1 | TAG = 43+0 | ---
Domanda 1
Discutere funzionamento e vantaggi di cache a pi`u livelli.
Domanda 2
Discutere la predizione dei branch nelle moderne architetture pipeline. In cosa consiste? Perch´e `e importante?
Domanda 3
Quali sono gli effetti dell’aumento della dimensione del blocco e/o della modifica del grado di associativit`a di una cache, rispetto all’hit rate della cache stessa? La risposta dipende da che localit`a esiste nel software di benchmark?
