Improving cellular automata scheduling through dynamics control

Cellular automata (CA) are dynamical systems with simple components but at the same time able to generate diverse and complex behaviour. In the present work we employ cellular automata to schedule programs over a multiprocessor system. The previously published CA-based scheduling models: SCAS-HP, SCAS-HP and SCAS-HP differ in the way they control the CA dynamical behaviour. Previous studies indicated that SCAS-HP tends to exhibit an inappropriate CA behaviour, which is mostly based on chaotic rules. Therefore, the parameters and are used to change the dynamical behaviour with the aim of improving the scheduling results. We investigate several instances of the scheduling problem which we split into two families of problems and by addressing each family separately to provide a more accurate evaluation of the models. The first family is formed by programs that solve linear equations by use of the Gaussian Elimination technique, while the second is comprised of artificial instances, which were randoml...