Caches e as suas "Especificidades"

[Rick Santos]

Introdução aos Caches:

Bem, hoje após um dia de trabalho ("Escola   hehe" ), decidi escrever algo relacionado com memórias cache (Sim MEMÓRIAS), portanto aqui vai. O título do artigo encontra-se entre aspas ("Especificidades") pois tenciono apenas apresentar, para os desconhecidos, o que é uma memória Cache, como funcionam, a sua presença e distribuição nos Processadores e como o seu bom ou mau uso podem afetar a performance de uma determinada rotina em desenvolvimento.

Antes de explicar em si o conceito de cache, pretendo ressaltar que um processador nunca acessa a memória diretamente, quer seja durante a busca ("Fetching") de dados ou instruções (Ambas diferentes). Querendo assim dizer que o Processador antes de chegar à memória terá de passar pelos caches existentes.

Uma cache nada mais é do que uma memória RAM dinâmica de altíssima velocidade e tamanho bastante reduzido presente nos processadores que tem, muito resumidamente, como função o armazenamento de uma CÓPIA dos dados presentes na memória. A partir da arquitetura de Processadores x86 é usualmente encontrado três "níveis" diferentes de memórias cache, denominadas: Cache L1, Cache L2 e Cache L3 (Durante o artigo referirei-me a elas por L1, L2, e L3), sendo possível encontrar em alguns processadores mais modernos uma Cache L4. É importante compreender que todos os caches existentes após o L1 não são considerados "úteis" para manter as instruções e dados provenientes da memória, veremos mais adiante o porquê. Podemos assumir, para fins didáticos, que o Cache L1 recebe os dados vindos do Cache L2 e este possivelmente do L3 (Possivelmente pois não é garantido a sua existência em todos os Processadores), o último nível de cache comunica-se diretamente com a memória enviando/recebendo dados da/para a mesma.

Tamanho dos Caches:

Como demonstrado na imagem adiante (se me lembrar de colocar ), o tamanho dos caches num processador pode derivar consoante o "modelo" (vá xD) dos mesmos, como tal, atualmente assumem-se intervalos de valores médios para tamanho destes.

Em processadores entre a "faixa" do Core 2 ao Core i7 o Cache L1 é o nível de cache mais interno ao Processador (Ou seja, mais próximo dos processadores lógicos da CPU, em cada núcleo)  que tem geralmente um tamanho de 64 KiB (veremos adiante que este se divide em 2, "cada um", obviamente, de 32 KiB). O Cache L2 é bem maior do que L1, tendo geralmente um tamanho entre 256 KiB e 16 MiB, este encontra-se no meio do cache L1 e, se houver, do cache L3 (O nível de cache mais próximo da memória) que pode ter um tamanho de 8 MiB a 32 MiB, ou mais.

Volto a referir que o Cache L1 é dividido em 2 "sub-níveis" de cache diferentes, chamados, L1d e L1i ('d' de Data e 'i' de Instructions). Basicamente L1d (32 KiB) trata de armazenar CÓPIAS de dados (Data) provenientes da memória, enquanto L1i (32 KiB) de Instruções. Em geral, devemos focar a nossa atenção durante o desenvolvimento de uma rotina para L1d que contém cópias dos dados da tarefa em questão.

Estrutura e Funcionamento de um Cache:

Nas arquiteturas de Processadores x86_64 e i386 o cache armazena as cópias da memória em Linhas. Na Cache L1 existem 1024 linhas num todo (512 Linhas para L1d e outras 512 para L1i, respetivamente), onde cada uma destas tem um tamanho padrão de 64 Bytes (Sim BYTES). Estas linhas são as unidades fundamentais para o funcionamento de um Cache, tendo cada uma delas propriedades que serão abordadas a seguir.

Quando falamos sobre Linhas de um cache, deparamo-nos logo com a sua propriedade associativa (Cujo em nada se relaciona com a propriedade aritmética da matemática), assim uma linha de 64 Bytes é composta por 4 associatividades/associações, ou seja caminhos diferentes (4 ways-associativity), com 16 Bytes de tamanho cada. Daí existir aquela prática por parte dos compiladores de alinhar pontos de entrada de uma Função ou de um Loop de 16 em 16 Bytes, assim conseguindo com que uma Função ou Loop caiba por inteiro numa associatividade (Ou até Linha!) não cruzando uma fronteira entre estas, o que levaria a um duplo acesso ao cache L1i (Cache de Instruções) e por conseguinte a um maior gasto de Ciclos de Clock (Perda de Performance). Isto quer dizer que não é à "toa" que tanto a Intel quanto a AMD (Não será "EMD" com algum engano hehehe??? (Esqueçam, é apenas uma brincadeira que tenho com um amigo) recomendam nos seus manuais o alinhamento de 16 em 16 bytes. E REPAREM que 16 Bytes equivale a exatamente 128 Bits, o que quer dizer que um conteúdo de algum Registador SIMD (Single Instruction, Multiple Data), que tem 128 Bits (16 Bytes), pode ser perfeitamente armazenado por completo numa linha, o que permite uma maior performance. Desta maneira o conceito "Localidade Espacial" de um Cache estará a ser respeitado, isto quer dizer, manter os dados relacionados o mais próximo possível entre si para garantir que não existirão múltiplos acessos porque um dado ou instrução "transbordou" a fronteira. Existe ainda um conceito relacionado aos dados chamado "Localidade Temporal", que será adiante descrito.

Ainda falando das associatividades dos Caches, observem um exemplo prático que pode ser cuidadosamente calculado pelo programador durante o desenvolvimento de uma rotina:

struct ways_example {
    int x[4];
    int y;
    char w;
    int v[3];
} data;

Neste simples código escrito em C (RESSALTO com toda a certeza, LINGUAGEM REI, asseguir ao Assembly ), temos uma estrutura de dados com 33 Bytes de tamanho que é composta por uma Array de (4*4 Bytes) 16 Bytes, representado pelo símbolo 'X', um dado do tipo inteiro, 4 Bytes, representado pela letra 'Y', por um dado do tipo char, de 1 Byte, representado pelo símbolo 'W' e finalmente por uma Array 'V' de (3*4 Bytes) 12 Bytes. 

Considerando uma linha (64 Bytes) do cache L1d, podemos concluir que:

A array de 4 inteiros, ou seja 'X', tendo 16 bytes ao certo caberá numa associação (Way) perfeitamente sem cruzar a fronteira com uma outra.

Após uma associação de 16 Bytes preenchida temos espaço numa outra para 'Y' (4 Bytes) e 'W' (1 Byte) ficando assim ocupados 5 Bytes da respetiva associação.

O problema agora vem com a Array de 3 inteiros 'V' (12 Bytes), que se ao armazenarmos uma cópia de char na associação do cache que já tem 5 Bytes ocupados por 'Y' e 'W', esta ficaria com 6. Isto quer dizer que 'V' (12 Bytes) não irá caber com completo numa associação da respetiva linha, pois terão de ser ocupados num todo 17 Bytes. Neste caso, é necessário para trabalhar com a Array 'V' dois acessos ao cache (Cada um em associações distintintas pois 'V' ultrapassou a fronteira), assim levando a um maior gasto de Ciclos de Clock e performance.

Reparem que para resolvermos este problema, basta alterara ordem da declaração das variáveis presentes na estrutura acima. Se declarar-mos "int v[3]" primeiro do que "char w', permite que 'V' caiba perfeitamente na associação que já contém Y, ficando assim, completamente preenchida. Em relação a 'W' (1 byte), este ficará, num todo, numa outra associação da linha o que quer dizer que caso seja acesso não terá de ter multiplicidade.

Segue a estrutura corretamente optimizada para uma melhor performance de caches, respeitando o máximo o conceito "Localidade Espacial":

struct ways_example {
    int x[4];
    int y;
    int v[3];
    char w;
} data;

Etiquetas/Tags:

Uma outra propriedade da unidade fundamental do cache (A linha!), são as Etiquetas ou "Tags". Numa linha de um cache, para além dos 64 Bytes que dados, existe também uma Tag, que armazena os bits superiores do endereço linear (Linear Address) dos dados na memória presentes na linha. Numa Tag (correspondente a uma linha), é indicada apenas os bits superiores do endereço linear dos dados da linha, sendo os outros 6 bits inferiores utilizados para obter o deslocamento e o caminho de um determinado dado presente na mesma. (2^6 = 64 Bytes).

Isto quer dizer, basicamente, que o Processador sempre que quiser acessar algum endereço de memória procurará sempre nas linhas do cache se existe alguma Tag correspondente ao endereço em questão. Caso o endereço solicitado for encontrado numa linha da cache, dá-se um algo chamado "acerto de cache", mais comummente chamado "Cache Hit". Por outro lado, caso o endereço solicitado não corresponder com nenhuma Tag da linha, dá-se algo chamado "perda de cache", vá fiquemos pelos nomes ingleses , "Cache Miss", e isto fará com que o processador copie a "Linha" da memória para o cache para assim, nos futuros acessos, não ter de requisitar novamente a memória.

Estados de uma Linha e o Protocolo MESI

Antes de explicar propriamente dito os estados de uma linha, acho importante dizer que quando o processador acessa uma linha, fará isso de acordo com o seu Estado.

Basicamente o Estado de uma Linha é uma outra propriedade que esta tem. Para explicar e aplicar estes estados foi desenvolvido um protocolo que tem como objetivo preservar o conceito "coerência de uma cache", isto é, impedir possíveis conflitos gerados por dados (L1d) partilhados por múltiplos caches locais (Como acontece por exemplo durante o uso de MultiThreading nos caches l1d). Este chama-se "MESI Protocol", de onde provêm os possíveis "Estados" que uma linha pode adquirir, como referido anteriormente (MESI = Modified, Exclusive, Shared e Invalid). Por agora vou apenas explicar os possíveis Estados que uma Linha de Cache se pode encontrar, mais adiante debruçar-me-ei um pouco sobre o Protocolo MESI e suas aplicações por parte da Intel e "EMD" (Ups! AMD ).

Para início de "conversa", é necessário compreender que um estado de uma linha de cache é exclusivamente mútuo, isto é, uma linha apenas pode ter um estado de cada vez. Para fins de escrita, irei-me referir ao estado Modified como M, Exclusive como E, Shared como S e Invalid como I.

Uma linha adquire o estado M, quando é realizado uma escrita (Write) de algum dado nesta, ficando assim uma "Linha Válida". Isto indica que a linha em questão foi modificada e que os dados prévios por conseguinte também, para além de de "Modified" outro nome para este estado é "Dirty", ou seja sujo, a linha ficou "suja" pois o processador escreveu "por cima" de alguma outra cópia de dados previamente armazenados nela.

Uma linha adquire o estado E, quando contém uma cópia de dados válida e única, isto é exclusiva. Se esse bloco de dados é exclusivo, significa que não existem esses mesmos dados numa outra cache l1d de todos os processadores lógicos da CPU, logo aquela linha adquire o estado "Exclusive".

Por outro lado, uma linha adquire o estado S quando contém uma cópia de dados já existente em pelo menos mais uma cache l1d. Logo essa linha é compartilhada ("Shared").

Finalmente o estado I (Invalid), indica que uma linha é inválida, ou seja vazia (Não está a ser usada no momento).

Com isto, surgiu um problema que fez com que as empresas fabricantes dos Processadores agissem criando assim o protocolo MESI, este problema foi a ocorrência de um "cache hit" numa linha cujo o estado era "Shared" (S), e de "Cache Misses" em linhas já previamente modificadas. As linhas partilhadas nos caches l1d possivelmente podem ser invalidadas, fazendo com que os outros caches l1d (pertencentes aos outros processadores lógicos da CPU) tenham de recarregar as linhas a partir de si. Para resolver este problema, deu-se a implementação do Protocolo MESI modificado.

MESIF/MOESI:

Já falei um pouco sobre o protocolo MOESI acima, agora vou falar um pouco sobre a sua modificação tanto por parte da Intel como da AMD.

Como tal, a Intel implementou uma modificação do protocolo original MESI chamada "MESIF Protocol", este protocolo na realidade apenas adiciona mais um possível estado em que uma linha de cache se pode encontrar, este é o estado F ("Forward"). O estado F, basicamente é um estado que substitui o estado S das linhas dos outros caches l1d, dizendo que já existe numa outra cache, uma linha com uma cópia de dados igual à do cache em questão e que essa linha encontra-se no estado M ("Modified").

Já a AMD, implantou uma modificação do protocolo MESI chamado "MOESI Protocol", onde surge um estado O ("Owned"). Este estado é idêntico ao F nas arquiteturas de processadores Intel, apenas utiliza a lógica oposta. Isto é, ele substitui o estado M para as linhas compartilhadas, deixando as restantes com o estado S.

Curiosidade: O próprio protocolo MESI, foi uma melhora de um anterior protocolo chamado "MSI Protocol", que apenas marcava 3 estados possíveis para uma linha de cache, Modified, Shared e Invalid.

Políticas de escrita em Caches:

Referente à escrita nas linhas do cache, existem certas políticas que devem ser seguidas, o processador decidirá como efetuar uma escrita de um bloco de dados numa linha dependendo da configuração desse bloco de dados (parte da memória) nos registadores MTRR (Memory Type Range Registers), ou então nas mais atuais PAT ("Page Attribute Table").

Basicamente ambas os métodos (MTRR e PAT) tem como fim definir como um determinado bloco de memória (região desta) deve ser "cacheado/a" (Durante o Power On da CPU), atualmente, maioritariamente em sistemas 64 bits, a PAT é mais utilizada do que os MTRR. A principal diferença entre estes, para além de um ser um conjunto de registadores e outro uma tabela, é que a PAT, ao contrário dos MTRR, permite manipular/definir página (4 KiB) a página da memória virtual como cada uma destas será "cacheada", enquanto por outro lado, o MTRR apenas permitem trabalhar nesse quesito com blocos de tamanhos fixos a partir de endereços físicos. Existem vários tipos de atributos que um "bloco" de dados pode ter, neste caso, só nos interessa principalmente dois deles, que são: Write Through (WT) e Write Back (WB).

Quando uma região de memória cacheada tem como atributo WT, o processador fará o mais rapidamente possível a escrita numa linha e manterá por pouco tempo o seu estado M ("Modified"). Por outro lado, quando uma região de memória cacheada tem o atributo WB, a linha do cache que armazena esses dados pode manter o seu estado M pelo tempo que quiser, e esta será "substituída" apenas quando necessário.

Prefetches em Caches:

Para finalizar (tenciono eu), se entretanto não me recordar de escrever mais alguma coisa relativamente importante aos caches, apresento-vos a técnica de prefetch de caches (Muitas das vezes realizada pelo processador automaticamente mas que também é (Ou pelo menos devia ser!) uma boa prática por parte dos "programadores" em casos bastante específicos).

Um Prefetch ("Pré-Carga") é uma técnica utilizada pelos Processadores de carregar (para um cache) previamente alguns dados da memória antes de estes serem usados, assim poupando tempo (ganhando performance) durante a execução de uma tarefa. Como referi anteriormente o processador já por si realiza prefetches de dados automaticamente, mas também é intressante que o programador em Assembly e até mesmo em C o faça. Para tal, existem várias instruções de Prefetch (Só irei falar de algumas).

OBS: Apesar de existirem excepções é bom compreender que a implementação de instruções de prefetch no nosso código maior parte das vezes é inútil e só nos traz uma tremenda perda de performance. Isto acontece pois estas instruções são totalmente dependentes da arquitetura e trabalham internamente com o algoritmo de "catching" do processador (Ele lá sabe o que faz! Não é preciso estragar! ).

A mais comum é instrução é a PREFETCHx (onde 0 ≤ x ≤ 2), ou seja 'x' dita a prioridade temporal de uma linha de cache que será pré-carregada com o valor apontado pelo ponteiro passado à instrução, sendo 0 a menos privilegiada e 2 a mais, isto quer dizer que quanto menor for 'x' mais facilmente uma determinada linha será "substituida".

Existe uma outra instrução de prefetch chamada PREFETCHW, cujo também tem como finalidade de pré-carregar uma cópia de um bloco de dados da memória para uma linha de cache mas desta vez avisando o processador que a qualquer momento pode surgir uma nova escrita na linha, neste ponto a linha em questão ainda se mantém no estado M.

Entre outras, existe uma instrução PREFETCHNTA, que ao pré-carregar dados para as linhas do cache marca a linha (de todos os níveis de caches) como não temporal. Isto quer dizer que aquela determinada linha será preservada pelo processador o máximo de tempo possível (Evitando substituições da mesma, etc...).

Eis um exemplo do uso da instrução PREFETCHx:

prefetch 0 [ebx]
prefetchw [esp-8]
prefetchnta [esp]

 

OBS: É possível em C, pedir ao gcc que utilize instruções de prefetching a partir da função "__builtin_prefetch ", cujo a descrição está fora do escopo do texto.

Finalização:

Bem, penso que após este extenso texto já tenha referido e introduzido aos leitores os conhecimentos fundamentais básicos que qualquer entusiasta da computação e do famoso "Low-Level" e estudo "arquitetónico" deve ter. Demorei umas horas, mas valeu a pena .

Ricardo Santos