Sistemas de Memória - INSTITUTO DE COMPUTAÇÃOpannain/mc722/aulas/arq_hp7.pdf · endereçamento tempo freqüência de acesso em ∆T espaço de endereçamento Temporal Espacial

1998 Morgan Kaufmann PublishersPaulo C. Centoducatte Ch7a-1

Sistemas de Memória


• SRAM:

– valor armazenado em um par de portas inversoras

– mais rápida porém usa mais espaço do que DRAM (4 a 6 transistores)

• DRAM:

– valor armazenado como carga de um capacitor (deve ser feito refresh)

– menor porém mais lenta do que SRAM (fator de 5 a 10)

Memórias: Review

data data

sel

Capacitor

Pass transistor

Word line

Bit line


• Usuários querem memórias grandes e rápidasSRAM access times: 2 - 25ns; custo de $100 a $250 por Mbyte.DRAM access times: 60-120ns; custo de $5 a $10 por Mbyte.Disk access times: 10 a 20 milhões de ns; custo de $.10 a $.20 por Mbyte.

• Solução: hierarquia de memória

Explorando Hierarquia de Memória

1997

CPU

Level n

Level 2

Level 1

Levels in thememory hierarchy

Increasing distancefromthe CPU in

access time

Size of the memory at each level


Custo(ci $/bit)

maior

menor

Hierarquia de Memória

CPU

Memória

Memória

Memória

Velocidade

rápida

lenta

Tamanho(Si)

menor

maior

b1

b2

b3


Hierarquia de memória (custo e velocidade)

• Custo médio do sistema ($/bit)

S1 C1 + S2 23 + …… + Sn Cn

S1 + S2 + …… + Sn

• Objetivos do sistema

– Custo médio ≈≈≈≈ custo do nível mais barato (disco)

– Velocidade do sistema ≈≈≈≈ velocidade do mais rápido (cache)

• Hoje, assumindo disco 40 GB e memória de 256 MB

– Calcular o custo médio por bit


Localidade

• Principio que torna possível o uso de hierarquia de memória

• um programa acessa uma porção relativamente pequena do espaço endereçável em um instante qualquer.

• Localidade temporal: Se um item é referenciado, ele tende a ser referenciado novamente.

• Exemplo �� loops ( instruções e dados).

• Localidade Espacial: Se um item é referenciado, itens cujos endereços são próximos a este, tendem a ser referenciados também.

• Exemplo �� acesso a dados de um array.


Localidade

• Bloco �� mínima unidade de informação que pode ou não estar presente em dois níveis de hierarquia de memória.

• Hit �� se o dado acessado aparece em algum bloco no nível superior.

• Miss �� se o dado acessado não aparece em algum bloco do nível superior.

• Hit ratio (hit rate)�� razão hits pelo número total de acessos ao nível superior.

• Miss ratio (miss rate)�� razão de misses pelo número total de acessos ao nível superior �� miss ratio = 1 – hit ratio.

• Hit time �� tempo de acesso ao nível superior da hierarquia de memória, que inclui o tempo necessário para saber se no acesso ocorrerá um hit ou um miss.

• Miss penalty �� tempo para recolocar um bloco no nível superior e enviá-lo ao processador, quando ocorrer um miss. O maior componente do miss penalty é o tempo de acesso ao nível imediatamente inferior da hierarquia de memória.


Princípio da localidade

espaço deendereçamento

tempo

freqüência de

acesso em ∆T

espaço de endereçamento

Temporal

Espacial


Visão em dois níveis

Processador

Transferência de dados (bloco)

Localidade temporal:guardar os mais usados

Localidade espacial:transf. em blocos em vez de palavras


• Memória Cache �� nível da hierarquia entre CPU e Memória Principal ou qualquer espaço de armazenamento usado para tirar vantagem da localidade de acesso.

• Supondo uma cache simples onde um bloco corresponde a uma palavra e o processador acessa a uma palavra.

• Supor um bloco Xn que inicialmente não esteja na cache:


Cache

a. Before the reference to Xn

X3

Xn – 1

Xn – 2

X1

X4

b. After the reference to Xn

X3

Xn – 1

Xn – 2

X1

X4

Xn

X2X2

Referência à posição Xn


• Duas perguntas no acesso à cache:– Como saber se o dado está na cache?– Se estiver, como encontra-lo?

• Se cada palavra tiver um lugar na cache �� saberemos como encontra-la.

• A maneira mais simples de assinalar uma posição da cache para uma palavra de memória é através de seu endereço na memória �� direct mapped

– (Endereço do bloco) mod (Número de blocos na cache)

• Políticas: – mapeamento de endereços entre cache e memória

– escrita: como fazer a consistência de dados entre cache e memória

– substituição: qual bloco descartar da cache

Cache


• Políticas:

– mapeamento de endereços entre cache e memória

– escrita: como fazer a consistência de dados entre cache e memória

– substituição: qual bloco descartar da cache

Cache


• Mapping: address is modulo the number of blocks in the cache

Direct Mapped Cache

00001 00101 01001 01101 10001 10101 11001 11101

00

0

Cache

Memory

001

01

001

11

00

101

110

11

1

cache: 8 posições3 bits de endereço

memória: 32 posições5 bits de endereço

Index V Tag Data

000

001

010

011

100

101

110

111

N

N

N

N

N

N

N

N

Index V Tag Data

000

001

010

011

100

101

110

111

N

N

N

N

N

N

Y

N

10 M(10110)

Index V Tag Data

000

001

010

011

100

101

110

111

N

N

Y

N

N

N

Y

N

10 M(10110)

11 M(11010)

Index V Tag Data

000

001

010

011

100

101

110

111

Y

N

Y

N

N

N

Y

N

10 M(10110)

11 M(11010)

10 M(10000)

Index V Tag Data

000

001

010

011

100

101

110

111

Y

N

Y

Y

N

N

Y

N

10 M(10110)

11 M(11010)

10 M(10000)

00 M(00011)

Preenchimento da cache a cada miss

end10 end2 endcache Hit

22 10 110 110

26 11 010 010

22 10 110 110 H

26 11 010 010 H

16 10 000 000

3 00 011 011

16 10 000 000 H

18 10 010 010


Direct Mapped CacheAddress (showing bit positions)

20 10

Byteoffset

Valid Tag DataIndex

0

1

2

1021

1022

1023

Tag

Index

Hit Data

20 32

31 30 13 12 11 2 1 0

• mapeamento direto

• byte offset:

• só para acesso a byte

• largura da cache:v+tag+dado

• cache de 2n linhas:

• índice de n bits

• linha da cache: 1+(30-n)+32v tag dado

• tamanho da cache= 2n*(63-n)


Via de dados com pipeline

• Data memory = cache de dados• Instruction memory = cache de instruções• Arquitetura

– de Harvard

– ou Harvard modificada

• Miss? semelhante ao stall– dados: congela o pipeline– instrução:

• quem já entrou prossegue• inserir “bolhas” nos estágios seguintes• esperar pelo hit

• enquanto instrução não é lida, manter endereço original (PC-4)

IM CPU DM

Harvard

IM

CPU

DM

Harvard modificada

Memória


Tamanho da Cache em bits

• Número de bits necessários para uma cache é função do tamanho da cache e do tamanho do endereço ( dados + tags)

• Número de bits de uma cache

• Endereço de 32 bits, cache com mapeamento direto de 2n

words com blocos de uma palavra (4 bytes) �� tag de 32 –(n + 2).

– 2 bits usados para offset do byte e n para o índice. O número total de bits da cache �� 2n X (32 + (32 – n –2) + 1) = 2n X (63 – n).


• Exemplo: Quantos bits são necessários para uma cache com mapeamento direto com 64KB de capacidade para dados e bloco de uma palavra, assumindo endereço de 32-bit?

Solução:

64KB �� 16K palavras �� 214 palavras �� 214 blocos

Cada bloco tem 32 bits de dados mais o tag (32 – 14 – 2 = 16) mais o bit de validade

Total de bits da cache 214 X ( 32 + 16+ 1) = 784 Kbits = 98 KB

Para esta cache, temos um overhead de 1.5, devido aos tag e aos bits de validade.


Tratamento de Cache Misses

• Quando a unidade de controle detecta um miss, ela busca o dado da memória. Se detecta um hit, continua o processamento como se nada tivesse acontecido.

• Mudança do datapath (cap. 5 e cap. 6) �� substituir as memórias por caches e alterar o controle para quando ocorrer miss.

• Alteração do controle �� atrasar ( stall semelhante ao stall do pipeline �� diferença que para todas as unidades do pipeline) da CPU, congelando o conteúdo de todos os registradores. Um controlador separado trata o miss, lendo o dado da memória.


Etapas de um cache miss de uma instrução

• Enviar o PC original ( PC corrente – 4) para a memória

• Fazer a leitura da memória e esperar o conteúdo

• Escrever na cache o dado vindo da memória, escrevendo os bits mais significativos do endereço (da ULA) no campo de tag e setando o bit de validade.

• Reiniciar a execução da instrução.


Etapas de um cache miss de dados

• stall no processador até a memória enviar o dado.


The caches in the DECStation 3100

Address (showing bit positions)

16 14 Byteoffset

Valid Tag Data

Hit Data

16 32

16Kentries

16 bits 32 bits

31 30 17 16 15 5 4321 0


Etapas para uma leitura na cache (de dados ou de instruções)

• Enviar o endereço para a cache (vem do PC para leitura de instruções ou da ULA para leitura de dados)

• Se existir o sinal hit, significa que a palavra desejada estádisponível na linha de dados. Se existir o sinal de miss o endereço é enviado à memória principal, e quando o dado chega, é escrito na cache.


Etapas para uma escrita na cache

• Escrita �� na escrita de uma instrução de store �� o dado tem que ser escrito na cache �� valores diferentes entre cache e memória principal �� inconsistência �� escrever também na memória principal �� write-through.

• Performance com write-through �� gcc tem 13% de instruções de store. Na DECStation 3100 a CPI para store é 1.2 e gasta 10 ciclos a cada escrita �� nova CPI = 1.2+13% X 10 = 2.5 �� reduz o desempenho por um fator maior que 2 �� solução possível ��write buffer.

• Outro esquema de atualização da memória �� write back �� a memória só é atualizada quando o bloco da cache que sofreu modificação for substituído por outro.

• Write miss �� dado escrito na cache pelo processador �� não háleitura da memória principal �� atualizar tag.


Localidade Espacial: Aumentando o Tamanho do Bloco

Address (showing bit positions)

16 12 Byteoffset

V Tag Data

Hit Data

16 32

4Kentries

16 bits 128 bits

Mux

32 32 32

2

32

Block offsetIndex

Tag

31 16 15 4 32 1 0


• Read hits– É o desejado

• Read misses– stall a CPU, fetch block da memória, preencher a cache

• Write hits:– atualiza o dado na cache e na memória (write-through)– atualiza o dado somente na cache (write-back the cache later)

• também conhecida como copy-back• dirty bit

• Write misses:– ler o block e coloca-lo na cache, então escrever o dado

• Comparação– desempenho: write-back

– confiabilidade: write-through– proc. paralelo: write-through

Hits vs. Misses (política de atualização ou escrita)


Largura da Comunicação Mem - Cache – CPU

dezati

CPU

Cache

Bus

Memory

a.One-word-wimemoryorgani on

CPU

Bus

b. Widememoryorganization

Memory

Multiplexor

Cache

CPU

Cache

Bus

Memorybank1

Memorybank2

Memorybank3

Memorybank0

c. Interleavedmemoryorganization

• Supor:

• 1 clock para enviar endereço• 15 clocks para ler DRAM• 1 clock para enviar uma palavra de volta

• linha da cache com 4 palavras


Cálculo do miss penalty vs largura comunicação

• Uma palavra de largura na memória:– 1 + 4*15 + 4*1 = 65 ciclos (miss penalty)– Bytes / ciclo para um miss: 4 * 4 / 65 = 0,25 B/ck

• Duas palavras de largura na memória:– 1 + 2*15 + 2*1 = 33 ciclos– Bytes / ciclo para um miss: 4 * 4 / 33 = 0,48 B/ck

• Quatro palavras de largura na memória:– 1 + 1*15 + 1*1 = 17 ciclos– Bytes / ciclo para um miss: 4 * 4 / 17 = 0,94 B/ck– Custo: multiplexador de 128 bits de largura e atraso

• Tudo com uma palavra de largura mas 4 bancos de memória interleaved (intercalada)– Tempo de leitura das memórias é paralelizado (ou superpostos)

• Mais comum:endereço bits mais significativos– 1 + 1*15 + 4*1 = 20 ciclos– Bytes / ciclo para um miss: 4 * 4 / 20 = 0,8 B/ck– funciona bem também em escrita (4 escritas simultâneas):

• indicado para caches com write through


Cálculo aproximado da eficiência do sistema

• objetivo: – tempo de acesso médio = estágio mais rápido

• supor dois níveis:– tA1 = tempo de acesso a M1– tA2 = tempo de acesso a M2 (M2+miss penalty)– tA = tempo médio de acesso do sistema– r = tA1 / tA2

– e = eficiência do sistema = tA1 / tA

tA = H * tA1 + (1-H) * tA2

tA / tA1 = H + (1-H) * r = 1/e

e = 1 / [ r + H * (1-r) ]

M1

M2

tA1

tA2

0%

20%

40%

60%

80%

100%

0% 20% 40% 60% 80% 100%

r=2

r=10

r=100

e

H


Medida e Melhoria de desempenho de Cache

• Modelo simplificado de Desempenho– execution time = (execution cycles + stall cycles) ×××× cycle time

stall cycles = RD + WR stalls

– RD stall cycles = # of RDs ×××× RD miss ratio ×××× RD miss penalty

– WR stall cycles = # of WRs ×××× WR miss ratio ×××× WR miss penalty (mais complicado do que isto)

• Melhoria de desempenho

– Redução da probabilidade de de dois blocos diferentes serem alocados na mesma linha de cache.

– Redução do miss pela adição de mais um nível de cache na hierarquia (multilevel caching).

O que acontece se aumentarmos

o tamnho do bloco?

Use split caches because there is more spatial locality in code:

Miss rate vs block size

1 KB

8 KB

16 KB

64 KB

256 KB

256

40%

35%

30%

25%

20%

15%

10%

5%

0%

Mis

sra

te

64164

Block size (bytes)

ProgramBlock size in

wordsInstruction miss rate

Data miss rate

Effective combined miss rate

gcc 1 6.1% 2.1% 5.4%

4 2.0% 1.7% 1.9%

spice 1 1.2% 1.3% 1.2%

4 0.3% 0.6% 0.4%

pior

menos local. espacial

pior

• fragmentação interna• menos blocos• miss penalty


Exemplo pag 565 - 566

• gcc: instruction miss ratio = 2%; data cache miss rate = 4%• CPI = 2 (sem stalls de mem); miss penalty = 40 ciclos• Instructions misses cycles = I * 2% * 40 = 0.8 I• Sabendo que lw+sw= 36%

– data miss cycles = I * 36% * 4% * 40 = 0.58 I• N. de stalls de mem = 0.8 I + 0.58 I = 1.38 I

– CPI total = 2 + 1.38 = 3.38• Relação de velocidades com ou sem mem stalls = rel de CPIs

– 3.38 / 2 = 1.69

• Se melhorássemos a arquitetura (CPI) sem afetar a memória– CPI = 1– relação = 2.38 / 1 = 2.38– efeito negativo da memória aumenta (Lei de Amdhal)

• ver exemplo da pag 567: aumento do clock tem efeito semelhante


Reduzindo o miss ratio com Associatividade

1

2Tag

Data

Block # 0 1 2 3 4 5 6 7

Search

Direct mapped

1

2Tag

Data

Set # 0 1 2 3

Search

Set associative

1

2Tag

Data

Search

Fully associative

memory block position =

(Block number) mod (Number of cache blocks)

set que contém o memory block =

(Block number) mod (Number of sets in the cache)


Reduzindo o miss ratio com Associatividade

Tag Data Tag Data Tag Data Tag Data Tag Data Tag Data Tag Data Tag Data

Eight-wayset associative (fully associative)

Tag Data Tag Data Tag Data Tag Data

Four-way set associative

Set

0

1

Tag Data

One-wayset associative(direct mapped)

Block

0

7

1

2

3

4

5

6

Tag Data

Two-way set associative

Set

0

1

2

3

Tag Data


Exemplo

• Existem 3 pequenas caches de 4 blocos de uma palavra. Uma é fully associative, a segunda two-way set associative e a terceira é direct mapped. Encontre o número de misses para cada uma, dado a seguinte seqüência de endereços de blocos: 0, 8, 0, 6, 8

• Direct mapped

Block address Cache block

0 0 mod 4 = 0

6 6 mod 4 = 2

8 8 mod 4 = 0


Exemplo

• Direct mapped

– 5 misses

Conteúdo do bloco da cache após areferência

Endereço dobloco dememóriaacessado

Hit ormiss

0 1 2 3

0 miss mem[0]

8 miss mem[8]

0 miss mem[0]

6 miss mem[0] mem[6]



Exemplo

• 2-way set associative

– 4 missesBlock address Cache set

0 0 mod 2 = 0

6 6 mod 2 = 0

8 8 mod 2 = 0



Hit ormiss

Set 0 Set 0 Set 1 Set 1

0 miss mem[0]


0 hit mem[0] mem[8]




Exemplo

• Fully associative

– 3 misses



Hit ormiss

bloco 0 bloco 1 bloco 2 bloco 3

0 miss mem[0]


0 hit mem[0] mem[8]

6 miss mem[0] mem[8] mem[6]

8 hit mem[0] mem[8] mem[6]


Uma implementaçãoAddress

22 8

V TagIndex

0

1

2

253

254

255

Data V Tag Data V Tag Data V Tag Data

3222

4-to-1 multiplexor

Hit Data

123891011123031 0 Tag Index Block Offset


Desempenho

0%

3%

6%

9%

12%

15%

Eight-wayFour-wayTwo-wayOne-way

1 KB

2 KB

4 KB

8 KB

Mis

sra

te

Associativity 16 KB

32 KB

64 KB

128 KB


Política de substituição

• Qual item descartar?

– FIFO

– LRU– Aleatoriamente

• ver seção 7.5


Reduzindo o miss penalty com multilevel caches

• Add a second level cache:– often primary cache is on the same chip as the processor

– use SRAMs to add another cache above primary memory (DRAM)– miss penalty goes down if data is in 2nd level cache

• Example (pag 576):– CPI of 1.0 on a 500MHz machine with a 5% miss rate, 200ns DRAM access

– Add 2nd level cache with 20ns access time and miss rate to 2%

– miss penalty (só L1) = 200ns/período = 100 ciclos

– CPI (só L1)= CPIbase + clocks perdidos = 1 + 5% * 100 = 6

– miss penalty (L2)= 20ns/período = 10 ciclos

– CPI (L1 e L2)= 1 + stalls L1 + stalls L2 = 1 + 5% * 10 + 2% * 100 = 3.5– ganho do sistema em velocidade com L2 = 6.0 / 3.5 = 1.7

• Using multilevel caches:– try and optimize the hit time on the 1st level cache– try and optimize the miss rate on the 2nd level cache


Memória Virtual


Virtual Memory

• Main memory can act as a cache for the secondary storage (disk)

• Advantages:– illusion of having more physical memory (programa independente da

configuração do hardware)– program relocation – protection (address space)

Physical addresses

Disk addresses

Virtual addresses

Address translation


Pages: virtual memory blocks

• Page faults: the data is not in memory, retrieve it from disk– huge miss penalty, thus pages should be fairly large (e.g., 4KB)

– reducing page faults is important (LRU is worth the price)– can handle the faults in software instead of hardware– using write-through is too expensive so we use write-back

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

12 bits: 4 KBVPN: 20 bits

1M page4 GB

PPN: 18 bits 256 K page1 GB


Page Tables

Physical memory

Disk storage

Valid

1

1

1

1

0

1

1

0

1

1

0

1

Page table

Virtual pagenumber

Physical page ordisk address


Page Tables

Page offsetVirtual page number

Virtual address

Page offsetPhysical page number

Physical address

Physical page numberValid

If 0 then page is notpresent in memory

Page table register

Pagetable

20 12

18

31 30 29 28 27 15 14 13 12 11 10 9 8 3 2 1 0

29 28 27 15 14 13 12 11 10 9 8 3 2 1 0

• uma PT por processo• estado:

• PT• PC• registradores


Política de substituição e tamanho da PT

• Se page fault (bit válido= 0)

– sistema operacional executa a carga da página• Para minimizar page faults, política de substituição mais usada: LRU

• Tamanho da PT (p/ end 32 bits, pag de 4KB, 4B / linha da PT)– número de linhas: 232 / 212 = 220

– tamanho da PT = 4 MB

– 1 PT por programa ativo !!– para reduzir área dedicada para PT: registradores de limite

superior e inferior

• PT também são paginados


TLB: translation lookaside buffer

Valid

1

1

1

1

0

1

1

0

1

1

0

1

Page table

Physical pageaddressValid

TLB

1

1

1

1

0

1

TagVirtual page

number

Physical pageor disk address

Physical memory

Disk storage

Typical values

- TLB size: 32 - 4,096 entries

- Block size: 1 - 2 page table entries- Hit time: 0.5 - 1 clock cycle

- Miss penalty: 10 - 30 clock cycle- Miss rate: 0.01% - 1%

- map direto ou fully associativo


TLBsand cacheDEC 3100

Valid Tag Data

Page offset

Pageoffset

Virtual page number

Virtual address

Physical page numberValid

1220

20

16 14

Cache index

32

Cache

DataCachehit

2

Byteoffset

Dirty Tag

TLBhit

Physical page number

Physical address tag

TLB

Physical address

31 3029 15 141312 11109 8 3 21 0

• mapeamentofully associative

• mapeamentodireto

• pior caso:3 missesTLB, PT, cache


TLBs and caches (DEC 3100)

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

• nesta máquina não há write hit• write through• linha de uma palavra• write buffer


TLB, Virtual memory and Cache (pag 595)

Cache TLB Virtualmemory Possible? If so, under what circumstance?

Miss Hit Hit Possible, although the page table is never really checked if TLB hits.

Hit Miss Hit TLB misses, but entry found in page table; after retry data is found in cache.

Miss Miss Hit TLB misses, but entry found in page table; after retry data misses in cache.

Miss Miss Miss TLB misses and is followed by a page fault; after retry, data must miss in cache.

Miss Hit Miss Impossible: cannot have a translation in TLB if page is not present in memory.

Hit Hit Miss Impossible: cannot have a translation in TLB if page is not present in memory.

Hit Miss Miss Impossible: data cannot be allowed in cache if the page is not in memory.


Protection with Virtual Memory

• Support at least two modes– user process

– operating system process (kernel, supervisor, executive)

• CPU state that user process can read but not write page table and TLB

– special instructions that are only available in supervisor mode

• Mechanisms whereby the CPU can go from user mode to supervisor ,

and vice versa

– user to supervisor : system call exception

– supervisor to user : return from exception (RFE)

• OBS: page tables (operating system´s address space)


Handling Page Faults and TLB misses

• TLB miss (software or hardware).– the page is present in memory, and we need only create the

missing TLB entry.– the page is not present in memory, and we need to transfer

control to the operating system to deal with a page fault.• Page fault (exception mechanism).

– OS saves the entire state the active process.

– EPC = virtual address of the faulting page.– OS must complete three steps:

• look up the page table entry using the virtual address and find the location of referenced page on disk.

• chose a physical page to replace; if the chosen page is dirty, it must be written out to disk before we can bring a new virtual page into this physical page.

• Start a read to bring the referenced page from disk into the chosen physical page.


Memory Hierarchies

• Where can a Block Be Placed?

Scheme name Number of sets Block per set

Direct mapped Number of blocks in cache 1

Set associative Number of blocks in cache

Associativity

Associativity (typically 2 – 8)

Fully associative 1 Number of block in the cache

Feature

Typical values for cache

Typical values for page memory

Typical values for a TLB

Total size in blocks 1000 –100,000 2000 – 250,000 32 – 4,000

Total size in kilobytes 8 – 8,000 8000 – 8,000,000 0.254 – 32 Block size in bytes 16 – 256 4000 – 64,000 4 – 32

Miss penalty in clocks 10 – 100 1,000,000 – 10,000,000 10 – 100

Miss rate 0.1% -- 10% 0.00001% -- 0.0001% 0.01% -- 2%


Miss rate vs set associativity

0%

3%

6%

9%

12%

15%

Eight-wayFour-wayTwo-wayOne-way

1 KB

2 KB

4 KB

8 KB

Mis

sr a

te

Associativity 16 KB

32 KB

64 KB

128 KB


Memory Hierarchies

• How Is a Block Found?

• OBS.: In virtual memory systems– Full associativy is beneficial, since misses are very expensive

– Full associativity allows software to use sophisticated replacement schemes that are designed to reduce the miss rate.

– The full map can be easily indexed with no extra hardware and no searching required

– The large page size means the page table size overhead is relatively small.

Associativity Location method Comparisons requiredDirect mapped Index 1Set associative Index the set, search among elements Degree of associativity

Search all cache entries Size of the cacheFullSeparate lookup table 0


Memory Hierarchies

• Which Block Should Be Replaced on a Cache Miss?

– Random : candidate blocks are randomly selected, possibly using some hardware assistance.

– Least Recently Used (LRU): The block replaced is the one that has been unused for the longest time


Memory Hierarchies

• What Happens on a Write?

– Write-through• Misses are simpler and cheaper because they never require a

block to be written back to the lower level.

• It is easier to implement than write-back, although to be practical in a high-speed system, a write-through cache will need to use a write buffer

– Write-back (copy-back)• Individuals words can be written by the processor at the rate that the

cache, rather than the memory, can accept them.

• Multiple writes within a block require only one write to the lower level in the hierarchy.

• When blocks are written back, the system can make effective use of a high bandwidth transfer, since the entire block is written


Modern Systems• Very complicated memory systems:

Characteristic Intel Pentium Pro PowerPC 604Virtual address 32 bits 52 bits

Physical address 32 bits 32 bits

Page size 4 KB, 4 MB 4 KB, selectable, and 256 MB

TLB organization A TLB for instructions and a TLB for data A TLB for instructions and a TLB for data

Both four-way set associative Both two-way set associative

Pseudo-LRU replacement LRU replacement

Instruction TLB: 32 entries Instruction TLB: 128 entries

Data TLB: 64 entries Data TLB: 128 entries

TLB misses handled in hardware TLB misses handled in hardware

Characteristic Intel Pentium Pro PowerPC 604Cache organization Split instruction and data caches Split intruction and data caches

Cache size 8 KB each for instructions/data 16 KB each for instructions/data

Cache associativity Four-way set associative Four-way set associative

Replacement Approximated LRU replacement LRU replacement

Block size 32 bytes 32 bytes

Write policy Write-back Write-back or write-through


• Processor speeds continue to increase very fast— much faster than either DRAM or disk access times

• Design challenge: dealing with this growing disparity

• Trends:– synchronous SRAMs (provide a burst of data)

– redesign DRAM chips to provide higher bandwidth or processing – restructure code to increase locality– use prefetching (make cache visible to ISA)

Some Issues


Evolução desempenho CPU vs MemIm

pro

ve

me

nt

facto

r

1

10

100

19801982

19841986

Year

19881990

19921994

1996

CPU (fast)

CPU (slow)

DRAM

Documents

Sistemas de Memória - INSTITUTO DE COMPUTAÇÃOpannain/mc722/aulas/arq_hp7.pdf · endereçamento tempo freqüência de acesso em ∆T espaço de endereçamento Temporal Espacial