Coerência de cache

Na arquitetura de computadores, a coerência de cache (ou consistência de cache) é a uniformidade (ou consistência) dos dados de recursos compartilhados armazenados em múltiplas caches locais. Em um sistema com coerência de cache, se vários clientes tiverem uma cópia em cache da mesma região de um recurso de memória compartilhado, todas as cópias serão iguais. Sem a coerência de cache, uma alteração feita na região por um cliente pode não ser percebida pelos demais, e erros podem ocorrer quando os dados utilizados por diferentes clientes são incompatíveis.^[1]

Um protocolo de coerência de cache [en] é usado para manter a coerência de cache. Os dois tipos principais são os protocolos de bisbilhotamento (ou snooping) e os baseados em diretório [en].

A coerência de cache é de particular relevância em sistemas de multiprocessamento, onde cada CPU pode ter sua própria cache local de um recurso de memória compartilhado.

Em um sistema multiprocessador de memória compartilhada [en] com uma memória cache separada para cada processador, é possível ter múltiplas cópias de dados compartilhados: uma cópia na memória principal e uma na cache local de cada processador que a solicitou. Quando uma das cópias dos dados é alterada, as outras cópias devem refletir essa alteração. A coerência de cache é a disciplina que garante que as alterações nos valores dos operandos compartilhados (dados) sejam propagadas por todo o sistema em tempo hábil.^[2]

A seguir estão os requisitos para a coerência de cache:^[3]

Propagação da Escrita

Alterações nos dados em quaisquer caches devem ser propagadas para outras cópias (daquela linha de cache) em caches pares.

Serialização de Transações

Cargas/escritas em um único local de memória devem ser vistas por todos os processadores na mesma ordem.

Teoricamente, a coerência pode ser realizada na granularidade de carga/armazenamento. No entanto, na prática, ela geralmente é realizada na granularidade dos blocos de cache (linhas de cache).^[4]

A coerência define o comportamento das leituras e das escritas em um único endereço.^[3]

Em um sistema multiprocessador, considere que mais de um processador armazenou em cache uma cópia do local de memória X. As seguintes condições são necessárias para atingir a coerência do cache:^[5]

1. Em uma leitura feita por um processador P em um local X que segue uma escrita do mesmo processador P em X, sem que ocorram escritas em X por outro processador entre as instruções de escrita e leitura feitas por P, X deve sempre retornar o valor escrito por P.
2. Em uma leitura feita por um processador P1 no local X que segue uma escrita de outro processador P2 em X, sem que ocorram outras escritas em X por qualquer processador entre os dois acessos e com a leitura e a escrita suficientemente separadas, X deve sempre retornar o valor escrito por P2. Essa condição define o conceito de visão coerente da memória. A propagação das escritas para o local de memória compartilhada garante que todos os caches tenham uma visão coerente da memória. Se o processador P1 ler o valor antigo de X, mesmo após a escrita por P2, podemos dizer que a memória é incoerente.

As condições acima satisfazem os critérios de Propagação da escrita (Write Propagation) necessários para a coerência de cache. No entanto, elas não são suficientes, pois não satisfazem a condição de Serialização de Transações. Para ilustrar melhor, considere o seguinte exemplo:

Um sistema multiprocessador consiste em quatro processadores — P1, P2, P3 e P4 —, todos contendo cópias em cache de uma variável compartilhada S cujo valor inicial é 0. O processador P1 altera o valor de S (em sua cópia em cache) para 10, após o que o processador P2 altera o valor de S em sua própria cópia em cache para 20. Se garantirmos apenas a propagação da escrita, então P3 e P4 certamente verão as alterações feitas em S por P1 e P2. No entanto, P3 pode ver a alteração feita por P1 após ver a alteração feita por P2 e, portanto, retornar 10 em uma leitura para S. P4, por outro lado, pode ver as alterações feitas por P1 e P2 na ordem em que são feitas e, portanto, retornar 20 em uma leitura para S. Os processadores P3 e P4 agora têm uma visão incoerente da memória.

Portanto, para satisfazer a Serialização de Transações e, consequentemente, alcançar a coerência de cache, a seguinte condição, juntamente com as duas anteriores mencionadas nesta seção, deve ser atendida:

• As escritas no mesmo local devem ser sequenciadas. Em outras palavras, se o local X recebeu dois valores diferentes A e B, nesta ordem, de quaisquer dois processadores, os processadores nunca poderão ler o local X como B e, em seguida, lê-lo como A. O local X deve ser visto com os valores A e B nessa ordem.^[6]

A definição alternativa de um sistema coerente é por meio da definição do modelo de memória de consistência sequencial [en]: "o sistema de cache coerente deve executar todas as cargas e armazenamentos das threads em um único local de memória em uma ordem total que respeite a ordem do programa de cada thread".^[4] Assim, a única diferença entre o sistema de cache coerente e o sistema sequencialmente consistente está no número de locais de endereço mencionados na definição (um único local de memória para um sistema de cache coerente e todos os locais de memória para um sistema sequencialmente consistente).

Outra definição é: "um multiprocessador é consistente em cache se todas as escritas no mesmo local de memória forem realizadas em alguma ordem sequencial".^[7]

Raramente, mas especialmente em algoritmos, a coerência pode se referir à localidade de referência. Múltiplas cópias dos mesmos dados podem existir em diferentes caches simultaneamente e, se os processadores puderem atualizar suas próprias cópias livremente, uma visão inconsistente da memória pode resultar.

Os dois mecanismos mais comuns para garantir a coerência são o bisbilhotamento e o baseado em diretório [en], cada um com suas próprias vantagens e desvantagens.^[8] Protocolos baseados em bisbilhotamento tendem a ser mais rápidos, se houver largura de banda da memória [en] suficiente disponível, uma vez que todas as transações são uma solicitação/resposta vista por todos os processadores. A desvantagem é que o bisbilhotamento não é escalável. Cada solicitação deve ser transmitida para todos os nós em um sistema, o que significa que, à medida que o sistema fica maior, o tamanho do barramento (lógico ou físico) e a largura de banda que ele fornece devem crescer. Diretórios, por outro lado, tendem a ter latências mais longas (com uma solicitação/encaminhamento/resposta de 3 saltos), mas usam muito menos largura de banda, uma vez que as mensagens são ponto a ponto e não transmitidas. Por esse motivo, muitos dos sistemas maiores ($> 64$ processadores) usam esse tipo de coerência de cache.

Ver artigo principal: Bisbilhotamento de barramento

Introduzido pela primeira vez em 1983,^[9] o bisbilhotamento é um processo em que caches individuais monitoram linhas de endereço em busca de acessos a locais de memória que elas armazenaram em cache.^[5] Os protocolos de invalidação de escrita e protocolos de atualização de escrita utilizam esse mecanismo.

Para o mecanismo de bisbilhotamento, um filtro de bisbilhotamento reduz o tráfego de bisbilhotamento mantendo uma pluralidade de entradas, cada uma representando uma linha de cache que pode pertencer a um ou mais nós. Quando a substituição de uma das entradas é necessária, o filtro de bisbilhotamento seleciona a substituição da entrada que representa a linha ou linhas de cache pertencentes ao menor número de nós, conforme determinado a partir de um vetor de presença em cada uma das entradas. Um algoritmo temporal ou de outro tipo é usado para refinar a seleção se mais de uma linha de cache pertencer ao menor número de nós, conforme determinado a partir de um vetor de presença em cada uma das entradas.^[10]

Em um sistema baseado em diretório, os dados compartilhados são colocados em um diretório comum que mantém a coerência entre caches. O diretório atua como um filtro por meio do qual o processador deve solicitar permissão para carregar uma entrada da memória primária para sua cache. Quando uma entrada é alterada, o diretório atualiza ou invalida as outras caches com essa entrada.

Sistemas de memória compartilhada distribuída [en] imitam esses mecanismos na tentativa de manter a consistência entre blocos de memória em sistemas fracamente acoplados.^[11]

Protocolos de coerência aplicam a coerência de cache em sistemas multiprocessadores. A intenção é que dois clientes nunca vejam valores diferentes para os mesmos dados compartilhados.

O protocolo deve implementar os requisitos básicos de coerência. Ele pode ser personalizado para o sistema ou aplicação de destino.

Os protocolos também podem ser classificados como de bisbilhotamento ou baseados em diretório. Normalmente, os primeiros sistemas usavam protocolos baseados em diretório, nos quais um diretório mantinha um registro dos dados compartilhados e dos compartilhadores. Nos protocolos de bisbilhotamento, as solicitações de transação (para leitura, escrita ou atualização) são enviadas a todos os processadores. Todos os processadores rastreiam a solicitação e respondem adequadamente.

A propagação da escrita em protocolos de bisbilhotamento pode ser implementada por um dos seguintes métodos:

Invalidação da escrita

Quando uma operação de escrita é observada em um local do qual uma cache possui uma cópia, o controlador de cache invalida sua própria cópia do local de memória rastreado, o que força uma leitura da memória principal do novo valor em seu próximo acesso.^[5]

Atualização da escrita

Quando uma operação de escrita é observada em um local do qual uma cache possui uma cópia, o controlador de cache atualiza sua própria cópia do local de memória rastreado com os novos dados.

Se o projeto do protocolo estabelece que sempre que qualquer cópia dos dados compartilhados for alterada, todas as outras cópias devem ser "atualizadas" para refletir a alteração, então é um protocolo de atualização de escrita. Se o projeto estabelece que uma escrita em uma cópia em cache por qualquer processador exige que outros processadores descartem ou invalidem suas cópias em cache, então é um protocolo de invalidação de escrita.

No entanto, a escalabilidade é uma deficiência dos protocolos de transmissão (broadcast).

Vários modelos e protocolos foram desenvolvidos para manter a coerência, como MSI [en], MESI (também conhecido como Illinois), MOSI [en], MOESI [en], MERSI [en], MESIF [en], write-once [en], Synapse, Berkeley, Firefly [en] e Dragon [en].^[2] Em 2011, a ARM Ltd propôs o AMBA 4 ACE^[12] para lidar com a coerência em SoCs. A especificação AMBA CHI (Coherent Hub Interface)^[13] da ARM Ltd, que pertence ao grupo de especificações AMBA5, define as interfaces para a conexão de processadores totalmente coerentes.

• Acesso não uniforme à memória (NUMA)
• Barreira de memória [en]
• Coerência baseada em diretório [en]
• Compartilhamento falso [en]
• Modelo de consistência [en]

• Patterson, David; Hennessy, John (2009). Computer Organization and Design 4th ed. [S.l.]: Morgan Kaufmann. ISBN 978-0-12-374493-7 
• Handy, Jim (1998). The Cache Memory Book 2nd ed. [S.l.]: Morgan Kaufmann. ISBN 9780123229809 
• Sorin, Daniel; Hill, Mark; Wood, David (2011). A Primer on Memory Consistency and Cache Coherence (PDF). [S.l.]: Morgan and Claypool. ISBN 978-1608455645. Consultado em 20 de outubro de 2017 
• Steinke, Robert C.; Nutt, Gary J. (1 de setembro de 2004). «A unified theory of shared memory consistency». Journal of the ACM. 51 (5): 800–849. ISSN 0004-5411. arXiv:cs/0208027. doi:10.1145/1017460.1017464