Calcolo prestazioni cache (1)

Consideriamo gcc:– miss rate x istruzioni = 2%– miss rate x dati = 4%– frequenza di letture e scritture=36%

Consideriamo inoltre un sistema con:– CPU: Clock=3Ghz, CPIideale=1 (in assenza di stalli per accesso a RAM /

100% HIT RATIO)– RAM: DDR 266 MHZ (2x133Mhz, 2 parole x ciclo di clock)

Calcoliamo:Tempo di accesso alla RAM= 1000ns/133 cicli/ns= 7,51 ns (per la primaparola)Miss penalty= 7,51 ns/ 0,3 cicli di clock/ns=25 cicli di clock

Sia I il numero totale di istruzioni del programma:cicli di stallo complessivi per i miss sulle istruzioni: 2% * 25* I = 0,5 * Icicli di stallo complessivi per i miss sui dati: 4% * 25* 36% *I=0,36 * ICicli di stallo complessivi per miss: (0,25+0,18)*I=0,86CPIeffettivo=CPIideale+cicli di stallo per miss=1,86

Differenza percentuale tra CPIeffettivo e CPIideale

(CPIeffettivo – CPIideale)/= CPIideale = 86%

E ora: Overclocking! (*)

Supponiamo di poter portare il clock della CPU a 6Ghz (…e muniamoci di unabuon dissipatore!)

Poiché il tempo di accesso alla RAM rimane costante, la penalità di MissraddoppiaMiss penalty= 2 * Miss Penalty con clock dimezzato =50 cicli di clock

Quindi i cicli di stallo complessivi per miss raddoppiano:0,86*2= 1,72CPIeffettivo=CPIideale+cicli di stallo per miss=2,72

Tempo di esecuzione di un programma con I istruzioni su un processore di cui ènoto il tempo di clock:

I*CPI*TEMPO DI CLOCKTempo di esecuzione a 3GHZ / Tempo di esecuzione a 6 GHZ == (I*CPI3 GHZ*TEMPO CLOCK 3GHZ) / (I*CPI 6 GHZ*TEMPO CLOCK 6GHZ) == (I*CPI 3 GHZ*TEMPO DI CLOCK 3GHZ) / (I*CPI 6 GHZ*1/2 * TEMPO CLOCK

3GHZ) == CPI A 3 GHZ/ (CPI A 6 GHZ* 0.5) = 1,86 / (2,72 * 0,5) = 66%

Quindi raddoppiando la velocità del processore, il tempo di esecuzione non è sceso al 50% bensì al 66%

I Limiti dell’indirizzamento fisico

CPU Memoria

A0-A31 A0-A31

D0-D31 D0-D31

“Indirizzo fisico” delle lcoazioni di memoria

Dati e istruzioni

Tutti i programmi condividono un solospazio di indirizzi:

Lo spazio di indirizzi fisico

Non ci sono modi di limitare gli accessialle risorse del sistema

I programmi in linguaggio macchina devonoconoscere l’organizzazione della CPU

Soluzione: indirizzi virtuali

CPU Memoria

A0-A31 A0-A31

D0-D31 D0-D31

Dati e istruzioni

I programmi sono eseguti in uno spaziodi indirizzi virtuale

Il sistema operativo gestiscela traduzione dell’indirizzo

da indirizzo virtuale a indirizzo fisico

“Inidirizzo fisico”

Traduzioneindirizzo

Virtual Physical

“Indirizzo Virtuale”

La traduzione è fatta in hardware e l’hardwaresupporta altre caratteristiche desiderabili:

Protezione, Condivisione ...

Memoria Virtuale

La memoria principale è come una cache per i dispositivi dimemorizzazione secondari (dischi)

Vantaggi:• illusione di disporre di un quantitativo superiore di mem.

fisica• Rilocazione dei programmi• Protezione dei singoli processi (spazi di indirizzam. separati)

Physical addresses

Disk addresses

Virtual addresses

Address translation

Disco

Memoriaprincipale

SpazioIndirizzi

Rilocazione o Allocazione Dinamica

In un sistema multi-utente o multi-applicazione per trasferire datitra memoria principale e secondaria si usano blocchi didimensione fissa detti PAGINE :

• Il programmatore o il compilatore specificano gli indirizzirelativi all’interno di singoli blocchi di programma (IndirizzoVIRTUALE)

• Il sistema operativo definisce in fase di esecuzione, lelocazioni nelle quali il singolo blocco viene posto (IndirizzoFISICO):

• E’ necessario porre in corrispondenza gli indirizzi virtualiusati da un programma con i diversi indirizzi fisici PRIMA chequesti vengano usati per indirizzare la memoria

• La Tabella delle Pagine contiene informazioni relative a:• Indirizzo fisico.• Presenza in memoria.• Se modificato da quando in memoria.• Diritti di accesso

I 4 stadi della metamorfosi di un programma…

… e delle relative modalità di indirizzamento:

RELATIVO

Gli albori della memoria virtuale: OVERLAY

In principio se un programma eccedeva le dimensione della memoriafisica, il programmatore doveva direttamente gestire lo spostamentodei dati dalla memoria secondaria alla memoria principale.

1) Identificazione delle parti mutualmente esclusive che a run-timevenivano sovrascritte (overlay=sovrapposte).

2) Tali parti venivano caricate e scaricate sotto il diretto controllo delprogramma.

3) Occorreva accertarsi che un il programma non cercasse mai diaccedere ad un overlay non caricato e che gli overlay noneccedessero mai la dimensione della memoria fisica

Contro:Notevole carico sui programmatori (meccanismi di gestione moltocomplessi + necessità di disporre di implementazioni efficienti pernon penalizzare le performance del sistema)

Traduzione degli indirizzi con la tavola delle pagine

Una macchina disolito supportapagine di date

dimensioni(MIPS R4000):

Spazio indirizzifisico

Una posizione nella tavola delle pagine contiene l’indirizzo fisico della pagina corrispondente e altre informazioni utili: presenza in

memoria, se modificato da quando in memoria. diritti di accesso

Lo spazio virtuale è diviso inblocchi di memoria detti

PAGINEframeframe

frame

frame

Una pagina di memoria èspecificata da un indirizzo virtuale

indirizzovirtuale

Tavola dellePagine

)

SO gestisce la tavola

Velocizzare la traduzione degli indirizzi

Problema: se la tavola delle pagine risiede in memoria leprestazioni sarebbero inaccettabili

Soluzione: Una cache per le traduzioni degli indirizzi: TLB,translation lookaside buffer: ciascun blocco del TLB contienel’indirizzo del page frame (calcolato a partire dal page tableregister e dall’offset presente nella page table in ram)associato ad una data pagina virtuale

Valori tipici per il TLB:•Dimensione del TLB: 32 - 4096 elementi

•Dimensione del blocco: 1-2 elementi della page table.

•Tempo di HIT: 0,5 – 1 ciclo

•Penalità di Miss: 10-30 cicli

•Frequenza di Miss: 0,01% - 1%

NOTA: la frequenza di miss è molto bassa perché abbiamo una fortelocalità spaziale e temporale per gli indirizzi nella stessa pagina!

V=0 indica che lapagina o è su disco o

non è allocatai diritti di accesso

limitano ladisponibilità della

pagina al programma

In questo caso paginefisiche e virtuali hannola stessa dimensione

Traduzione degli indirizzi con il TLB

TLB

Tavoa dellepagine

2

0

1

3

indirizzo virtuale

page off

2frame page

250

indirizzo fisico

page off

Cache TLB

for ASID

Indirizzofisico

Page faults

Se i dati non sono in memoria principale, occorre recuperarli dal disco.

Enorme penalità di miss (milioni di cicli), il cui costo è dovuto in granparte al prelievo della prima parola (miss obbligaotri):

– le pagine sono scelte sufficientemente grandi (esempio da 4KB)

– ridurre i page faults è importante:

• collocazione completamente associativa

• Implementazione di politiche di gestione complesse (LRU)

– Usare il write-through è troppo costoso così si usa il writeback(scrittura di una pagina per volta + dirty bit)

3 2 1 011 10 9 815 14 13 1231 30 29 28 27

Page offsetVirtual page number

Virtual address

3 2 1 011 10 9 815 14 13 1229 28 27

Page offsetPhysical page number

Physical address

Translation

2^32 ind.virtuali (4 Gb)

2^18 page frames (1 Gb)

Page Faults

Il sistema operativo tiene traccia di quali processi e quali indirizzi virtualiusino una data pagina fisica.

Se le pagine fisiche sono esaurite, in caso di page fault, occorresostituire qualche pagina (swap out) in base ad un criterio cheminimizzi la possibilità di dover accedere a quella pagina di lì a breve:LRU.Approssimazione di LRU tramite l’uso di un bit di riferimento settatoad uno ogni volta che si accede alla pagina e periodicamenteresettato.

Quando la politica di gestione della gerarchia non è efficiente siverificano troppi page faults, si ha il fenomeno di Thrashing:

La CPU spende il proprio tempo ad allocare e disallocare aree di memoriasenza più svolgere lavoro utile.

CAUSA:cattivo dimensionamento della memoria rispetto ai dati utilizzati dalprogramma che opera sul sistema.

TLB e CACHE nella DECStation3100

• Cache acorrispondenzadiretta

• TLB completamenteassociativo.

• Cache indicizzatatramite indirizzifisici, per cui, primadi accedervi, èsempre necessarioutilizzare il TLB.

• Speciale gruppo diistruzioni usato dalSO per caricarelinee del TLB

• Elemento darimpiazzare nel TLBscelto casualmente.

TLB e cache

Yes

Deliver datato the CPU

Write?

Try to read datafrom cache

Write data into cache,update the tag, and put

the data and the addressinto the write buffer

Cache hit?Cache miss stall

TLB hit?

TLB access

Virtual address

TLB missexception

No

YesNo

YesNo

Write accessbit on?

YesNo

Write protectionexception

Physical address

Meccanismi di protezione

La memoria virtuale permette che più processicondividano (e riusino) la stessa memoria principale

I processi in esecuzione possono eseguire operazioni discrittura in memoria

PROBLEMA:occorre garantire che non sia possibile per un processo

leggere o scrivere all’interno dello spazio diindirizzamento di un altro processo o del sistemaoperativo

Se così non fosse è possibile per un processo accederee modificare i dati di un altro programma e delsistema operativo

Meccanismi di protezione

La memoria virtuale permette che più processi condividano (e riusino) lastessa memoria principale

PROBLEMA:occorre garantire che non sia possibile per un processo leggere o scrivere

all’interno dello spazio di indirizzamento di un altro processo o delsistema operativo:

NOTA: Ciascun processo ha la propria page table, per cui è sufficiente che:1) il SO deve impedire che un processo possa cambiare il riferimento alla

propria page table.2) Il SO deve poter modificare le tabelle delle pagine.

SOLUZIONE:1) Porre le page tables nello spazio di indirizzamento del SO.2) In caso di richiesta di condivisione di pagine tra processi è compito del

sistema operativo effettuare le necessarie operazioni sulle rispettivepage tables.

Meccanismi di protezione

Il problema si risolve con il supporto dell’hardware:1) (Almeno) 2 modi di funzionamento (modo utente/modo Kernel - o

anche SO) che indicano se è in esecuzione un processo utente oil SO.

2) Impedire ad un processo eseguito in modo utente di accedere adalcune informazioni di stato della CPU (le relative operazionisono eseguibili solo in modo kernel):1) Bit modo utente/modo kernel2) Page table register3) TLB

3) Permettere il passaggio sicuro da modo utente a modo kernel eviceversa:• System Call: Il meccanismo è simile a quello delle

interruzioni hw (context switch), in questo caso si parla diinterruzioni software.

Meccanismi di protezione

Bisogna garantire la sicurezza degli accessi:

PROBLEMA:• In caso di cambio di processo o di contesto, in presenza di

TLB, non è sufficiente cambiare il puntatore alla pagetable.

• Occorre invalidare il TLB così da forzarlo a caricare letraduzioni degli indirizzi del nuovo processo.

• NOTA: Se la frequenza di cambio di contesto è troppo altale prestazioni si deteriorano!

Problemi (e soluzioni) analoghe possono sorgere con lacache, nel caso in cui essa sia indicizzata tramite indirizzivirtuali.

Paginazione vs Segmentazione

Oggi si usano le pagine..

In passato era diffuso uno schema con blocchi didimensioni variabili, detti SEGMENTI:

– insieme di bytes contigui e posti in relazionelogica, definiti dal compilatore a partire daimoduli o blocchi dei programmi di alto livello.

– Il segmento è il blocco elementare che vienetrasferito fra le gerarchie

Segmentazione

VANTAGGI• La struttura del segmento corrisponde alla naturalesuddivisione dei dati e dei programmi.• E' agevole gestire meccanismi di separazione e di protezioneper i dati dei singoli utenti.

SVANTAGGII segmenti hanno dimensioni fisiche diverse, quindi:

• allocazione complessa• frammentazione (esterna)• necessità di ricompattazione della memoria.

CAUSE PER IL MANCATO UTILIZZO DELLO SPAZIO• Regioni vuote. Frammenti di memoria non utilizzati.• Regioni occupate dal sistema di gestione.• Regioni occupate da informazioni che non vengono utilizzate.

Segmentazione: frammentazione

La frammentazione esterna riduce l'utilizzazione della memoria quandorisulta necessario disporre i dati dei segmenti in celle di memoriacontigue. Lo stesso problema si verificava sui sistemi di memoriasecondaria (dischi) quando i ogni file doveva essere memorizzato insegmenti adiacenti.

S1

S2

S3

S4

Memoria libera

Segmentazione: Ricompattazione

La memoria non può essere sfruttata completamente.

Tra le aree occupate rimangono zone di piccola dimensione nelle qualinon possono essere allocati segmenti.

Per migliorare l'utilizzazione della memoria: ricompattazione!

S1

S2

S3

S4

S1

S2

S3

S4