Uma abordagem de balanceamento de carga baseada em algoritmo de aprendizado de máquina genético
Resumo
A utilização de agregados de computadores está cada vez mais presente no contexto computacional atual. Um dos grandes problemas de tais ambientes, muitas vezes, é a má utilização dos recursos computacionais. O módulo de escalonamento de processos é um importante componente para a melhoria de distribuição das cargas do sistema. Neste artigo, apresentamos uma abordagem de escalonamento dinâmico de processo baseada em sistemas classificadores. Sistemas classificadores são algoritmos de aprendizado de máquina, baseados em algoritmos genéticos, altamente adaptáveis. Em adição, apresentamos a implementação do pacote de software necessário para a execução dos testes, o qual é testado sob o paradigma de uma arquitetura mestre-escravo de agregados de computador. Nossos resultados experimentais demonstram um diferencial na capacidade de adaptação do sistema classificador mediante o ambiente sob qual está inserido.
Referências
A.Y. Zomaya, Y.H. Teh, "Observations on Using Genetic Algorithms for Dynamic Load-Balancing", IEEE Trans. On parallel and Distributed Systems, vol. 12, no. 2, Sep. 2001, pp. 899-911.
E.S.H. Hou, N. Ansari, H. Ren, "A Genetic Algorithm for Multiprocessor Scheduling", IEEE Trans. On parallel and Distributed Systems, vol..5, no. 2, Feb. 1994, pp. 113-120.
A.Y. Zomaya, C. Ward, B. Macey, "Genetic Scheduling for Parallel Processor Systems: Comparative Studies and Performance lssues", IEEE Trans. On parallel and Distributed Systems, vol 10, no. 8, Aug. 1999, pp. 795-812.
S.Zhou, "A Trace-driven Simulation Study of Dynamic Load Balancing", IEEE Trans. On Software Eng., vol. 14, no. 9, sep. 1988, pp. 1327-1 341.
O. Kremien, J. Kramer, "Methodical Analys is of Adaptative load Sharing Algorithms", IEEE Trans. On parallel and Distributed Systems, vol. 3, no. 6, Nov. 1992, pp. 747-760.
T.H. Casavant, J.G. Khul, "A Taxonomy ofScheduling in General-Purpose Distributed Computing Systems", IEEE Trans. On Software Eng.. vol. 14, no. 2, Feb. 1988, pp. 141-154.
Y.T.Wang, R.J.T. Morris, "Load Sharing in Distributed Systems", IEEE Trans. On Computers., vol. 34, no. 3, Mar. 1985, pp. 204-217.
D.L. Eager, E.D. Lazowska, J. Zahorjan, "Adaptative Load Sharing in Homogeneous Distributed Systems", IEEE Trans. On Software Eng.. vol. 12, no. 5, May 1986, pp. 662-675.
M.L. Powell, B.P. Miller, "Process migration in DEMOS/MP", in Proc. 9th ACM Symp. Operat. Syst. Principies, 1983, pp.110-119. Foz do Iguaçu, 27 a 29 de Outubro de 2004
D.E. Goldberg, Genetic Algoritlrm in Search. Optimization, and Machine Learning, Addison-Wesley, 1989.
J.H. Holland, "Genetic Algorithms and adaptation", in Proc. Of the NATO Advanced Research lnstitute on Adaptative Control of III-Defined Systems, 1984, pp. 317-333.
M. Mitchell, An Introduction to Genetic Algoritm, MIT Press., 1996.
D. Culler, P. Jaswinder, parallel Computer Architecture: A Hardware Software Approach, Morgan Kaufmann Publishers, 1999.
M.A.R. Dantas, E.J. Zaluska, Efficient Scheduling of MPI Applications on Networks of Workstations, pp 489-499, Future Generation Computing Systems, 1998.
C. Papadimitriou, K. Steilglitz. Combinatoriul Optimization: Algoritms and Complexity, Dover Publications, 1998.
J. M. Corrêa, A. C. Melo., "Using a Classifier System to lmprove Dynamic Load Balancing", in Proc. International Conference on parallel Processing.. IEEE Press. Valencia, Spain, Sep., 2001. pp. 411-416.
A.R. Pinto, C.Rista, M.A.R. Dantas, "OSCAR: Um Gerenciador de Agregado para Ambiente Operacional Linux", in ERAD 2004: 4' Escola Regional de Alto Desempenho, Pelotas, Brasil, 2004, pp.193-196.
M.A.R. Dantas, W.J. Queiroz, G.H. Plitscher, "An Efficient Threshold Approach on Distributed Workstation Clusters", in HPC in Simulation. Washington, USA, 2000, pp. 313-317.
D.Ferrari, S.Zhou, "An Empirical Investigation or Load Indices for Load Balancing Applications", in Proc. Performance '87, the 12th Int 'l Symp. on Computer Performance Modeling. Measurement and Evaluation, Amsterdam, The Netherlands, 1988, pp. 515-528.
J.Baumgartner, D.J. Cook, B.Shirazi, "Genetic Solutions to the Load Balancing Problem", in Proc. of the International Conference on parallel Processing, pp. 72-78 1995.
S.H. Woo, S.B. Yang, S.D. Kim, T.D.Han, "Task scheduling in Distributed computing Systems with a genetic algorithm", in Proc. of the High-Performance Computing on the lnformation Superhighway. HPC-Asia '97, 1997, pp.301-305.
Maya, Anu, Asmita, Snehal, Krushna (April 1st 2004) "MigShm: Shared memory over openMosix" A project report on MigShm [online]. Disponible in http://openmosix.sourceforge.net/#Documentation
W. Zhang (April 151 2004) "Linux Virtual Server for Scalable Network Services" [Online]. Disponible in http://www.linuxvirtualserver.org/docs/scheduling.html
M. Munetomo, Y. Takai, and Y. Sato"A Genetic Approach to Dynamic Load-Balancing in a Distributed Computing System",Proc.First lnt'l Conf. Evolutionary Computation, IEEE World Congress Computational lntelligence, vol. I, 1994, pp. 418-421.
E.S.H. Hou, N. Ansari, H. Ren, "A Genetic Algorithm for Multiprocessor Scheduling", IEEE Trans. On parallel and Distributed Systems, vol..5, no. 2, Feb. 1994, pp. 113-120.
A.Y. Zomaya, C. Ward, B. Macey, "Genetic Scheduling for Parallel Processor Systems: Comparative Studies and Performance lssues", IEEE Trans. On parallel and Distributed Systems, vol 10, no. 8, Aug. 1999, pp. 795-812.
S.Zhou, "A Trace-driven Simulation Study of Dynamic Load Balancing", IEEE Trans. On Software Eng., vol. 14, no. 9, sep. 1988, pp. 1327-1 341.
O. Kremien, J. Kramer, "Methodical Analys is of Adaptative load Sharing Algorithms", IEEE Trans. On parallel and Distributed Systems, vol. 3, no. 6, Nov. 1992, pp. 747-760.
T.H. Casavant, J.G. Khul, "A Taxonomy ofScheduling in General-Purpose Distributed Computing Systems", IEEE Trans. On Software Eng.. vol. 14, no. 2, Feb. 1988, pp. 141-154.
Y.T.Wang, R.J.T. Morris, "Load Sharing in Distributed Systems", IEEE Trans. On Computers., vol. 34, no. 3, Mar. 1985, pp. 204-217.
D.L. Eager, E.D. Lazowska, J. Zahorjan, "Adaptative Load Sharing in Homogeneous Distributed Systems", IEEE Trans. On Software Eng.. vol. 12, no. 5, May 1986, pp. 662-675.
M.L. Powell, B.P. Miller, "Process migration in DEMOS/MP", in Proc. 9th ACM Symp. Operat. Syst. Principies, 1983, pp.110-119. Foz do Iguaçu, 27 a 29 de Outubro de 2004
D.E. Goldberg, Genetic Algoritlrm in Search. Optimization, and Machine Learning, Addison-Wesley, 1989.
J.H. Holland, "Genetic Algorithms and adaptation", in Proc. Of the NATO Advanced Research lnstitute on Adaptative Control of III-Defined Systems, 1984, pp. 317-333.
M. Mitchell, An Introduction to Genetic Algoritm, MIT Press., 1996.
D. Culler, P. Jaswinder, parallel Computer Architecture: A Hardware Software Approach, Morgan Kaufmann Publishers, 1999.
M.A.R. Dantas, E.J. Zaluska, Efficient Scheduling of MPI Applications on Networks of Workstations, pp 489-499, Future Generation Computing Systems, 1998.
C. Papadimitriou, K. Steilglitz. Combinatoriul Optimization: Algoritms and Complexity, Dover Publications, 1998.
J. M. Corrêa, A. C. Melo., "Using a Classifier System to lmprove Dynamic Load Balancing", in Proc. International Conference on parallel Processing.. IEEE Press. Valencia, Spain, Sep., 2001. pp. 411-416.
A.R. Pinto, C.Rista, M.A.R. Dantas, "OSCAR: Um Gerenciador de Agregado para Ambiente Operacional Linux", in ERAD 2004: 4' Escola Regional de Alto Desempenho, Pelotas, Brasil, 2004, pp.193-196.
M.A.R. Dantas, W.J. Queiroz, G.H. Plitscher, "An Efficient Threshold Approach on Distributed Workstation Clusters", in HPC in Simulation. Washington, USA, 2000, pp. 313-317.
D.Ferrari, S.Zhou, "An Empirical Investigation or Load Indices for Load Balancing Applications", in Proc. Performance '87, the 12th Int 'l Symp. on Computer Performance Modeling. Measurement and Evaluation, Amsterdam, The Netherlands, 1988, pp. 515-528.
J.Baumgartner, D.J. Cook, B.Shirazi, "Genetic Solutions to the Load Balancing Problem", in Proc. of the International Conference on parallel Processing, pp. 72-78 1995.
S.H. Woo, S.B. Yang, S.D. Kim, T.D.Han, "Task scheduling in Distributed computing Systems with a genetic algorithm", in Proc. of the High-Performance Computing on the lnformation Superhighway. HPC-Asia '97, 1997, pp.301-305.
Maya, Anu, Asmita, Snehal, Krushna (April 1st 2004) "MigShm: Shared memory over openMosix" A project report on MigShm [online]. Disponible in http://openmosix.sourceforge.net/#Documentation
W. Zhang (April 151 2004) "Linux Virtual Server for Scalable Network Services" [Online]. Disponible in http://www.linuxvirtualserver.org/docs/scheduling.html
M. Munetomo, Y. Takai, and Y. Sato"A Genetic Approach to Dynamic Load-Balancing in a Distributed Computing System",Proc.First lnt'l Conf. Evolutionary Computation, IEEE World Congress Computational lntelligence, vol. I, 1994, pp. 418-421.
Publicado
27/10/2004
Como Citar
PINTO, A. R.; DANTAS, M. A. R..
Uma abordagem de balanceamento de carga baseada em algoritmo de aprendizado de máquina genético. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 5. , 2004, Foz do Iguaçu.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2004
.
p. 145-152.
DOI: https://doi.org/10.5753/wscad.2004.19012.
