O Problema de Coerência de Memória Cache em Sistemas

MultiprocessadosJunio Figueiredo e Wagner Silva Costa

Elaborado em Novembro/2011

Arquitetura de Computadores

Prof. Dr. Alisson Brito

1. Introdução2. Apresentação do Problema3. Como Resolver o Problema de Coerência de Cache4. Esquemas e Protocolos de Coerência de Cache

ObjetivosObjetivos

Pág. 2

5. Conclusão6. Referências Bibliográficas

Alunos: Junio e WagnerArquitetura de Computadores

Coerência:

Qualidade, estado ou atitude de coerente [Aurélio]

Coerência de Cache: É garantir qualquer processador sempre receba o dado

IntroduçãoIntrodução

Pág. 3

É garantir qualquer processador sempre receba o dado mais atual contido em qualquer cache para um mesmo endereço.

Alunos: Junio e WagnerArquitetura de Computadores

Problemas de coerência de cache aparecem maiscomumente em sistemas que possuem mais de umprocessador. [1]

Apresentação do ProblemaApresentação do Problema

Pág. 4 Alunos: Junio e WagnerArquitetura de Computadores

Apresentação do ProblemaApresentação do Problema

1. P1 realiza a leitura do dado X = 0. O dado é gravado na cache privada;

2. P2 realiza a leitura do dado X = 0. O dado é gravado na cache privada;3. P1 realiza X = X + 1. O dado X = 0 é lido da cache privada, e X = 1 é então gravado;

Pág. 5 Alunos: Junio e WagnerArquitetura de Computadores

então gravado;4. P2 realiza X = X + 3. O dado X = 0 é lido da cache privada, e X = 3 é então gravado.No passo 4, como P2 leu o dado X da cache privada, a alteração realizada por P1 no passo 3 não foi levada em conta; ocorre incoerência entre as caches devido à violação da condição chave acima.

1. Esquemas Simples:• Baseiam na limitação do tipo de dado que pode ir para a

Como Resolver o Problema de Como Resolver o Problema de

Coerência de CacheCoerência de Cache

Pág. 6

• Baseiam na limitação do tipo de dado que pode ir para acache, permitindo que apenas dados para leitura oumesmo dados não-compartilhados (privados aoprocessador) possam ser armazenados na cache.

Alunos: Junio e WagnerArquitetura de Computadores

2. Esquemas Baseados em Software e Hardware

• Esquemas de Sofware:

Como Resolver o Problema de Como Resolver o Problema de

Coerência de CacheCoerência de Cache

Pág. 7

• Esquemas de Sofware:Delega-se ao compilador ou ao sistema operacional aresponsabilidade de garantir a coerência. A vantagem dosesquemas baseados em software é evitar que um outrohardware seja necessário para realizar o tratamento doproblema de coerência.

Alunos: Junio e WagnerArquitetura de Computadores

2. Esquema Baseado em Software e Hardware

• Esquemas de Hardware:Detectam as condições de inconsistências, livrando

Como Resolver o Problema de Como Resolver o Problema de

Coerência de CacheCoerência de Cache

Pág. 8

Detectam as condições de inconsistências, livrando completamente o SO, compilador e o programador do problema de coerência de cache.

Alunos: Junio e WagnerArquitetura de Computadores

Esquemas de Coerência Baseados em Software:São mais baratos, porém pode exigir um esforço extra do Sistema Operacional , do Compilador e por parte do programador.

Esquemas e Protocolos de Coerência Esquemas e Protocolos de Coerência

de Cachede Cache

Pág. 9

Esquemas Implementados como parte do:Compilador (Rodam em tempo de compilação);SO (Rodam em tempo de execução);

São divididas em duas Soluções;�Estáticas�Dinâmicas

Alunos: Junio e WagnerArquitetura de Computadores

Esquemas de Coerência Baseados em Software:

Estáticas:

Esquemas e Protocolos de Coerência Esquemas e Protocolos de Coerência

de Cachede Cache

Pág. 10

� Resultam de ações realizadas durante a criação do programa, normalmente pelo compilador

Dinâmicas:

� São soluções feitas em tempo de execução, por isso são baseadas em ações do sistema operacional

Alunos: Junio e WagnerArquitetura de Computadores

Exemplos:

Esquemas e Protocolos de Coerência Esquemas e Protocolos de Coerência

de Cachede Cache

-Controle de Versão-Timestamp-Ultracomputer

Esquemas Estáticos

Pág. 11 Alunos: Junio e WagnerArquitetura de Computadores

-Coerência no Pedido de interrupção

- One-time IdentifierEsquemas Dinâmicos

Baseadosem

Software

Esquema de Coerência Baseados em Software

Controle Versão (Estáticas)

� Cada nova escrita de um dado compartilhado gera umanova versão de conteúdo. Os processadores incrementam onovo número a cada escrita que ocorra.[2]

Esquemas e Protocolos de Coerência Esquemas e Protocolos de Coerência

de Cache de Cache

Pág. 12

novo número a cada escrita que ocorra.[2]

� Para todo acesso ao dado compartilhado, os números da cache e o corrente processador são comparados.[3]

� Caso a versão do processador seja maior que o da versão na cache. O processador esta trabalhando com o Dado corrento.[1]

Alunos: Junio e WagnerArquitetura de Computadores

Coerência no Pedido de Interrupção (Dinâmicas)

� Solução que utiliza a mesma idéia de memória virtual.

Esquemas e Protocolos de Coerência Esquemas e Protocolos de Coerência

de Cachede Cache

Pág. 13

� Ao se detectar um page fault, o hardware interrompe a execução chamando o sistema operacional para fazer o tratamento adequado.[3]

Alunos: Junio e WagnerArquitetura de Computadores

Protocolos de Coerência Baseados em Hardware:

� Utilizados principalmente em sistemas multiprocessadores .� Tais protocolos lidam com a coerência em tempo de

Esquemas e Protocolos de Coerência Esquemas e Protocolos de Coerência

de Cachede Cache

Pág. 14

� Tais protocolos lidam com a coerência em tempo de execução, sendo assim considerados dinâmicos. [2]

� São mais complexos de implementar, pois sãocaracterizados pelo uso de recursos de baixo nível dearquitetura.[1]

�São Classificados em Snoopy e Directory

Alunos: Junio e WagnerArquitetura de Computadores

Protocolos de Coerência Baseados em Hardware:

Protocolo Snoopy: (Protocolo de Monitoramento)[4]

� Responsabilidade de manter a coerência entre todos os caches;

Esquemas e Protocolos de Coerência Esquemas e Protocolos de Coerência

de Cachede Cache

Pág. 15

� Responsabilidade de manter a coerência entre todos os caches;

Protocolo Singles Bus

� Utiliza duas Política:

�Write-Invalidade;�Write-update;

Alunos: Junio e WagnerArquitetura de Computadores

Protocolos Snoopy (Singles bus “Write-Invalidade”)

� Permite ter um escritor e vários leitores;

� Uma escrita em um dado compartilhado gera uma

Esquemas e Protocolos de Coerência Esquemas e Protocolos de Coerência

de Cachede Cache

Pág. 16

� Uma escrita em um dado compartilhado gera umainvalidação de todas as cópias desse dado antes que aescrita se inicie

Protocolos Snoopy (Singles bus “Write-update”)

� Atualiza todas as cópias do dado compartilhado antes de realizar a escrita

Alunos: Junio e WagnerArquitetura de Computadores

Protocolos de Coerência Baseados em Hardware:

Protocolo Directory: (Protocolo de Monitoramento)

Esquemas e Protocolos de Coerência Esquemas e Protocolos de Coerência

de Cachede Cache

Pág. 17

Protocolo Directory: (Protocolo de Monitoramento)

�Utilizam um controlador central para manter a coerência de cache;

�Guardam as informações das cópias de dados

�Utiliza um diretório na memória principal, onde armazena o estado global do conteúdo das varias caches

Alunos: Junio e WagnerArquitetura de Computadores

Devido ao crescimento de sistemas multiprocessados, ocompartilhamento de memória torna-se um ponto importantepara obter um bom desempenho de sua arquitetura, levando

ConclusãoConclusão

Pág. 18

a solucionar problemas de coerência de cache com apremissa de baixo custo Vs. Alto desempenho. Dando aorigem a diversa soluções baseadas em software ehardware.

Alunos: Junio e WagnerArquitetura de Computadores

1.Covacevive, Aleksey V.,Baldochi,B.Y., De Castro,F.RCoerência de Cache. Instituto de Computação – UNICAMP2.Geiss, Lenise Cristina.Coerência de Cache emMultiprossedores.Instituto de Informática UFRGS3. Da Costa,Andre L.N., Barbosa,Davi.M.J., Silva, FelipeS.S.Coerência de Cache: O Problema e Algumas Soluções.Instituto de Computação – UNICAMP

ReferênciasReferências

Pág. 19

Instituto de Computação – UNICAMP4. M. M. K. Martin. Formal verication and its impact on thesnooping versus directory protocol debate. Proceedings ofthe 2005 International Conference on Computer Design,pages 543-549, 2005.5.Neves,Renato S., Coerência de Memórias Cache eModelos de Consistência de Memória. Instituto deComputação – UNICAMP

Alunos: Junio e WagnerArquitetura de Computadores