Entendendo a coerência de cache

Antes de você começar a ler a coisa boa desse artigo deixe-me te dizer que a primeira coisa que deve ser pensada para garantir que uma função seja rápida não está relacionada ao comportamento do cache, com o sistema de paginação, com a contagem de ciclos de clock… O que importa, inicialmente, é o algoritmo usado. Refiná-lo até o ponto onde você acha que não pode melhorar é o primeiro passo. A partir dai você descobre que ainda tem muito a percorrer. O cache e os outros detalhes entram na jogada… Este artigo descreve, com algum detalhe, mas sem a profundidade que eu gostaria, o comportamento do cache…

Tanto aqui quanto no meu inacabado livro faço questão de ressaltar a importância dos caches quando estou falando de performance absoluta de rotinas. Já deve ser de conhecimento geral que o processador jamais acessa memória diretamente. Que ela é “cacheada” (se é que esse verbo existe) sempre! E o cache é uma memória RAM de alta velocidade, bem mais rápida que a memória RAM, dinâmica, instalada na sua placa-mãe. Nos processadores x86 modernos existem, pelo menos, três níveis de cache: L1, L2 e L3.

Para efeitos de explicação, considerarei, na maioria das vezes, que o cache L1 é o único que existe. Na prática, o cache L1 recebe seus dados do cache L2 e este do cache L3, se houver. O último nível de cache recebe/envia dados para a memória física…

Os níveis de cache:

O primeiro nível de “cacheamento” é dividido em dois: “dados” e “instruções”. Tanto dados quanto instruções têm de ser lidos da memória, certo? Desses dois, o que nos interessa mais é o cache de dados, chamado de L1D e ele  é excepcionalmente importante porque trata-se do acesso direto das unidades de execução às cópias de dados da memória física. A palavra importante aqui é “cópia”. Quando falamos de cache falamos de cópias de blocos de dados que se encontram na memória RAM do seu sistema.

A memória física está bem longe do primeiro nível de cache. O cache L1D está mais perto dos processadores lógicos. Entre ele e a memória temos os caches L2 e, possivelmente, o cache L3. Só então a memória física pode ser encontrada.. O cache L1D é pequeno, tendo apenas cerca de 32 KiB de tamanho. O cache L2 costuma ter uns 256 KiB e o cache L3, se houver, alguns MiB de tamanho (no meu sistema, 8 MiB). Os caches L1 e L2 costumam estar localizados no interior do processador. O cache L3 pode ser interno ou estar localizado numa memória estática, de alta velocidade, externa.

Estrutura dos caches:

Caches funcionam com unidades fundamentais de uma “linha”. Na arquitetura Intel (i386 ou x86-64), especialmente em processadores mais modernos, o tamanho dessa linha é de 64 bytes (ou 512 bits). O cache L1D é dividido em 512 linhas (para 32 KiB). É fácil calcular a quantidade de linhas dos outros caches, mas essas linhas sempre terão o mesmo tamanho.

Uma linha sofre outras divisões chamadas de “caminhos” (ways). Essencialmente, é uma divisão igualitária dos 64 bytes em blocos menores. Num processador com “associatividade” de 4 caminhos (4 ways associativity), temos 4 blocos de 16 bytes cada, o que é conveniente para conter o conteúdo de registradores para Streaming SIMD Extension (SSE). Aliás, este é o motivo pelo qual a Intel e a AMD recomendam que os pontos de entrada de funções e pontos de entrada de loops sejam alinhados de 16 em 16 bytes, para evitar duas leituras (do cache L1I), necessárias quando uma instrução cruza a fronteira de um caminho…

A associatividade só é importante se houver particionamento de informações dentro de uma linha. Se tentarmos ler/escrever dados que cruzem a fronteira de um caminho, alguma penalidade pode ser adicionada na execução de uma instrução. Para fazer um tuning fino do acesso ao cache, devemos evitar coisas como:

struct {
  int a[3]; /* a, b e parte de c cabem numa associação. */
  char b;
  int c;    /* Os byte final cabe em outra associação! */
} data;

Essa estrutura tem 17 bytes de tamanho e portanto cabe numa única linha, mas a variável c não cabe dentro de um único caminho. Para alterar o conteúdo de c devemos acessá-lo, no cache, duas vezes…

Outra informação importante é que cada “núcleo” do seu processador tem o próprio cache L1D. Note que falei cada “núcleo”, que tem tipicamente dois processadores lógicos. Assim, um cache é compartilhado por dois processadores lógicos o tempo todo. Isso causará penalidades se tivermos duas threads executando em dois processadores do mesmo núcleo…

Em uma linha, além dos 64 bytes de dados, temos duas outras informações: Uma “tag” ou “etiqueta”, que informa ao processador a qual região da “memória linear” a linha pertence. É importante ressaltar “memória linear” ao invés de “física” aqui, já que os sistemas operacionais modernos usam o recurso de “memória virtual” através de paginação.

Essa “etiqueta” contém apenas os bits superiores do “endereço linear”, já que os 6 bits inferiores serão usados para obter o offset do dado contido na linha (2^{6}=64). De fato, os quatro bits inferiores contém o offset e os dois bits seguintes o “caminho”.

Sempre que o processador queira acessar memória ele vai procurar nas linhas do cache L1D se existe uma etiqueta correspondente ao endereço solicitado. Se não houver temos um cache miss (dá pra ouvir a voz do Faustão dizendo “Errou!”) e o processador copiará a linha da memória e colocará no cache, para que as outras referências a esse bloco sejam feitas pelo cache, não pela memória do sistema, que é mais lenta.

Mas, se ao tentar acessar a memória uma etiqueta correspondente for encontrada no cache, temos um cache hit. Daí, o processador decide como acessar essa linha, de acordo com o “estado” em que ela se encontra.

Os estados das linhas de cache:

Além da “etiqueta” temos um campo de “estado” da linha. Existem 4 estados possíveis: Modified, Exclusive, Shared e Invalid (daí o nome do protocolo MESI). Esses estados são mutuamente exclusivos. Quero dizer, somente um deles pode estar sendo usado numa linha de cache a qualquer momento.

O estado mais óbvio é o I. Uma linha de cache inválida é uma linha “vazia”, que não contém uma cópia válida. Existem casos em que o processador decide “invalidar” uma linha, como veremos adiante.

O estado M ocorre quando há uma escrita numa linha válida. Indica que a linha sofreu alguma modificação e encontra-se num estado diferente do bloco de dados original, lido da memória. Outra designação para esse estado é “sujo” (Dirty). Ao escrever no cache o processador “sujou” a linha.

O estado E diz que a linha contém uma cópia válida e exclusiva. Ou seja, essa é a única cópia e não existem outras nos outros caches L1D associados aos outros processadores lógicos. O estado S é o contrário de E: ele diz que a linha é compartilhada (shared) em, pelo menos, dois caches L1D.

O protocolo MESI:

O diagrama abaixo mostra o protocolo MESI em algum detalhe (clique na imagem para ver de forma mais clara):

1024px-MESI_protocol_activity_diagram_1024

A cópia de blocos depende tanto do tipo de acesso (leitura ou escrita), quanto da capacidade de encontrar uma linha válida (cache hit, ou seja, “encontrei”, ou miss, “não encontrei”) e seu estado. O algoritmo acima explica muito bem o protocolo… Existe uma complicação quando temos um cache hit para escrita em linhas no estado S e em cache misses, quando tivermos outras linhas já modificadas. Linhas contidas em outros caches L1D podem ser invalidadas para manter a integridade dos dados, fazendo com que o processador lógico associados aos outros caches tenham que recarregar as linhas a partir do próprio cache. Para evitar isso, a Intel e a AMD resolvem implementar o protocolo MESI modificado.

No caso da Intel, ela usa o protocolo MESIF, com a adição de um estado Forward. Esse novo estado é um substituto para o estado S nos outros caches. Diz ao processador que a linha contendo os dados modificados está “adiante”, numa linha marcada com o estado M, em outro cache. Já a AMD usa o protocolo MOESI, onde o estado Owned (“proprietário” ou “dono”) faz praticamente a mesma coisa que o F, só que no sentido contrário: Ele substitui o estado M para linhas compartilhadas, indicando quem é o dono real da linha, deixando as demais, marcadas com S, intactas.

Não vou debulhar os protocolos MESIF ou MOESI aqui, basta saber que eles tentam acelerar um pouco a coerência dos caches, em ambientes multi threaded, evitando a invalidação de linhas e sua posterior recarga.

Por que o conceito do protocolo MESI é importante?

Se você realmente pretende lidar com multi threading terá que saber que um bloco de dados, que pode ser maior que uma simples variável, pode estar sendo compartilhada entre processadores lógicos e escritas podem causar penalidades na performance. Por isso, podemos querer evitar que linhas de cache adquiram estado S, mantendo-as exclusivas no ato da leitura. O problema de linhas em estado S é que eventualmente precisarão ser sincronizadas, como citei acima, e o processador vai gastar algum tempo para fazer isso.

Claro que alguma penalidade também pode ser percebida em escritas… Lembre-se que o que temos nos caches é uma cópia da memória física e, em algum momento, esses dados terão que ser “despejados” do cache. Da mesma forma que o processador deu uma “paradinha” para carregar uma linha, eventualmente ele terá que dar outra “paradinha” para copiá-la de volta para a memória.

Tipos diferentes de escrita:

O comportamento do processador com relação à escrita depende de como o bloco de memória física é configurado no power on (via MTRR – Memory Type Range Registers): Se a região da memória sendo cacheada é marcada como write through (“escrever através” [do cache]) o processador manterá o estado M por pouco tempo, fazendo a escrita o mais rapidamente possível. Este é o caso de I/O mapeada em memória, já que a maioria dos dispositivos de I/O é sensível à temporização de escrita…

Se a região é marcada como write back (“escrever por trás”), a linha em estado M pode ser mantida tanto tempo quanto for necessário neste estado até que precise ser usada para conter um bloco de dados de outra região. Neste caso, o processador copiará a linha atual e lerá outra, mudando o estado de M para E ou S, dependendo apenas se já existe ou não uma linha com a mesma etiqueta em outro cache. Ou seja, o processador só vai transferir a linha quando for absolutamente necessário…

Dicas de codificação para aproveitar o cache L1D:

O que se pode esperar de toda essa lenga-lenga?

  1. Evite compartilhar linhas de cache entre threads! Isso pode ser feito alinhando-se blocos de dados usados por threads diferentes de 64 em 64 bytes. Em C isso não costuma ser muito problemático, já que variáveis locais às threads costumam ser alocadas na pilha e cada thread tem sua própria pilha… O problema é o uso de variáveis globais por várias threads, que deve ser minimizado, mesmo porque, vale à pena evitar o sincronismo de threads;
  2. Evite usar blocos de dados muito grandes. Blocos de dados grandes geram dois problemas: Aumentam a pressão nos caches (muitas linhas terão que ser descartadas e outras, lidas) e pode colocar pressão no sistema de paginação se usarmos blocos maiores que 4 KiB. Se você tiver que trabalhar com blocos grandes, tente traduzi-lo em “pedaços”;
  3. De preferência, faça prefetches para garantir que os “pedaços” que você precisa que estejam no cache realmente sejam colocados lá de antemão.

Busca antecipada ou prefetches:

Para finalizar minha explicação sobre os efeitos do cache, devo falar sobre prefetches.

Prefetch pode ser traduzido livremente como “pré busca” ou “pré carga”, em inglês. É o ato de pré carregar um bloco de dados antes de manipulá-lo. O processador faz isso sozinho, quase sempre, mas é interessante fornecer “dicas” informando-o que, em certos pontos, ele deve fazer uma pré carga… Essas dicas são enviadas ao processador através de instruções PREFETCH e existem algumas delas.

Existe um outro campo escondido nas linhas de cache que especificam uma prioridade “temporal” para elas. As instruções PREFETCHTn (note o “Tn“) pedem ao processador para pré carregar uma linha de cache e atribuir uma prioridade entre 0 e 2, onde 0 é menos prioritária e 2, mais. Quando menor o valor, mais facilmente o processador pode “esquecer” a linha do cache.

Essas instruções são essencialmente inóquas em relação ao cache L1D e altamente dependentes de arquitetura. No Pentium III, por exemplo, a instrução PREFETCHT0 tendia a pré carregar uma linha no cache L1D, sempre. Do Pentium 4 em diante, o prefetch de leitura temporal é feito automaticamente pelo processador. Se for  realizar prefetch para leitura, prefira PREFETCHT0, mas saiba que o processador pode não respeitar seu pedido.

Já a instrução PREFETCHW é um pouco mais útil. Ela pede ao processador a pré carga no cache L1D e prepara o processador para uma escrita na linha. Isso não muda o estado da linha para M, mas literalmente faz o processador ficar com “orelha em pé”, esperando que em qualquer momento haja uma escrita.

A instrução de prefetch com maior prioridade é PREFETCHNTA. Ela marca a linha como “não temporal” (NT) em todos os níveis de caches (A, de “All”). O processador tenta manter a linha que tenha essa marca o maior tempo possível no cache L1D. Assim, ela será a última linha escolhida para substituição se o processador precisar de espaço. Claro que se você usar PREFETCHNTA para todo e qualquer acesso de seus dados, o sistema de prioridades não será de nenhuma valia… E o uso dessa instrução não significa que a linha nunca será liberada para outro uso. Ela só estará presente por mais tempo.

Anúncios