Improving the Performance of a Dynamic Load Balancer Using a Classifier System - Correa, Jan M.; Melo, Alba C. (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), 2001)
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.