Memória partilhada e coerência

Dois núcleos guardam cópias da mesma linha. Quando um altera uma palavra, o outro não deve continuar a lê-la como se nada tivesse mudado. Um protocolo de coerência organiza as cópias; a sincronização coordena quando os núcleos podem consumir resultados. Estas duas tarefas são necessárias, mas distintas.

Uma redução paralela

Para somar 100 valores, dez núcleos somam dez elementos cada um. Com valores de 0 a 99, as somas locais são [45,145,245,345,445,545,645,745,845,945].

Uma redução por pares vizinhos pode transportar uma soma sem par à ronda seguinte:

Ronda	Somas ativas após combinar	Adições no caminho mais longo da ronda
Local	45, 145, 245, 345, 445, 545, 645, 745, 845, 945	10 por núcleo, a partir de zero
1	190, 590, 990, 1390, 1790	1
2	780, 2380, 1790	1, com 1790 transportado
3	3160, 1790	1
4	4950	1

São quatro rondas, cada uma com uma adição por participante ativo. Uma barreira faz os participantes esperar pelos resultados necessários antes da ronda seguinte. Sem ela, um núcleo poderia ler a soma anterior de outro. Uma implementação deve também evitar sobrescrever um valor que outro ainda precise de ler.

A ficha docente usa outro emparelhamento: combina a metade baixa com a alta e incorpora a soma ímpar no núcleo 0 antes de reduzir a metade restante. São dois algoritmos diferentes para a mesma soma, com custos diferentes por ronda.

Transição de participantes	Somas ativas depois	Máximo de adições num núcleo
10 → 5	590, 790, 990, 1190, 1390	1
5 → 2	2970, 1980	2 no núcleo 0
2 → 1	4950	1

Aqui são três rondas, mas o caminho crítico da redução continua a ter quatro adições. Na segunda, o núcleo 0 calcula $590+1390=1980$ e depois $1980+990=2970$. Com somas locais de dez adições, ambos os esquemas dão $14t_a$, ignorando comunicação e barreiras. Não substituas o tempo pelo número de rondas sem examinar o trabalho dentro de cada uma.

Com oito núcleos e 128 elementos, cada soma local usa 16 adições a partir de zero. A redução 8→4→2→1 acrescenta três tempos de adição: total $19t_a$. O vetor tem mais elementos e menos participantes, por isso não é uma comparação de rapidez para a mesma tarefa.

Coerência não é consistência

Coerência organiza leituras/escritas da mesma posição e propagação das escritas. Consistência define que ordenações de operações sobre posições diferentes os programas podem observar.

Um núcleo pode escrever dados=42 e depois pronto=1. Ver pronto=1 noutro núcleo não garante que uma leitura seguinte de dados veja 42: a coerência de cada linha não ordena acessos a posições diferentes. Usa as operações de sincronização exigidas pelo modelo de memória.

Também não torna uma atualização indivisível, ou atómica. Se dois núcleos leem um contador antes de qualquer um escrever, ambos podem calcular e guardar o mesmo incremento. Uma operação atómica ou exclusão mútua impede que outra atualização se intercale entre a leitura e a escrita. Uma barreira, por si só, só coordena fases.

Monitorizar e invalidar

Em snooping, caches observam as transações do interligador. Na política write-invalidate, um núcleo que escreve obtém autorização e invalida cópias da linha nos outros. Write-update, que difunde os novos dados, é outra opção.

Modelo do exemplo: caches WB, memória inicialmente atualizada; uma leitura externa de uma linha dirty faz o proprietário fornecer a linha e atualizar a memória, deixando as duas cópias limpas. Outros protocolos podem transferir o bloco sem atualizar imediatamente a memória, por isso usa o contrato indicado.

Um traço de duas palavras

Segue os valores de X e Y separadamente, mas validade e dirty referem-se à linha toda: uma linha tem duas palavras (X,Y), inicialmente (5,8), limpa nas caches dos núcleos 1 e 2 e na memória.

Operação	Cache1	Cache2	Memória e tráfego
N1 escreve X=9	(9,8), válida, dirty	Inválida	Memória fica (5,8); invalidação
N2 lê Y	(9,8), limpa	(9,8), válida, limpa	N1 fornece a linha; memória atualiza (9,8); leitura devolve 8
N2 escreve Y=11	Inválida	(9,11), dirty	Memória mantém (9,8); invalidação
N1 lê X	(9,11), limpa	(9,11), limpa	Transferência e atualização da memória; leitura devolve 9

Uma escrita em X não altera Y. Uma leitura de Y pode, contudo, precisar de obter a linha toda. Quando copias uma linha, conserva todos os seus elementos, não apenas a palavra que motivou o acesso.

Partilha verdadeira e falsa

Partilha verdadeira: um núcleo lê o valor que outro modifica. Partilha falsa: núcleos modificam ou leem palavras diferentes da mesma linha e sofrem invalidações por causa da granularidade do protocolo.

A falsa partilha não altera resultados, só gera tráfego: cada núcleo continua a ler e escrever os seus valores corretos, mas as linhas viajam entre caches a cada invalidação. Dois contadores independentes de 4 bytes numa linha de 64 B podem disputar essa linha a cada atualização. Separá-los em linhas diferentes pode reduzir tráfego; isso aumenta espaço e deve atender ao alinhamento real, porque dois contadores na mesma linha continuam a partilhá-la mesmo depois de os afastar alguns bytes.

Uma falta após invalidação não é apenas uma falta por conflito de índice. É uma falta de coerência. Identifica qual escrita invalidou a linha e se o acesso usa o dado modificado ou apenas um vizinho.

Acesso direto, etiquetas e vítimas

Para 4 linhas de 16 B com endereços 16 bits, etiqueta 10 bits, índice 2 e deslocamento 4. No endereço 0xA6B0, etiqueta=0x29A, índice 3 e palavra 0. 0xA6B8 tem a mesma etiqueta/índice, mas palavra 2.

Se a escrita em 0xA6B0 muda só a palavra 0, a posterior leitura de 0xA6B8 deve devolver a palavra 2 conservada. A invalidação atinge a linha 3 inteira. Reconstrói endereço e posição antes de seguir o protocolo, para não invalidares uma entrada errada nem devolveres a palavra errada.