A Comparison of a Proposed Dynamical Direct Verification of Lattice’s Configuration and a Forecast Behavior Parameter on a Cellular Automata Model to Task Scheduling

This paper compares two strategies to evolve cellular automata (CA) rules avoiding an undesirable dynamical behavior. Here long-cycle rules are considered inappropriate, specially the chaotic rules. The first approach employs a forecast parameter to guide a genetic algorithm (GA) toward rules out of the region where long-cycle rules are most probably to happen. The second one is proposed here and directly evaluates the lattice convergence in the spatio-temporal evolution to classify the cycle as long (or not). The problem taking in account here is the task scheduling for multiprocessor architectures. CA-based schedulers use two stages: (a) learning, where a GA is used to find rules to schedule an specific program graph and (b) operation, where the evolved rules are used to schedule new instances. The experimental results show that both approaches are able to find more CA rules with adequate dynamical behavior in both stages. Moreover, a reasonable improvement of makespan in the operation phase is obtained by controlling the CA dynamics.