Estratégias de balanceamento de carga para um algoritmo branch-and-bound paralelo para executar em grids computacionais

• Ano de defesa: 2006
• Autor(a) principal: Silva, Juliana Mendes Nascente
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Programa de Pós-Graduação em Computação; Computação
• Palavras-chave em Português: Ciência da computação; Algoritmo; Algoritmo de balanceamento de carga; Problema de Steiner; Grids computacionais; Branch-and-Bound; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO
• Link de acesso: https://app.uff.br/riuff/handle/1/17863

This work introduces three techniques of load balancing strategies for a distributed branchand-bound algorithm, applied to the Steiner Problem in Graphs (SPG), to be executed on computational Grids. Many Grids are composed of cluster of processors not dedicateds and heterogeneous. Moreover, the processors belonging to a same cluster are connected via highspeed links and the clusters, geographically distant, are connected through lowspeed links, in a hierarchical fashion. In order to improve the the efficience of parallel algorithms in these enviroments, dynamic load solved among the available resources, are crucial. Two completely distributeds strategies and a centralized one that employs the usual master-worker paradigm were proposed. They estimate the size of the load to be transfered and evaluate the performance presented by processors at each load request. The experiments were carried out using SPG intance from SteinLib. The proposed strategies showed to be efficiente when compared with other existing load balance strategies for this problem.Two strategies total distributed and one employ the usual master-worker paradigm.They estimate the size of the load and evaluate the performances presented for the processors to do transference. The tests experiments had been carried through instances of the SPG contained in SteinLib. The strategies demonstrated its efficiency and scalability.