Skip navigation
PDF 2.01 MB
DOI: http://dx.doi.org/10.7551/978-0-262-33027-5-ch095
Pages 538–545
First published 20 July 2015

Searching for non-regular neighborhood cellular automata rules applied to scheduling task and guided by a forecast dynamical behavior parameter

Tiago I. Carvalho and Gina M. B. Oliveira

Abstract

Cellular automata (CA) have been recently considered for the scheduling task. Since the problem of forecasting dynamic behavior of CA is undecidable, several parameter-based approximations have been developed to the problem. Sensitivity parameter is one of the most-studied CA forecast parameters and it has shown efficient to identify the dynamical behaviour of CA rules characterized by regular neighborhood. Here we perform an investigation about the usage of sensitivity to identify dynamical classes in cellular automata rules with a non-linear neighborhood model in a scheduling task. The results show that sensitivity can help the identification of long-cycle rules, avoiding this undesirable behavior in the search for CA rules appropriate to schedule the tasks of parallel programs in a multiprocessor architecture.