Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

Composing memory

Wider words (more bits per word)

r/w

enable RAM/ROM RAM/ROM RAM/ROM

A[0]

A[1]

A[k-1] D[2N-1]

D[2N] D[N] D[0]

D[3N-1] D[N-1]

Vahid, Givargis - 19 -

Composing memory

Wider addressing space (more words)

r/w RAM/ROM

A[0]

A[k-1]

A[k] RAM/ROM

D[N-1] D[0]

Vahid, Givargis - 20 -

Il principio di localit à dei programmi

spaziale

Località

se l’istruzione di indirizzo i entra in esecuzione, con

|

probabilità 1 anche l’istruzione di indirizzo i di

entrerà in esecuzione (di è un intero piccolo)

Motivazione

di solito le istruzioni sono eseguite in sequenza

i salti sono relativamente rari o comunque spesso sono

polarizzati verso un ramo

Il principio di localit à dei programmi

temporale

Località

se un’istruzione entra in esecuzione al tempo t, con

|

probabilità 1 la stessa istruzione sarà rieseguita al

tempo t dt (dove dt è piccolo rispetto a t)

Motivazione

spesso le istruzioni rieseguite fanno parte di un ciclo,

la cui presenza è giustificata solo se esso viene

reiterato molte volte

se un’istruzione appartenente a un ciclo entra in

esecuzione, è molto probabile che, entro il tempo di

un’iterazione del ciclo, essa venga rieseguita

i cicli brevi generalmente sono molto più numerosi di

quelli lunghi

Il principio di localit à dei programmi

Località spaziale e temporale sono indipendenti

Se valgono entrambi, sono riassunti nel principio di

spazio-temporale

località

se l’istruzione di indirizzo i entra in esecuzione al

|

tempo t, con probabilità 1 l’istruzione di indirizzo

i di entrerà in esecuzione al tempo t dt, dove di e

dt sono piccoli rispetto a i e t, rispettivamente

La località spazio-temporale è statisticamente ben

verificata dalla maggior parte dei programmi

la maggioranza delle istruzioni appartiene a cicli

interni, con corpo sequenziale, brevi, iterati

numerose volte e operanti su dati contigui

legge empirica: 90% del tempo è speso sul 10% codice

Interpretazione del principio di localit à

Le istruzioni del programma si possono raggruppare

in “blocchi” di istruzioni consecutive

se un’istruzione (qualsiasi) di un blocco entra in

esecuzione, allora l’intero blocco di istruzioni verrà

eseguito

se un blocco (qualsiasi) entra in esecuzione, allora

entro breve tempo lo stesso blocco verrà rieseguito

I blocchi sono per esempio i “corpi” dei cicli più

interni al programma

Anche i dati (oltre alle istruzioni) possono soddisfare

al principio di località spazio-temporale

La gerarchia di memoria

La memoria viene organizzata in livelli

caratterizzati da velocità, dimensioni e costi diversi

I blocchi possono essere trasferiti da un livello

inferiore a uno superiore

Cerco di tenere i blocchi di informazione usati più di

frequente vicino alla CPU, per ottimizzare i tempi

Il dimensionamento del sistema e le politiche di

gestione derivano da analisi statistico/quantitative

delle applicazioni

L’obiettivo è fornire la sensazione di una memoria

con la velocità del primo livello e la capacità del

(dei) successivo(i)

Memory hierarchy

Registers & L1 Cache Processor

Small, very expensive, Registers 8

2 bytes

very fast

L2 Cache L1 Cache 16 bytes

2

Larger, expensive, very fast

Main memory L2 Cache 20 bytes

2

Large, inexpensive, slower Main Memory 30 bytes

2

Disk

Very large, inexpensive, slow Disk 40 bytes

2

Tape Tape

Largest, inexpensive, 40 bytes

2

sequential access

Vahid, Givargis - 21 -

Cache memory

Usually designed with SRAM

Faster but more expensive than DRAM

Usually on same chip as processor

Space limited

Faster access (1 cycle vs. several cycles)

Cache operation:

Request for main memory access (read/write)

First, check cache for copy

Cache hit: copy is in cache, quick access

Cache miss: copy not in cache, read address and

possibly its neighbors into cache

Vahid, Givargis - 22 -

Cache mapping

Far fewer number of available cache addresses

Cache mapping

Assigns main memory address to cache addresses

Determine hit or miss

Three basic techniques:

Direct mapping

Fully associative mapping

Set-associative mapping

Caches partitioned into blocks (lines) of adjacent

memory addresses

Usually 4 or 8 addresses per line

Vahid, Givargis - 23 -

Direct mapping

Main memory address divided into 3 fields

Index

Cache address

Number of bits determined by cache size

Tag

Compared with tag stored in cache at the address

indicated by the index

If tags match, check valid bit

Offset

Used to find particular word in cache line

Valid bit

Indicates whether data has been loaded from memory

Vahid, Givargis - 24 -

Direct mapping

tag index offset

valid tag data

index =

tag

offset valid data

Vahid, Givargis - 25 -

Fully associative mapping

Main memory address divided into 2 fields

Tag

Compared with all tags stored in cache simultaneously

If tags match, check valid bit

If valid bit is 1, the cache line is found

Offset

Used to find particular word in cache line

Valid bit

Indicates whether data has been loaded from memory

Vahid, Givargis - 26 -

Fully associative mapping

tag offset

valid tag data valid tag data valid tag data

= = =

tag

offset valid data

Vahid, Givargis - 27 -

Set

- associative mapping

Compromise between direct mapping and fully

associative mapping

Main memory address divided into 3 fields

Index, Offset and Tag

Same as in direct mapping

But…

Each cache address contains data and tags of 2 or

more memory address locations

Tags of a set are simultaneously compared

As in fully associative mapping

Cache with set size N called N-way set-associative

2-way, 4-way, 8-way are common

Vahid, Givargis - 28 -

Set associative mapping

tag index offset

valid tag data valid tag data valid tag data

index = = =

tag

offset valid data

Vahid, Givargis - 29 -

Replacement policy

Technique for choosing which block to replace

When fully associative cache is full

When set-associative cache’s line is full

Direct mapped cache has no choice

Random

Replace block chosen at random

LRU: Least-Recently Used

Replace block not accessed for longest time

FIFO: First-In-First-Out

Push block onto queue when accessed

Choose block to replace by popping queue

Vahid, Givargis - 30 -


PAGINE

21

PESO

236.67 KB

AUTORE

Atreyu

PUBBLICATO

+1 anno fa


DESCRIZIONE DISPENSA

La memoria viene organizzata in livelli caratterizzati da velocità, dimensioni e costi diversi. I blocchi possono essere trasferiti da un livello inferiore a uno superiore. Tenere i blocchi di informazione usati più di frequente vicino alla CPU ottimizza i tempi. Il dimensionamento del sistema e le politiche di gestione derivano da analisi statistico/quantitative delle applicazioni. L’obiettivo è fornire la sensazione di una memoria con la velocità del primo livello e la capacità del (dei) successivo(i).


DETTAGLI
Corso di laurea: Corso di laurea magistrale in ingegneria delle telecomunicazioni
SSD:
Università: L'Aquila - Univaq
A.A.: 2011-2012

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Atreyu di informazioni apprese con la frequenza delle lezioni di Sistemi embedded e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università L'Aquila - Univaq o del prof Pomante Luigi.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Sistemi embedded

Programmazione concorrente
Dispensa
Sistemi Embedded
Dispensa
SystemC
Dispensa
Real-time and embedded operating systems
Dispensa