Memria Cache

Princpio da Localidade Apenas uma parte relativamente pequena do

espao de endereamento dos programas acessada em um instante qualquer Localidade Temporal

Um item referenciado tende a ser referenciado novamente dentro de um espao de tempo curto

Localidade Espacial Se um item referenciado, itens cujos endereos

sejam prximos ao dele tendem a ser logo referenciados

2

Localidade em Programas Localidade temporal:

Em funo de sua estrutura, as instrues e dados da maioria dos programas tendem a ser acessados de maneira repetitiva

Localidade espacial: As instrues so acessadas quase sempre de

maneira seqencial Elementos de arrays ou registros

3

Nveis de Memria - 01 Dados sempre copiados entre nveis de memria

adjacentes Anlise focada apenas em dois nveis, um superior

e um inferior Bloco:

Unidade mnima de informao trocada entre nveis

4

Nveis de Memria - 02

5

Processador

Dados transferidos

Taxa/Razo de Acertos Mede desempenho da Hierarquia Acerto:

Informao solicitada pelo processador encontra-se no nvel superior

Taxa de acerto: frao de acessos com acerto Falta:

Informao solicitada pelo processador no se encontrada no nvel superior Nvel inferior acessado em busca do bloco.

Taxa de faltas = (1 taxa de acerto)

6

Tempo de Acerto e Penalidade por Faltas

Determinam a eficincia da implementao de uma hierarquia de memria Tempo de acerto tempo para acesso ao nvel

superior, incluindo o tempo para determinar o acerto ou falta

Penalidade por falta tempo para a substituio dos blocos mais o tempo de envio da informao ao processador

Tempo de acerto

Memria Cache Originalmente, nvel da hierarquia de memria

situado entre o processador e a memria principal

Termo estendido para qualquer memria gerenciada de modo a tirar vantagem da localidade de acesso

8

Caractersticas - 01 Diminui o gargalo existente entre processador e

memria principal Diferena de velocidade

5 a 10 vezes mais rpidas que a memria principal

Ligada diretamente MP

9

Caractersticas - 02 Tecnologia semelhante da CPU e, em

conseqncia, possui tempos de acesso compatveis com a mesma, resultando numa considervel reduo da espera da CPU para receber dados e instrues da cache

10

Nveis De Cache - 01 L1 Level 1 (nvel 1)

Dentro do processador Mesma velocidade do processador

L2 Level 2 (nvel 2) Dentro do invlucro, fora do chip Metade da velocidade do processador

L3 Level 3 (nvel 3) Cache externa, situada na placa me

11

Nveis De Cache - 02

12

Cache L1

ProcessadorCache L2 Memria

principal

Invlucro do processador

Diviso da Cache L1 A cache L1 geralmente dividida em cache de

dados e cache de instrues: processamento mais rpido

13

dados

processador

instrues

Cache L1

Localidade Devido ao princpio da localidade, interessante

que a memria cache armazene o pedao do programa que executado repetidas vezes, deixando o restante do programa que no est sendo utilizado na memria principal

14

Utilizao da Cache - 01 Sempre que o processador vai buscar uma nova

instruo (ou dado), ele acessa a memria cache: Se a instruo estiver na cache (acerto ou hit), ela

transferida em alta velocidade para o processador Se a instruo no estiver na cache (falta ou miss), a

execuo do programa interrompida e a instruo desejada transferida da MP para a MC

15

Utilizao da Cache - 02 No feita a transferncia somente da instruo,

mas sim de um bloco que, segundo o princpio da localidade, contm instrues que sero usadas em seguida

16

17

Processador Cache

controlador de cache

Memriaprincipal

Bloco de palavras

Palavra(instruoou dado)

Elementos de Projetos de uma Cache Funo de mapeamento MP/MC Algoritmos de substituio de dados na cache Polticas de escrita

18

Funo de Mapeamento A funo de mapeamento indica quais blocos da

MP esto presentes na cache e onde eles esto localizados na cache A MC e MP esto divididas em blocos de x

palavras A MC pode conter m blocos (linhas) A MP pode conter b blocos

19

20

.

.

.Bloco 0

Byte 0Byte 1

Byte 63

.

.

.

Byte 0Byte 1

Byte 63

Bloco 1

.

.

.

Byte 0Byte 1

Byte 63

Bloco 226 -1

.

.

.

MP

Diviso da MP de 4G bytes em blocos de 64 bytes ento tem-se 226 blocos de 64 bytes

21

Byte 0

Byte 0

Byte 0

Tag ou rtulo

MC

Byte 0

Byte 1

Byte 1

Byte 1

Byte 1

Byte 63

Byte 63

Byte 63

Byte 63 ...

...

...

...

.

.

.

Linha 0

Linha 1

Linha 2

Linha 1023

Diviso da MC de 64K bytes em linhas de 64 bytes ento tem-se 1024 linhas de 64 bytes

Mapeamento Direto - 01 Cada bloco da MP tem uma linha de cache

previamente definida para ser armazenado Muitos blocos iro ser destinados a uma mesma

linha

22

23

.

.

.B 0

Byte 0Byte 1

Byte 63

.

.

.

Byte 0Byte 1

Byte 63

B 1

.

.

.

Byte 0Byte 1

Byte 63

B 226 -1

.

.

.

Byte 0

Byte 0

Byte 0

Byte 0

Byte 1

Byte 1

Byte 1

Byte 1

Byte 63

Byte 63

Byte 63

Byte 63 ...

...

...

...

.

.

.

Linha 0

Linha 1

Linha 2

Linha 1023

tag

Bloco 1023

Mapeamento Direto - 02 Cada linha da MC dever acomodar 216 blocos ou

65536 blocos (um de cada vez) O campo tag serve para identificar qual bloco a

linha est armazenando no momento

24

Mapeamento Direto - 03 Cada endereo de MP pode ser dividido nos

seguintes elementos:

25

Nmero do bloco na linha Nmero da linha Nmero do byte

16 bits216= 64K blocos

10 bits210= 1024 linhas

6 bits26= 64 bytes

32 bits

Mapeamento Direto - 04 Exemplo:

O processador manda para a MC o seguinte endereo:

26

00000000000001000000011001001000

4 25 8

27

Byte 0

Byte 0

Byte 0

Tag ou rtulo

Byte 0

Byte 1

Byte 1

Byte 1

Byte 1

Byte 63

Byte 63

Byte 63

Byte 63 ...

...

...

... Linha 0

Linha 1

Linha 2

Linha 1023

00000000000001000000011001001000

4 25 8

Byte 0Byte 1Byte 63 Byte 84 Linha 25

Mapeamento Direto - 05 Se o campo tag do endereo for igual ao campo

tag da linha da cache, o contedo do byte solicitado enviado para o processador

28

Mapeamento Direto - 06 Se os campos tag forem diferentes, isso significa

que o bloco desejado no se encontra na cache e, portanto, deve ser transferido da MP para a linha 25, substituindo o atual bloco para, em seguida, a palavra (o byte) requerida ser transferida para o processador pelo barramento de dados

29

Mapeamento Direto - 08 A tcnica de mapeamento direto simples e de

baixo custo Desvantagem: fixao da localizao para os

blocos Imagine se durante a execuo de um programa um

dado cdigo fizer referncias repetidas a palavras situadas em blocos alocados na mesma linha, ento haver necessidade de sucessivas idas MP para substituio de blocos (muitas faltas) e queda no desempenho do sistema

30

Mapeamento Associativo - 01 Os blocos no tm uma linha fixada previamente

para seu armazenamento O bloco armazenado em uma linha que

selecionada de acordo com o algoritmo de substituio de cache

31

32

.

.

.B 0

Byte 0Byte 1

Byte 63

.

.

.

Byte 0Byte 1

Byte 63

B 1

.

.

.

Byte 0Byte 1

Byte 63

B 226 -1

.

.

.

Byte 0

Byte 0

Byte 0

Byte 0

Byte 1

Byte 1

Byte 1

Byte 1

Byte 63

Byte 63

Byte 63

Byte 63 ...

...

...

...

.

.

.

Linha 0

Linha 1

Linha 2

Linha 1023

tag

Mapeamento Associativo - 02 Cada linha da MC pode acomodar um dos 226

blocos da memria principal O campo tag tem agora 26 bits de tamanho

33

Mapeamento Associativo - 03 Cada endereo de MP dividido nos

seguintes elementos:

34

Nmero do bloco Nmero do byte

26 bits226 blocos

6 bits26 bytes

32 bits

Mapeamento Associativo - 04 Quando o processador realiza um acesso

memria, o campo bloco do endereo comparado com todos os 1024 tags da cache para verificar se o bloco est ou no presente

35

Mapeamento Associativo - 05 Se o bloco estiver presente, o byte transferido

para a CPU seno o endereo do bloco usado para buscar na memria principal o bloco ausente

36

Mapeamento Associativo - 06 Desvantagem: teste do campo bloco do endereo

de memria com todos os tags da cache

37

Mapeamento Associativo por Conjunto de N Posies - 01 Esquema intermedirio entre o direto e o

totalmente associativo Nmero fixo de posies onde um bloco pode ser

armazenado na cache Cache associativa de n posies:

n posies possveis para cada bloco Cache com conjuntos de n posies Blocos mapeados diretamente em um conjunto e

colocado em qualquer elemento do conjunto

38

Bits de Validade Quando o processador inicializado, a cache

est vazia e os rtulos no tm significado Bits de validade so adicionados cache para

identificar se um bloco tem informaes vlidas Bit igual a zero -> Informao invlida

39

Tratamento de Faltas 01 Atividades do controle principal:

Parar o processador Congelar o contedo dos registradores

Um controle separado trata as faltas: Busca a informao necessria na memria Atualiza a informao na cache

Execuo retomada no ciclo gerador da falta

40

Tratamento de Faltas 02

1. Enviar memria o valor original de PC

2. Comandar uma leitura da unidade de memria e esperar o resultado

3. Escrever o resultado da leitura na entrada da cache, seu rtulo e bit de validade

4. Reiniciar a execuo da instruo no passo 1

41

Parada em Uso Tcnica para reduo do nmero de ciclos

parados pela falta no acesso cache Baseia-se no processamento de outras instrues

durante o tratamento de faltas Na falta produzidas pelo acesso a dados novas

instrues que no dependem do dado podem ser executadas

No ajuda para faltas no acesso a instrues Geralmente, no mostra ganhos expressivos pela

dependncia do dado sendo acessado

42

Algoritmos De Substituio De Cache - 01 Qual bloco atualmente armazenado na cache

deve ser retirado para dar lugar a um novo bloco que est sendo transferido? LRU (Least Recently Used): O controlador de cache

escolhe o bloco que est h mais tempo sem ser utilizado pela CPU

FIFO (First in first out): O controlador de cache escolhe o bloco que est armazenado h mais tempo na cache, independentemente de estar sendo usado ou no com freqncia pela CPU

43

Algoritmos De Substituio De Cache - 02

LFU (Least Frenquently Used): o controlador de cache escolhe o bloco que tem tido menos acessos (menos referncias) por parte da CPU

Escolha aleatria

44

Polticas de Escrita pela Memria Cache - 01 Quando o processador realiza uma operao de

escrita, esta acorre imediatamente na cache A memria cache uma memria intermediria

logo necessrio que a MP seja atualizada para que o sistema mantenha sua correo e integridade

45

46

Cache

Memria Principal

X = 1Y = 7Z = 2

X = Y + Z

X = 1Y = 7Z = 2

X = Y + Z

Bloco 4 Bloco 4

Processador

X = Y + Z

Antes da execuo da instruo X = Y + Z

47

Cache

Memria Principal

X = 9Y = 7Z = 2

X = Y + Z

X = 1Y = 7Z = 2

X = Y + Z

Bloco 4 Bloco 4

Processador

X = Y + Z

Depois da execuo da instruo X = Y + Z

48

Processador

CacheX = 1

Processador

CacheX = 1

ProcessadorX = Y + Z

cacheX = 9

MP X = 1

X = 9X = 9X = 9

Polticas de Escrita pela Memria Cache - 02 O bloco 4 (o valor de X) precisa ser atualizado na

memria Quando?

Depende da poltica de escrita

49

Write Through - 01 Cada escrita em uma palavra da cache acarreta

em uma escrita na palavra correspondente na MP, assegurando validade permanente e igual ao contedo de ambas as memrias

Caso haja outras CPUs, estas alteraro tambm suas caches

50

Write Through - 02 Simples, mas no favorece o desempenho Qualquer escrita faz com que a informao seja

escrita tambm na memria principal Aumento do nmero de ciclos de clock

Buffer de escrita: Armazena o dado enquanto este aguarda sua escrita na

memria Reduz o problema das escritas na mem. principal Buffer cheio Processador parado em escritas

51

Write Through - 03 Faltas de escrita:

Processador simplesmente atualiza a memria principal, como antes

No ocorrem leituras da memria principal durante a escrita pelo processador

52

Write Back Quando ocorre uma escrita, o novo

valor escrito apenas no bloco da cache O bloco s ser escrito na memria

principal quando ele precisar ser substitudo na cache

Pode melhorar muito o desempenho, porm mais complexo que o write-through

53

Tamanho do Bloco 01 Relaciona-se com a explorao da localidade

espacial e desempenho Em geral, a taxa de faltas cai com o aumento

do tamanho do bloco

54

Tamanho do Bloco 02 Taxa de faltas pode crescer se o bloco

representar uma frao considervel do tamanho da cache Pequeno nmero de blocos -> Alta competio Blocos retirados da cache sem muita explorao

55

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55