Esempio MIPS 32 bit• Indirizzo su 32 byte • Cache ad accessi diretto • Dimensioni della cache 2n blocchi, di cui n bit usati per

l’indice • dimensione del blocco di cache 2m parole ossia 2m+2

byte • In questo caso la dimensione del tag è data da 32 – (n

+ m + 2) • Numero totale bit nella cache:

2n x (dim. blocco + dim. tag + valid bit) • Per convenzione si considera solo la dimensione del

blocco.

4KB Cache

Esercizio• Si consideri una cache con 64 blocchi di 16 byte ciascuno.

A quale numero di blocco corrisponde l’indirizzo 1200

espresso in byte?

• Blocco identificato da:

(indirizzo blocco) modulo (numero blocchi in cache)

(indirizzo blocco) = (indirizzo dato in byte) / (byte per blocco)

• Quindi l’indirizzo del blocco è 1200/16 = 75

• Blocco contente il dato è 75 modulo 64 = 11

Dimensione del blocco• Dimensioni di linea di cache molto grandi esaltano la

località spaziale e da questo punto di vista diminuiscono le

probabilità di miss

• Tuttavia avere pochi blocchi diminuisce l’efficacia nello

sfruttamento della località temporale

• Inoltre avere dei miss con blocchi grandi porta a un costo di

gestione alto (bisogna spostare molti byte)

• Quindi abbiamo un tradeoff

Tradeoff

Gestione delle miss• La Parte di Controllo deve rilevare le miss e portare in

cache i dati contenuti nella memoria indirizzata

• Hit in lettura (conseguenza di i-fetch e load) • accesso alla memoria con il massimo della velocità

• Miss in lettura (conseguenza di i-fetch e load) • La Parte di Controllo mette in stallo la CPU (cicli di attesa,

con registri interni immutati), finché la lettura del blocco (dalla memoria in cache) viene completata • Instruction cache miss: si ripete il fetch dell’istruzione • Data cache miss: si completa l’accesso al dato

dell’istruzione (load)

Gestione delle miss• Hit in scrittura (solo conseguenza di store)

• write-through: scrive sulla cache e in memoria (con buffer di scrittura)

• write-back: scrive solo sulla cache, e segnala che il blocco è stato modificato (setting del bit di Dirty)

• Miss in scrittura (solo conseguenza di store) • con politica write-back, stallo della CPU (cicli di attesa),

lettura del blocco dalla memoria in cache (write allocate), completamento dell’istruzione di store in cache

• con politica write-through, solitamente non si ricopia il blocco in cache prima di effettuare la scrittura (no write allocate) che avviene in memoria

Esempio FastMATH Intrinsity

• Split cache • 256 blocchi • 16 word per blocco • write-through e write-

back • I miss rate: 0.4 % • D miss rate: 11.4 % • Total miss rate: 3.2 %

Prestazioni delle cache• Tempo di CPU: somma di

• (Cicli di esecuzione CPU) x (periodo di clock) • (Cicli di stallo causati dalla memoria) x (periodo di

clock) • Costo di hit trascurabile • Cicli di stallo in memoria causati da cache miss

(semplificazione); somma di: • cicli di stallo in lettura • cicli di stallo in scrittura

Prestazioni delle cache• Cicli di stallo in lettura:

(# letture/programma) x (frequenza miss in lettura) x

(penalità miss in lettura) • Cicli di stallo in scrittura (write-through):

(# scritture/programma) x (frequenza miss in scrittura) x (penalità miss in scrittura) +

# stalli buffer di scrittura • Gli stalli del buffer in scrittura avvengono quando è pieno, ma

se è abbastanza profondo, hanno un costo trascurabile. • Nel write-back dobbiamo includere anche il costo di scrivere il

blocco di cache nella memoria principale

Prestazioni delle cache• Nelle cache write-through spesso si ha:

(penalità miss in lettura) = (penalità miss in scrittura) • Pari al tempo necessario per prelevare un blocco dalla

memoria principale • Cicli di stallo in scrittura:

(# accessi memoria/programma) x (frequenza miss) x (penalità miss)

= (istruzioni/programma) x (miss/istruzioni) x (penalità miss)

Esercizio• Cache istruzioni con 2% di frequenza di miss • Cache dati con 4% di frequenza di miss • Processore con 2 CPI in assenza di stalli di memoria • Penalità di miss di 100 cicli di clock • Istruzioni LOAD e STORE pari al 36% delle istruzioni I dei

programmi

• Quando sarebbe più veloce il processore se dotato di una cache perfetta ideale che non provochi mai miss?

• Cicli di miss per istruzioni = I x 2% x 100 • Cicli di miss per dati = I x 36% x 4% x 100

Esercizio• Cicli di miss per istruzioni = 2.00 x I • Cicli di miss per dati = 1.44 x I

• CPImiss = 3.44 x I • CPInormale = 2 x I • CPIstallo = 5.44 x I

TCPUstallo/TCPUideale = CPIstallo / CPInormale =

5.44 / 2 = 2.72

Cache Full Associative• Le cache ad accesso diretto sono piuttosto semplici da realizzare

• Tuttavia hanno un problema: se ho spesso bisogno di locazioni di memoria che si mappano sullo stesso blocco, ho cache miss in continuazione

• All’estremo opposto ho una cache completamente associativa • Posso mappare qualsiasi blocco in qualsiasi blocco di cache

• Il problema per le cache full associave è che devo cercare ovunque il dato (il tag è tutto l’indirizzo del blocco)

• Per effettuare la ricerca in maniera efficiente, devo farla su tutti i blocchi in parallelo

• Per questo motivo ho bisogno di n comparatori (uno per ogni blocco di cache che operino in parallelo)

• Il costo hardware è così alto che si può fare solo per piccole cache

Cache Set Associative• Le cache set associative sono un via di mezzo tra

l’accesso diretto e la completamente associativa • In pratica ogni blocco può essere mappato su n > 1

blocchi diversi (vie) • Quindi combiniamo due idee

1. associamo ciascun blocco a una linea (una degli n blocchi su cui possiamo mappare il blocco)

2. All’interno della linea effettuiamo una ricerca parallela come se avessimo una cache completamente associativa

Mappatura del blocco• In una cache ad accesso diretto il blocco viene mappato

nel blocco dato da: tag blocco = (indirizzo blocco) modulo (numero di blocchi)

• In una cache set associative la linea che contiene il blocco viene individuata da:

tag linea = (indirizzo blocco) modulo (numero di linee) • Per trovare il blocco all’interno della linea dobbiamo

confrontare il tag con tutti i tag dei blocchi della linea

Esempio

• Mappatura diretta: tag blocco = 12 modulo 8 = 4, il blocco 12 è in posizione 4 • Mappatura associativa a 2 vie: tag linea = 12 modulo 4 = 0, il blocco 12 è in

posizione 0 o 1 • Mappatura completamente associativa: il blocco 12 è in posizione 0, 1, 2, …, 11

Configurazioni per cache a 8 blocchi

Confronto: cache ad accesso diretto• Cache a 4 blocchi • Determinare il numero di miss per gli indirizzi: 0, 8, 0, 6, 8

• 5 miss per 5 accessi

Confronto: cache associativa a 2 vie

• 4 miss per 5 accessi

• Cache a 4 blocchi • Determinare il numero di miss per gli indirizzi: 0, 8, 0, 6, 8

• Rimpiazzamento del blocco usato meno di recente:

Confronto: cache full associative

• 3 miss per 5 accessi

• Cache a 4 blocchi • Determinare il numero di miss per gli indirizzi: 0, 8, 0, 6, 8

• Aumentando l’associatività: • Vantaggi: minor frequenza di miss • Svantaggi: complessità

• La scelta dipende da questo tradeoff

Vantaggi dell’associatività

Esempio cache a 4 vie

Sostituzione blocchi• Nelle cache ad accesso diretto quando ho una cache

miss sicuramente so chi sostituire (l’unico blocco in cui posso mapparmi)

• Nelle cache associative ho più scelte. Se la linea è piena chi sostituisco?

• Politiche di rimpiazzamento (eviction policies) • First In First Out (FIFO) • Least Recently Used (LRU)

Impatto delle gerarchie di memoria