Novas abordagens na evolução de autômatos celulares aplicados ao escalonamento de tarefas em multiprocessadores

Abstract

Scheduling tasks in multiprocessor architectures still is a challenge in parallel computing field. In this work, we studied a scheduling algorithm based on cellular automata (CA) with the goal of allocate parallel program tasks in a system with two processors. The scheduling algorithm has two phases: a learning phase and an operating phase. The purpose of the learning phase is to discover CA rules for scheduling. A genetic algorithm (GA) is used for search these rules. In the operating phase, the rules discovered in the previous phase are applied in new instances of parallel programs. It is expected that for any initial allocation of the tasks, CA will be able to find an allocation of tasks where the total execution time T is minimized (or close to it). We first studied CA and GA models proposed and published for the task scheduler architecture. After the understanding of these models and the reproduction of some published results, our goal turned to study the generalization ability of the CA transition rules. We investigated if the rules found for a specific parallel program can be applied, successfully, in other programs. Our main conclusion about this investigation is that there is a lot of space for improving this ability. Aiming to improve this generalization ability, we present two new approaches for the learning phase of the scheduling algorithm based on CA: the joint evolution and a coevolutionary environment. Results obtained through these new approaches show that, applying them, the evolved CA rules present a better generalization ability.