Improving the Performance of a Dynamic Load Balancer Using a Classifier System
Resumo
Processor scheduling in its general formulation is a NP-Complete problem. In the Dynamic Load Balancing problem the scheduler has to redistribute processes during their running lifetime trying to improve the performance according some optimization criterion. To tackle such a difficult problem is worth use heuristics to seek for better results. Among various heuristics, genetic algorithms are often used to handle problems with high complexity. In this paper we try to optimize the decisions taken by a dynamic load balancer with preemptive migration in a distributed environment using a Classifier System (CS). CS is an adaptive program that evolves decision rules applying genetic algorithms over a population of rules and selecting the best of them. CS has the ability of adapt to environment changes. The rules are rewarded or punished depending on their performance. This performance-driven behavior allows them to perform well even with few information. The results have been impressive and the classifier system was able to surpass, without previous knowledge of the properties of workload, the performance of a well designed analytic criterion.
Referências
BARAK, A., LA'ÁDAM O. and SHILOHA. Scalable Cluster Computing with MOSIX for LINUX, Proc. Linux Expo '99, pp. 95-100, Raleigh, U.S.A., May 1999.
BARRY, A.M. "XCS Performance and Population Structure within Multiple-StepEnvironments", PhD Thesis, Queens University Belfast, Sept 2000.
CARTER, E.F, 1994; The Generation and Application of Random Numbers, Forth Dimensions Vol XVI Nos 1 & 2, Forth Interest Group, Oakland California
CASAVANT, Thomas L., KUHL Jon G., A Taxonomy of Scheduling in General-Purpose Distributed Computing System, IEEE Transactions on Software Engineering, Vol 14, No. 2, Febuary 1988.
CORRÊA, Jan M., MELO, Alba C., Algoritmos Genéticos para Escalonamento de Processadores, Workshop em Sistemas Computacionais de Alto Desempenho, São Pedro, Brasil 2000
CORREA, Jan M., MELO, Alba C., Using a Classifier System in a Dynamic Changing Environment: An Application to Dynamic Load Balancing to appear in Encontro Nacional de Inteligência Artificial, Fortaleza, Julho, 2001
CORRÊA, Jan M., MELO, Alba C., Using a Classifier System to lmprove Dynamic Load Balancing, to appear in 303 - International Conference on Parallel Processing, Valencia, Spain, September, 2001
CORRÊA. Ricardo C.; FERREIRA, Afonso; REBREYEND, Pascal Scheduling Multiprocessors Tasks with Genetic Algorithms, IEEE Transaction On Parallel and Distribute Systems, Vol 10, No.8, pp 825-837 August 1999
COUCH, Alva L. Visualizing Huge Tracefiles with Xscal,Tenth USENIX System Administration Conference Chicago, IL, USA, Sept. 29- Oct. 4, 1996.
DUSSA-ZIEGER, K. and SCHWEHM, M. Scheduling of Parallel Programs on Configurable Multiprocessors by Genetic Algorithms, Journal of Approximate Reasoning, Special Issue on' Approximative Methods in Scheduling', Vol 19 (1-2) 23-38, 1998.
GOLDBERG, David E., Genetic Algorithms in Search, Optimization, And Machine Learning, Addison-Wesley, 1989.
GRAJCAR, M. Genetic List Scheduling Algorithm for Scheduling and Allocation on a Loosely Coupled Heterogeneous Multiprocessor System; Proceedings of the 36th Design Automation Conference (DAC), New Orleans, 1999
HARCHOL-BALTER, Mor and DOWNEY, Allen B. Exploiting process Iifetime distributions for dynarnic load balancing. In Proceedings of the 1996 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, pages 13--24, May 1996.
HOLLAND, J. H. and REITMAN, J. S., Cognitive systems based on adaptive algorithms, Pattern-directed inference systems. Academic Press, New York, 1978.
MICHALEWICZ, Z. Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, 1996, .
PAPADIMITRIOU, C. and STEIGLITZ, K. Combinatorial Optimization: Algorithms and Complexity, Dover Publications Inc.,1998
SANDNES, F.E. and MEGSON, G.M. Improved Static Multiprocessor Scheduling Using Cyclic Task Graphs - A Genetic Approach. IPPS'97 Workshop on Randomised Parallel Computing, 1997.
SAXON, S, and BARRY A. (1999). XCS and the Monk's Problem. Second International Workshop on Learning Classifier Systems (IWLCS-99), Orlando, FL, USA, July 13, 1999.
SUNG-HO Woo; SUNG-BONG Yang; SHIN-DUG Kim; TACK-DON Han, "Task scheduling in distributed computing systems with a genetic algorithm",Proceedings of the High-Performance Computing on the Information Superhighway, HPCAsia '97, 1997.
TOMLINSOM, A. and BULL, L. A corporate XCS. In Proceedings of the 1999 Genetic and Evolutionary Computation Conference Workshop, pages 298--305, Morgan Kaufmann, San Francisco, California.1999
WILSON, S. Classifier fitness based on accuracy. Evolutionary Computation, 1995.
WU, M. On Runtime Parallel Scheduling for Processors Load Balancing, IEEE Transactions on Parallel and Distributed Systems, v.8, n.2, February, 1997
