Algoritmos BSP/CGM para Programação Dinâmica - Download

Autores: Loureiro, Leonardo Vinicius Rolan
Orientadores: Cáceres, Edson Norberto

 Dissertação de Mestrado apresentada à Faculdade de Computação do Centro de Ciências Exatas e Tecnologia da Universidade Federal de Mato Grosso do Sul.
Resumo: À medida que a computação paralela vem deixando de ser um tópico a parte e isolado no mundo da computação para ser um tópico essencial e presente em todas as máquinas recentes, o estudo dos modelos e algoritmos paralelos passa a ser uma obrigação para os futuros cientistas da computação. Neste trabalho abordaremos os principais modelos de computação paralela, desde os modelos teóricos (PRAM) até os modelos reais (BSP, CGM, LogP) mostrando suas principais características, seus pontos de acerto e suas falhas ao modelar as arquiteturas paralelas reais. Dois problemas de grande importância em Programação Dinâmica foram estudados: o problema do Alinhamento Local e o problema do Produto da Cadeia de Matrizes. Para cada um dos problemas apresentados, estudamos e desenvolvemos algoritmos paralelos BSP/CGM usando o paradigma de frente de onda, os algoritmos foram implementados num cluster usando a biblioteca LAM-MPI e numa grid usando o middleware InteGrade. Os tempos obtidos foram os esperados de acordo com a análise de complexidade do modelo BSP/CGM e os resultados mostram que o overhead da computação em grid é satisfatório considerando as facilidades da mesma.

 Formato: .pdf
Tamanho: 576 KB

-Gabriel Antonio

 /Novaeraserahackers