Balanceamento de Carga na Paralelização da Meta-heurística GRASP
Resumo
Compara-se o desempenho de duas estratégias de balanceamento de carga na paralelização da meta-heurística GRASP (Greedy Randomized Adaplive Search Procedure): decomposição pré-escalonada (balanceamento estático) ou auto-escalonada (balanceamento dinâmico) dos dados. As duas estratégias foram testadas sob a influência dos mesmos fatores externos. O balanceamento de carga dinâmico revelou-se como a melhor alternativa, mostrando significativas melhorias no desempenho da paralelização.
Referências
A.C.F. Alvim, Estratégias de Paralelização da Meta-heurística GRASP, Dissertação de Mestrado, Departamento de Informática, Pontifícia Universidade Católica do Rio de Janeiro, 1998.
T.A. Feo e M.G.C. Resende, "Greedy Randomized Adaptive Search Procedures", Journal of Global Optimization 6 (1995), 109-133.
R. Jain, The Art of Computer Systems Performance Analysis - Techniques for Experimental Design, Measurement, Simulation, and Modeling, Wiley, 1991, New York.
S.L. Martins, C.C. Ribeiro e M.C. Souza, "A Parallel GRASP for the Steiner Problem in Graphs", Proceedings of the 5º International Symposium on Solving Irregularly Structured Problems in Parallel, Berkeley, 1998, a ser publicado em Lecture Notes in Computer Science.
P.M. Pardalos, L. Pitsoulis, T. Mavridou, e M. Resende, "Parallel Search for Combinatorial Optimization: Genetic Algorithms, Simulated Annealing, Tabu Search and GRASP", Lecture Notes in Computer Science 980 (1995), Springer-Verlag, Berlim, 317-331.
P.M. Pardalos, L. Pitsoulis e M.G.C. Resende, "A Parallel GRASP for MAX-SAT Problems", Lecture Notes in Computer Science 1180 (1996), Springer-Verlag, Berlim, 575-585.
M. Prais e C.C. Ribeiro, "Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment", INFORMS Journal on Computing, 1998, a ser publicado.
M.G.C. Resende e C.C. Ribeiro, "A GRASP for Graph Planarization", Networks 29 (1997), 173-189.
T.A. Feo e M.G.C. Resende, "Greedy Randomized Adaptive Search Procedures", Journal of Global Optimization 6 (1995), 109-133.
R. Jain, The Art of Computer Systems Performance Analysis - Techniques for Experimental Design, Measurement, Simulation, and Modeling, Wiley, 1991, New York.
S.L. Martins, C.C. Ribeiro e M.C. Souza, "A Parallel GRASP for the Steiner Problem in Graphs", Proceedings of the 5º International Symposium on Solving Irregularly Structured Problems in Parallel, Berkeley, 1998, a ser publicado em Lecture Notes in Computer Science.
P.M. Pardalos, L. Pitsoulis, T. Mavridou, e M. Resende, "Parallel Search for Combinatorial Optimization: Genetic Algorithms, Simulated Annealing, Tabu Search and GRASP", Lecture Notes in Computer Science 980 (1995), Springer-Verlag, Berlim, 317-331.
P.M. Pardalos, L. Pitsoulis e M.G.C. Resende, "A Parallel GRASP for MAX-SAT Problems", Lecture Notes in Computer Science 1180 (1996), Springer-Verlag, Berlim, 575-585.
M. Prais e C.C. Ribeiro, "Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment", INFORMS Journal on Computing, 1998, a ser publicado.
M.G.C. Resende e C.C. Ribeiro, "A GRASP for Graph Planarization", Networks 29 (1997), 173-189.
Publicado
28/09/1998
Como Citar
ALVIM, Adriana Cesário de Faria; RIBEIRO, Celso Carneiro.
Balanceamento de Carga na Paralelização da Meta-heurística GRASP. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 10. , 1998, Búzios/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1998
.
p. 279-282.
DOI: https://doi.org/10.5753/sbac-pad.1998.22696.
