Improving cellular automata scheduling through dynamics control

ABSTRACT

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 randomly created in order to stress the scheduling performance of each model. The results indicate that both and can be used to adjust the dynamical behaviour in such models providing better scheduling results.

Graphical Abstract

Keywords:

• Cellular automata
• genetic algorithm
• task scheduling problem

Acknowledgements

Authors are grateful to FAPEMIG, CNPq and CAPES.

Notes

No potential conflict of interest was reported by the authors.

1 Deterministic Highest Level First with Estimated Time.