Orientador: João Carlos Setubal

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação

Resumo: Modelos de Computação são uma ferramenta muito importante para um bom desenvolvimento de algoritmos. Em geral, eles visam facilitar o trabalho de projetistas abstraindo diversos fatores existentes nas máquinas reais. Em computação paralela, a necessidade de um modelo é extrema devido a...

Resumo: Modelos de Computação são uma ferramenta muito importante para um bom desenvolvimento de algoritmos. Em geral, eles visam facilitar o trabalho de projetistas abstraindo diversos fatores existentes nas máquinas reais. Em computação paralela, a necessidade de um modelo é extrema devido a grande variedade de arquiteturas. O surgimento de um modelo de computação paralela poderia impulsionar ainda mais o crescimento da área que já é bastante acentuado, devido a limitações físicas existentes em computadores seqüenciais. Nesta dissertação fazemos um estudo de modelos de computação paralela sob o ponto de vista de projeto de algoritmos e com enfoque na computação paralela derivada da arquitetura de von Neumann. Para tanto, começamos por estudar um conjunto de máquinas paralelas para que suas diferenças fiquem claras. Escolhemos as máquinas paralelas mais conhecidas, ou mais difundidas, como: CM-2, Sequent Symmetry, MasPar MP-l, CM-5, entre outras. Após este estudo de máquinas, partimos diretamente para os modelos de computação paralela. Escolhemos três como base. Tais modelos apresentam características bem distintas quanto a simplicidade e realismo. Os modelos estudados são PRAM, BSP [Val90] e LogP [CKP+93]. Muitos defendem que continuemos usando o modelo PRAM , pois este, apesar de ser muito abstrato, facilita bastante o trabalho dos projetistas. A proposta do modelo BSP é um pouco mais ousada pois Valiant tenta, com seu modelo, influenciar as áreas de hardware e software da mesma forma que a arquitetura von Neumann fez com a computação seqüencial. Já a proposta do modelo LogP é bastante imediatista, visto que tenta resolver o problema atual de dificuldade de projeto de algoritmos. Para que pudéssemos avaliar um modelo sob o ponto de vista de projeto de algoritmos, fizemos um estudo de casos com os problemas de Transformada de Fourier e Eliminação de Gauss. Com este estudo de casos pudemos avaliar quão fácil ou difícil é projetar algoritmos em cada um dos modelos.

Abstract: Models of Computation are one of most important tools in algorithm design With these models, the work of an algorithm designer becomes easier, because these models leave out many characteristics of real machines. In parallel computing there is a great need for a general model, because we...

Abstract: Models of Computation are one of most important tools in algorithm design With these models, the work of an algorithm designer becomes easier, because these models leave out many characteristics of real machines. In parallel computing there is a great need for a general model, because we have many different parallel machines. The advent of a parallel computing model could make the area grow more than it is already growing. In this dissertation we study some parallel computing models. First we take a look at a representative set of parallel machines, in order to learn the differences between each architecture. Our set of machines contains some of the most important commercial machines such as: CM-2, Sequent Symmetry, MasPar MP-l and CM-5. After this, we study the models themselves. The models chosen were: PRAM, BSP [Va190] and LogP [CKP+93]. Many researchers argue that the PRAM is the best model for algorithm design although it is not realistic. The proposal of the BSP mo dei is bold, since it also seeks to influence parallel architecture design The proposal of LogP model although similar to the BSP, does not require parallel machines to have synchronization mechanisms. This makes LogP the most realistic but also the most difficult model to use. We evaluate these models based on the problems of Fourier Transform and Gaussian Elimination. After this study we made an evaluation of the three models.