Algoritmos BSP/CGM para programação dinâmica

Abstract

À 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.

As parallel computing are no longer an apart and isolated topic in the world of computing to be an essential and present topic in all recent machines, study of parallel models and algorithms becomes an obligation for future scientists computing. This paper will discuss the main parallel computing models, from the theoretical models (PRAM) to the real models (BSP, CGM, LogP) showing its main characteristics, their hit points and their failures to model the real parallel architectures. Two major problems in Dynamic Programming were studied: the Local Alignment problem and the Matrix Chain Product problem. For each of the problems, we study and develop a BSP/CGM algorithm using the wavefront paradigm, the algorithms were implemented in a cluster using the LAMMPI library and in a grid using the InteGrade middleware. The running times obtained were those expected according to the analysis of complexity of the BSP/CGM model and the results show that the overhead of grid computing is satisfactory considering the facilities of the same.