Modelos de Computação Paralela e Projeto de Algoritmos

O modelo PRAM vem sendo já há mais de 15 anos o modelo principal para projeto e análise de algoritmos paralelos. A sua simplicidade o torna um modelo pouco fiel à realidade, o que motivou o aparecimento de extensões e de outros modelos, dentre os quais BSP (Valiant, 1990) e LogP (Culler et al., 1993). Apresentamos uma descrição sucinta desses 3 modelos e mostramos os diferentes níveis de abstração em que se situam. São apresentadas as vantagens e desvantagens de cada um, particularmente com relação ao projeto e análise de algoritmos. A relevância de cada um frente ao panorama atual de máquinas paralelas é discutida, concluindo-se que o modelo LogP, apesar de ser de mais baixo nível, é o que tem mais chance de se disseminar em situações práticas.

1995