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 mu and SCAS-HP rho 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 mu and rho 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 randomly created in order to stress the scheduling performance of each model. The results indicate that both mu and rho can be used to adjust the dynamical behaviour in such models providing better scheduling results. [GRAPHICS] Activity diagram briefly showing the main steps of the investigated three cellular automata task schedulers - SCAS-HP, SCAS-HP mu and SCAS-HP rho.