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

Introduction Several scheduling algorithms have been developed for constraint satisfaction in real-time systems. Optimality is difficult to reach, and the problem becomes NP-hard when a large set of constraints must be satisfied. To solve this type of problem, approximate methods are used, such as Artificial Neural Networks (ANNs). Neural networks have demonstrated their efficiency in optimization problems. They converge in a reasonable time if the number of neurons and connections between neurons can be limited. Another limitation concerns the need to regularly re-initialize the network when it converges towards a stable state which does not belong to the set of valid solutions. On the other hand, embedded applications are usually implemented on complex System-on-Chip (SoC) which are built around heterogeneous processing units. On such platform, task instantiation on execution resources is realized by using the scheduling service of an OS. As each task can be defined for several targets, this service must decide, on-line, on which resource the task should be instantiated. In this work, we propose an on-line scheduling based on a neural network for heterogeneous system-on-chip (SoC) architectures with a limited number of neurons...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