Présentation
En anglaisRÉSUMÉ
Le simple fait d'ajouter un processeur supplémentaire à la plateforme augmente drastiquement la complexité des problèmes d'ordonnancement temps réel. C.L. Liu, fondateur de l'ordonnancement temps réel, a très tôt constaté que très peu de résultats connus en environnement monoprocesseur pouvaient être directement généralisés aux systèmes multiprocesseurs. Cet article présente les principaux résultats sur l'ordonnancement des systèmes multiprocesseurs.
Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.
Lire l’articleABSTRACT
The simple act of adding an additional processor to the platform drastically increases the complexity of real-time scheduling problems. CL Liu, founder of the real-time scheduling realized, very early on, that very few known results in a uniprocessor environment could be directly generalized to multiprocessor systems. This article presents the main results on the scheduling of multiprocessor systems.
Auteur(s)
-
Pascal RICHARD : Professeur des universités en Informatique à l’université de Poitiers
-
Emmanuel GROLLEAU : Professeur des universités en Informatique à l’ISAE-ENSMA (Chasseneuil-du-Poitou)
-
Michaël RICHARD : Maître de conférences en Informatique à l’ISAE-ENSMA (Chasseneuil-du-Poitou)
-
Frédéric RIDOUARD : Maître de conférences en Informatique à l’université de Poitiers
INTRODUCTION
Depuis le début des années 2000, on perçoit un ralentissement de l’accroissement exponentiel (loi de Moore) des vitesses de calcul d’une génération de processeur à la suivante. Sur les ordinateurs personnels, l’accroissement en puissance de calcul est maintenu par un accroissement du nombre de cœurs de calcul sur une même puce. Ce phénomène peut être expliqué par la miniaturisation atteinte par les fondeurs de processeurs sur une technologie basée sur des transistors en silicium : pour une taille de transistors donnée, accélérer la vitesse de calcul a un coût quadratique en énergie. Or, la taille d’un transistor n’est aujourd’hui que de quelques atomes ; elle est donc de plus en plus difficile à diminuer, et les gains en fréquence des calculateurs se font alors de moins en moins sentir.
Lorsque les calculateurs sont embarqués sur un procédé (avion, automobile, train, satellite artificiel, etc.) contrôlé par un système, le compromis entre puissance de traitement et énergie consommée penche souvent en faveur de la limitation des fréquences de calcul des processeurs embarqués lorsque ceux-ci sont alimentés sur batterie, énergie ambiante ou en consommant du carburant. La diminution de la puissance des calculateurs est alors compensée par la multiplication de leur nombre pour une même puissance globale de calcul.
On peut naturellement envisager deux façons de multiplier les calculateurs : connecter plusieurs calculateurs par des réseaux de communication (on parle alors de systèmes répartis) ou bien mettre sur une même puce plusieurs cœurs de calculs (on parle alors de systèmes multiprocesseurs ou multicœurs lorsque les cœurs de calcul sont sur une même puce). Bien entendu, on peut associer les deux et avoir des réseaux de communication reliant des systèmes multicœurs.
Sur un système critique complexe, tel qu’un avion civil, le système de contrôle est constitué d’un système réparti de systèmes monoprocesseurs. L’architecture avionique de demain, et vraisemblablement celle des autres types systèmes embarqués complexes doit augmenter les ressources de calcul sans augmenter la complexité du réseau de communication déjà très complexe dans ces systèmes. Ainsi, l’architecture des systèmes critiques de demain sera constituée de systèmes répartis multicœurs.
Les systèmes embarqués critiques sont généralement soumis à des contraintes de temps : chaque fonctionnalité doit s’exécuter dans un intervalle de temps donné, malgré le fait que les ressources de calcul sont partagées entre plusieurs fonctionnalités. On parle alors de systèmes embarqués temps réel, qui doivent être non seulement valides fonctionnellement mais aussi temporellement.
L’objet de cet article est de présenter la problématique de la validation temporelle d’applications temps réel sur processeurs multicœurs. Il peut être considéré comme la suite de l’article [S 8 055v2] et de l’article [S 8 056].
L’avènement des systèmes multiprocesseurs dans les domaines des systèmes critiques pose de nombreux défis scientifiques et entre autres :
-
la validation temporelle, à travers l’étude de l’ordonnancement des traitements sur les cœurs de calcul, leurs migrations éventuelles, leurs placements, etc. ;
-
le calcul de pire durée d’exécution d’un traitement, en fonction des migrations éventuelles. Dans certains cas, de nombreuses migrations simultanées peuvent utiliser intensivement le réseau pour passer les données d’un cœur à un autre, et ainsi une migration peut au pire subir un délai très important. De même, sur certaines architectures avec caches hiérarchisés, la durée de déplacement des données en cache d’un cœur vers un autre dépend du placement des cœurs source et de la destination dans la hiérarchie de caches ;
-
le routage et l’optimisation de l’utilisation du réseau reliant les cœurs de calcul : on parle de NOC (Network On Chip).
-
Les accès simultanés à des ressources partagées (p.ex., mémoire) peuvent mener à une dégradation significative du temps d'exécution des programmes.
Cet article se focalise sur l’ordonnancement et la validation temporelle sur systèmes multicœurs. La problématique étant en elle-même complexe, l’aspect surcoût éventuel lié aux migrations est le plus souvent négligé dans les modèles utilisés. Cependant, il faut avoir conscience du fait que les migrations, surtout lorsqu’elles sont nombreuses et simultanées, n’ont dans la réalité pas un coût négligeable.
MOTS-CLÉS
panorama problématiques techniques de base Transport énergie système embarqué informatique temps réel systèmes multiprocesseurs
KEYWORDS
survey | problems | solving technics | transport | energy | embedded systems | real-time systems | multiprocessor systems
DOI (Digital Object Identifier)
CET ARTICLE SE TROUVE ÉGALEMENT DANS :
Accueil > Ressources documentaires > Technologies de l'information > Technologies logicielles Architectures des systèmes > Systèmes embarqués > Ordonnancement temps réel - Ordonnancement multiprocesseur > Architectures des applications temps réel
Cet article fait partie de l’offre
Automatique et ingénierie système
(137 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Présentation
1. Architectures des applications temps réel
1.1 Architecture matérielle multiprocesseur
Les architectures matérielles sont généralement classées en deux catégories : les systèmes centralisés, qui s’exécutent sur une seule puce et les systèmes répartis ou distribués qui s’exécutent sur différentes puces distantes les unes des autres.
HAUT DE PAGE
Même si cette puce peut avoir plusieurs cœurs de calcul, on qualifie de centralisé un processeur contenu dans une seule puce, ou dans plusieurs puces « proches » se trouvant sur un même support physique.
La taxinomie de Flynn peut être employée pour désigner les familles de calculateurs :
-
SISD (Single Instruction Single Data) désigne les architectures de processeurs simples capables de traiter une instruction à la fois ;
-
SIMD (Single Instruction Multiple Data) met en œuvre des architectures vectorielles ou matricielles, comme sur les processeurs graphiques (GPU) ou bien sur des jeux d’instructions particulières permettant d’effectuer des calculs identiques sur plusieurs données à la fois ;
-
MISD (Multiple Instruction Single Data) traite parallèlement la même donnée et le même calcul, mais n’a pas ou a peu de mise en œuvre ;
-
MIMD (Multiple Instruction Multiple Data) est la catégorie d’architecture qui contient les systèmes multiprocesseurs ou multicœurs. Cette architecture permet d’exécuter simultanément plusieurs instructions sur des données différentes. C’est ce type d’architecture sous-jacente que nous considérons dans cet article.
Les architectures MIMD peuvent avoir une mémoire partagée (accédée par un bus, ou bien de façon hiérarchique), ou bien avoir une mémoire distribuée (chaque processeur possède sa propre mémoire). Dans le cas d’une mémoire distribuée, les données sont échangées par le biais de messages passés entre les processeurs,...
Cet article fait partie de l’offre
Automatique et ingénierie système
(137 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive
Architectures des applications temps réel
BIBLIOGRAPHIE
-
(1) - CARPENTER (J.), FUNK (S.), HOLMAN (P.), SRIVINASAN (A.), ANDERSON (J.), BARUAH (S.) - * - . – A categrization of real-time multiprocessor scheduling problems and algorithms chez Hanbook of Scheduling : Algorithms, Models, and Performance Analysis, Chapman Hall/CRC Press (2004).
-
(2) - LEUNG (J.), WHITEHEAD (J.) - On the complexity of fixed-priority scheduling of periodic real-time tasks - Performance Evaluation, vol. 2, n° 14, pp. 237-250 (1982).
-
(3) - HORN (W.) - Some simple scheduling algorithms - Naval Research Logistics Quaterly, vol. 21, pp. 177-185 (1974).
-
(4) - HONG (K.), LEUNG (J.) - On-line scheduling of real-time tasks - IEEE Transactions on Computers, vol. 41, n° 110, pp. 1326-1331 (1992).
-
(5) - DERTOUZOS (M.), MOK (A.) - Multiprocessor Online Scheduling of Hard-Real-Time Tasks - IEEE Transactions on Software Engineering, vol. 15, pp. 1497-1506 (1989).
-
...
Cet article fait partie de l’offre
Automatique et ingénierie système
(137 articles en ce moment)
Cette offre vous donne accès à :
Une base complète d’articles
Actualisée et enrichie d’articles validés par nos comités scientifiques
Des services
Un ensemble d'outils exclusifs en complément des ressources
Un Parcours Pratique
Opérationnel et didactique, pour garantir l'acquisition des compétences transverses
Doc & Quiz
Des articles interactifs avec des quiz, pour une lecture constructive