5.7. Memória Cache

Como foi dito anteriormente, as memórias Cache vem tendo um papel cada vez mais importante nos sistemas computacionais. Inicialmente elas nem existiam nos computadores. Depois foram adicionadas fora do processador e em pequena quantidade. Em seguida elas foram levadas para dentro do processador e hoje em dia ocupam entre 60% e 80% da área do chip do processador.

O princípio básico das memória Cache é o de manter uma cópia dos dados e instruções mais utilizados recentemente (Princípio da Localidade) para que os mesmos não precisem ser buscados na memória principal. Como elas são muito mais rápidas do que a memória principal, isso traz um alto ganho de desempenho.

A Figura 5.4, “Funcionamento da Memória Cache” apresenta este princípio. Todo dado a ser lido ou escrito em memória pelo processador antes passa para a Cache. Se o dado estiver na Cache, a operação é feita nela e não se precisa ir até a Memória Principal. Caso contrário, um bloco inteiro de dados (geralmente com 4 palavras de memória) é trazido da Memória Principal e salvo na Cache. Só então a CPU realiza a tarefa com o dado.

Figura 5.4. Funcionamento da Memória Cache


Sendo assim, o desempenho do computador ao acessar um dado de memória é probabilístico. Para cada dado a ser acessado há uma probabilidade dele estar na memória Cache. Se isso ocorrer dizemos que houve um Cache Hit e o sistema ganha muito tempo com isso. Caso contrário, ocorre uma Cache Miss e o desempenho é bastante prejudicado. A grande questão é, como fazemos para aumentar a probabilidade de um determinado dado estar na memória Cache ao invés da Memória Principal? Podemos também refazer esta pergunta de uma forma mais geral. Como aumentar a taxa de Cache Hit (ou diminuir a taxa de Cache Miss)?

Há três principais estratégias para isso. São elas:

Vamos estudar como cada uma delas funciona.

5.7.1. Tamanho

A grande dificuldade das memórias Cache é que elas sempre estão presentes em menor quantidade do que a Memória Principal. Geralmente a Memória Cache de um computador é 1.000 vezes menor do que a Memória Principal. Se você tem um computador com 4GB de Memória Principal (não usa mais RAM para indicar este tipo de memória!), você terá muita sorte se seu processador tiver 4MB de Memória Cache.

Como a Memória Cache trabalha armazenando cópias de dados da Memória Principal, quanto maior for a Memória Cache, mais dados ela é capaz de armazenar, sendo assim, maior a probabilidade do processador buscar por um dado e ele estar na Cache. Entretanto, é importante observar que esse crescimento não é constante, muito menos infinito. Veremos a seguir que o ganho de desempenho com o aumento do tamanho da Cache possui um limite.

5.7.2. Função de mapeamento

A função de mapeamento diz respeito a estratégia utilizada para determinar onde cada dado da memória principal estará na Cache. Ela determina onde cada dado da Memória Principal será copiado na Cache caso ele seja acessado. Isso é muito importante porque o processador vai seguir essa mesma estratégia para conseguir localizar se o dado está, ou não na Cache. Há três tipos de mapeamento:

  • Mapeamento direto
  • Mapeamento associativo
  • Mapeamento associativo por conjunto

Mapeamento direto

Para entendermos a diferença entre os tipos de mapeamento, vamos fazer uma analogia com uma sala de cinema. Imagine que o cinema é a Memória Cache e cada pessoa é um dado a ser armazenado na memória. No mapeamento direto cada pessoa (sócia daquele cinema) receberá uma cadeira dedicada a ele. Sempre que ele for ao cinema, deverá sentar no mesmo lugar. O problema é que a Memória Principal é muito maior do que a Memória Cache, então não há cadeira para todos. Para resolver, cada cadeira é distribuída por várias pessoas, apostando que nem sempre as pessoas que compartilham o mesmo número de cadeira irão assistir ao mesmo filme no mesmo horário. Mas quando isso acontece, a pessoa que chegou por último não pode sentar em outra cadeira mesmo estando livre. A pessoa que chega depois toma o lugar da pessoa que está sentada, porque no caso da memória Cache, o último sempre tem preferência. Imagine quanta confusão isso geraria nesse cinema!

O bom do mapeamento direto é porque ele é muito fácil de organizar e a CPU encontra sempre seu dado muito facilmente. No exemplo do cinema, se alguém estiver querendo saber se uma pessoa está no cinema (na Cache) ou não (na Memória Principal) basta saber o número da cadeira dele e ir lá verificar se é ele quem está sentado. Isso acelera bastante o trabalho de busca da CPU. Mas se a memória Cache for muito menor que a Memória Principal, haverá muitos blocos com mesmo código e pode haver muito conflito de posição, reduzindo o desempenho.

Por exemplo, imagine uma Cache que armazena apenas 5 linhas (é o termo utilizado o local onde um bloco da Memória Principal é salvo na Cache), com numeração de 1 a 5. A Memória Principal será mapeada da seguinte forma, o bloco 1 será salvo na linha 1 da Cache, o bloco 2 na linha 2 etc. até o bloco 5 que será salvo na linha 5. Já o bloco 6 da memória será salvo novamente na linha 1 da Cache, o bloco 7 na linha 2, bloco 8 na linha 3 etc. Isso será feito até o que todos blocos da Memória Principal tenham uma linha a ser armazenada.

Agora suponha que os seguintes blocos da Memória Principal sejam acessados em sequência: 1, 5, 1, 10, 11, 5. Como será o mapeamento e quando ocorrerá Cache Hit e Cache Miss?

No início o bloco 1 é acessado mas ele não está na Cache, ocorre um Cache Miss e a cópia é salva. Então temos:

Cache hit: 0
Cache miss: 1

Posição da Cache: 1  2   3   4   5
Linhas na Cache:  1  -   -   -   -

Em seguida o bloco 5 é acessado. Ele não está na Cache, ocorre um Cache miss e uma cópia é salva na posição 5. Temos então:

Cache hit: 0
Cache miss: 2

Posição da Cache: 1  2   3   4   5
Linhas na Cache:  1  -   -   -   5

No terceiro acesso, o bloco 1 é buscado. Ele já consta na Cache. Enão ocorre um cache hit e a cache não precisa ser alterada. Ficando assim:

Cache hit: 1
Cache miss: 2

Posição da Cache: 1  2   3   4   5
Linhas na Cache:  1  -   -   -   5

Ao acessar em seguida o bloco 10 é acessado, como ele deve ocupar mesma posição do bloco 5 (isso porque 10 - 5 = 10), há um cache miss, o 5 é removido e substituído pelo 10.

Cache hit: 1
Cache miss: 3

Posição da Cache: 1  2   3   4   5
Linhas na Cache:  1  -   -   -   10

No próximo acesso o bloco 11 é buscado na posição 1 porque 11 - 5 = 6 e 6 - 5 = 1. Ele não é encontrado, mas sim o bloco 1. Há um cache miss e o bloco 1 é substituído pelo 11, resultado no seguinte:

Cache hit: 1
Cache miss: 4

Posição da Cache: 1  2   3   4   5
Linhas na Cache: 11  -   -   -   10

Por último, o bloco 5 é buscado novamente, mas o bloco 10 é quem ocupa esta posição. Há um cache miss e o bloco 10 é substituído pelo 5. Como resultado final, temos:

Cache hit: 1
Cache miss: 5

Posição da Cache: 1  2   3   4   5
Linhas na Cache: 11  -   -   -   5

Mapeamento associativo

No mapeamento associativo, o mecanismo de alocação de blocos da Memória Principal na Cache não segue posição fixa. Cada bloco vai ocupar a primeira posição vazia encontrada. Voltando ao exemplo do cinema, seria uma sala sem cadeira reservada, mas com um porém. Se uma pessoa chegar e o cinema estiver cheio, a direção do cinema (no computador é o Sistema de Memória) vai escolher uma pessoa a ser removida para dar lugar a nova pessoa que chegou (talvez alguém que estiver dormindo ou conversando durante o filme).

O mapeamento associativo termina sendo mais eficiente do que o mapeamento direto no momento de alocar blocos da memória na Cache. Só haverá espaço inutilizado se não houver acesso suficiente à Memória Principal. A desvantagem deste tipo de mapeamento está no momento de buscar um bloco na Cache. Imagine agora que alguém chegue no cinema cheio a procura de uma pessoa. Como encontrá-la? Será necessário percorrer todas cadeiras para verificar se a pessoa se encontra em alguma delas. Para o sistema computacional, essa busca é custosa o que resulta na utilização deste mapeamento apenas se a Cache não for grande demais.

Agora vamos voltar ao mesmo exemplo de acesso à uma memória Cache de 5 linhas para a mesma sequência de acesso: 1, 5, 1, 10, 11, 5. Como será o mapeamento associativo e quando ocorrerá Cache Hit e Cache Miss?

No início o bloco 1 é acessado mas ele não está na Cache, ocorre um Cache Miss e a cópia é salva. Sempre há cache miss nos primeiros acessos de um programa e eles são impossíveis de serem evitados. Então temos:

Cache hit: 0
Cache miss: 1

Posição da Cache: 1  2   3   4   5
Linhas na Cache:  1  -   -   -   -

Em seguida o bloco 5 é acessado e há novamente um cache miss, mas dessa vez vamos adicioná-lo na primeira posição livre que encontrarmos. Neste caso, na posição 2. Temos então:

Cache hit: 0
Cache miss: 2

Posição da Cache: 1  2   3   4   5
Linhas na Cache:  1  5   -   -   -

No próximo acesso ao bloco 1 há um cache hit porque o bloco 1 é acessado e ele já está presente na Cache:

Cache hit: 1
Cache miss: 2

Posição da Cache: 1  2   3   4   5
Linhas na Cache:  1  5   -   -   -

Em seguida o bloco 10 é acessado. Ele não está na Cache e ocorre um Cache Miss e ele é salvo na posição 3.

Cache hit: 1
Cache miss: 3

Posição da Cache: 1  2   3   4   5
Linhas na Cache:  1  5   10   -   -

No próximo passo o bloco 11 é acessado. Ele também não está na Cache e é salvo na posição 4.

Cache hit: 1
Cache miss: 4

Posição da Cache: 1  2   3   4   5
Linhas na Cache:  1  5   10  11   -

No último acesso o bloco 5 é acusado novamente. Como ele está na Cache, há um cache hit e a cache não é modificada.

Cache hit: 2
Cache miss: 4

Posição da Cache: 1  2   3   4   5
Linhas na Cache:  1  5   10  11   -

Perceba que ao final, o mesmo exemplo com Mapeamento Associativo teve 1 cache miss a menos do que o Mapeamento Direto, ou seja, ele foi mais eficiente para esse exemplo, já que precisou ir menos à Memória Principal mais lenta para trazer os blocos. Note também que a memória Cache permanece mais utilizada quando o mapeamento associativo é aplicado. Isso aumenta bastante a probabilidade novos cache hit.

Mapeamento associativo por conjunto

O problema do Mapeamento Associativo é encontrar blocos em memórias Cache grandes. A solução para isso é utilizar uma abordagem mista, que utiliza os princípios dos mapeamentos direto e associativo. Ela divide a memória em conjuntos. Cada bloco então é mapeado para um conjunto (semelhante ao que é feito para o Mapeamento Direto, mas para o nível de conjunto). Sempre que um bloco for ser buscado ou salvo, ele será feito no conjunto fixo dele, mas dentro do conjunto ele pode ser armazenado em qualquer posição livre.

Voltando ao cinema, é como se uma grande sala fosse dividida em salas menores. Cada pessoa teria no seu ingresso o número da sala, mas a poltrona seria escolhida livremente. Escolhendo a quantidade certa e o tamanho das salas, é possível utilizar bem os espaços e facilitar o processo de busca por uma pessoa.

5.7.3. Política de substituição

Nos mapeamentos associativo e associativo por conjunto uma outra política deve ser adotada. Quando a memória cache enche e um novo bloco precisa ser armazenado, o Sistema de Memória deve escolher que bloco deve ser removido para dar espaço ao novo bloco. No mapeamento direto isso não existe porque cada bloco sempre fica na mesma posição.

Sendo assim, há 3 principais políticas de substituição de linhas de Cache. São elas:

  • Randômica
  • FIFO
  • LRU

Na substituição randômica o sistema simplesmente escolhe aleatoriamente o bloco que deve ser removido. Ele sai da Cache dando lugar ao novo bloco que foi acessado. Este método tem a vantagem de ser muito fácil de implementar e, por consequência, rápido de executar. Porém ele pode não ser muito eficiente.

Já no FIFO (First-In First-Out) adota o princípio de fila. Aquele bloco que chegou primeiro, está há mais tempo na Cache. Já se beneficiou bastante e deve então dar lugar ao novo bloco.

No LRU (Least-Recently Used), ou “Menos Usado Recentemente” aplica o Princípio da Localidade Temporal e torna-se por isso mais eficiente na maioria dos casos. Nesta política o sistema escolhe o bloco que menos foi utilizado recentemente e o remove. Isso faz com que fiquem na Cache aqueles blocos que são acessados mais vezes nos últimos instantes.