\documentclass[12pt]{article}


\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}

\setlength{\unitlength}{28pt}
\setlength{\textwidth}{15cm}
\setlength{\textheight}{26cm}
\setlength{\oddsidemargin}{0.1in}
\setlength{\evensidemargin}{0.1in}
\voffset=-2.5cm
\hoffset=1cm
\newcommand{\p}{\vspace{1.44ex}}

\begin{document}

\begin{center}
{\bf MAC 5741 - Introdução a Algoritmos e Arquiteturas
Paralelas\\
 Lista de exercícios 3}

\end{center}
\p

O modelo CREW permite leitura concorrente
de uma mesma posição da memória compartilhada por
vários processadores. 
O modelo EREW já não permite esse acesso simultâneo.

\p

Há um teorema que diz que um algoritmo paralelo
no modelo CREW pode ser simulado por um outro
no modelo EREW com um {\it slowdown} de 
$O(\log p)$ onde $p$ é o número de processadores.

\p

Se num algoritmo CREW há uma
leitura concurrente de uma variável $x$ por,
digamos, todos os $p$ processadores, mostre
um trecho do algoritmo que simula essa leitura
no modelo EREW.

\p

(dica: vai dobrando o número de vezes em que esse
valor aparece na memória compartilhdada.)
 

\end{document}


