Architettura degli Elaboratori (modulo II)

Architettura degli Elaboratori (modulo II) (Compito 10 Gennaio 2019)

Cognome e Nome: Matricola:

Esame completo: 2 Solo modulo II: 2 Integrazione: 2 Usare fogli separati per Modulo I e Modulo II.

Esercizio 1

Considerare il seguente sistema di memoria:

• indirizzo virtuale: 40 b, indirizzo fisico: 32 b, page size: 8 KB.

• TLB associativa a 4-vie, con 32 insiemi.

• cache associativa a 2-vie da 32 KB, con blocchi da 64 B.

Calcolare la dimensione in MB della page table, con 5 bit per ogni entry destinati a Valid, Protection, ecc.

Calcolare la dimensione in bit di ciascun entry della TLB, che contiene gli stessi 5 bit della page table.

Calcolare la dimensione della TAG della cache.

Soluzione

page size = log 8KB = log 2

= 13 b.

VPN = 40 - log 2

= 27b PPN = 32 - log 2

= 19b

2

∗ (5 + 19)b = 2

∗ 3B = 3 ∗ 128 = 384 MB INDEX della TLB = log 32 = 5 b.

TAG della TLB = VPN - INDEX = 27 - 5 = 22 b

Dimensione in b della entry della TLB = TAG + PPN + 5 bit = 22 + 5 + 19 = 46 b

# blocchi della cache = 32 KB / 64 B = 2

# set della cache = 2

/2 = 2

INDEX della cache = log n set = log 2

= 8 b OFFSET cache = log 64 = 6 b

TAG della cache = IND fisico - INDEX - OFFSET = 32 - 8 - 6 = 18 b.

Esercizio 2

Tradurre in C la seguente porzione di codice MIPS, dove $s0 e $s1 memorizzano gli indirizzi di due array di interi: int a[] e int b[]:

addi $t0, $s0, 8 lw $t1, 0($t0) sw $t1, 4($s1)

Tradurre in MIPS, passando prima dalla traduzione con if-goto e goto, la seguente funzione, rispettando le solite convenzioni di chiamata:

int copy(char a[], char b[]) { int i = 0;

while (b[i] != 0) { a[i] = b[i];

i++;

} a[i] = 0;

return i;

}

Soluzione

Traduzione da MIPS a C:

b[1] = a[2]

oppure:

*(b+1) = *(a+2)

Traduzione della funzione con if-goto e goto:

int copy(char a[], char b[]) { i = 0;

init_w:

if (b[i] == 0) goto exit_w;

a[i] = b[i];

i++;

goto init_w;

exit_w:

a[i] = 0;

return i;

}

Traduzione MIPS:

copy:

li t0, 0 init_w:

add $t1, $a1, $t0 # $t1 = &b[i]

lb $t2, 0($t1) # $t2 = b[i]

beq $t2, $0, exit_w

add $t3, $a0, $t0 # $t3 = &a[i]

sb $t2, 0($t3) # a[i] = b[i]

addi $t0, $t0, 1 j init_w exit_w:

add $t3, $a0, $t0 # $t3 = &a[i]

sb $zero, 0($t3) # a[i] = 0 ori $v0, $t0, 0

jr $ra

Esercizio 3

Si consideri il seguente programma:

loop: lw $3, a($4) sw $3, b($4) addi $4, $4, 4 bne $4, $6, loop

dove $4 ` e inizializzato a 0 e $6 a 16000.

• Disegnare il diagramma di esecuzione e calcolare il CPI nel caso di esecuzione sulla pipeline a 5 stadi vista a lezione, senza tecniche di forwarding e senza register file speciale. Si supponga inoltre che, successivamente alla bne, venga inserita una nop (funzionale al delayed branch).

• Calcolare il CPI nel caso in cui vengano introdotte tecniche di forwarding assieme al register file speciale (che scrive e legge nello stesso ciclo di clock). Si consideri che l’istruzione bne viene completata entro lo stadio ID (dove viene anticipato il confronto dei registri e il calcolo del salto).

Soluzione

Abbiamo una dipendenza tra la lw e la successiva sw sul registro $3. Inoltre abbiamo una dipendenza tra la addi e la successiva bne su $4. Otteniamo quindi il seguente diagramma esecuzione:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

--- lw | IF | ID | EX | ME | WB |

--- sw | IF | ID |<ID>|<ID>|<ID>| EX | ME | WB |

--- addi | IF |<IF>|<IF>|<IF>| ID | EX | ME | WB |

--- bne | IF | ID |<ID>|<ID>|<ID>| EX | ME | WB |

--- nop | IF |<IF>|<IF>|<IF>| ID | EX | ME | WB |

---

lw | IF | ID | EX | ME | WB |

--- ...

Ogni loop richiede quindi 11 cicli di clock. Poich` e vengono eseguiti 16000 / 4 = 4000 volte, otteniamo un numero totale di cicli di 11 · 4000 = 44000 (i 3 cicli di svuotamento della diventano irrilevanti rispetto ai 44000 necessari per il loop). Poich´ e le istruzioni sono 4 * 4000 = 16000 otteniamo CPI = 44000 / 16000 = 2.75.

Purtroppo il forwarding non risolve tutti gli stalli:

1 2 3 4 5 6 7 8

--- lw | IF | ID | EX | ME | WB |

--- sw | IF | ID |<ID>| EX | ME | WB |

---

addi | IF |<IF>| ID | EX | ME | WB |

--- bne | IF | ID |<ID>| ME | WB |

---

nop | IF |<IF>| ID | EX | ME | WB |

---

lw | IF | ID | EX | ME | WB |

--- ...

In questo caso un loop richiede 7 cicli di clock. Non considerando il caricamento otteniamo un CPI = 7/4 = 1.75.

Domande

1. Perch´ e ` e necessaria la TLB nella traduzione da indirizzo virtuale a fisico?

2. Discutere la programmazione dell’I/O tramite DMA, funzionamento e vantaggi.

3. Come pu` o essere modellato l’accesso al disco? La banda misurata del disco (banda reale di trasferimento dei dati) dipende

solo dalle caratteristiche hardware del disco e del sottosistema di I/O?