Contrôle en ligne des systèmes multiprocesseurs hétérogènes embarqués

Définition du parallélisme et limitations

              En architecture, le parallélisme est lié à la possibilité de pouvoir exécuter plusieurs traitements simultanément. On définit deux types de parallélisme : le parallélisme de données et le parallélisme de contrôle. Le parallélisme de données consiste à exécuter une même opération sur des unités de calcul et des données différentes. A l’inverse, le parallélisme de contrôle exécute des opérations différentes simultanément. Pour cela, les différents traitements exécutés en parallèle doivent être indépendants. Deux traitements sont indépendants sur les données lorsque leurs opérandes peuvent être utilisées de manière concurrente et lorsque le résultat d’un des traitements n’a pas d’incidence sur l’autre traitement. Une formalisation de ce principe a été établi par H.J. Bernstein en 1966 [2]. On dit également qu’ils sont indépendants sur le séquencement si l’exécution d’un des traitements n’est pas conditionné par l’exécution de l’autre traitement. Statistiquement, la probabilité d’occurence des dépendances croît avec le nombre d’instructions que l’on désire exécuter en parallèle. Autrement dit, le parallélisme est restreint dans chaque application et séquence d’instructions [3, 4]. En pratique, des techniques particulières sont utilisées pour limiter l’effet de ces dépendances. Celles-ci se déclinent en deux approches : la première consiste à accélérer le transfert entre les éléments qui produisent l’information et ceux qui l’utilisent. La seconde prédit, par des techniques statistiques, les valeurs que prendront ces résultats intermédiaires [5]. Les valeurs spéculées permettent de poursuivre l’exécution des instructions tant que celles-ci ne remettent pas en cause l’état des mémoires et des registres. On parle alors d’exécution spéculative. Dès que les valeurs des résultats intermédiaires sont connues, les exécutions spéculatives sont transformées en exécutions normales ou sont détruites. Pour ne pas trop pénaliser les performances, les mécanismes de prédiction doivent être les plus efficaces possibles. D’autres techniques peuvent être utilisées pour réduire les dépendances de données. Elles consistent notamment à renommer dynamiquement les registres physiques qui contiennent les dernières valeurs des registres utilisés par le programme. Enfin, des techniques de compilation particulières sont employées pour limiter le coût de l’extraction du parallélisme au cours de l’exécution. Les techniques de compilation permettent de supprimer des dépendances de contrôle et de donnée, ainsi que d’extraire, par exemple, le parallélisme dans les cœurs de boucle. En fait, deux programmes peuvent être exécutés en parallèle s’ils sont indépendants, si la méthode d’extraction du parallélisme choisie est appropriée et s’il existe suffisamment de ressources pour qu’ils puissent s’exécuter simultanément. En effet, si deux traitements doivent partager une ressource commune, leur exécution concurrente ne garantit plus l’intégrité et la cohérence des données. Des mécanismes de synchronisation doivent alors être mis en place au niveau applicatif ou architectural sous la forme, par exemple, de sémaphores ou de verrous. Le sémaphore permet la coordination asynchrone entre des traitements parallèles, alors que le verrou peut être utilisé pour rendre exclusif l’accès aux ressources partagées. Cela se traduit en général, au niveau architectural, par la mise en place de registres de synchronisation. Bien souvent, même si les traitements sont considérés comme étant indépendants, les synchronisations demeurent inévitables. Par exemple, une application peut être constituée d’une tâche pour l’affichage des résultats et d’une autre pour leur élaboration. A la fin de l’obtention des résultats, la tâche de calcul se synchronise avec la tâche de visualisation pour les afficher. Ceci contribue à réduire les performances du système puisque la non-disponibilité d’une ressource empêche le traitement de se poursuivre.

Exécution successive

               Les architectures multitâches à exécution successive change la tâche à exécuter après chaque cycle d’exécution (figure 1.6-a). Les architectures HEP [33], MASA [34], Alewife [35] ou Cray MTA [36] illustrent ce principe. L’avantage de cette solution est qu’il n’est plus nécessaire de disposer de matériel complexe pour spéculer l’exécution des instructions. Les dépendances de contrôle et de données sont éliminées. De plus, le pipeline peut atteindre un bon niveau d’occupation. Par ailleurs, la latence d’accès aux instructions ou du changement de contexte n’a pas d’incidence sur les temps d’exécution. Cependant, cette architecture nécessite d’exécuter simultanément au moins autant de tâches qu’il y a d’étages de pipeline. Il est cependant possible de permettre l’exécution successive d’instructions indépendantes d’une même tâche. Mais ceci est parfois difficile à obtenir par les outils de compilation. Le fait d’avoir conçu une architecture devant exécuter plusieurs tâches les unes à la suite des autres limite la puissance de calcul disponible pour une seule tâche. Le processeur MTA développé par Cray a, par exemple, une efficacité transistor de 0,62- GOPs/MT et une efficacité énergétique inférieure à 0,02 MOPs/mW. Par conséquent, l’efficacité transistor a été améliorée par rapport aux architectures superscalaires, malgré un grand nombre de registres pour l’exécution successive de ses 128 tâches. Ceci est principalement dû à la simplification de l’architecture et de son contrôle.

Le contrôle logiciel des multiprocesseurs asymétriques

              Les techniques de contrôle logicielles sont presque toujours utilisées avec les architectures multiprocesseurs. La première approche consiste à partitionner les applications en tâches indépendantes en tenant compte de la structure de l’architecture. Cette méthode est par exemple exploitée par l’outil SynDEx (Synchronized Distributed Execution) de l’INRIA Rocquencourt [78, 79] ou SPEAR (Signal Processing Environments and ARchitectures) du groupe Thales [80]. Elle repose sur la distribution statique des tâches et n’a alors pas besoin d’ordonnancement. L’avantage de cette solution est sa simplicité de mise en œuvre matérielle. Néanmoins, l’ordonnancement statique des tâches ne permet pas la création dynamique d’application et souffre d’une faible réactivité. La réactivité est une grandeur caractérisant le temps de prise en compte des informations provenant des ressources matérielles et d’exécution du contrôle correspondant. Ceci limite la flexibilité du système et l’empêche de s’adapter aux évènements ou aux contraintes extérieures. Contrairement à cette approche statique, la seconde solution utilise un programme qui agit comme un intermédiaire entre l’utilisateur et le matériel. Il est appelé système d’exploitation (SE) [81, 82]. Son but est d’abstraire la complexité de l’architecture et de faciliter sa programmation. Il sélectionne également les tâches à exécuter, les ordonnance et les alloue sur une ressource de calcul adaptée. Avant d’étudier quelles sont les solutions employées dans les multiprocesseurs asymétriques, nous allons détailler leur fonctionnement et tenter d’explorer l’ensemble des solutions qu’il est possible d’utiliser.

Le contrôle matériel des multiprocesseurs asymétriques

              Dans la conception de systèmes électroniques, deux mondes se complètent et s’opposent. D’un côté, les architectes sont spécialisés dans la conception de solutions matérielles et tentent de relever tous les défis qu’ils rencontrent, en proposant essentiellement des évolutions matérielles. D’un autre côté, les développeurs de logiciels choisissent d’abstraire la complexité des architectures pour concevoir des applications de plus en plus complexes. Malheureusement, ceci empêche de pouvoir pleinement exploiter les améliorations des architectures qui doivent être de plus en plus évoluées pour continuer à apporter suffisamment de performances aux applications. Ainsi, le système d’exploitation est un élément non optimisé et est bien souvent considéré comme étant une contrainte pour l’architecte, bien qu’il soit une nécessité pour le développeur. Ce paradoxe existe depuis de nombreuses années. La situation est restée inchangée malgré les tentatives de simplification des structures des systèmes d’exploitation (micro-noyaux), la réduction de leur fonctionnalité et les améliorations des techniques de compilation. En pratique, le souci de garder une programmabilité importante sans changer le modèle de programmation reste un frein important. De ce point de vue, la plateforme de programmation OpenMP [132] est une avancée majeure. Les architectes ont alors tenté d’apporter des solutions supplémentaires. Celles-ci ont principalement consisté à étendre le jeu d’instructions en y intégrant des primitives de contrôle particulières, ou encore à se passer d’un contrôle logiciel en concevant des solutions dédiées (ASIC : Application Specific Integrated Circuit) [136]. Ainsi, des solutions sont apparues pour tenter d’accorder davantage les besoins applicatifs avec les architectures. Mais l’exercice est difficile car il n’est pas aisé de maîtriser l’ensemble du flot de conception d’un système embarqué. Tout d’abord, les architectes ont accéléré quelques primitives de contrôle à l’aide d’un coprocesseur ou d’un accélérateur matériel. Puis, ils ont intégré de plus en plus de fonctionnalités, jusqu’à mettre en œuvre des systèmes d’exploitation temps-réel sur silicium. Le fait de déporter une partie des services offerts normalement par le système d’exploitation, permet d’améliorer sensiblement la latence du contrôle, la prise en compte des interruptions, la précision des horloges ou le temps de disponibilité du processeur pour l’exécution des tâches.

Table des matières

Introduction
Le contexte de l’étude
La problématique de l’étude
L’organisation du manuscrit
1 Les architectures parallèles pour les systèmes embarqués
1.1 Définition du parallélisme et limitations 
1.2 Contraintes des systèmes embarqués
1.3 Classification des architectures parallèles 
1.4 Techniques d’accélération des processeurs monotâches 
1.4.1 Unité d’exécution unique
1.4.2 Unités d’exécution multiples
1.4.3 Conclusion
1.5 Les processeurs multitâches
1.5.1 Exécution successive
1.5.2 Exécution bloquée
1.5.3 Exécution simultanée
1.5.4 Synthèse des processeurs multitâches
1.6 Les multiprocesseurs 
1.6.1 Avec des processeurs monotâches
1.6.2 Avec des processeurs multitâches
1.7 Synthèse 
2 Le contrôle des architectures multiprocesseurs 
2.1 Le contrôle logiciel des multiprocesseurs asymétriques 
2.1.1 Les systèmes d’exploitation
2.1.2 Les exécutifs temps-réel
2.1.3 Exemples de techniques employées dans les architectures CMP
2.1.4 Limitations de l’approche logicielle
2.2 Le contrôle matériel des multiprocesseurs asymétriques 
2.2.1 Principe et état de l’art des accélérateurs de noyau temps-réel
2.2.2 Les accélérateurs de noyau temps-réel pour les multiprocesseurs
2.2.3 Synthèse de l’approche matérielle
2.3 Synthèse
3 L’architecture SCMP-LC 
3.1 Identification des problèmes liés aux multiprocesseurs 
3.1.1 Les dépendances de contrôle et de données
3.1.2 L’occupation des ressources de calcul
3.1.3 Le déterminisme
3.1.4 Bilan des solutions proposées
3.2 Présentation et caractéristiques de l’architecture SCMP-LC 
3.2.1 Couplage et principe d’utilisation
3.2.2 Caractérisation d’une tâche
3.2.3 Modèle d’exécution
3.3 Principe de l’exécution 
3.3.1 Exécution d’une application
3.3.2 Exécution flot de données
3.4 Caractérisation des ressources
3.4.1 Ressources de calcul
3.4.2 Ressources de mémorisation
3.4.3 Ressources d’interconnexion
3.5 Synthèse 
4 L’architecture OSoC 
4.1 Présentation et caractéristiques
4.2 Modèle de programmation
4.2.1 Des réseaux de Petri
4.2.2 …à une modélisation haut niveau
4.2.3 Synthèse
4.3 Gestion des tâches et mise en œuvre du contrôle
4.3.1 Présentation du RAC
4.3.2 Modifications du RAC
4.3.3 Mise en œuvre de la sélection dynamique des tâches
4.3.4 Conclusion
4.4 Ordonnancement des tâches 
4.4.1 Ordonnancement non-temps-réel multiprocesseur
4.4.2 Ordonnancement temps-réel multiprocesseur
4.4.3 Ordonnancement basse-consommation multiprocesseur
4.4.4 Mise en œuvre de l’ordonnancement dans l’OSoC
4.5 Allocation des tâches 
4.6 Communications et interface 
4.7 Synthèse 
5 Validation de l’architecture OSoC 
5.1 Validations et implémentation matérielle
5.1.1 La méthodologie de conception et de validation
5.1.2 Validation fonctionnelle
5.1.3 Validation matérielle
5.1.4 Conclusion
5.2 Mise en œuvre d’applications et analyse des performances 
5.2.1 Introduction
5.2.2 Analyse des performances
5.2.3 Conclusion
5.3 Comparaisons matériel/logiciel 
5.3.1 Caractéristiques du noyau temps-réel
5.3.2 Analyse des résultats et des performances
5.3.3 Conclusion
5.4 Comparaisons avec MicroCOS-II et l’état de l’art
5.4.1 Comparaison avec MicroCOS-II
5.4.2 Comparaison avec les autres accélérateurs matériels
5.5 Synthèse 
Conclusions et perspectives
Synthèse des contributions
Perspectives
A court terme
A long terme
Glossaire

Télécharger le rapport complet