Fundamentos da Arquitetura de Computadores Memória Cache Prof. André Renato 1º Semestre / 2012 Memória Cache Vamos revisar alguns pontos importantes: ◦ O principal uso dos sistemas computacionais é para execução de programas; ◦ A velocidade do processador é bem maior do que a da memória principal; ◦ O processador precisa de dados da memória para realizar operações; ◦ Na maior parte do tempo, o processador fica ocioso, esperando o dado chegar da memória; Memória Cache Para que meu sistema computacional possa melhorar de desempenho é preciso tratar o ponto que está sendo o gargalo do processamento; Se eu entender como funciona a execução de um programa e como é o acesso à memória, eu vou conseguir melhorar o desempenho; Memória Cache O que acontece com um programa qualquer (Word, por exemplo) após ser iniciado pelo usuário? O estudo do fluxo de execução dos programas mostrou que eles podem ser divididos e executados por partes. Memória Cache Memória Cache Assim, os programas costumam executar um “pequeno” grupo de instruções várias vezes em diversos momentos; Foi elaborado então o princípio da localidade como forma de ajudar na melhoria do desempenho de execução dos programas; Memória Cache O princípio da localidade é uma tentativa de “prever” qual será a demanda futura da CPU por instruções do programa que estão na memória principal; Ele é divido em duas partes: localidade espacial e localidade temporal; Memória Cache A localidade espacial é baseada em uma das principais estruturas de controle de fluxo: a sequência; É muito comum que um programa seja composto por diversos comandos que devem ser executado um após o outro; Memória Cache Na hora da compilação, estes comandos são transformados em instruções de máquina que ficam próximas entre si; Assim, se um programa precisa de uma instrução que está na célula X da memória, é muito provável que em breve ele precise da instrução que está na célula X+1, X+2, X+3.... Memória Cache Sendo comum que um grupo de instruções seja executado mais frequentemente que os demais, é bem provável que após executar uma instrução T, em breve, o programa execute a instrução T novamente; Memória Cache Como tirar proveito do princípio da localidade? O projetista do sistema vai criar um elemento de memória intermediário entre CPU/MP, chamado de memória cache. Memória Cache Ele deve ter elevada velocidade e ser grande o suficiente para guardar partes do programa, aproveitando ao máximo o princípio da localidade e pequena o suficiente para não elevar muito o custo do sistema. Como vai funcionar o sistema? Memória Cache 1) Sempre que a CPU precisar de um informação (dado ou instrução), ela acessa a memória cache. 2) Se a informação estiver lá, é chamado de acerto de cache (cache hit) e ela é transmitida em velocidade compatível com a CPU. Memória Cache 3) Se a informação não estiver, é chamado de falha de cache (cache miss). A informação é então pedida à MP e enviada para a CPU. ◦ No entanto, não só a informação é pedida à MP, mas também as informações subsequentes, pressupondo que estas serão solicitadas mais tardes – princípio da localidade espacial. Memória Cache Memória Cache O desempenho do sistema só vai aumentar se a quantidade de hits for bem maior do que a quantidade de misses. Isto é necessário pois quando ocorre um miss há um gasto extra de tempo para trazer o conjunto de informações da MP para a cache e depois enviar para a CPU a informação inicialmente solicitada por ela. Memória Cache Estudos mostram que o índice de acertos (hit rate) deve ser de 80% a 99%; Ou seja, em pelo menos 80% dos casos, a CPU consegue encontrar a informação na memória cache; A taxa de acerto pode chegar a 100%? Memória Cache Tipos de memória cache: ◦ A mais usual é a cache de MP; ◦ Existe também a cache de disco: nela a cache funciona de maneira idêntica em relação aos dados que são buscado no disco, porém é utilizada uma parte da MP para fazer as vezes de cache do disco. Memória Cache Cache em múltiplos níveis: ◦ Os projetistas desenvolveram vários tipos de cache de MP, com características de velocidade e capacidade de armazenamento diferente, formando uma verdadeira hierarquia de memórias cache; ◦ São utilizadas memórias SRAM; ◦ As caches são divididas em níveis, sendo os primeiros níveis mais próximos da CPU. Memória Cache Cache nível 1 (L1): sempre localizada no interior do processador, muito rápida, pouca capacidade; Cache nível 2 (L2): localizada na placamãe. Atualmente os processadores já trazem consigo a L2 dentro do mesmo chip; Cache nível 3 (L3): existe apenas para poucos processadores, normalmente externa ao chip; Memória Cache CPU L1 L2 L3 MP Memória Cache Como a memória cache não poderá ter o mesmo tamanho da MP, surge uma questão? Onde colocar os dados que chegam para serem armazenados até que a CPU precise deles? O endereço da MP não serve mais como referência direta.... Memória Cache É preciso fazer uma associação entre os endereços da MP e as linhas da memória cache para que seja possível procurar por um informação lá. Em primeiro lugar, é necessário lembrar que a informação pedida pela cache à MP vem em blocos. Logo, a MP deve ser dividida não mais em células, mas em blocos de células. Memória Cache Bloco com 4 células Bloco com 8 células Memória Cache Mapeamento associativo: ◦ Neste modelo, cada bloco da MP pode estar em qualquer uma das linhas da cache, pois não há uma posição pré-definida; ◦ Por exemplo, o bloco 147 pode estar na linha 35 da cache. Em uma outra vez, ele pode estar na linha 102. ◦ Como saber qual bloco está em cada uma das linhas da cache? Memória Cache É preciso guardar em cada linha, além das informações provenientes da MP, uma marcação (tag) informando o número do bloco que está ocupando aquela linha. Linhas (quadros) tag Célula 0 Célula 1 Célula 2 Célula 3 Memória Cache Quando a CPU pede uma informação através de um endereço de MP, este endereço é dividido em duas partes: ◦ A primeira parte indica em qual bloco está a informação desejada; ◦ A segunda parte indica qual é a célula procurada dentro do bloco; Memória Cache O dispositivo que controla a cache verifica se em alguma das linhas existe um tag idêntico ao número do bloco pedido pela CPU; ◦ Se existir, a célula solicitada é obtida da linha da cache e entregue à CPU; ◦ Se não existir, a cache pega o bloco todo da MP e coloca-o em alguma linha que esteja disponível. Depois repassa à CPU a célula pedida. Memória Cache Mapeamento direto: ◦ Neste modelo, cada bloco da MP pode aparecer em apenas uma única linha da cache; ◦ Em outras palavras, existe um posicionamento prévio de onde cada bloco pode estar; ◦ Se o bloco não estiver na linha correspondente, ele não estará em mais lugar algum da cache; Memória Cache Imagine, por simplificação, que a cache possui apenas duas linhas; Blocos de números pares só poderão estar na linha 0 da cache, enquanto blocos ímpares só poderão estar na linha 1 MP tag blocos Memória Cache Para o que serve a tag? ◦ Para identificar qual dos blocos pares (ou ímpares) está ocupando aquela linha da cache. ◦ Vários blocos podem ocupar a mesma linha da cache, mas um mesmo bloco ou está na linha específica para ele ou não está na cache. ◦ Por isto, esta técnica é chamada de mapeamento direto. Memória Cache Na prática, os linhas da cache não estão designadas a apenas linhas pares e ímpares. Existirão vários grupos de blocos dependendo da quantidade de linhas da cache. Memória Cache MP tag blocos Memória Cache Como calcular tudo isso? Primeiro, é preciso lembrar que a função da cache é usar bem o princípio da localidade. Desta forma, as células da memória serão dividas em blocos. Memória Cache Se a memória tem MP bytes e cada bloco será composto por B bytes, a quantidade de blocos QB será: QB = MP/B Memória Cache Se a memória cache tem L linhas, isto significa que os blocos serão divididos em L grupos distintos. A quantida de blocos por grupo BG será: BG = QB/L Memória Cache A quantidade de bits que a tag precisa ter vai depender apenas da quantidade de blocos por grupo (BG). Bits = log2 BG Memória Cache Vamos a um exemplo prático: A memória principal de um computador possui 4Gbytes. A cache possui 1024 linhas, podendo armazenar 64 bytes de dados em cada linha. A quantidade de blocos é 4G/64 = 64M blocos. Memória Cache Como há 64M blocos ao todo na memória e existem 1024 linhas de cache, cada linha poderá conter 64k blocos (um de cada vez), pois: BG = QB/L BG = 64M/1024 = 64K Memória Cache O tamanho do tag será: Bits = log2 (64K) = 16 bits, pois 216 = 64K. Memória Cache Nesse sistema, um endereço de memória será composto por 32 bits, pois 232 = 4G. Quando a CPU pedir um dado na memória através de um endereço assim, como a cache saberá se tem o dado ou não? O endereço precisa ser dividido em pedaços para ser analisado. Memória Cache 16 bits Indica o número específico do bloco a ser buscado na linha da cache 10 bits Indica em qual das linhas da cache pode estar o dado buscado 6 bits Indica qual das células dentro do bloco é a requerida pela CPU Memória Cache Vamos imaginar que a CPU pediu à cache abaixo o dado através do endereço 0000000000001010 0010010010 001001 144 34 145 78 146 10 147 31 148 123 149 90 Memória Cache Mapeamento associativo por conjuntos: ◦ Esta técnica é uma mistura das duas anteriores: ◦ Agora, cada linha da cache pode conter mais de um bloco. ◦ O que vai acontecer é que diversos blocos (conjuntos) podem estar relacionados com a mesma linha. ◦ Quando a linha for descoberta, será preciso ainda analisar cada conjunto de blocos para saber se o bloco requerido está ou não na cache. Memória Cache quadro tag Linha 0 Quadro 0 Quadro 1 Quadro 2 Quadro 3 Linha 1 Quadro 4 Quadro 5 Quadro 6 Quadro 7 Linha 2 Quadro 8 Quadro 9 Quadro 10 Quadro 11 Linha 3 Quadro 12 Quadro 13 Quadro 14 Quadro 15 Memória Cache Para a cache funcionar corretamente ainda é necessário pensar no que acontece se a cache estiver “cheia”, ou seja, se for preciso trazer um dado da MP e colocar em uma linha da cache que já tenha um dado posicionado. Isto depende da técnica escolhida: ◦ No mapeamento direto, o novo dado só pode ocupar um único lugar. Logo, o dado antigo deverá ser substituído. Memória Cache No mapeamento associativo e no associativo por conjunto, será necessário escolher um bloco para ser retirado. Existem alguns critérios: ◦ LRU (least recently used) – o controlador da cache escolhe o bloco que foi utilizado há mais tempo. Este critério tem por base o princípio da localida temporal Memória Cache ◦ Fila – o sistema escolhe para ser retirado, o bloco que foi colocado primeiro na cache, independente do uso dele; ◦ LFU (least frenquently used) – o sistema escolhe o bloco que foi menos utilizado (acessado); ◦ Escolha aleatória: um bloco qualquer é escolhido independente de outros critérios; Memória Cache Um último ponto precisa ser levado em consideração: ◦ Estivemos sempre preocupados em como fazer para obter (ler) um dado da cache e repassar para a CPU; ◦ A memória, como vimos algumas vezes, permite que se façam dois tipos de operações: leitura e escrita; ◦ Quando a CPU precisar gravar um novo dado na MP, como isso acontecerá? Memória Cache Se o dado for salvo diretamente, sem passar pela cache, haverá um problema de consistência: ◦ Como assim? Se o dado for salvo apenas na cache, também poderá haver problemas. Qual a solução? Memória Cache Devemos levar em consideração dois fatores: ◦ A MP pode ser acessada tanto pela CPU quanto por componentes E/S. Um dado pode ter sido alterado na cache e não na MP (desatualizada). Um componente E/S pode ter alterado o dado diretamente na MP e não na cache (desatualizada). Memória Cache ◦ Uma mesma MP pode ser acessada por diversas CPUs, cada uma contendo sua própria cache. A alteração feita em uma cache deve ser refletida na MP e, consequentemente, nas demais caches. Existem alguma técnicas conhecidas para estes problemas. Memória Cache Escrita em ambas (write through): ◦ Cada escrita em uma palavra da cache resulta na escrita da palavra correspondente da MP. Se houver outras cache, elas também serão alteradas; Escrita somente no retorno (write back): ◦ Não faz atualização simultânea, mas somente quando o bloco for retirado da cache e se ele tiver sido alterado. Memória Cache Escrita uma única vez (write once): ◦ O bloco da MP é atualizado quando o bloco da cache for alterado pela primeira vez. Os demais componentes são alertados de que houve uma alteração e são impedidos de usar o dado. Outras alterações ocorrem apenas na cache e a MP só é atualizada quando o bloco sair da cache. Exercício