Universidade Catolica Dom Bosco Curso de Engenharia de Computaca Disciplina: Topicos AvanÃ§ados em Sistemas de Computacao

Exercicio sobre Coerencia de Caches

1. Considere um sistema de memoria compartilhada baseado em barramento que possui trÃ^{a}s processadores P_{1}, P_{2}, P_{3}. A memoria possui quatro blocos distintos: x, y, z, w. Cada processador possui uma cache que armazena apenas um bloco de cada vez. Cada bloco deve estar em um de dois estados: Valido ou Invalido. Considere que as caches estÃ£o inicialmente vazias e os processadores acessam esses blocos na seguinte ordem:

Acao  Estado P_{1} Estado P_{2} Estado P_{3}

P_{1} le x P_{2} le x P_{3} le x

P_{1} escreve em x

P_{1} le z P_{3} escreve em x P_{1} escreve em z

(a) Indique qual o estado de cada cache apos cada uma das acoes.

2. Considere agora os protocolos Write-Update (Atualizacoes em uma cache geram atualizacoes nas outras caches) e Write-Invalidate (possui estados de Valido e Invalido conforme exercÃcio 1). Qual e’ o valor das caches dos processadores P_{1},P_{2}, P_{3}, considerando as seguintes acoes?

Acao  Estado P_{1} Estado P_{2} Estado P_{3} Estado P_{1} Estado P_{2} Estado P_{3}

P_{1} le x P_{2} le x

P_{1} escreve em x→ x′

P_{3} le x P_{3} escreve em x→ x′′

P_{1} le x P_{2} escreve em x→ x′′

3. Sob qual(is) condicao(oes) uma cache implementada com o protocolo MESI gera menos mensagens no barramento do que uma cache implementada com MSI?

4. Considerando uma cache implementada com o protocolo MESI, e’ possÃvel que um bloco dessa cache esteja no estado S mesmo que nÃ£o existam copias desse bloco em outras caches? Justifique sua resposta.

5. Sob qual(is) condicao(oes) a aÃ§Ã£o de Flush seria desnecessaria na transicao de S → I ?

6. Na Ã^{o}ltima aula vimos o projeto de uma cache com um protocolo snooping e uma politica write-back. Sobre isso, responda:

(a) Por que sao utilizados dois comparadores? Eles seriam necessÃ¡rios mesmo para uma politica write-through? Por que?

(b) Qual a motivacao para utilizar dois controladores (Bus e Proc) de tags e estados?

7. Quais sao os estados dos processadores e acoes no barramento para os eventos a seguir, considerando os protocolos MSI e MESI?

Acao  Estado P_{1} Estado P_{2} Estado P_{3} Estado P_{4} Estado P_{5} Acao no barramento

P_{1} le x P_{2} le x

P_{1} escreve em x P_{3} le x P_{4} le x

P_{3} escreve em x P_{1} escreve em x P_{4} escreve em x

P_{5} le x P_{2} le x

P_{2} escreve em x P_{5} le x P_{5} le x