Escalonamento de tarefas baseado em autômatos celulares com uso dos parâmetros de previsão do comportamento dinâmico

Abstract

Multiprocessor scheduling has been one of the most classic NP-hard optimization problem. Given a program divided by N jobs and a set of P processors, the problem is to assign each job j є N to a processor p є P in a way that minimizes the execution time for that program. This problem is related with the perfomance of the modern computers, whose is designed with a increasingly number of processors. To solve this problem many heuristics and meta-heuristics has been studied. In that kind of approach a solution is searched for a specific instance of the problem. Nevertheless, the heuristics and metaheuristic are incapable of acquiring a knowledge about scheduling process which could be extracted and potentially used for solving new instances of scheduling problem. For this purpose was proposed the use of a cellular automata. In cellular automata based multiprocessor scheduling two modes are used. In learning mode, a genetic algorithm is applied to discover rules of cellular automata suitable for solving a instance of a scheduling problem. In operation mode, discovered rules of cellular automata are able to find an optimal or suboptimal solution of the scheduling problem for many program graph. In a recent celullar automata based scheduling model (SCAS-HP) was stated that some rules evolved in this scheduler was not appropriated for solving the scheduling problem in operation mode because of their caotic behaviour. On other hand, the classic approach for handling the behaviour of cellular automata rules is done by calculating a parameter considering that rule. The parameter sensitivity µ was selected for an heuristic approach for avoiding caotic rules. A new scheduler was proposed EACS-CD - Cellular Automata Based Scheduler with Dynamic Behaviour. This new scheduler was compared with SCAS-HP. Experimental results showed that in the new model fewer caotic rules was trained and thus the perfomance of the new scheduler was better in operation mode.