%--------------------------------------------------------------------%
%
% Purpose: Initial description of a mapping from Elcor operations to MIPS-like ISA.
%
% Author(s):  Ricardo Ribeiro dos Santos
%
% Last Update: 18/08/2005
%--------------------------------------------------------------------%

\documentclass[a4paper,12pt]{article}
\usepackage[portuges,brazil]{babel}
\usepackage{plain}
\usepackage{isoaccent}
\usepackage{graphicx}
\usepackage{epstopdf}
\usepackage[top=30mm,bottom=25mm,left=25mm,right=20mm]{geometry}
\usepackage{amssymb}  % diversos símbolos matemáticos
\usepackage[latin1]{inputenc}
\usepackage{amsmath,epsfig,psfrag,latexsym}
\usepackage{setspace}
\usepackage{rotate}
\usepackage{rotating}
\usepackage{color}
\usepackage{cite}
\usepackage{colortbl}
\usepackage{array}
\usepackage{indentfirst}
\usepackage{ae}
\usepackage{tabularx}

\clubpenalty=10000
\widowpenalty=10000
\hyphenpenalty=1000

\newcommand{\filldouble}{\multicolumn{1}{|>{\columncolor[gray]{0.5}}c||}{}}
\newcommand{\fillsimple}{\multicolumn{1}{|>{\columncolor[gray]{0.5}}c|}{}}

\begin{document}
Universidade Catolica Dom Bosco

Curso de Engenharia de Computaca

Disciplina: Topicos Avançados em Sistemas de Computacao

\centerline \huge Exercicio sobre Coerencia de Caches


\begin{enumerate}
\item Considere um sistema de memoria compartilhada baseado em barramento que possui trê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:

\begin{table}[!h]
\begin{tabular}{|c|c|c|c|}\hline
Acao & Estado $P_1$ & Estado $P_2$ & Estado $P_3$ \\\hline
$P_1$ le x & & &\\\hline
$P_2$ le x & & &\\\hline
$P_3$ le x & & &\\\hline
$P_1$ escreve em x & & &\\\hline
$P_1$ le z & & &\\\hline
$P_3$ escreve em x & & &\\\hline
$P_1$ escreve em z & & &\\\hline

\end{tabular}
\end{table}

\begin{enumerate}
\item Indique qual o estado de cada cache apos cada uma das acoes.
\end{enumerate}

\item 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?

\begin{table}[!h]
\small
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
Acao & Estado $P_1$ & Estado $P_2$ & Estado $P_3$ & Estado $P_1$ & Estado $P_2$ & Estado $P_3$\\\hline
$P_1$ le x & & & & & &\\\hline
$P_2$ le x & & & & & &\\\hline
$P_1$ escreve em x$\rightarrow$ $x'$ & & & & & &\\\hline
$P_3$ le x & & & & & &\\\hline
$P_3$ escreve em x$\rightarrow$ $x''$ & & & & & &\\\hline
$P_1$ le x & & & & & &\\\hline
$P_2$ escreve em x$\rightarrow$ $x''$ & & & & & &\\\hline
\end{tabular}
\end{table}


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

\item 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.

\item Sob qual(is) condicao(oes) a ação de \textit{Flush} seria desnecessaria na transicao de $S\rightarrow I$ ?

\item Na última aula vimos o projeto de uma cache com um protocolo \textit{snooping} e uma politica \textit{write-back}. Sobre isso, responda:
\begin{enumerate}
\item Por que sao utilizados dois comparadores? Eles seriam necessários mesmo para uma politica \textit{write-through}? Por que?
\item Qual a motivacao para utilizar dois controladores (\textit{Bus} e \textit{Proc}) de \textit{tags} e estados?
\end{enumerate}
\item Quais sao os estados dos processadores e acoes no barramento para os eventos a seguir, considerando os protocolos MSI e MESI?

\begin{table}[!h]
\small
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
Acao & Estado $P_1$ & Estado $P_2$ & Estado $P_3$ & Estado $P_4$ & Estado $P_5$ & Acao no barramento\\\hline
$P_1$ le x & & & & & &\\\hline
$P_2$ le x & & & & & &\\\hline
$P_1$ escreve em x & & & & & &\\\hline
$P_3$ le x & & & & & &\\\hline
$P_4$ le x & & & & & &\\\hline
$P_3$ escreve em x & & & & & &\\\hline
$P_1$ escreve em x & & & & & &\\\hline
$P_4$ escreve em x & & & & & &\\\hline
$P_5$ le x & & & & & &\\\hline
$P_2$ le x & & & & & &\\\hline
$P_2$ escreve em x & & & & & &\\\hline
$P_5$ le x & & & & & &\\\hline
$P_5$ le x & & & & & &\\\hline
\end{tabular}
\end{table}
\end{enumerate}
\end{document}
