Implementação e análise de algoritmos BSP/CGM em um Beowulf e no InteGrade

Abstract

Com o avanço da ciência e da tecnologia nas mais diversas áreas surgiram problemas que necessitam cada vez mais de alto poder computacional. Inicialmente, para resolver esses problemas, eram utilizados computadores paralelos de grande porte e elevado custo. Em seguida, no entanto, tornou-se mais eficiente e barato montar clusters com PCs que trabalham em conjunto para oferecer um alto poder de processamento a um custo menor que o método anterior. Recentemente, porém, vem sendo desenvolvido a ideia de interligar clusters dispersos geograficamente, formando uma única grade computacional e uma dessas propostas é o middleware InteGrade. Visto que a utilização de grades computacionais para elevar o poder de processamento disponível para a solução dos mais diversos problemas vem se tornando mais comum, o principal objetivo do nosso trabalho é avaliar o desempenho do InteGrade em relação ao cluster. Para fazer essa avaliação, estudamos problemas paralelos com diferentes aspectos de computação e de comunicação e os implementamos utilizando o modelo BSP/CGM (Bulk Synchronous Parallel/Coarse Grained Multicomputer). Entre os problemas estudados estão o Problema da Mochila 0-1, o Problema da Árvore Geradora e por fim o Problema do Fecho Transitivo. Todos os algoritmos foram implementados utilizando o padrão MPI (Message Passing Interface) e a linguagem C.

As the science and technology advanced in all diverse areas, problems which require more and more computer power to be solved were risen. In the beginning, these problems were solved by high performance parallel computers which were huge and very expensive. After that, though, making clusters with PCs which worked together to offer a higher processing capacity at a lower cost than the previous one became more efficient and inexpensive. Recently, however, the idea of linking geographically spread clusters making a single computer net, which one of the proposals is the middleware InteGrade, has been developed. Once using grid computing to improve the available processing capacity to solve the range of the most different problems has become more common, the main objective of our work is to compare the performance between InteGrade to the cluster’s. To value this we have studied the parallel problems with different computer and communication aspects and implemented it using the BSP/CGM model (Bulk Synchronous Parallel/Coarse Grained Multicomputer). The studied problems were 0-1 Knapsack Problem, the Spanning Tree Problem and Transitive Closure Problem. All the algorithms were implemented using the MPI pattern (Message Passing Interface) and C language.