Balanceamento de Carga em um algoritmo Branch-and-Bound para execução em Grades computacionais
Resumo
This work introduces new techniques of load balance for a distributed branch-and-bound algorithm, applied to the Steiner Problem in Graphs (SPG), to be executed on computational Grids. Many Grids are composed of cluster of processors connected via highspeed links and the clusters, geographically distant, are connected through low-speed links, in a hierarchical fashion. In Grids, the processor performance may vary a lot during a certain period of time due to the fact that they are usually shared with several other applications. The proposed load balance algorithms have the following features: i) they do not employ the usual master-worker paradigm; ii) they consider the hierarchical structure of such Grids and the processors performance iii) they estimate the future load of processes. Several experiments were executed showing the efficiency of the proposed algorithms.
Referências
K. Aida. W. Natsume, Y. Futakata, "Ditributed Computing with Hierarchical Master-Worker Paradigm for Parallel Branch-and-Bound Algorithms", In the Proceedings of the Third International Symposium on Cluster Computing and Grid, 2003, p. 156-162.
A. Bruin, G.A.P. Kindervater, H.W.J.M. Trienekens. "Asynchronous Parallel Branh-and-Bound and Anomalies. Erasmus University, Department of Computer Science. EURCS-95-05. Roterdam. Holand, 1995.
C. Duin, C. "Steiner's Problems in Graphs", Ph.D. thesis. University of Amsterdam. Holand, 1993.
E. Elnozazhy, D. Johnson, Y. e Wang. "A Survey of Rollback-Recovey Protocols in Message Passing Systems", Technical Report, CMU-CS-96-181, School of Computer Science. Carnegie Mellon University, 1996.
A. lamnitch, I. Foster, "A Problem Specific Fault-Tolerance Mechanism for Asynchronous, Ditributed System". lnthe Proceedings of the International Conference on Parallel Processing. 2000, p. 4-14.
I. Foster, C. Kessekman, "The Globus Project: a Status Report", In the Proceedings of the Seventh Heterogeneous Computing Workshop (HCW'98). 1998, p. 4-18.
T. Koch. A. Martin, S. Voss, "SteinLib: An Update Library on Steiner Problems in Graphs". Konrad-Zuse-Zentrum für lnformationstechnik Berlin, ZIB-Report 00-37, 2003, http://elib.zib.de/steinlib, last visited Oct 30th, 2003.
T.-H. Lai, S. Sahni. "Anomalies in Parallel Branch-and-Bound Algorithms". Communications of the ACM. 27. 1984. p. 594-602.
M. Poggi de Aragão, E. Uchoa. R.S. Wernewck. "Dual Heuristics on the Exact Solution of Large Steiner Problems", Eletronic Notes in Discrete Mathematics. 7, 2001.
C. Roucairol, V. Cung, N. Yafoufi, "Design. lmplementation and Robustness in Parallel Branch-and-Bound", Technical Report PRISM 2000119, Université de Versailles Saint-Quentin. 2000.
M. Snir. S.M. Otto. S. Huss-Lederman. J. Dongarra. MPI: The Complete Reference, The MIT Press, 1996.
E. Uchoa, "Algoritmos para Problemas de Steiner com Aplicações em Projeto de Circuitos VLSI", Ph.D. thesis. Universidade Católica do Rio de Janeiro, Rio de Janeiro. Brasil, 2001.
R. Wong, "Dual Ascent Approach for Steiner Tree Problems on a Discrete Graph", Mathematical Programming, 28. 1984. p. 271-287, 112.
L. Drummond. E. Uchoa, A. Gonçalves, J. M.N. Silva, M. Santos and M. de Castro, "A Grid-Enabled Distributed Branch-and-Bound Algorithm with Application on the Steiner Problem in Graphs", Relatório técnico. Universidade Federal Fluminense. Niterói. Aceito para publicação na Parallel Computing em 2005.
k. Anstreicher, N. Brixius, J. Goux, J. Linderoth, "Solving Large Quadratic Assignment Problems on Computational Grids", Mathematical Programming. 2002, p 563-588.
C. Roucairol. S. Dowaji, "Load Balancing Strategy and Priority of Tasks in Distributed Environments", Computers and Communications, 1995.
L. Drummond. E. Uchoa, M. C. S. Castro, J. Viterbo. A. D. Gonçalves. "A Distributed Branch-and-Bound Algorithm for Wide-Area Environments". In Proceedings of the 6th International Meeting of High Performance Computing for Computational Science, 2004, p 927-932.
A. Bruin, G.A.P. Kindervater, H.W.J.M. Trienekens. "Asynchronous Parallel Branh-and-Bound and Anomalies. Erasmus University, Department of Computer Science. EURCS-95-05. Roterdam. Holand, 1995.
C. Duin, C. "Steiner's Problems in Graphs", Ph.D. thesis. University of Amsterdam. Holand, 1993.
E. Elnozazhy, D. Johnson, Y. e Wang. "A Survey of Rollback-Recovey Protocols in Message Passing Systems", Technical Report, CMU-CS-96-181, School of Computer Science. Carnegie Mellon University, 1996.
A. lamnitch, I. Foster, "A Problem Specific Fault-Tolerance Mechanism for Asynchronous, Ditributed System". lnthe Proceedings of the International Conference on Parallel Processing. 2000, p. 4-14.
I. Foster, C. Kessekman, "The Globus Project: a Status Report", In the Proceedings of the Seventh Heterogeneous Computing Workshop (HCW'98). 1998, p. 4-18.
T. Koch. A. Martin, S. Voss, "SteinLib: An Update Library on Steiner Problems in Graphs". Konrad-Zuse-Zentrum für lnformationstechnik Berlin, ZIB-Report 00-37, 2003, http://elib.zib.de/steinlib, last visited Oct 30th, 2003.
T.-H. Lai, S. Sahni. "Anomalies in Parallel Branch-and-Bound Algorithms". Communications of the ACM. 27. 1984. p. 594-602.
M. Poggi de Aragão, E. Uchoa. R.S. Wernewck. "Dual Heuristics on the Exact Solution of Large Steiner Problems", Eletronic Notes in Discrete Mathematics. 7, 2001.
C. Roucairol, V. Cung, N. Yafoufi, "Design. lmplementation and Robustness in Parallel Branch-and-Bound", Technical Report PRISM 2000119, Université de Versailles Saint-Quentin. 2000.
M. Snir. S.M. Otto. S. Huss-Lederman. J. Dongarra. MPI: The Complete Reference, The MIT Press, 1996.
E. Uchoa, "Algoritmos para Problemas de Steiner com Aplicações em Projeto de Circuitos VLSI", Ph.D. thesis. Universidade Católica do Rio de Janeiro, Rio de Janeiro. Brasil, 2001.
R. Wong, "Dual Ascent Approach for Steiner Tree Problems on a Discrete Graph", Mathematical Programming, 28. 1984. p. 271-287, 112.
L. Drummond. E. Uchoa, A. Gonçalves, J. M.N. Silva, M. Santos and M. de Castro, "A Grid-Enabled Distributed Branch-and-Bound Algorithm with Application on the Steiner Problem in Graphs", Relatório técnico. Universidade Federal Fluminense. Niterói. Aceito para publicação na Parallel Computing em 2005.
k. Anstreicher, N. Brixius, J. Goux, J. Linderoth, "Solving Large Quadratic Assignment Problems on Computational Grids", Mathematical Programming. 2002, p 563-588.
C. Roucairol. S. Dowaji, "Load Balancing Strategy and Priority of Tasks in Distributed Environments", Computers and Communications, 1995.
L. Drummond. E. Uchoa, M. C. S. Castro, J. Viterbo. A. D. Gonçalves. "A Distributed Branch-and-Bound Algorithm for Wide-Area Environments". In Proceedings of the 6th International Meeting of High Performance Computing for Computational Science, 2004, p 927-932.
Publicado
24/10/2005
Como Citar
NASCENTE, Juliana M.; DRUMMOND, Lúcia M. A.; UCHOA, Eduardo.
Balanceamento de Carga em um algoritmo Branch-and-Bound para execução em Grades computacionais. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 6. , 2005, Rio de Janeiro.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2005
.
p. 105-112.
DOI: https://doi.org/10.5753/wscad.2005.18982.
