Hierarquia da Memória Caches 1 Hierarquia da memória Uma afirmação antiga, mas perfeitamente actual… “Ideally one would desire an indefinitely large memory capacity such that any particular word would be immediately available. We are forced to recognize the possibility of constructing a hierarchy of memories, each of which has greater capacity than the preceding but is less quickly accessible.” Burks, Goldstine & von Newmann (1946) 2 Hierarquia da memória Capacidade Chip do processador CPU Registos Cache Memória Principal Memória Secundária (RAM) (Disco) Rapidez de acesso Custo 3 Memórias Cache Introdução A memória cache é uma memória com pouca capacidade, mas rápida, tipicamente associada ao processador Esta memória guarda blocos de dados ou instruções copiados da memória principal (RAM) Uma vez na cache, o acesso aos valores guardados passa a ser muito mais rápido As caches tiram partido do carácter local das referências 4 Memórias Cache Carácter local das referências Espacial Se uma dada posição de memória foi acedida, é provável que posições de memória que lhe são vizinhas também venham a ser acedidas. os dados de uma matriz as instruções de um programa, etc Temporal Se uma dada posição de memória foi acedida, é provável que no futuro próximo seja acedida mais vezes. as instruções dentro de um ciclo do programa uma variável utilizada muitas vezes, etc 5 Memórias Cache Acesso à memória cache Quando é efectuada um acesso à memória, o CPU acede em primeiro lugar à cache Podem ocorrer duas situações: cache hit – os dados pretendidos encontram-se na cache caso ideal a taxa de hits deve ser tão alta quanto o possível cache miss – os dados não estão na cache nesse caso terão que ser lidos da memória principal substitui-se um bloco na cache pelo bloco copiado da memória principal onde estão os dados pretendidos pode introduzir penalizações temporais adicionais 6 Memórias Cache Exemplo: Suponha que o acesso à RAM requer 10 ns, ao passo que à cache requer apenas 1 ns. A percentagem de hits na cache é 90%, mas quando acontece um miss, o processador perde 1 ns adicional, para além dos tempos referidos. Qual será o tempo médio de acesso à memória? Tacesso = 0.9 1ns + 0.1 (10ns + 1ns + 1ns) = 0.9 + 1.2 = 2.1ns 7 Organização e tipos de cache Tipos de caches Cache directa (direct-mapped cache) Cache associativa completamente associativa (fully associative) associativa de n-vias (n-way set-associative) A organização interna varia consoante o tipo 8 Cache Directa Estrutura de uma cache directa Bit de validade Tag Linhas Bloco de dados 0 1 2 3 4 ... ... 9 Cache Directa Descrição A cache encontra-se organizada segundo linhas Em cada tem-se: Bit de validade Tag ou etiqueta Indica se o conteúdo dessa linha é válido ou não Identifica o bloco de memória de onde vieram os dados Bloco Conjunto de dados ou de instruções que foram copiados de posições consecutivas da memória 10 Cache Directa Estruturação de um endereço para acesso à cache Etiqueta Índice de linha Índice de palavra Indexa as palavras dentro do bloco 0 1 2 3 4 5 ... 11 Cache Directa Determinação de hit ou miss BUS Endereços Linha Tags Tag Dados Tag em cache Comparador hit / miss BUS Dados 12 Cache Directa Exemplo Quantas linhas terá uma cache directa com uma capacidade para 1 KByte de dados organizados por blocos de 128 Bytes ? N linhas 1 KByte 210 7 2 3 8 linhas 128 Bytes 2 Qual a estruturação dos endereços, admitindo um espaço de endereçamento de 64K x 1 Bytes 128 Bytes por bloco 7 bits p/ indexar os blocos 8 linhas 3 bits p/ indexar as linhas 64K 16 bits de endereçamento etiquetas de 6 bits (16–3–7=6) 6 bits 3 bits 7 bits Etiqueta Linha Palavra 13 Cache Directa Exemplo (cont.) Para que linha será carregado o blocos composto pelos endereços 1024 a 1151 (0x0400 a 0x047F)? Etiqueta Linha Palavra 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 ... 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 0x0400 ... 0x047F A linha será a 0. 14 Cache Associativa Completamente associativa Numa cache completamente associativa, um bloco poderá ocupar qualquer entrada na cache Não existe o conceito de linha Não ocupam posições “pré-determinadas” como nas caches directas Ou então pode considerar que existe um única linha, com capacidade para todos os blocos Só são utilizadas as tags e o índice de palavra Estruturação dos endereços Etiqueta Índ. palavra 15 Cache Associativa Completamente associativa (cont.) Mais complexa do que uma cache directa: Quando há um acesso, é necessário “procurar” o bloco em causa em todas as entradas da cache Se o bloco não for encontrado em nenhuma das entradas, então ocorre um miss Essa procura é feita em paralelo para todas as entradas da cache mais hardware (muitos comparadores) e apesar do paralelismo, são introduzidos atrasos 16 Cache Associativa Associativa de n-vias Este tipo de cache encontra-se a meio caminho entre uma cache directa e uma cache completamente associativa A ideia consiste em dividir a cache segundo linhas com lugar para n blocos Uma vez mapeado para uma dada linha, um bloco poderá ocupar uma das n entradas dessa linha 17 Cache Associativa Uma cache associativa de 2 vias Via 0 Via 1 ... ... 0 1 2 3 4 ... Estruturação dos endereços Etiqueta Índ. linha Índ. palavra 18 Políticas de substituição de blocos Quando ocorre um miss e a linha correspondente está ocupada, qual o bloco que deverá ser substituído na cache ? Principais estratégias: Escolha aleatória o bloco a substituir é escolhido de forma aleatória muito fácil de implementar Algoritmo LRU (Least Recently Used) o bloco a substituir é aquele que não é acedido à mais tempo, na esperança de já não voltar a ser necessário obriga a utilizar um “selo temporal” associado a cada bloco em cache estratégia mais complexa e mais cara 19 Políticas de substituição de blocos Alguma estatística Dimensão da cache Aleatório LRU 16KB 5.69 % 5.18 % 64KB 2.01 % 1.88 % 256KB 1.17 % 1.15 % % de cache misses durante a execução de um programa utilizando uma cache associativa de 2 vias com blocos de 16 bytes. Tabela retirada do livro “Computer architecture: a quantitative approach” Observações: O desempenho com LRU é melhor, principalmente em caches pequenas À medida que a dimensão da cache cresce, o desempenho da escolha aleatória tende a igualar o algoritmo LRU – preferível utilizar escolha aleatória 20 Políticas de Escrita O que acontece numa escrita ? Estratégias mais comuns, em caso de hit numa escrita Write through (ou store through) Os dados são sempre escritos tanto na cache como na memória principal. Write back (ou store in) Os dados são apenas escritos na cache. Só serão copiados para a memória depois do bloco em cache ser substituído. Utiliza-se um bit extra – dirty bit – em cada linha da cache, que indica se um dado bloco foi modificado desde que está em cache. Quando um bloco é substituído, se o seu dirty bit estiver a ‘1’, então esse bloco é copiado para a memória principal 21 Políticas de Escrita Write back Geralmente mais eficiente, pois causa menos acessos para escrita na memória principal Write through Mais simples de implementar Todas as escritas obrigam a aceder à memória principal Perde-se mais tempo… A memória principal tem sempre os dados actualizados Vantajoso em situações de partilha de memória com outros dispositivos (tanto periféricos como outros CPUs) 22 Políticas de Escrita Estratégias em caso de cache miss Write allocate (ou fetch on write) No-write allocate (ou write around) O bloco é carregado na cache, antes de se escreverem os dados O bloco não é carregado em cache. Apenas se escreve na memória principal. Normalmente utiliza-se write back em conjunto com write allocate write through em conjunto no-write allocate ... embora possam ser utilizadas outras combinações 23 Redução de misses Classificação de cache misses: Cold-start O primeiro acesso a um bloco que não se encontra em cache Acontece, por exemplo, no início da execução de um programa Colisões Vários blocos de um programa estão à partida destinados a utilizar a mesma linha da cache, o que pode obrigar a substituições. Acontecem porque: Os programas podem usar uma quantidade de memória superior à capacidade da cache Os programas podem referenciar zonas de memória diferentes que são mapeadas para a mesma linha da cache 24 Redução de misses Para reduzir a taxa de misses, a hipótese mais óbvia seria aumentar a capacidade da cache Mantendo a cache com a mesma capacidade, existem estratégias para reduzir os misses Aumentar a dimensão do bloco Usar um maior grau de associatividade (mais vias) Utilização de “caches vítimas” Optimizações do compilador (software) 25 Redução de misses Aumento da dimensão do bloco (mantendo a mesma capacidade da cache) Tenta-se tirar mais partido da localização espacial das referências Por um lado diminuem os cold-start misses, mas... ... aumentam os misses devido a colisões ... ... e perde-se mais tempo em caso de miss são necessários ler mais dados da memória principal devido ao bloco ser maior Atenção que o desempenho pode na realidade piorar quando se aumenta a dimensão do bloco! 26 Redução de misses Maior grau de associatividade Aumentando a associatividade reduzem-se os misses devido a interferências. Os restantes mantém-se. O preço a pagar é um maior tempo de acesso à própria cache, o que poderá ter implicações negativas Na prática, compensa aumentar a associatividade até certo ponto. Dimensão da cache 2 vias 4 vias 8 vias 16 KB 5.18 % 4.67 % 4.39 % 64KB 1.88 % 1.54 % 1.39 % 256KB 1.15 % 1.13 % 1.12 % % de cache misses durante a execução de um programa em função do grau de associatividade de uma cache (blocos de 16 bytes). Tabela retirada do livro “Computer architecture: a quantitative approach” 27 Redução de misses Utilização de caches vítimas Uma cache vítima é basicamente uma cache de dimensões muito reduzidas (4 a 8 entradas) A cache vítima contém blocos que foram substituídos na cache principal Para ser muito rápida Sempre que ocorre um miss na cache principal verifica-se se o bloco pretendido se encontra na “vítima” No caso de lá se encontrar, trocam-se os blocos entre as duas caches Esta técnica reduz de forma significativa os misses devido a interferências Não apresenta nenhuma desvantagem de maior, excepto o aumento do custo e um ligeiro aumento da penalidade devido a um miss completo (miss na cache principal e na vítima) 28 Redução de misses Técnicas de compilação Quando os programas (linguagem de alto nível) são traduzidos para código-máquina, o compilador poderá ter em conta a cache do processador Sendo assim, poderá gerar código-máquina que execute a mesma função, mas que tira partido das características da cache Manipular o modo de indexação das matrizes Trocas de índices em ciclos dentro de ciclos Fusões de ciclos etc. 29 Níveis de Cache Níveis de caches Abordagem comum para redução do tempo médio de acesso à memória Quando ocorre um miss no 1º nível, verifica-se se o bloco pretendido se encontra na cache de 2º nível (maior) e assim sucessivamente Só se acede à memória principal se não for encontrado o bloco pretendido em nenhum dos níveis Cache Nível 1 Cache Nível 2 Memória principal RAM CPU 30 Exemplo – Intel Core 2 Duo E6600 Caches nível 1 Cache nível 2 31 Exemplo – AMD Quad Core Opteron Caches nível 1 Caches nível 2 Cache nível 3 32 Hierarquia da Memória Memória virtual 33 Memória Virtual Espaço de endereçamento virtual Espaço de endereçamento que engloba a memória primária (RAM) e a secundária (disco) O objectivo é poder carregar múltiplos programas (e dados) sem estar limitado às dimensões físicas da memória RAM Cada programa a ser executado pode ter partes carregadas em RAM, em disco, ... ... ou em ambos os lados Transferem-se instruções e dados entre a RAM e o disco (swapping) consoante as necessidades 34 Memória Virtual Espaço de endereçamento virtual As formas mais comums para implementar memória virtual são Paginação Segmentação Misto (segmentação + paginação) A dimensão do espaço virtual corresponde ao número total de endereços que são indexáveis pelo processador Exemplo um processador com endereços de 32 bits consegue gera um espaço de endereçamento virtual de 232 posições de memória ou seja, 4 Giga posições de memória (para cada programa) 35 Memória Virtual Endereços reais Correspondem aos endereços físicos envolvidos no acesso à memória ou outros dispositivos (o que temos visto até agora) Endereços virtuais Endereços utilizados internamente pelo processador São convertidos em endereços reais através de uma unidade localizada no CPU, designada MMU (Memory Management Unit) e recorrendo a estruturas de dados, mantidas em memória 36 Memória Virtual MMU (Memory Management Unit) Converte endereços virtuais em endereços reais Assinala o CPU quando é feito um acesso a um endereço que fisicamente não se encontra localizado na memória principal CPU Memória RAM MMU Controlador de Disco Bus de endereços (reais) 37 Paginação Método mais comum para implementação de memória virtual O espaço de endereçamento virtual é divido em blocos de dimensão fixa designados por páginas. A dimensão de cada página é uma potência de 2 A memória principal é dividida em blocos com a mesma dimensão de uma página – estes blocos designam-se por molduras ou page frames 38 Paginação Espaço virtual 8000 RAM 4000 7000 3000 6000 2000 5000 1000 4000 0000 molduras 3000 Disco 2000 1000 0000 páginas 39 Paginação Tabelas de páginas (page tables) Endereço virtual Deslocamento Nº Página Tabela de páginas 0 Descritor da página 0 1 Descritor da página 1 2 Descritor da página 2 3 Descritor da página 3 N-1 Descritor da página N-1 Nº Moldura Deslocamento Endereço real 40 Paginação Principais campos num descritor de página Bit de presença – Indica se a página se encontra carregada na memória principal (RAM) ou não Moldura – Índice de moldura (page frame) – indica qual moldura onde se encontra a página Protecção – Bits de protecção da página (exemplo, read-only) Controlo – Bits auxiliares (por exemplo, para o funcionamento dos algoritmos de substituição de páginas) Descritor de página Índice da moldura Bit de presença Bits de controlo Bits de protecção 41 Paginação Exemplo 0010 0110 1010 0001 0x26A1 (9889) 0110 1010 0001 0x66A1 (26273) Tabela de páginas 0000 1 101 0001 0 xxx 0010 1 110 0011 0 xxx 0100 1 100 0101 1 111 0110 1 010 0111 0 xxx 1000 0 xxx 1001 0 xxx 1010 1 001 1011 0 xxx 1100 0 xxx 1101 0 xxx 1110 1 000 1111 1 011 110 42 Paginação Page fault Quando é acedida uma página que não se encontra na memória principal, ocorre uma page fault Quando o CPU recebe o sinal de page fault Efectuam-se as alterações necessárias na tabela de páginas, de modo a que esta fique consistente Se todas as molduras já estiverem ocupadas é necessário escolher uma página a transferir para o disco, nesse caso corre-se o algoritmo de substituição de páginas Normalmente a cargo do sistema operativo Carrega-se a página em falta (do disco para a RAM) 43 Paginação Algoritmos de substituição de páginas LRU (least recently used) NFU (not frequently used) descarta a que foi acedida menos vezes FIFO (first in, first out) descarta a que não é acedida à mais tempo descarta a que já se encontra em RAM à mais tempo Como são implementados pelo Sistema Operativo, terão mais detalhes nessa disciplina) 44 Paginação Tabelas multi-nível Usadas para evitar ter que manter em RAM tabelas de páginas com grandes dimensões Vantagem Existe uma tabela principal (1º nível) chamada directoria, relativamente pequena, e que é sempre mantida em RAM A directoria indexa várias tabelas de páginas (2º nível) que podem estar ou não na RAM, consoante a necessidade Só são mantidas na memória principal a directoria e as tabelas de páginas que estão a ser utilizadas Desvantagem Demora-se mais tempo a converter um endereço virtual em real, pois é necessário um acesso à directoria e depois um acesso à tabela de páginas resultante 45 Paginação Endereço virtual 10 bits 10 bits 12 bits TP_L1 TP_L2 Deslocamento Tabela de 1º nível (Directoria) Tabelas de 2º nível (Tabelas de páginas) 0 1 2 0 1 2 1023 1023 0 1 2 1023 Nº de moldura 0 1 2 Deslocamento Endereço real 1023 46 Paginação TLB (Translation Lookaside Buffer) Ao efectuar a conversão de um endereço virtual para endereço físico, é necessário de consultar a(s) tabela(s) envolvidas Como consequência, são feitos acessos à memória Para minimizar o número de acessos, existe a TLB Uma “cache especial” para auxiliar a paginação Tipicamente é uma cache completamente associativa, que guarda informação sobre os descritores de página Bit de validade Etiquetas (N de página) Blocos de dados (Descritores) 1 24 Descritor da página 24 1 56 Descritor da página 56 0 xxx xxx 1 3 Descritor da página 3 0 xxx xxx 0 xxx xxx os 47