# Memória partilhada e coerência Barreiras, reduções paralelas, invalidação e falsa partilha de linhas de cache. Página: https://resumos.rgo.pt/cadeiras/ac/coerencia/ 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. ![Estado de uma linha com duas cópias limpas, escrita exclusiva do núcleo 1 que invalida núcleo 2, e leitura posterior que obtém a linha atualizada do proprietário dirty.](https://resumos.rgo.pt/cadeiras/ac/coerencia/figura-1.svg) 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. ## Exercícios Incluir a árvore Oito núcleos iniciam cada soma em zero e adicionam 16 elementos cada um; depois reduzem por pares 8→4→2→1. Uma adição custa ta; ignora barreiras/comunicação. Qual é o tempo total em unidades ta? Pista A fase local e a árvore são sucessivas. Solução 19 ta, porque cada ronda faz uma adição por participante ativo e o máximo de trabalho por núcleo na ronda é 1. Erros frequentes Dividir apenas 128 por 8 e esquecer a combinação. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/coerencia/#uma-redu%C3%A7%C3%A3o-paralela) Uma leitura de vizinho Linha(X, Y)=(5,8), limpa em ambos. N1 escreve X=9; N2 lê Y. No modelo dirty-owner→RAM da lição, descreve eventos e valor lido. Pista Invalidar não altera o valor de Y. Solução N1 fica (9,8), dirty, N2 inválida, RAM (5,8). N2 falha; N1 fornece (9,8) e atualiza RAM; ambas as cópias ficam limpas. A leitura Y devolve 8. Confere a tua resposta: * Invalidei a linha inteira no segundo núcleo. * Mantive Y=8 apesar da escrita X=9. * Expliquei a falta por falsa partilha e a transferência da linha. Erros frequentes Devolver 9 para Y ou manter N2 válida após a escrita. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/coerencia/#um-tra%C3%A7o-de-duas-palavras) Decodificar a palavra da linha Cache direta 4 linhas de 16 B; palavras 4 B. Que índice de palavra dentro da linha corresponde a 0xA6B8? Pista Os 4 bits baixos são o deslocamento. Solução Palavra 2. Índice de cache 3; etiqueta 0x29A. Escrever a palavra 0 dessa linha não muda a palavra 2. Erros frequentes Trocar índice de cache com posição da palavra. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/coerencia/#acesso-direto-etiquetas-e-v%C3%ADtimas) Coerência não torna uma atualização atómica Um contador começa em 0. Cada um de dois núcleos lê-o, soma 1 e escreve o resultado, em três operações separadas. Num modelo coerente e sequencialmente consistente, o resultado tem de ser 2? Justifica com uma ordem possível. Pista As escritas são ordenadas, mas cada atualização tem uma leitura anterior. Solução Não. Uma ordem possível é N1 lê 0; N2 lê 0; N1 escreve 1; N2 escreve 1. O valor final é 1. A coerência conserva as escritas e a consistência sequencial permite essa ordem; nenhuma torna as três operações indivisíveis. Usa uma operação atómica de incremento ou um mecanismo de exclusão mútua. Confere a tua resposta: * Mostrei os dois núcleos a ler 0 antes das escritas. * Expliquei como ambos podem guardar 1. * Indiquei uma operação atómica ou exclusão mútua para a atualização. Erros frequentes Supor que coerência ou uma barreira isolada torna automaticamente atómica a sequência ler, somar, escrever. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/coerencia/#coer%C3%AAncia-n%C3%A3o-%C3%A9-consist%C3%AAncia) Distinguir rondas de caminho crítico Dez somas parciais já estão prontas. Compara dois esquemas: A combina pares vizinhos e transporta a soma sem par; B combina metades e, com número ímpar, acrescenta a última soma ao participante 0 antes de combinar as metades restantes. Uma adição demora ta; ignora comunicação e barreiras. Indica rondas e tempo da redução em cada esquema. Solução A passa por 10→5→3→2→1: quatro rondas de ta, total 4ta. B passa por 10→5→2→1: três rondas, mas o participante 0 executa duas adições sucessivas na ronda 5→2. O caminho crítico custa (1+2+1)ta=4ta. Menos rondas não garante menos tempo. Confere a tua resposta: * Obtive quatro rondas transportando a soma ímpar. * Obtive três rondas incorporando a soma ímpar antes de reduzir. * Contei quatro adições no caminho crítico em ambos os esquemas. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/ac/coerencia/#uma-redu%C3%A7%C3%A3o-paralela)