Real-Time Scheduling on Heterogeneous SoC Architectures Using A Neural Network. Ordonnancement de Tâches par Réseaux de Neurones pour Architectures de Soc Hétérogènes

Real-Time Scheduling on Heterogeneous SoC Architectures Using A Neural Network

Ordonnancement de Tâches par Réseaux de Neurones pour Architectures de Soc Hétérogènes

Daniel Chillet Sébastien Pillement  Olivier Sentieys

ENSSAT – Université de Rennes 1 – IRISA – Équipe CAIRN, BP 80518, 6 Rue de Kerampont, 22305 Lannion, France

Page: 
77-89
|
Received: 
25 February 2008
|
Accepted: 
N/A
|
Published: 
28 February 2009
| Citation

OPEN ACCESS

Abstract: 

In this paper, a scheduling service modelled by a neural network is presented. An adaptation of the Hopfield model is proposed. The major contributions of our work concern the limitation of slack neurons and the simplification of the network control thanks to the absence of re-initializations. To limit the number of neurons, we replace numerous slack neurons of classical solutions by several inhibitor neurons. Based on these inhibitor neurons, a new structure of a neural network is presented. Furthermore, in classical solutions, a lot of neuron network re-initialisations are necessary to converge towards a valid solution. This is due to the existence of local minima of energy function. We propose to replace the addition of two k-out-of-N rules by the addition of k1-out-of-N1 and at-most-k2-among-N2 rules. We have shown that this specific additivity of rules always ensures the convergence and yet limits the number of slack neurons. These two contributions are important advances for our future works which consist in dening a hardware implementation of the scheduling service in the context of SoC architecture. The major problem for the hardware implementation concerns the large number of connections between neurons.

Résumé

Les technologies de conception de circuits intégrés permettent aujourd’hui de concevoir des systèmes complets et complexes sur une seule et même puce. On parle alors de systèmes sur puce, ou encore de System-on-Chip (SoC). Ces systèmes ont en charge l’exécution d’applications complexes, composées de nombreuses tâches, le tout étant orchestré par un système d’exploitation dont l’un des rôles principaux consiste à ordonnancer les tâches et à les allouer aux ressources de calcul.

L’une des particularités de ces architectures concerne l’hétérogénéité des cibles d’exécution qui rend le problème de l’ordonnancement particulièrement délicat et complexe. Notons de plus que le critère temps réel des applications s’exécutant sur ce type de plate forme nécessite l’étude de solutions d’ordonnancement efficaces, notamment en terme de temps de calcul. Dans ce papier, nous présentons nos travaux de modélisation du problème de l’ordonnancement pour architectures multi-processeurs hétérogènes par utilisation de réseaux de neurones. Des travaux précédents ont montré qu’une structure de réseaux de neurones suivant le modèle de Hopfield peut être définie pour ordonnancer des tâches sur une architecture homogène. Une extension à ces travaux a montré qu’il était possible de prendre en compte l’hétérogénéité de l’architecture mais au prix d’un grand nombre de neurones supplémentaires. De plus, ces solutions posent un problème de convergence important qui se traduit par un temps de convergence assez long et le besoin de ré-initialiser le réseau de neurones lorsque celui-ci se stabilise dans un état qui n’est pas une solution valide.

Pour contrer ces principaux inconvénients, nous proposons une nouvelle structure basée sur la mise en place de neurones inhibiteurs. Ces neurones particuliers permettent de limiter le nombre de neurones nécessaires à la modélisation et permettent surtout de se passer de ré-initialisations pour atteindre la convergence. Nous illustrons l’apport de notre proposition en comparant les solutions classiques à base de réseaux de neurones de Hopfield avec notre proposition. Nous montrons que le nombre de neurones est assez largement réduit et surtout qu’il n’est plus nécessaire de ré-initialiser le réseau pour assurer sa convergence, ce qui laisse envisager une implémentation efficace de ce type de structure.

Keywords: 

Task Scheduling, Artificial Neural Networks, Heterogeneous Architecture, System-on-Chip.

Mots clés

Ordonnancement de tâches, réseaux de neurones artificiels, architectures hétérogènes, système sur Puce.

1. Introduction
2. État de l’Art et Modélisations Classiques
3. Notre Proposition
4. Résultats
5. Conclusion
  References

[1] C. CARDEIRA and Z. MAMMERI, Preemptive and non-preemptive real-time scheduling based on neural networks, In Proc. of Distributed Computer Control Systems, pages 67-72, Toulouse, France, September 1995.

[2] C. LIU and J. LAYLAND, Scheduling algorithms for multiprogramming in a hard real-time environment, J. of the ACM, 20(1) :46-61, 1973.

[3] J. Y.-T. LEUNG and J. WHITEHEAD, On the complexity of fixedpriority scheduling of periodic real-time tasks, Performance Evaluation 2, 2 :237-250, 1982.

[4] K. SCHILD and J. WÜRTZ, Off-line scheduling of a real-time system. In K. M. George, editor, Proceedings of the 1998 ACM Symposium on Applied Computing, SAC98, pages 29-38, Atlanta, Georgia, 1998. ACM Press.

[5] N. MEGOWand A.S. SCHULZ, On-line scheduling to minimize average completion time revisited, Operations Research Letters, 32(5):485-490, 2004.

[6] X. LU, R. SITTERS, and L. STOUGIE, A class of on-line scheduling algorithms to minimize total completion time, Oper. Res. Lett., 31(3):232-236, 2003.

[7] M. YOUNG and L.C. SHU, Hybrid online/offline scheduling for hard real-time systems, Technical Report SERC-TR-100-P, 1991.

[8] A. SRINIVASAN, P. HOLMAN, J.H. ANDERSON, and S. BARUAH, The case for fair multiprocessor scheduling. In Proc. of the 17th International Symposium on Parallel and Distributed Processing, page 114, Washington, DC, USA, 2003.

[9] S. BARUAH and N. FISHER, The partitioned multiprocessor scheduling of sporadic task systems. In Proc. of the 26th IEEE International Real-Time Systems Symposium, pages 321-329, Washington, DC, USA, 2005.

[10] S. BARUAH and N. FISHER, The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems, IEEE Trans. Comput., 55(7) :918-923, 2006.

[11] A. MORTON and W.M. LOUCKS, A hardware/software kernel for system on chip designs. In Proceedings of the ACM Symposium on Applied Computing, pages 869-875, 2004.

[12] P. KOHOUT, B. GANESH, and B. JACOB, Hardware support for real-time operating systems. In CODES+ISSS ‘03: Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, pages 45-51, New York, NY, USA, october 2003. ACM Press.

[13] P. KUACHAROEN, M. SHALAN, and V. MOONEY III, A configurable hardware scheduler for real-time systems. In Proceedings of the International Conference on Engineering of Reconfigurable Systems and Algorithms, pages 96-101, Las Vegas, USA, June 2003.

[14] C. CARDEIRA and Z. MAMMERI, Neural network versus max-flow algorithms for multiprocessor real-time scheduling, IEEE Proceedings of EURWRTS, pages 175-180, 1996.

[15] C. CARDEIRA, M. SILVA, and Z. MAMMERI, Handling precedence constraints with neural network based real-time scheduling algorithms. In Proc. of the 9th Euromicro Workshop on Real Time Systems, pages 207-214, Toldeo, Spain, june 1997.

[16] J. J. HOPFIELD and D. W. TANK, Neural computation of decisions in optimization problems, Biological Cybernetics, 52 :141-52, 1985.

[17] M.A. COHEN and S. GROSSBERG, Absolute stability of global pattern formation and parallel memory storage by competitive neural networks, IEEE Trans. on Systems, Man, and Cybernetics, 13(5) :815-826, Sept./Oct. 1983.

[18] S. GROSSBERG, Studies of Mind and Brain : Neural Principles of Learning, Perception, Development, Cognition, and Motor Control, volume 70. Reidel Press Bonston, 1982.

[19] I. BENKERMI, S. PILLEMENT, and O. SENTIEYS, Application des réseaux de neurones à l’ordonnancement de tâches temps réel sur une architecture multiprocesseurs hétérogènes, SympAAA’2003, 14-17 Octobre 2003.

[20] I. BENKERMI, Modèle et algorithme d’ordonnancement pour architectures reconfigurables dynamiquement. PhD thesis, ENSSATUniversité de Rennes, 2007.

[21] D. CHILLET, S. PILLEMENT, and O. SENTIEYS,A neural network model for real-time scheduling on heterogeneous soc architectures. In International Joint Conference on Neural Networks, IJCNN 2007, Orlando, Floride, august, 12-17 2007.

[22] D. CHILLET, S. PILLEMENT, and O. SENTIEYS, Vers une implémentation matérielle d’un réseau de neurones pour le service d’ordonnancement des tâches au sein d’un soc. In GRETSI 2007, 2007.