Site menu Como funcionam os caches de memória
e-mail icon
Site menu

Como funcionam os caches de memória

e-mail icon

A memória RAM típica de qualquer computador comum moderno é muito mais lenta que o processador. Isso ocorre porque a RAM é construída com base em cargas de minúsculos capacitores - as chamadas "RAMs dinâmicas". É uma tecnologia barata, que permite memórias gigantescas em pequeno espaço físico, mas sua velocidade deixa a desejar frente aos processadores modernos.

Existe uma memória RAM cuja velocidade é compatível com os processadores. É a RAM estática, cujas células de memória são compostas por circuitos (flip-flops) semelhantes aos que se encontram dentro dos processadores. Porém, tal memória consome mais energia, é maior em tamanho físico, e muitíssimo mais cara por megabyte.

Assim como memória RAM é usada como cache do disco rígido, uma memória RAM estática pequena pode ser usada como cache da RAM dinâmica. É o que é feito em todos os processadores. De uns tempos para cá, o cache tem sido incluído dentro do processador, numa ligação íntima com o núcleo do mesmo.

O "milagre" de qualquer cache, seja de disco, memória ou acesso a Web, é explorar a localidade dos acessos. Resumindo: parte do princípio que um grupo relativamente pequeno de objetos será acessado mais freqüentemente que o resto. Isso é verdade para a maioria das aplicações. Basta ver quais os sites Web que você acessa mais freqüentemente, provavelmente não passam de meia dúzia.

Vou dar um exemplo bem mais prosaico: pessoas × banheiros. Se uma pessoa vive numa casa, essa casa precisa ter um banheiro. Porém, se 10 pessoas vivem lá, um número menor de banheiros atende a todas elas, porque elas dificilmente vão precisar usar o banheiro todas ao mesmo tempo. É claro, quanto mais banheiros melhor, é mais confortável e dá mais privacidade, mas três banheiros já atenderiam a 10 pessoas sem muito conflito.

Como as RAMs estáticas podem ser fabricadas em diversas velocidades, e a velocidade maior implica em custo maior, o cache de memória é hierarquizado em cache L1, L2 e eventualmente L3. Em geral o cache L3 é instalado fora do processador principal e não é algo comum em computadores pessoais.

O cache L1 é o mais próximo do núcleo do processador, e tem a maior velocidade possível, embora seja pequeno. O cache L2 é maior e um pouco mais lento.

Assim como o objeto "cacheável" de um proxy é um arquivo da Web, a menor unidade do cache de RAM é o cacheline ou linha de cache. Consiste de um punhado de bytes adjacentes da memória RAM principal, algo entre 32 e 128 bytes. O cacheline sempre é lido, gravado e invalidado em bloco, de forma indivisível.

O ideal para as aplicações é um cacheline pequeno, quanto menor melhor, pois mais exatas ficam as estatísticas de uso por pedaço de RAM. Mas isso aumenta o "custo" de administração do cache. O tamanho ideal do cacheline, que balanceia custo e boa localidade, varia muito conforme a aplicação. É bom lembrar também que o barramento de acesso entre processador e RAM está modernamente entre 8 e 32 bytes, e não faria sentido o cacheline ser menor que isso.

Um cacheline grande é mais eficiente do ponto de vista dos circuitos de cache e RAM. As RAMs dinâmicas modernas costumam apresentar uma latência grande para gravar o primeiro byte, mas um alto desempenho daí para diante. Assim, consome-se quase o mesmo tempo para gravar 1 ou 128 bytes. Isso também favorece o uso de cachelines grandes, pois o custo de cada transação é diluído.

O cacheline típico do IBM PC é 64 bytes, com a notória exceção do Pentium IV que usava 128 bytes. Esse último tinha desempenho muito bom em aplicações "mastigadoras de números", mas nem tanto para aplicações normais. O Pentium IV dependia de RAM dinâmica muito rápida (e cara) para dar performance, o que ajudou a derrubá-lo no mercado.

Nos "specs" de um processador, costuma aparecer a informação "4-way set associative L2 cache". Afinal, o que é isso? Bem, isso revela algo sobre o relacionamento entre o cache e a RAM principal.

Idealmente, qualquer cacheline deveria poder cachear qualquer pedaço da RAM principal, e de fato há caches com essa característica. São denominados fully associative ou completamente associáveis. Os caches L1 costumam ser assim, em relação ao cache L2.

Usando a comparação com banheiros, supondo um ambiente com 12 pessoas e 3 banheiros, qualquer das das pessoas pode usar qualquer dos banheiros. Estes seriam banheiros "completamente associáveis".

Embora seja desejável sob todos os aspectos, esse tipo de cache traz complexidade ao circuito, o que torna seu custo proibitivo a partir de certo tamanho.

O extremo oposto, extremamente simples e barato, é o direct-associative cache. Nesse tipo de cache, cada pedaço de RAM pode ser cacheado por um e apenas um cacheline. Existe uma associação direta entre cada pedaço de RAM e célula de cache, por isso o nome.

Supondo novamente 12 pessoas e três banheiros "de associação direta", a Maria, o João, o José e o Aroldo podem usar apenas o banheiro 1; outras quatro pessoas bem-definidas poderiam usar apenas o banheiro 2, e assim por diante. (Se João e Maria tiverem uma indigestão ao mesmo tempo, um dos dois terá de correr pra moita, porque o outro já ocupa o banheiro 1 que está alocado para eles.)

Para ilustrar o funcionamento do mesmo, imagine uma memória de 64kB de RAM, dividida em cachelines de 64 bytes. Isso dá 1000 pedaços. Imagine também um cache de 1Kb, ou seja, com capacidade de 16 cachelines.

Cada pedaço de RAM principal só pode ser cacheado por um determinado cacheline. Assim:

Cacheline 1: pode cachear os pedaços 0, 16, 32, 48, 64... da RAM
Cacheline 2: pode cachear os pedaços 1, 17, 33, 49, 65... da RAM
Cacheline 3: pode cachear os pedaços 2, 18, 34, 50, 65... da RAM
Cacheline 4: pode cachear os pedaços 3, 19, 35, 51, 66... da RAM
...
até o cacheline 16.

Talvez não fique imediatamente óbvio, mas alguns pedaços da RAM nunca poderão estar ao mesmo tempo no cache. Por exemplo, os pedaços 1 e 17 estão ambos associados ao cacheline 2. Se a aplicação ficar requisitando os pedaços na sequência 1, 17, 1, 17, 1, 17... o respectivo cacheline terá de ser invalidado e recarregado a cada acesso. O desempenho será bastante prejudicado.

Esta é a grande desvantagem desse tipo de cache. Se a aplicação apresentar um comportamento "patológico", ou seja, acessar os pedaços de RAM numa ordem azarada, o cache de associação direta não tem como explorar a localidade do acesso à RAM.

Para que o cache de associação direta seja efetivo, ele deve ser grande em relação à RAM. Ele costuma ser usado no nível L3, quando este existe, pois assim ele pode ser grande e barato.

Já nos caches 2-way set associative, 4-way, etc. os cachelines do cache são reunidos em grupos, ou "caminhos". No cache "4-way", há 4 caminhos, ou seja, 4 cachelines por grupo.

Usando mais uma vez a metáfora dos banheiros, imagine 12 pessoas e 4 banheiros. Juntamos os banheiros dois a dois, formando dois banheiros espaçosos. Alocamos 6 pessoas específicas para cada um dos dois banheiros, porém como cada banheiro tem duas "casinhas", até duas pessoas de um mesmo grupo podem usar o mesmo banheiro ao mesmo tempo.

Voltando ao nosso cache de exemplo, supondo que ele seja um cache 2-way set associative. Os 16 cachelines, agrupados de 2 em 2, ficam:

Grupo 1 (com 2 cachelines): pode cachear os trechos 0, 8, 16, 24...
Grupo 2 (com 2 cachelines): pode cachear os trechos 1, 9, 17, 25...
...
... até o grupo 8.

Agora os trechos 1 e 17 não são mais mutuamente excludentes. Se a aplicação acessar os pedaços de RAM na seqüência 1, 17, 1, 17, 1, 17... isso não vai mais quebrar o cache porque os dois pedaços podem ser acomodados no Grupo 2.

A aplicação continua tendo o "poder" de arrasar o cache adotando um comportamento propositadamente patológico, digamos, acessando as páginas 1, 9, 17, 25, 1, 9, 17, 25..., mas é bem mais improvável que uma aplicação normal vá apresentar um comportamento assim.

O número de caminhos não precisa ser uma potência de 2 para ser eficiente. O Pentium original tinha um cache L2 de 5 caminhos. Naturalmente, quanto mais caminhos, mais complexo fica o circuito. Alguns processadores ARM tinham caches de 32 caminhos, provavelmente pelo fato do seu cache ser pequeno, já que o ARM visa baixo consumo de energia. O comum em processadores atuais é 2 ou 4 caminhos.

e-mail icon