MAC 5741 - Introdução a Algoritmos e Arquiteturas Paralelas
Lista de exercícios 3

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.

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

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.

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