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

Detalhes bibliográficos
Ano de defesa: 2006
Autor(a) principal: Silva, Juliana Mendes Nascente
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
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
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://app.uff.br/riuff/handle/1/17863
Resumo: 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.