Multiprocessadores e Coerencia de Cache - Arquitetura de Computadores

Arquitetura de Computadores II Prof Leonel Tedesco leoneltedescouniscbr Multiprocessadores e coerência de cache Arquitetura de Computadores II Leonel Tedesco Slide 2 Motivação Aplicações científicas podem demorar muito para executar em um monoprocessador Previsão do tempo astronomia correntes oceânicas reações químicas são exemplos práticos Muitas dessas aplicações são caracteristicamente paralelas e compostas por laços que operam sem dependência de dados Essas aplicações podem ser mais eficientemente executadas em máquinas multiprocessadas Cada processador pode executar uma iteração de um dado laço que não possua dependência de dados Arquitetura de Computadores II Leonel Tedesco Slide 3 Motivação Muitos sistemas multiusuário precisam de mais poder computacional que um computador monoprocessado Sistema de venda de passagens aéreas servidor web de uma grande corporação etc Esses são bons exemplos de transações paralelas que operam em dados independentes Essas aplicações também são mais efetivas em ambientes multiprocessados onde cada operação pode ser executada em um processador diferente Arquitetura de Computadores II Leonel Tedesco Slide 4 Projeto de Multiprocessadores Como os processadores paralelos compartilham dados Multiprocessadores de espaço de endereço único Máquinas UMA Uniform Memory Acess e NUMA Non Uniform Memory Acess Troca de mensagens para comunicação Uso de memórias privadas Como processadores paralelos são coordenados Sincronização primitivas embutidas protocolos de SO Como são implementados Por um único barramento Através de uma rede Arquitetura de Computadores II Leonel Tedesco Slide 5 Classificação de Flynn Single Instruction Single Data Aplicações monoprocessadores Single Instruction Multiple Data Aplicações processamento de vetores Multiple Instruction Single Data Sem aplicações Multiple Instruction Multiple Data Aplicações multiprocessadores sistemas paralelos Arquitetura de Computadores II Leonel Tedesco Slide 6 Multiprocessadores e Multicomputadores Estes modelos se distinguem pelo uso da memória Memória comum compartilhada Memória não compartilhada distribuída Multiprocessadores de memória compartilhada Multicomputadores de memória distribuída Arquitetura de Computadores II Leonel Tedesco Slide 7 Organização de Multiprocessadores Multicomputadores Memória distribuída multicomputador Processadores possuem seu próprio espaçamento de memória Transferência de mensagens utilizado para acessar a memória de outro processador Múltiplas cópias de SO Programação mais complicada Mais escalável O sistema é composto por nós interconectados por uma rede de passagem de mensagem Cada nó é computador autônomo Memórias locais são privadas e acessíveis apenas pelo processador local NORMA NOnRemoteMemoryAccess Arquitetura de Computadores II Leonel Tedesco Slide 8 Multicomputadores de memória distribuída Rede com passagem de mensagem M P M P M P M P M P M P M P M P M P M P Arquitetura de Computadores II Leonel Tedesco Slide 9 Organização de Multiprocessadores Multicomputadores Memória compartilhada multiprocessador Todos os processadores compartilham o mesmo espaço de endereçamento Cópia única do sistema operacional Relativamente simples de programar e portar código sequencial Ex Máquina UMA Uniform Memory Access ou SMP Symmetric MultiProcessing Arquitetura de Computadores II Leonel Tedesco Slide 10 Multiprocessadores Compartilhamento de memória Os modelos dependem da localização e do acesso à memória UMA Uniform memory access NUMA Nonuniform Memory Access COMA Cache Only Memory Access Arquitetura de Computadores II Leonel Tedesco Slide 11 Uniform Memory Access Memória física é uniformemente compartilhada por todos os processadores O acesso por qualquer processador a qualquer posição de memória é feito em tempo uniforme Pode haver cache privada Dizse fortemente acoplado devido ao alto grau de compartilhamento P1 P2 P3 Pn Subsistema de comunicação crossbar barramento rede multiestágio IO MC1 MC2 MC3 Arquitetura de Computadores II Leonel Tedesco Slide 12 Nonuniform Memory Access O tempo de acesso a posições de memória não é uniforme para todas as posições e todos os processadores Normalmente a memória compartilhada ou parte dela é distribuída entre os processadores como memória local C O M U N I C A Ç Ã O P1 P2 P3 Pn ML1 ML2 ML3 MLn Arquitetura de Computadores II Leonel Tedesco Slide 13 Nonuniform Memory Access MGC MGC MGC SubSistema de Comunicação Global P P P ML ML ML Cluster 1 P P P ML ML ML Cluster N C O M U N C O M U N Arquitetura de Computadores II Leonel Tedesco Slide 14 Nonuniform Memory Access Três padrões de acesso a memória são observados Acesso a memória local Mais rápido Acesso a memória global Intermediário Acesso a memória remota Mais lento Arquitetura de Computadores II Leonel Tedesco Slide 15 Cache Only Memory Access Tratase de um caso especial do modelo NUMA onde as memórias distribuídas são substituídas por cache local Todas as caches formam o espaço de endereçamento global O acesso a caches remotas pode ser assistido por diretórios distribuídos Arquitetura de Computadores II Leonel Tedesco Slide 16 Cache Only Memory Access Subsistema de comunicação D C P D C P D C P Arquitetura de Computadores II Leonel Tedesco Slide 17 Memória Compartilhada Principais questões Coerência de cache assegurar que todos os stores para dados em cache sejam vistos por todos os processadores Sincronização a coordenação entre os processadores acessando os dados compartilhados Consistência de memória definição de quando um processador deve observar uma escrita feita por outro Arquitetura de Computadores II Leonel Tedesco Slide 18 Coerência de Cache Cache Coherence Problema Presença de caches privadas em multiprocessadores necessariamente introduz problemas de coerência de cache Descrição do problema Múltiplas cópias de mesma posição de memória podem existir em diferentes caches Cada processador atualiza sua cópia local não se preocupando com a existência de outras cópias em outros processadores Se essas cópias existirem cópias de mesmo endereço de memória poderão possuir valores diferentes Caracteriza uma situação de inconsistência de dados Arquitetura de Computadores II Leonel Tedesco Slide 19 Coerência de Cache Definição de coerência de cache Uma arquitetura multiprocessada com caches privadas é coerente se e somente se uma leitura de uma posição x de memória efetuada por qualquer processador i retorne o valor mais recente desse endereço Toda vez que uma escrita for efetuada por um processador i em um endereço de memória x tem que ser garantido que todas as leituras subseqüentes de x independentemente do processador forneçam o novo conteúdo de x Coerência de cache em multicomputadores Esse problema não ocorre Cada nó possui hierarquia de memória inteira Não existe espaço de endereçamento global compartilhado por todos Arquitetura de Computadores II Leonel Tedesco Slide 20 Coerência de Cache Alternativa para eliminar o problema Não permitir que dados compartilhados para operações de escrita sejam colocados nas caches do sistema Somente instruções e dados privados são cacheable Dados compartilhados são considerados noncacheable Operacionalização Compilador é responsável por colocar etiqueta tag nos dados Mecanismos de cópia de dados entre níveis de memória sabem quais dados devem ser repassados diretamente sem passar pelas caches ao processador Arquitetura de Computadores II Leonel Tedesco Slide 21 O Problema da Inconsistência de Dados Necessidade de consistência de dados É imprescindível que a implementação monoprocessada e a multiprocessada gerem o mesmo resultado para um programa Problema Quando dois processos compartilham mesma memória através de caches diferentes existe risco de uma posição de memória não possuir valor mais recente Causas mais comuns desse tipo de inconsistência de dados Inconsistência no compartilhamento de dados Inconsistência na migração de processos Inconsistência de ES Arquitetura de Computadores II Leonel Tedesco Slide 22 Inconsistência no Compartilhamento de Dados Descrição do problema P1 P2 e P3 possuem caches privadas Estes estão interconectados através de barramento a uma memória principal compartilhada Arquitetura de Computadores II Leonel Tedesco Slide 23 Inconsistência no Compartilhamento de Dados Descrição do problema P1 tenta ler u de sua cache Como u não está presente dado é lido da memória principal e copiado para sua cache P3 faz o mesmo gerando também cópia de u em sua cache Arquitetura de Computadores II Leonel Tedesco Slide 24 Inconsistência no Compartilhamento de Dados Descrição do problema P3 efetua escrita em u e altera conteúdo da posição de 5 para 7 Quando P1 efetuar uma leitura de u novamente ele receberá o conteúdo da posição u que se encontra em sua cache 5 e não o valor mais recente de u que é 7 Arquitetura de Computadores II Leonel Tedesco Slide 25 Política de Atualização de Cache Esse problema ocorre independentemente da política de atualização da memória principal Writethrough escrever através A cada escrita na cache a posição da memória principal é atualizada também A alteração de P3 teria sido repassada também à memória principal Não impediria P1 de ler o valor menos recente de u de sua cache Arquitetura de Computadores II Leonel Tedesco Slide 26 Política de Atualização de Cache Esse problema ocorre independentemente da política de atualização da memória principal Writeback escrever de volta A alteração de P3 teria apenas marcado o bloco de u na cache como sujo através de seu dirtybit A memória principal não seria atualizada imediatamente Somente em uma eventual substituição desse bloco na cache é que a memória principal seria atualizada Se P2 efetuasse uma leitura em u nesse meiotempo copiaria para sua cache o valor menos recente de u valor 5 Arquitetura de Computadores II Leonel Tedesco Slide 27 Inconsistência na Migração de Processos Descrição do problema Novo processo é escalonado devido a operação de ES Não existe garantia que este vá retornar sua execução no mesmo processador de uma máquina multiprocessada Escalonador associará processo a processador livre segundo sua política de escalonamento quando a operação de ES estiver concluída Muitas vezes o processo volte a executar em outro processador perdendo as informações de sua antiga cache Arquitetura de Computadores II Leonel Tedesco Slide 28 Inconsistência de Cache devido a Operação de ES Introdução ao problema Problemas de inconsistência de dados também podem ocorrer durante operações de ES outros componentes que não os processadores com DMA a memória principal Estas operações não se preocupam se os dados estão sendo compartilhados por vários processadores com cópias em diferentes caches Arquitetura de Computadores II Leonel Tedesco Slide 29 Inconsistência de Cache devido a Operação de ES Descrição Supondo atualização do valor x escrito na memória principal por writethrough Quando controladora de ES carregar dado x na memória principal ocorre inconsistência de dados entre x e as cópias nas caches dos processadores que possuem antigo valor x Supondo atualização de valor x com política de write back Quando valor x é lido da memória principal em operação de ES pode ocorrer inconsistência se valor atual das cópias de memória nas caches ainda não tenha sido substituído e portanto ainda não tenha sido copiado para a memória principal Arquitetura de Computadores II Leonel Tedesco Slide 30 Coerência de cache Duas escritas provocando incoerência CPU 0 cache CPU 1 cache main memory A A 1 CPU 0 lê bloco A CPU 0 cache CPU 1 cache main memory A A 2 CPU 1 lê bloco A A CPU 0 cache CPU 1 cache main memory A A 3 CPU 0 escreve no bloco A A Cópia desatualizada Do bloco A Arquitetura de Computadores II Leonel Tedesco Slide 31 Estratégias de Coerência de Cache Problema da coerência de cache resumese Existir simultaneamente múltiplas cópias de um dado o qual pode ser alterado sem que se faça algo em relação às outras cópias Estratégias básicas para tratar coerência de cache Escrita na cache resulta atualização de outras cópias desse dado nas demais caches writeupdate Escrita na cache resulta invalidação de outras cópias desse dado nas demais caches writeinvalidate Arquitetura de Computadores II Leonel Tedesco Slide 32 Estratégias de Coerência de Cache Vantagens e Desvantagens Invalidação tem custo menor mas maior latência de acesso caso as cópias invalidadas sejam novamente acessadas Necessita buscar da memória principal Atualização tem custo mais alto especialmente em máquinas com muitos processadores muitas cópias potenciais de mesmo endereço mas menor latência Novo acesso a cópias é resolvido em nível de cache Arquitetura de Computadores II Leonel Tedesco Slide 33 Estratégias de Coerência de Cache Questão Qual das estratégias resulta melhor desempenho para sistema como um todo Resposta Está diretamente ligado ao compartilhamento da carga de trabalho Ou seja o compartilhamento dos programas que executam na máquina Se processadores que estavam usando as cópias antes de serem atualizadas fizerem novos acessos a esses dados vale a pena o custo das atualizações Se processadores não utilizarem esses dados novamente o tráfego gerado pelas atualizações penalizou o sistema Neste caso a invalidação eliminaria as cópias antigas e acabaria com uma situação de compartilhamento aparente Arquitetura de Computadores II Leonel Tedesco Slide 34 Protocolos de coerência Snoopy Objetivo assegurar que blocos em cache que são atualizados devem ser vistos por todos os processadores Atribuir um bit de estado a todos os blocos de cache Definir ações para executar leituras e escritas de blocos em cada estado de modo a assegurar a coerência Arquitetura de Computadores II Leonel Tedesco Slide 35 Protocolos de coerência Snoopy São implementados nos controladores de cada cache Neste protocolo os controladores ficam monitorando o barramento para saber se eles possuem alguma cópia do bloco solicitado Assim as informações de compartilhamento do bloco são mantidas em cada cache Ideais para multiprocessadores baseados em barramento pelo fato de que o barramento compartilhado favorece o broadcast Arquitetura de Computadores II Leonel Tedesco Slide 36 Write invalidate MSI Protocolo de coerência que tenta assegurar a coerência atribuindo estados aos blocos de caches utilizados 3 estados disponíveis Modificado leituraescrita esse bloco de cache já foi escrito e não pode ser compartilhado Compartilhado Shared apenas leitura esse bloco está limpo e pode ser compartilhado A cache pode removêlo sem ter que escrever na memória Inválido O bloco deve ser buscado na memória ou em outra cache para ser acessado Bloco limpo possui mesma cópia que a memória principal Bloco sujo processador atualizou dado e agora é diferente da memória principal Arquitetura de Computadores II Leonel Tedesco Slide 37 Write invalidate MSI Ações em loads que resultam em coincidência Na cache local lê o dado Em caches remotas não fazer nada Ações em loads que resultam em falha Na cache local requisitar bloco que pode vir de memória ou outra cache definir o estado como compartilhado Na cache remota procurar se o dado está presente se está a cache deve sinalizar que possui uma cópia Se esse bloco estiver no estado modificado seu novo valor deve ser enviado Bloco passa para o estado compartilhado Arquitetura de Computadores II Leonel Tedesco Slide 38 Write invalidate MSI Ações em um store que resultam em coincidência Na cache local Se o estado do bloco é modificado permanecer com estado inalterado Se o estado é compartilhado mandar um sinal de invalidação para todas as caches remotas escrever no bloco e mudar o estado para modificado Nas caches remotas recebendo o sinal de invalidação procurar o bloco e invalidálo caso ele esteja presente Ações em um store que resultam em falha Na cache local requisita o bloco e manda o sinal de invalidação Após recebêlo muda o estado para modificado Nas caches remotas procura se o bloco está presente Se está presente sinaliza que o possui e muda o estado para inválido Se o estado do bloco for modificado seu novo valor é enviado Arquitetura de Computadores II Leonel Tedesco Slide 39 Exemplo MSI Processador 1 Cache Memória Processador 2 Cache Processador 3 Cache Processador 4 Cache P1 lê M1000 P1 escreve M1000 P2 lê M1000 P1 escreve M1000 P3 lê M1000 P4 escreve M1000 P2 lê M1000 M1000 Arquitetura de Computadores II Leonel Tedesco Slide 40 Exemplo MSI Processador 1 Cache Memória Processador 2 Cache Processador 3 Cache Processador 4 Cache P1 lê M1000 P1 escreve M1000 P2 lê M1000 P1 escreve M1000 P3 lê M1000 P4 escreve M1000 P2 lê M1000 M1000 Modified Arquitetura de Computadores II Leonel Tedesco Slide 41 Exemplo MSI Processador 1 Cache Memória Processador 2 Cache Processador 3 Cache Processador 4 Cache P1 lê M1000 P1 escreve M1000 P2 lê M1000 P1 escreve M1000 P3 lê M1000 P4 escreve M1000 P2 lê M1000 M1000 Shared M1000 Shared Arquitetura de Computadores II Leonel Tedesco Slide 42 Exemplo MSI Processador 1 Cache Memória Processador 2 Cache Processador 3 Cache Processador 4 Cache P1 lê M1000 P1 escreve M1000 P2 lê M1000 P1 escreve M1000 P3 lê M1000 P4 escreve M1000 P2 lê M1000 M1000 M1000 Modified M1000 Invalid Arquitetura de Computadores II Leonel Tedesco Slide 43 Exemplo MSI Processador 1 Cache Memória Processador 2 Cache Processador 3 Cache Processador 4 Cache P1 lê M1000 P1 escreve M1000 P2 lê M1000 P1 escreve M1000 P3 lê M1000 P4 escreve M1000 P2 lê M1000 M1000 M1000 Shared M1000 Shared Arquitetura de Computadores II Leonel Tedesco Slide 44 Exemplo MSI Processador 1 Cache Memória Processador 2 Cache Processador 3 Cache Processador 4 Cache P1 lê M1000 P1 escreve M1000 P2 lê M1000 P1 escreve M1000 P3 lê M1000 P4 escreve M1000 P2 lê M1000 M1000 Invalid M1000 Modified M1000 Invalid Arquitetura de Computadores II Leonel Tedesco Slide 45 Exemplo MSI Processador 1 Cache Memória Processador 2 Cache Processador 3 Cache Processador 4 Cache P1 lê M1000 P1 escreve M1000 P2 lê M1000 P1 escreve M1000 P3 lê M1000 P4 escreve M1000 P2 lê M1000 M1000 Shared M1000 Shared Arquitetura de Computadores II Leonel Tedesco Slide 46 Complicações do protocolo MSI Operações não são atômicas Por exemplo detecção de miss detém o barramento recebe uma resposta Cria a possibilidade de deadlock e condições de corrida Geração de invalidates sem necessidade Extensões Estado exclusivo para indicar bloco limpo em apenas uma cache protocolo MESI Se o bloco está neste estado ele pode ser gravado sem gerar nenhuma invalidação Owned state protocolo MOESI Indica que o bloco associado é de propriedade daquela cache e está desatualizado na memória cache proprietária do bloco é fornecedora Arquitetura de Computadores II Leonel Tedesco Slide 47 MESI Protocolo mais comum utilizado para coerência Assegura que quando uma cache quer escrever em um dado bloco o mesmo é invalidado em outras caches remotas Cada bloco de cache possui 4 estados Modificado M nenhum outro processador possui uma cópia memória principal possui cópia desatualizada Exclusivo E inicialmente nenhum outro processador possui uma cópia memória principal possui mesma cópia Compartilhado S outros processadores podem ter uma cópia memória principal possui a mesma cópia Inválido I conteúdo não é válido Vantagem gravação subsequente para um bloco no estado exclusivo pelo mesmo núcleo não precisa obter acesso ao barramento ou gerar uma invalidação Arquitetura de Computadores II Leonel Tedesco Slide 48 Protocolo MESI Ações em loads que resultam em coincidência Na cache local lê o dado Em caches remotas não fazer nada Ações em loads que resultam em falha Na cache local requisitar bloco Se este dado não está em uma cache remota ou seja está na memória principal usar estado exclusivo Caso contrário usar estado compartilhado Na cache remota procurar se o dado está presente Se está a cache deve sinalizar que possui uma cópia e marcar o bloco como compartilhado Se este mesmo bloco estiver no estado modificado seu novo valor deve ser repassado Arquitetura de Computadores II Leonel Tedesco Slide 49 Protocolo MESI Ações em um store que resultam em coincidência Na cache local checar o estado do bloco Se compartilhado mandar um sinal de invalidação para todas as caches remotas escrever no bloco e mudar o estado para modificado Nas caches remotas recebendo o sinal de invalidação procurar o bloco e invalidálo caso ele esteja presente Ações em um store que resultam em falha Na cache local requisita o bloco e manda o sinal de invalidação Após recebêlo muda o estado para modificado Nas caches remotas procura se o bloco está presente Se está sinaliza que o possui e muda o estado para inválido Se o estado deste mesmo bloco for modificado seu novo valor deve ser repassado