Organização da memória - Departamento de Ciência da ...rjacobi/ensino/OAC/Memoria.pdf–Para uma DRAM rápida de 4Mb tRAC = 60 ns tRC: tempo mínimo entre o início de um acesso

1

Universidade de BrasíliaUniversidade de BrasUniversidade de BrasUniversidade de Brasííílialialia

Organizaçãoda memóriaOrganizaçãoda memória

Organização eArquitetura deComputadores

OrganizaOrganizaOrganizaçãçãção eo eo eArquitetura deArquitetura deArquitetura deComputadoresComputadoresComputadores

Objetivo

Apresentar uma organização hierárquicada memória que possibilita um melhordesempenho do sistema computacional.

2

“““DatapathDatapathDatapath”””

ControleControleControle

EntradaEntradaEntrada

SaSaSaííídadada

MemMemóóriaria

Potência: um grande problema

Energia drenada da fonte nasubida do sinal:

Energia R CVdd2

Potência R CVdd2 f

CA

B

B

A

Vdd

3

Métrica importante: total de energia consumidaSimplesmente baixar a freqüência não resolve: tudo ficamais lento (a energia total por operação é a mesma)

É preciso baixar a voltagem ou baixar acapacitância.

Com voltagem mais baixa CMOS é mais lenta.

Potência: um grande problema

Básica

MultMult

ADD

MultMult

ADD

MultMult

ADD

MUXMUX

Paralelismo– Clock divide

– Capacitância dobra

– Menor voltagem

MultMult

ADD

Pipeline– Mesmo clock

– Menor voltagem,etapas mais simples.

Reduzindo energia/OP

4

Valores são armazenados num par deportas inversoras.

Bastante rápida porém necessita maisespaço que a DRAM (4 a 6 transistores).

SRAM

Célula SRAM 6 Transistores

bit bit

Word (seleção de linha)

10

0 1Write:

1. Ativar as linhas de bit:

2. Selecionar linha.

Read:1. Pré-carga de em Vdd ou Vdd/2 fi assegurar que são iguais!

2. Selecionar linha.

3. Células levam uma das linhas para low.

4. Sense amp na coluna detecta a diferença entre

0 e 1 == bitbit

bitbit e

bitbit e

bit bit

word

SRAM: organização de 16-word x 4-bit

Qual é mais longa:word line ou bit line?

SRAMCell

SRAMCell

SRAMCell

SRAMCell

SRAMCell

SRAMCell

SRAMCell

SRAMCell

SRAMCell

SRAMCell

SRAMCell

SRAMCell

: : : :

Word 0

Word 1

Word 15

Dout 0Dout 1Dout 2Dout 3

- +Wr Driver &Precharger - +

Wr Driver &Precharger - +

Wr Driver &Precharger - +

Wr Driver &Precharger

Address D

ecoder

WrEnPrecharge

Din 0Din 1Din 2Din 3

A0

A1

A2

A3

- +Sense Amp - +Sense Amp - +Sense Amp - +Sense Amp

5

• Write Enable normalmente é active low (WE_L)

• Din and Dout são combinados para economia de pinos:– É necessário um novo sinal de controle: output enable (OE_L)

– WE_L é ativado (Low), OE_L é desativado (High)• D funciona como entrada de dados

– WE_L é desativado (High), OE_L é ativado (Low)• D funciona como saída de dados

SRAM: diagrama lógico

A

OE_L

WE_L DM

N 22NN wordswords x x MM bitsbits

SRAMSRAM

SRAM: timing

Write Timing:

D

Read Timing:

WE_L

A

WriteHold Time

Write Setup Time

A

DOE_L

2 N wordsx M bitSRAM

N

M

WE_L

Data In

Write Address

OE_L

High Z

Read Address

Junk

Read AccessTime

Data Out

Read AccessTime

Data Out

Read Address

6

Valor é armazenado como carga num capacitor(necessita refresh). Bem menor, porém mais lentaque a SRAM (fator de 5 a 10).

DRAM

Word line

Bit line

Transistor de passagem

Capacitor

DRAM: célula de memória1-Transistor• Write:

– 1. Ativa bit line

– 2. Seleciona linha (row)

• Read:– 1. Pré-carga da bit line para Vdd

– 2. Seleciona linha (row)

– 3. Célula e bit line compartilham cargas• Pequena variação de voltagem na bit line

– 4. Sentido (sense amp)• Pode detectar trocas de ~1 milhão de elétrons

– 5. Write: re-escreve o valor

• Refresh– 1. Executa uma leitura em cada célula.

row select

bit

7

DRAM (square):organização clássica

row

decoder

rowaddress

Column Selector & I/O Circuits

ColumnAddress

data

RAM Cell Array

word (row) select

bit (data) lines

Cada intersecção representauma célula 1-T DRAM

DRAM (4 Mbit): organização lógica

MemMemóóriariaDRAMDRAM

Buf

fer

de e

nder

eços

Dat

a In

D

Q

Dat

a O

ut

Decodificador Coluna

Sense Amps & E/S

Array 2048 x 2048

…

Dec

odif

icad

or li

nha

Word line

Storage cell

Bit

line

…A0 … A10 11

CASRASpor 2 bits

8

DRAM (4 Mbit): organização física

D

Q

I/OI/O I/OI/O12

8 K

bits

128

Kbi

ts

512

SAm

p51

2 SA

mp

128

Kbi

ts12

8 K

bits

Dec

odif

icad

orco

luna

9:

512

Dec

odif

icad

orco

luna

9:

512

128

Kbi

ts12

8 K

bits

512

SAm

p51

2 SA

mp

128

Kbi

ts12

8 K

bits

I/OI/O I/OI/O

128

Kbi

ts12

8 K

bits

512

SAm

p51

2 SA

mp

128

Kbi

ts12

8 K

bits

Dec

odif

icad

orco

luna

9:

512

Dec

odif

icad

orco

luna

9:

512

128

Kbi

ts12

8 K

bits

512

SAm

p51

2 SA

mp

128

Kbi

ts12

8 K

bits

I/OI/O I/OI/O

128

Kbi

ts12

8 K

bits

512

SAm

p51

2 SA

mp

128

Kbi

ts12

8 K

bits

Dec

odif

icad

orco

luna

9:

512

Dec

odif

icad

orco

luna

9:

512

128

Kbi

ts12

8 K

bits

512

SAm

p51

2 SA

mp

128

Kbi

ts12

8 K

bits

I/OI/O I/OI/O

128

Kbi

ts12

8 K

bits

512

SAm

p51

2 SA

mp

128

Kbi

ts12

8 K

bits

Dec

odif

icad

orco

luna

9:

512

Dec

odif

icad

orco

luna

9:

512

128

Kbi

ts12

8 K

bits

512

SAm

p51

2 SA

mp

128

Kbi

ts12

8 K

bits

Sele

tor

I/O

Sele

tor

I/O

BlocoLinhaDecod9:512








Bloco 0 Bloco 3

Endereço

coluna

Endereço

linha

Dat

a In

Dat

a In

Dat

a O

utD

ata

Out

Tc = Tciclo + Tcontrolador + Tdriver

DRAM: sistema de memória

Controladortiming damemória

N

N/2

DRAM2N x 1DRAM

2N x 1DRAM2N x 1DRAM

2N x 1

ControladorDRAM

Drivers debarramento W

Endereço

Dados

9

• Sinais de controle: RAS_L, CAS_L, WE_L, OE_L todos active low

• Din e Dout são combinados: D– WE_L é ativado (Low), OE_L é desativado (High)

• D funciona como entrada.

– WE_L é desativado (High), OE_L é ativado (Low)• D funciona como saída.

• Endereços de linhas e colunas compartilham os mesmos pinos: A.– RAS_L vai para low: pinos A são lidos pela memória como endereço de linha.

– CAS_L vai para low: pinos A são lidos pela memória como endereço de coluna.

– RAS/CAS sensíveis à borda.

A D

OE_L256K x 8DRAM

9 8

WE_LCAS_L

RAS_L

DRAM: diagrama lógico

Cada acesso à DRAM começa com:– ativação de RAS_L

– 2 modos de escrita:early ou late c/CAS

WE_L

A Row Address

OE_L

Junk

WR Access Time WR Access Time

CAS_L

RAS_L

Col Address Row Address JunkCol Address

D Junk JunkData In Data In Junk

DRAM WR Cycle Time

Ciclo Early Wr: WE_L ativado antes de CAS_L Ciclo Late Wr: WE_L ativado depois de CAS_L

DRAM: write timingA D

OE_L

256K x 8DRAM

9 8

WE_LCAS_L

RAS_L

10

OE_L

A Row Address

WE_L

Junk

Read AccessTime

Output EnableDelay

CAS_L

RAS_L

Col Address Row Address JunkCol Address

D High Z Data Out

DRAM Read Cycle Time

Ciclo Early Read: OE_L ativado antes de CAS_L Ciclo Late Read: OE_L ativado depois de CAS_L

Junk Data Out High Z

DRAM Read TimingA D

OE_L

256K x 8DRAM

9 8

WE_LCAS_L

RAS_L

Cada acesso à DRAM começa com:– ativação de RAS_L

– 2 modos de leitura:early ou late c/CAS

tRAC: tempo mínimo entre a descida de RAS e dado válido nasaída.– velocidade da DRAM.

– Para uma DRAM rápida de 4Mb tRAC = 60 ns

tRC: tempo mínimo entre o início de um acesso de linha e o iníciodo próximo acesso de linha.– tRC = 110 ns para uma DRAM 4Mb com um tRAC of 60 ns

tCAC: tempo mínimo entre a descida de CAS e dado válido nasaída.– 15 ns para uma DRAM de 4Mb com um tRAC of 60 ns

tPC: tempo mínimo entre o início de um acesso de coluna e oinício do próximo acesso de coluna.– 35 ns para uma DRAM de 4Mb com um tRAC of 60 ns

DRAM: parâmetros de timing.

11

• Uma DRAM de 60 ns (tRAC) pode– executar um acesso à linha somente a cada 110 ns (tRC)– executar um acesso à coluna em 15 ns (tCAC), porém o tempo entre

dois acessos à colunas é de pelo menos 35 ns (tPC).• Na prática varia em torno de 40 a 50 ns devido a atrasos externos de

endereçamento e barramentos.

• Estes tempos não incluem o tempo de obtenção do endereçodo microprocessador nem o overhead do controlador dememória.– DRAMs paralelas, controlador externo de memória, barramentos,

módulos SIMM, pinos …– 180 ns to 250 ns de latência memória-processador é bom para uma

DRAM “60 ns” (tRAC)

DRAM: desempenho

Melhorando o desempenhoCPUCPU

CacheCache

BusBus

MemóriaMemória

Simples:CPU, cache,bus, memóriamesma largura(32 bits)

CPUCPU

MultiplexadorMultiplexador

CacheCache

BusBus

MemóriaMemória

Wide:

CPU/Mux 1 word;

Mux/Cache, bus, memória N words(Alpha: 64 bits & 256 bits)

CPUCPU

CacheCache

BusBus

Memóriabanco 1

Memóriabanco 1

Memóriabanco 2

Memóriabanco 2

Memóriabanco 0

Memóriabanco 0

Memóriabanco 3

Memóriabanco 3

Interleaved:

CPU, Cache, bus 1 word

Memória N módulos(4 módulos); exemplo é wordinterleaved

Facilitando a leitura de múltiplas words com a utilização de bancos de memória.

12

Módulo N-1MMóódulo N-1dulo N-1Módulo 1MMóódulo 1dulo 1Módulo 0MMóódulo 0dulo 0

Memória interleaved

ENDEREENDEREÇÇOSOS

DADOSDADOS

A idéia básica de um esquema de memória interleaved(N-way) é organizar N módulos de memória de modo queN endereços seqüenciais, a0, a1, …, aN-1 sejam distribuídosatravés dos módulos de acordo com a seguinte regra:

endereço ai é atribuído ao módulo Mj se j = i mod N

Memória interleaved

Endereço Banco 0 Endereço Banco 1 Endereço Banco 2 Endereço Banco 3

048

12

159

13

26

1014

37

1115

13

• DRAM (Read/Write)– Tempo de ciclo >> Tempo de acesso (2:1, porque?)

• DRAM (Read/Write) Tempo de ciclo :– Com que freqüência podem ser realizados os acessos?

• DRAM (Read/Write) Tempo de acesso:– Com que velocidade são obtidos os dados uma vez iniciado um acesso?

Memória: desempenho

Tempo

Tempo de acesso

Tempo de ciclo

Interleaving: aumentando a largura debanda

Padrão de acesso sem interleaving:

Inicia acesso a D1 Inicia acesso a D2

D1 disponível

CPUCPU MemóriaMemória

Padrão de acesso com 4-way interleaving:

Acesso banco 0

Acesso banco 1

Acesso banco 2

Acesso banco 3

Banco 0 pode ser acessado novamente

CPUCPU

Memóriabanco 0

Memóriabanco 0

Memóriabanco 1

Memóriabanco 1

Memóriabanco 2

Memóriabanco 2

Memóriabanco 3

Memóriabanco 3

14

• Modelo de timing

– 1 para envio de endereço,

– 4 para tempo de acesso, 10 para tempo de ciclo, 1para enviar dado

– Bloco de cache de 4 words

• Simples = 4 x (1 + 10 + 1) = 48• Wide = 1 + 10 + 1 = 12• Interleaved = 1 + 10 + 1 + 3 = 15

Memória: desempenho

Latência: período de inatividade entre um estímulo e aresposta por ele provocada (Aurélio).

Tempo decorrido entre uma requisição de informação doprocessador para a memória e a recepção da informaçãopelo processador.

TecnologiaTempo de acesso típico$/Mbyte em 1997SRAM5 - 25 ns$100 - $250DRAM60 - 120 ns$5 - $10Disco magnético10 - 20 milhões ns$0.10 - $0.20

Problema de latência

15

Tunneling Magnetic Junction RAM(TMJ-RAM)

IBM breakthrough!

Velocidade da SRAM, densidade da DRAM, não-volátil (sem refresh).

Nova área chamada “Spintronics”, combinação de spin (física quântica) eeletrônica. Mesma tecnologia utilizada em discos de alta densidade.

Synchronous DRAM (SDRAM)

Utiliza um clock parasincronizar entrada e saídanum chip de memória.

O clock é coordenado com oclock da CPU de modo asincronizar o timing damemória com o timing daCPU.

SDRAM economiza tempo na execução de comandos etransferência de dados, contribuindo para o aumento do desempenhoglobal do sistema.

16

Double-data rate SDRAM é uma versão mais rápida daSDRAM, capaz de ler dados tanto na subida quanto nadescida do clock do sistema, dobrando a taxa de transferênciado chip de memória.

DDR ou SDRAM II

RDRAM é um projeto desenvolvido por uma únicaempresa, a Rambus, Inc. É extremamente rápida. Utiliza umcanal de grande largura de banda para transmitir dados avelocidade até dez vezes mais rápida que a DRAM standard.

RDRAM® (Rambus™ DRAM)

SLDRAM é a maior concorrente da RDRAM. Desenvolvidapor um consórcio de fabricantes de chips, Synclink estende aarquitetura Synchronous DRAM four-bank para 16 banks eincorpora uma nova interface e lógica de controle paraaumentar o desempenho.

SLDRAM (Synclink DRAM)

17

Velocidade Tamanho Custo ($/bit)

Mais rápida Menor Mais alto

Mais lenta Maior Mais baixo

Hierarquia da memória

Memória

Memória

Memória

CPU

Nível n

. . .

Nível 2

Nível 1

CPU

Tamanho da memória em cada nível

Distância da CPUem tempo deacesso


18

ProcessadorProcessadorProcessador

Registros

Cachenível 11s ns

1s Kbs

Cachenível 2

SRAM

10s ns100s Kbs

Memóriaprincipal

DRAM

100s ns100s Mbs

Memóriasecundária

Disco

10s ms10s Gbs

Memóriasecundária

Fita

10s s10s Tbs

ControleControleControle

DataDataDatapathpathpath

Hierarquia de memória de umsistema computacionalmoderno

10 0

00 0

00 0

00

10 0

00 0

00

10

0

10

1

Processador

MemóriacacheSRAM

Memóriaprincipal

DRAM

Controladorcache

MemóriaSecundária

(discos)Memória LocalRegistros - bCache - Kb Kb

Mb

Gb


19

Tem como objetivo estabelecer, através de meiosarquiteturais, um subsistema de memória que apresentaao usuário a capacidade (virtualmente ilimitada) damemória secundária com a velocidade dos componentesmais rápidos (memória local ou cache).


• Memórias interleaved, onde a informação é distribuída emvários módulos de memória podendo ser acessada em paralelo.

• Projeto e implementação de um mecanismo de memóriavirtual que oferece ao usuário a ilusão de uma memóriaprincipal ilimitada com um mínimo de latência.

• Gerenciamento eficiente do subsistema memóriaprincipal/memória cache, de modo que as requisições deinstruções e dados possam ser resolvidas mais rapidamentepela memória cache.

Este objetivo é alcançado pela combinação dosseguintes meios:


20

Eficiência = f (freqüência de faltas)

Porque

latênciamemória secundária >> latênciamemória principal

Excessivas faltas resultam em muito tempo despendidotransferindo dados para a memória principal.

Desempenho

Transferência de blocos para minimizar freqüênciade faltas

O bloco não contém somente o item que falta mastambém os itens com expectativa de seremreferenciados num futuro imediato.

Desempenho

21

Princípio da localidade• Um princípio que torna a existência de uma hierarquia de

memória uma boa idéia. É o que faz funcionar a hierarquiade memória.

• Se um item é referenciado,

a tendência é que ele seja referenciado novamente embreve (localidade temporal) e,

itens próximos serão referenciados em breve (localidadeespacial).

Porque o código possui estes tipos de localidade?

Localidade espacial

Os endereços gerados por um programa normalmente estãorestritos a uma pequena região do espaço de endereçamentovirtual (instruções de um programa e estruturas de dados).

Princípio da localidade

Espaço de endereçamento virtual0 2N - 1

Probabilidadede referência

22

Localidade temporal

O conjunto de endereços varia lentamente no tempo.

Se um item é referenciado, itens cujos endereços sãopróximos tendem a ser referenciados brevemente(execução de loops).

Princípio da localidade

• Dois tipos de localidade:– Localidade temporal (localidade no tempo): se um item é referenciado, a

tendência é que ele seja referenciado novamente em breve.

– Localidade espacial (localidade no espaço): se um item é referenciado,itens vizinhos tendem a ser referenciados em breve.

• Tirando vantagem do princípio da localidade:– Oferecer ao usuário a maior quantidade possível de memória com a

tecnologia mais barata.

– Providenciar acesso com a velocidade oferecida pela tecnologia maisrápida.

• DRAM é lenta porém barata e densa:– Boa escolha para oferecer bastante memória ao usuário.

• SRAM é rápida porém cara e não muito densa:– Boa escolha para oferecer tempo de acesso rápido ao usuário.

Resumindo

23

Se a memória virtual cria a ilusão de uma memóriaprincipal, física, ilimitada e mais rápida que a secundária, oobjetivo da memória cache é criar outra grande ilusão: queas referências à memória serão atendidas na velocidade doprocessador.

Memória cache (cachée)

ProcessadorMemóriacachéeSRAM

Memóriaprincipal

DRAM

Controladorcachée

Hierarquia memóriacache/memóriaprincipal

Memória cache

24

Tradução de endereço

se $ k | cachée(k ).endereço = endereço_físicoentão nova_informação = cachée(k ).informaçãosenão nova_informação = memória(endereço_físico) Ÿ $ l |

nova cachée(l ).endereço = endereço_físico Ÿnova cachée(l ).informação =

memória(endereço_físico)

endereço_físico

endereço informação

cachée

MemóriaPrincipal

informação

buffer deendereços

buffer dedados

Memóriacache

• Política de alocação

• Tamanho e natureza dos blocos transferidos

• Política de substituição

• Tamanho do cache

• Política de atualização da memória principal

• Coerência em sistemas multiprocessados

Memória cache(Características de projeto)

25

• Read hits– é o que queremos!

• Read misses– pausa a CPU, busca o bloco na memória, escreve na cache, restart

• Write hits– pode atualizar dado na cache e na memória (write-through)

– escreve o dado somente na cache (write-back na memória depois)

• Write misses– leva o bloco inteiro para a cache e então escreve a word.

Acertos x falhas

O desempenho de uma memória cachée depende deum conjunto de parâmetros tais como tamanho deblocos, tamanho da cachée e do tipo de mapeamentoutilizado.

Taxa de acerto: HR (hit rate)

Número de referências à memória encontradas na cachéeNúmero total de referências à memória

Taxa de falha: MR ( miss rate)MR = 1 - HR

Medida de desempenho

26

Desempenho

Modelo simplificado:

tempo_de_execução = (ciclos_de_execução + ciclos_de_pausa) x tempo_de_ciclo

ciclos_de_pausa = # de_instruções x taxa_de_falha x penalidade_de_falha

Dois modos de melhorar o desempenho:

diminuir a taxa de falha

diminuir a penalidade de falha

O que acontece se aumentarmos o tamanho do bloco?

Utilizar caches separadas pois há maior localidade espacial no código:

1 KB

8 KB

16 KB

64 KB

256 KB

256

40%

35%

30%

25%

20%

15%

10%

5%

0%

Mi s

s r a

te

64164

Block size (bytes)

Program

Block size in words

Instruction 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%

Desempenho

Aumentar o tamanho dos blocos tende a diminuir a taxa de falha:

27

• Mapeamento direto

• Mapeamento totalmente associativo

• Mapeamento associativo por grupos

Alocação e organização

Como sabemos se um dado se encontra na cache?Caso afirmativo como localizá-lo?

Mapeamento direto

FRAME 000FRAME 000

FRAME 001FRAME 001

FRAME 010FRAME 010

FRAME 011FRAME 011

FRAME 100FRAME 100

FRAME 101FRAME 101

FRAME 110FRAME 110

FRAME 111FRAME 111

BLOCO 000000BLOCO 000000



































. . .. . .

Memória físicaprincipal

Memória físicaprincipal

Memória cache

Para cada item da memória principal existeexatamente uma localização na cache onde o itempode estar.

Endereço é módulo(número_de_blocos_na_cache).

Vários itens da memória principal compartilhamlocalizações na cache.

28

Que tipo de localidade está sendo explorada?

Tag Index Wordoffset

1 011 231 12

=

Index

0

1

2

.

.

.

.

.

1021

1022

1023

VL Tag Data

20

20 10

32

Hit

Data

Cache commapeamentodireto naarquiteturaMIPS

Endereço

Hit

Tag Index15 431 16

12

Blockoffset

3 2Wordoffset

1 0

16 2

Endereço

=

VL Tag Data

16 32

Data

32 32 32

Mux

4 Kentradas

Explorando alocalidade espacial

29

endereço_bloco palavra endereço tag bloco frame 0

endereço tag bloco frame 1

endereço tag bloco frame F-1

igualdade...

.

.

.

endereço físico

k2 w

Mapeamento totalmenteassociativo

Mapeamento associativopor grupos

Address

22 8

V TagIndex

012

253254255

Data V Tag Data V Tag Data V Tag Data

3222

4-to-1 multiplexor

Hit Data

123891011123031 0

30

Diminuindo a taxa de falhacom associatividade

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

Eight-way set associative (fully associative)

Tag Data Tag Data Tag Data Tag Data

Four-way set associative

Set

0

1

Tag Data

One-way set 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

0 %

3 %

6 %

9 %

1 2 %

1 5 %

Ei ght-wa yF our- wayTw o-w ayOn e-w ay

1 KB

2 KB

4 KB

8 KB

Mis

s ra

te

As so ciativi ty 16 K B

32 K B

64 K B

12 8 KB

Diminuindo a penalidade de falha com cache multiníveis

•Adicionar um segundo nível de cache:–normalmente a cache primária está no mesmo chip do processador

–utilizar SRAMs para adicionar outra cache acima da memória primária(DRAM)

–a penalidade de falha diminui se a informação se encontra na cache L2.

•Exemplo:–CPI de 1.0 numa máquina de 500Mhz com uma taxa de falha de 5%, DRAM comtempo de acesso de200ns.

–Adicionar uma cache L2 com tempo de acesso de 20ns diminui a taxa de falhapara 2%.

31

Política de substituição

•FIFOFácil de implementar, mas tem uma taxa de falhaaproximadamente 12% maior que

•LRUMelhor desempenho a um custo maior que FIFO.

• Copy-backQuando uma palavra é modificada na cache um flag éativado. A palavra correspondente na memória principalsomente será atualizada quando o bloco que contém apalavra modificada for substituído na cache.

• Write-through (store-through)Sempre que uma palavra é modificada na cache, ela éatualizada na memória principal.

Política de atualização damemória principal

32

É um dos mecanismos utilizados para explorar ahierarquia de memória a fim de maximizar adisponibilidade de espaço de memória sem pagar umcusto excessivo de latência.

O papel específico do mecanismo de memória virtual écriar para o usuário a ilusão de um espaço de memória,diretamente endereçável, maior do que existefisicamente.

Memória virtual

A implementação da memória virtualenvolve pelo menos dois níveis dememória (primária e secundária) e umaação cooperativa entre o processador eo sistema operacional.

Memória virtual

33

Definição

Um endereço utilizado por um programador échamado de endereço virtual e o conjunto detais endereços é chamado de espaço deendereçamento virtual.

Memória virtual

Definição

Um endereço de uma word (ou byte) na memóriafísica é chamado de endereço de memória ouendereço físico ou real e o conjunto de taisendereços é chamado de espaço de memória ouespaço de endereçamento físico ou real.

Memória virtual

34

Denominando N={0, 1, 2, …, n-1} o espaço de endereçamentovirtual e M={0, 1, 2, …, m-1} o espaço de endereçamento físico,em geral n >> m.

O objetivo de um mecanismo de memória virtual é realizar umafunção de mapeamento

MAP: N Æ M » {f} | " a Œ N

MAP(a) = a' se o item no endereço virtual a estápresente no endereço de memória a' Œ M

MAP(a) = f se o item no endereço virtual a não estápresente em M

Memória virtual

MAP: N Æ M » {f} | " a Œ N

MAP(a) = a' se o item no endereço virtual a está presenteno endereço de memória a' Œ M

MAP(a) = f se o item no endereço virtual a não estápresente em M

Memória virtual

PROCESSADORPROCESSADOR Tradutor deendereço

Tradutor deendereço

Espaço de endereçamento

virtual N

Espaço de endereçamento

virtual NFault

handler

Fault handler

Memóriaprincipal

Memóriaprincipal

Memória secundária

Memória secundária

Hierarquia de memória

a

a

a'

f

35

A memória principal pode funcionar como cache para amemória secundária

Memória virtual

Endereços virtuais Endereços físicos

Tradução deendereços

Endereços em discoVantagens:

• ilusão de ter uma memória física maior• realocação de código• proteção

A implementação de um sistema de memóriavirtual envolve, além da hierarquia da memóriafísica, uma cooperação entre o processador e osistema operacional.

Além disso quatro questões influenciam asdecisões de projeto de uma memória virtual.

Questões básicas de projeto

36

1. Tamanho e natureza das informaçõesdos blocos transferidos da memóriasecundária para a principal

• Paginação

• Segmentação


2. Quando um bloco de informação é trazidopara o espaço de memória física, M, e Mestá ocupado, alguma região de M deveser liberada para fazer lugar ao novobloco.

A definição da região da memória M quedeve ser liberada é chamada política desubstituição.


37

3. De modo similar, a definição da regiãode M a ser utilizada para receber onovo bloco de informação é chamadapolítica de alocação.


4. Os itens faltantes não são buscados namemória secundária somente na detecçãode faltas.

Escolha da regra de busca (ou load), quedetermina quando um item faltante (oubloco de encapsulamento) deve ser trazidoda memória.


38

Neste caso, tanto o espaço de endereçamentovirtual quanto o espaço de endereçamento físico(real) são divididos em blocos de tamanhoidêntico.

Na memória virtual os blocos são chamados depáginas.

Na memória física os blocos são chamados deframes de páginas.

Tamanho e natureza dos blocos:Paginação

Para um dado programa ocupando umespaço de endereçamento virtual N, umsubconjunto de suas páginas pode sermapeado num subconjunto de framesem M.

Paginação

39

Mapeamento direto

Paginação

Página 0Página 0

Página 1Página 1

Página 2Página 2

Página 3Página 3

Página 4Página 4

........

........

Página 31Página 31

Tradução de endereço(função de

mapeamento)

Tradução de endereço(função de

mapeamento)

Frame 0Frame 0

Frame 1Frame 1

Frame 2Frame 2

......

......

Frame 7Frame 7

31744

4096

3072

2048

1024

0

1024

3072

2048

0

7168

Endereçosvirtuais

Endereçosfísicos

A página serve tanto como unidade demapeamento lógico de N para M comounidade de transferência entre memóriasecundária e memória principal.

Paginação

40

Válid

o

11

11

11

11

11

00

11

11

00

11

11

00

11

11

Tabela de página

Endereço físico ouendereço em disco

Endereço virtual

Memória em disco

Tabelas de página

Memória física

Tabeladepágina

Registro Base Tabela de PRegistro Base Tabela de Pááginagina

NNúúmero de pmero de páágina virtualgina virtual OffsetOffset na p na pááginagina

Endereço virtual

Endereço físico

NNúúmero de pmero de páágina fgina fíísicasica OffsetOffset na p na pááginagina

VL DA Endereço

Número de página física

Se VL= 1 então página está na memória

Senão página está na memória secundária

DA: R=read only; W= read/write; X=execute only

41


if is_valid PT(P).DA then

if PT(P).VL = 1

then new memory address = PT(P).ENDR + desl;

else trap page_fault;

else trap protection_violation_fault;

Paginação

VL DA Endereço

Uma cache para tradução deendereços:

Translation Lookaside Buffer

Acelerando a tradução deendereços

11

11

11

11

11

00

11

11

00

11

11

00

11

11

Tabela de página

Página física válida ouendereço em disco

Número depágina virtual

Endereço depágina físicaTag

00

11

11

11

11

00

11Válido

Memória em disco

Memória física

TLB

TLB size: 32 - 4096 entradas

Block size: 1-2 entradas de tabelade página (4-8 bytes cada)

Hit time: 0.5 - 1 ciclo de clock

Penalidade: 10-30 ciclos de clock

Taxa de falha: 0.01% - 1%

42

Paginação

Disco

SistemaOperacional

SistemaSistemaOperacionalOperacional

MEMÓRIAVIRTUAL

EndereçoLógico

MEMÓRIAVIRTUAL

EndereçoLógico

FalhaFalhade pde pááginagina

Falha deFalha deproteproteçãçãoo

Acessoinválido

Página estána memóriasecundária

11

11

00

11

11

11

11

11

00

11

11

00

11

11

Tabela de página

Referência

Resume

Memória física

Encontraum frame livre

e traz novapágina

Atualizaa tabelade página

A principal vantagem dos sistemas de paginação éque a unidade de transferência é de tamanho fixo:a página.

O algoritmo de alocação pode ser bastantesimples: atribuir uma página a qualquer framedisponível ou liberado pelo algoritmo desubstituição.

Paginação

43

Fragmentação

O termo refere-se às áreas do espaço deendereçamento real, que por alguma razãodeixam de estar disponíveis paraarmazenamento de programas e seus dados.

Paginação

Fragmentação de Tabela

Ocorre quando as tabelas de páginas tornam-seextremamente grandes devido a espaços deendereçamento virtuais muito grandes.

Uma parte significativa da memória principalnão estará disponível para atribuição de páginas.

Paginação

44

Uma maneira de reduzir o tamanho da tabelade páginas é a utilização do mapeamentoassociativo ao invés do mapeamento direto.

Neste caso o tamanho da tabela é dado por |M|,o número de frames do espaço deendereçamento real e não |N|, o número depáginas do espaço de endereçamento virtual.

Paginação

Cada entrada da tabela contémo número da página (NP) e oendereço do frame (ADDR).

PaginaçãoNNúúmero de pmero de páágina virtualgina virtual OffsetOffset na p na pááginagina

Endereço virtual

Endereço físico

NNúúmero de pmero de páágina fgina fíísicasica OffsetOffset na p na pááginagina

VL DA

Tabela de página

NP Endereço ADDR

Dado um endereço virtual, a tabela é pesquisada associativamente,comparando np com o campo NP.

Mapeamentoassociativo

45

Fragmentação interna

Acontece quando o programa não ocupa um número inteiro depáginas. Quando o programa é trazido para a memória principal,uma parte do último frame utilizado para armazenar o programaé perdida.

Paginação

0 1 |M|-1Frames de página

Parte nãoutilizada doúltimo frame

Frames ocupados

Tira proveito do modo de dividir os programas emmódulos ou segmentos.

Num sistema de memória virtual segmentada, oespaço de endereçamento virtual do usuário é vistocomo uma coleção de segmentos que,diferentemente das páginas, podem ter tamanhosdiversos

Tamanho e natureza dos blocos:Segmentação

46

DA: direito de acesso ao segmento

LGTH: comprimento do segmento

if VL=1 then segmento está na memória em ADDR

else segmento está no disco em ADDR

SegmentaçãoNNúúmero de segmento virtualmero de segmento virtual OffsetOffset no segmento no segmento

Endereço virtual

Endereço físico

NNúúmero de segmento fmero de segmento fíísicosico OffsetOffset no segmento no segmento

VL DA

Tabela de segmento (P)

LGTH Endereço ADDR


if TS(P)(ns).VL=0 then trap segment_fault

else if TS (P)(ns).DA é válido

then if TS (P)(ns).LGTH < offset

then trap overflow_fault

else novo Endereço_memória=TS (P)(ns).ADDR+offset

else trap protection_violation_fault

Segmentação

VL DA LGTH Endereço ADDR

47

Cada entrada na tabela de segmentos TS(P) é denominadadescritor de segmento.

Corresponde a um dos segmentos de P e contém o endereçode início (ADDR) do segmento na memória principal, ocomprimento do segmento (LGTH) e os campos de direito deacesso (DA) e presente na memória (VL).

Segmentação

VL DA LGTH Endereço ADDR

Descritor de segmento no Pentium:

AVL Disponível para o SO

BASE Endereço base do segmento

D/B Tamanho default

0 = segmento 16-bit; 1 = segmento 32-bit

DPL Nível de privilégio do descritor

G Granulosidade (fator de escala de LIMIT)

LIMIT Limite do segmento (b/4Kb)

P Segmento presente

S Tipo de descritor

0 = sistema; 1 = aplicação

TYPE Tipo de segmento

n Reservado

GD/B

0AVL

BASE 31...24SEGLIMIT19...16

P DPL S TYPE BASE 23...16

BASE ADDRESS 15...0 SEGMENT LIMIT 15...0

31 24 23 22 21 20 19 16 15 1214 13 11 8 7 0

31 16 15 0

+4

+0

48

Diferentes das páginas, os segmentos podem variarconsideravelmente em tamanho.

Enquanto a alocação é uma questão trivial nos sistemaspaginados, é mais sério nos sistemas segmentados vistoque deve ser preciso encontrar uma área na memóriafísica, de tamanho suficiente para receber o segmentotransferido.

Alocação

S1 S2 h1 S3 h2 S4 S5 S6 h3 S7 h4

Sejam l1, l2, …, ln os comprimentos ea1, a2, …, an os endereços das lacunash1, h2, …, hn, respectivamente.

Algoritmos de alocação

49

Algoritmo best-fit

As lacunas estão ordenadas de tal modo que

l1 £ l2 £ … £ ln.

O novo segmento S de comprimento L éalocado na lacuna hi de modo que li é o menorcomprimento e L £ li.


Algoritmo first-fit

As lacunas estão ordenadas de tal modo quea1 £ a2 £ … £ an.

O novo segmento S de comprimento L éalocado na lacuna hi com o menor endereçotal que L £ li.


50

Fragmentação externa

Independente da regra de alocação utilizada,pode ocorrer que as lacunas disponíveis namemória sejam muito pequenas parareceberem um determinado segmento.


Fragmentação externaQuando isto ocorre, deve ser acionado um procedimentode compactação de memória para coletar todas as lacunasdispersas e criar um único bloco de memória disponível:garbage collection.


S1 S2 S3 S4 S5 S6 S7 h

51

Quando uma página é trazida para amemória principal e não há nenhumframe disponível, a seleção da página aser removida é definida pelo algoritmode substituição.

Políticas de substituição

String de referências

R = r1 r2 r3 … rk …

é a seqüência de referências sucessivas às páginasno curso de execução de um programa.

t(ri )

é o instante em que a referência ri produz umafalta de página.


52

Se o algoritmo de substituição exige umconhecimento preciso das referências de páginasfuturas ri+1, ri+2, …, no instante da falta depágina t(ri ), o algoritmo é dito irrealizável.

Se o algoritmo é baseado em suposições acercadas referências futuras, ele é dito realizável.


Nosso objetivo principal é selecionar um algoritmode substituição que minimiza a freqüência de faltasde páginas. Isto é, que minimiza os instantes emque uma página referenciada não é encontrada namemória principal.

Um modo é maximizar o tempo entre faltas depágina (o que conduz ao princípio da otimalidade).


53

Princípio de “otimalidade”Seja {0,1, 2, 3, …, n} o conjunto de páginas na memória noinstante t(ri ) em que ocorre uma falta de página e seja t( j )≥ t(ri ) a mais próxima referência (subseqüente) à página j.

Definindo T( j ) = t( j ) - t(ri )

para todas as páginas em {0,1, 2, 3, …, n},

então a página j selecionada para substituição é aquela cujoT( j ) é máximo.

(irrealizável)


Algoritmo FIFO (First-In, First-Out)No instante t(ri ), de falta de página, substituir a página queestá na memória por mais tempo.

Fácil de implementar (nonlookahead) mas não respeita oprincípio da localidade. Uma página freqüentementereferenciada pode ser substituída por ser a mais antiga namemória.


54

Algoritmo LRU (Least-Recently-Used)No instante t(ri ), de falta de página, substituir a páginaque está na memória com a referência mais antiga.

Menos fácil de implementar que a FIFO, pois exigeconhecimento das referências passadas, mas respeita oprincípio da localidade.


Algoritmo PFF (Page-Fault-Frequency)Tenta manter a freqüência de faltas abaixo de um valormáximo especificado utilizando um parâmetro P, freqüênciade faltas de página.

No instante t(rk ) da falta, a distância temporal Df até a faltaanterior é comparada com 1/P. Se Df £ 1/P nenhuma página ésubstituída, ao contrário, a alocação de memória do programa éaumentada de uma página.

Se Df > 1/P, as páginas não referenciadas no intervalo Df (sehouver alguma) são retiradas da memória.


55

Algoritmo NRU (Not-Recently-Used)Associado a cada página j na memória há um flag dereferência ref(j ) tal que

ref(j )= 1 se a página j foi referenciada recentemente

= 0 senão.

No instante t(ri ) da falta, substituir a página j cujo valorde ref(j ) = 0


Working SetSeja N = {0,1, 2, 3, …, n} o conjunto de páginas queconstituem um programa. Dada uma string dereferências R = r0r1 r2 r3… rk…, o working set de umprograma na késima referência, rk, é definido como

WS(k, h) = {i Œ N | i Œ {rk-h+1, … , rk}}


56

Exemplos de Working SetSeja R* = <4,4,5,4,5,5,6,20,20,21,4,5,5,6,20> umastring de referências de um programa.

k WS(k, 2) WS(k, 4) WS(k, 6) 3 {4, 5} {4, 5} {4, 5}

6 {5} {4, 5} {4, 5}

9 {20} {5, 6, 20} {4, 5, 6, 20}

12 {4, 5} {4, 5, 20, 21} {4, 5, 6, 20, 21}

15 {6, 20} {5, 6, 20} {4, 5, 6, 20, 21}


Algoritmo WS ( Working Set)

O algoritmo WS mantém todo o tempo o working setWS(k, h), para uma determinada janela h.

Numa falta de página t(rk ), uma página só é removidase ela não estiver referenciada nas h referências.


57

Paginação por demandaAs páginas são buscadas na memória secundáriaquando ocorre uma falta de página.

Pré-paginaçãoTenta antecipar referências futuras às páginas e trazê-las antes de sua utilização.

Pode reduzir o overhead de transferência de páginas.

Paginação por demanda epré-paginação

Sistemas modernos

• Sistemas de memória bastante complicados:

Characteristic Intel Pentium Pro PowerPC 604Virtual address 32 bits 52 bitsPhysical address 32 bits 32 bitsPage size 4 KB, 4 MB 4 KB, selectable, and 256 MBTLB 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 associativePseudo-LRU replacement LRU replacementInstruction TLB: 32 entries Instruction TLB: 128 entriesData TLB: 64 entries Data TLB: 128 entriesTLB 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 cachesCache size 8 KB each for instructions/data 16 KB each for instructions/dataCache associativity Four-way set associative Four-way set associativeReplacement Approximated LRU replacement LRU replacementBlock size 32 bytes 32 bytesWrite policy Write-back Write-back or write-through

58

Referências

•Dasgupta, S. Computer architecture. A modernsynthesis. Vol 1: Foundations. Wiley.

•John Kubiatowiczhttp://www-inst.eecs.berkeley.edu/~cs152/

•Patterson, D. A., Hennessy, J. L., ComputerOrganization and Design: The Hardware/SoftwareInterface. Morgan Kaufmann.

Pseudo-LRU

The Pentium processor with MMX technology employs a pseudo-LRU replacement algorithm which requires three blts per set in each ofthe caches. When a line must be replaced, the cache will first select which of l0:l1 and l2:l3 was least recently used. Then the cache willdetermine which of the two lines was least recently used and mark it for replacement. This decision tree is shown in Figure 2-7.

Documents

Organização da memória - Departamento de Ciência da ...rjacobi/ensino/OAC/Memoria.pdf–Para uma DRAM rápida de 4Mb tRAC = 60 ns tRC: tempo mínimo entre o início de um acesso