Th. univ.--Autom.--Grenoble--I.N.P., 1980. N°: DU 7.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

De nos jours, les systèmes d'actionnement électriques à hautes performances sont présents dans de nombreux domaines tels que les structures automatisées complexes, la robotique ou l'aéronautique. Les algorithmes de commande de ces actionneurs ont évolué au cours des années, et ont atteint une complexité qui exige des calculateurs numériques dotés d'une puissance de calcul importante. Par ailleurs, le contexte dans lequel ces actionneurs sont utilisés impose une fiabilité et un respect des contraintes temps-réel qui n'est pas offert par les processeurs classiques du marché. C'est dans ce cadre que nous avons développé une architecture multiprocesseur entièrement intégrée dédiée à la commande de machines à courant alternatif. Nous avons montré qu'une architecture de type multiprocesseur offre des avantages en termes de souplesse et de fiabilité dans le cadre qui nous intéresse. Nous avons ensuite, sur base des contraintes propres à la commande d'actionneurs électriques et de celles dues à la présence de plusieurs processeurs sur un seul circuit intégré, conçu une architecture de processeur de type RISC adapté aux besoins, ainsi que des périphériques et un système de communication. Des simulations, effectuées sur un modèle complet du circuit, associé à un modèle de moteur et d'électronique de puissance, ont permis de valider les hypothèses qui ont été posées au cours de ce travail.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

.

Les applications temps réel modernes deviennent plus exigeantes en termes de ressources et de débit amenant la conception d'architectures multiprocesseurs. Ces systèmes, des équipements embarqués au calculateur haute performance, sont, pour des raisons d'autonomie et de fiabilité, confrontés des problèmes cruciaux de consommation d'énergie. Pour ces raisons, cette thèse propose de nouvelles techniques d'optimisation de la consommation d'énergie dans l'ordonnancement de systèmes multiprocesseur. La premiére contribution est un algorithme d'ordonnancement hiérarchique á deux niveaux qui autorise la migration restreinte des tâches. Cet algorithme vise á réduire la sous-optimalité de l'algorithme global EDF. La deuxiéme contribution de cette thèse est une technique de gestion dynamique de la consommation nommée Assertive Dynamic Power Management (AsDPM). Cette technique, qui régit le contrôle d'admission des tâches, vise á exploiter de manière optimale les modes repos des processeurs dans le but de réduire le nombre de processeurs actifs. La troisiéme contribution propose une nouvelle technique, nommée Deterministic Stretch-to-Fit (DSF), permettant d'exploiter le DVFS des processeurs. Les gains énergétiques observés s'approchent des solutions déjà existantes tout en offrant une complexité plus réduite. Ces techniques ont une efficacité variable selon les applications, amenant á définir une approche plus générique de gestion de la consommation appelée Hybrid Power Management (HyPowMan). Cette approche sélectionne, en cours d'exécution, la technique qui répond le mieux aux exigences énergie/performance.

Les systèmes temps réel à contraintes temporelles strictes sont caractérisés par des ensembles de tâches pour lesquelles sont connus l'échéance, le modèle d'arrivée (fréquence) et la durée d'exécution pire cas (WCET). Nous nous intéressons à l'ordonnancement de ces systèmes sur plate-forme multiprocesseur. Garantir le respect des échéances pour un algorithme d'ordonnancement est l'une des problématiques majeures de cette thématique. Nous allons plus loin en nous intéressant à la sûreté temporelle, que nous caractérisons par les propriétés (i) de robustesse et (ii) de viabilité. La robustesse consiste à proposer un intervalle sur les augmentations(i-a) de WCET et (i-b) de fréquence tel que les échéances soient respectées. La viabilité consiste cette fois à garantir le respect des échéances lors du relâchement des contraintes (ii-a) de WCET (réduction), (ii-b) de fréquence (réduction) et (ii-c) d'échéance(augmentation). La robustesse revient alors à tolérer l'imprévu, tandis que la viabilité est la garantie que l'algorithme d'ordonnancement n'est pas sujet à des anomalies suite à un relâchement de contraintes. Nous considérons l'ordonnancement en priorités fixes, où chaque occurrence d'une tâche est ordonnancée avec la même priorité. Dans un premier temps, nous étudions la propriété de robustesse dans les approches d'ordonnancement hors-ligne et sans migration (partitionnement). Nous traitons le cas des tâches avec ou sans partage de ressources. Dans un second temps, nous étudions la propriété de viabilité d'une approche d'ordonnancement en ligne avec migrations restreintes et sans partage de ressources / The hard real-time systems are characterized by sets of tasks for which are known the deadline, the arrival model (frequency) and the Worst-Case Execution Time (WCET). We focus on the scheduling of these systems on multiprocessor platforms. One of the main issues of this topic is to ensure that all deadlines are met. We go further by focusing on the temporal safety which we characterized by the properties of (i) robustness and (ii) sustainability. The robustness consists in providing an interval on the increases of (i-a) WCET and (i-b) frequency in such a way that the deadlines are met. The sustainability consists in ensuring that no deadline is missed when the following constraints are relaxed : (ii-a) WCET (decreasing), (ii-b) frequency (decreasing) and (ii-c) deadline (increasing). The robustness amounts to tolerate unexpected behaviors while the sustainability is the guarantee that the scheduling algorithm does not suffer from anomalies because of a relaxation of constraints. We consider fixed-priority scheduling for which any job of a task is scheduled with the same priority. Firstly, we study the property of robustness in off-line scheduling approaches without migration (partitioning). We deal with the case of tasks with or without shared resources. Secondly, we study the property of sustainability of an online restricted-migration scheduling approach without shared resources

La complexité croissante des systèmes multiprocesseurs sur puce (MPSoC) rend la vie plus difficile aux ingénieurs à cause des bugs et des inefficacités qui peuvent avoir un très large éventail de sources. L'interaction matériel / logiciel peut être l'une de ces sources, dont l'identification précoce et la résolution doivent être une priorité pour l'intégration rapide du système. Ainsi, en raison du grand nombre d'entrelacements d'exécution possibles, reproduire les conditions d'apparition d'une erreur ou d'un problème de performance est très difficile. Une approche de ce problème consiste à tracer une exécution et exploiter cette trace en faisant des analyses postérieures. L'obtention de traces à partir de vrai matériel va à l'encontre du processus de développement récent, désormais largement adoptés par l'industrie et l'académie, qui repose sur la simulation pour anticiper l'intégration matériel / logiciel. De nombreux systèmes multi-cœurs sur puce ont tendance à avoir des hiérarchies mémoire spécifiques, pour rendre le matériel plus simple et prévisible, au prix de voir percoler les contraintes matérielles vers les niveaux élevés de la pile logicielle. Malgré les efforts des ingénieurs, il est difficile d'assurer que toutes les mesures de prévention sont prises pour assurer une propriété donnée, comme l’absence de course lors de l'accès aux variables partagées ou la cohérence des données. Dans ce contexte, le processus de débogage est particulièrement pénible car il implique d'analyser des flux d'exécution parallèles. L'exécution d'un programme à plusieurs reprises est une partie intégrale du processus de débogage classique, mais le non-déterminisme du fait de l'exécution en parallèle conduit souvent à différents chemins d'exécution et donc des comportements différents.Cette thèse détaille les défis et les enjeux derrière la production et l'exploitation des traces "bien formés" dans un environnement de prototypage virtuel qui utilise la traduction binaire dynamique comme technique de simulation des processeurs. Ces traces contiennent des relations de causalité entre les événements qui permettent, d'une part, de simplifier l'analyse et, d'autre part, d'éviter de faire confiance à des horloges globales pour synchroniser les événements. Nous proposons un formalisme de définition des traces et détaillons sa mise en œuvre qui permet de rester non-intrusif aussi bien du point de vue matériel que logiciel. Nous utilisons ces traces pour aider à identifier et corriger les bugs sur les plateformes qui ont multiple cœurs. Nous présentons tout d'abord une méthode pour identifier les violations potentielles de cohérence de cache dans des plates-formes possédant des caches mais qui n'ont pas de matériel garantissant leur cohérence. Notre méthode identifie des violations potentielles qui peuvent apparaître au cours d'une exécution donnée en analysant les traces pour les deux stratégies d’écritures de cache: "write-through" et "write-back". Finalement, Nous nous intéressons à la simplification du processus de débogage des logiciels exécutés en parallèle sur MPSoC en utilisant les traces. Dans cet objectif, nous proposons un processus de débogage qui rejoue une exécution fautive en utilisant des traces. Nous détaillons une stratégie pour fournir des fonctionnalités d'exécution inverse pour éviter des temps de simulation élevé pendant une session de débogage.Nous avons mené des expériences en utilisant des applications parallèles s'exécutant sur acs{MPSoC} pour quantifier notre proposition et montrer que l'ensemble des stratégies d'analyse et de débogage complexes peuvent être mis en œvre par des traces, conduisant ainsi à des résultats déterministes en moins de temps que la simulation seule. / The increasing complexity of Multiprocessor System on Chip (MPSoC) makes the engineers' life harder as bugs and inefficiencies can have a very broad range of sources. Hardware/software interactions can be one of these sources, their early identification and resolution being a priority for rapid system integration. Thus, due to the huge number of possible execution interleavings, reproducing the conditions of occurrence of a given error/performance issue is very difficult. One solution to this problem consists of tracing an execution for later analysis. Obtaining the traces from real platforms goes against the recent development processes, now broadly adopted by industry and academy, which rely on simulation to anticipate hardware/software integration. Multi/many core systems on chip tend to have specific memory hierarchies, to make the hardware simpler and predictable, at the cost of having the hardware percolate towards the high levels of the software stack. Despite the developers efforts, it is hard to make sure all preventive measures are taken to ensure a given property, such as lack of race conditions or data coherency. In this context, the debugging process is particularly tedious as it involves analyzing parallel execution flows. Executing a program many times is an integral part of the process in conventional debugging, but the non-determinism due to parallel execution often leads to different execution paths and different behaviors.This thesis details the challenges and issues behind the production and exploitation of "well formed" traces in a transaction accurate virtual prototyping environment that uses dynamic binary translation as processor simulation technology. These traces contain causality relations among events, which allow firstly to simplify the analysis, and secondly to avoid relying on timestamps. We propose a formalism to define the traces and detail an implementation to produce them in a non-intrusive manner. We use these traces to help identify and correct bugs on multi/many-core platforms. We firstly introduce a method to identify the potential cache coherence violations in non-cache-coherent platforms. Our method identifies potential violations which may occur during a given execution for write-through and write-back cache policies by analyzing the traces.We secondly focus on easing the debugging process of parallel software running on MPSoC using traces. To that aim, we propose a debugging process which replays a faulty execution using traces. We detail a strategy for providing forward and reverse execution features to avoid long simulation times during a debug session.We conducted experiments on MPSoC using parallel applications to quantify our proposal, and overall show that complex analysis and debug strategies can be implemented over traces, leading to deterministic results in shorter time than simulation alone.

L'ordonnancement de tâches sur un système temps réel dur correspond à trouver une façon de choisir, à chaque instant, quelle tâche doit être exécutée sur le processeur pour que chacune ait le temps de terminer son travail avant son échéance. Ce problème, dans le contexte monoprocesseur, est déjà bien étudié et permet des applications sur des systèmes en production (aérospatiale, bourse etc.). Aujourd'hui, les plateformes multiprocesseur se sont généralisées et ont amené de nombreuses questions telles que l'utilisation efficace de tous les processeurs. Dans cette thèse, nous explorons les approches existantes pour résoudre ce problème. Nous étudions tout d'abord l'approche par partitionnement qui consiste à utiliser les recherches existantes en ramenant ce problème à plusieurs systèmes monoprocesseur. Ici, nous proposons un algorithme générique dont les paramètres sont adaptables en fonction de l'objectif à atteindre. Nous étudions ensuite l'approche par semi-partitionnement qui permet la migration d'un nombre restreint de tâches. Nous proposons une solution avec des migrations restreintes qui pourrait être assez simplement implémentée sur des systèmes concrets. Nous proposons ensuite une solution avec des migrations non restreintes qui offre de meilleurs résultats mais est plus difficile à implémenter. Enfin, les programmeurs utilisent de plus en plus le concept de tâches parallèles qui peuvent utiliser plusieurs processeurs en même temps. Ces tâches sont encore peu étudiées et nous proposons donc un nouveau modèle pour les représenter. Nous étudions les ordonnanceurs possibles et nous définissons une façon de garantir l'ordonnançabilité de ces tâches pour deux d'entre eux / The scheduling of tasks on a hard real-time system consists in finding a way to choose, at each time instant, which task should be executed on the processor so that each succeed to complete its work before its deadline. In the uniprocessor case, this problem is already well studied and enables us to do practical applications on real systems (aerospace, stock exchange etc.). Today, multiprocessor platforms are widespread and led to many issues such as the effective use of all processors. In this thesis, we explore the existing approaches to solve this problem. We first study the partitioning approach that reduces this problem to several uniprocessor systems and leverage existing research. For this one, we propose a generic partitioning algorithm whose parameters can be adapted according to different goals. We then study the semi-partitioning approach that allows migrations for a limited number of tasks. We propose a solution with restricted migration that could be implemented rather simply on real systems. We then propose a solution with unrestricted migration which provides better results but is more difficult to implement. Finally, programmers use more and more the concept of parallel tasks that can use multiple processors simultaneously. These tasks are still little studied and we propose a new model to represent them. We study the possible schedulers and define a way to ensure the schedulability of such tasks for two of them

Cette thèse est consacrée a l'étude de l'implantation du langage Prolog sur les architectures parallèles Mimd sans mémoire commune. Nous présentons le modèle opéra qui exploite implicitement le parallélisme ou le Prolog pour repartir dynamiquement l'évaluation des programmes sur les différents nœuds du réseau de processeurs. Le système opéra est de type multisequentiel: il n'y a parallélisation que lorsqu'un processeur est inoccupé. Ce système se décompose en une partie operative chargée de l'évaluation du programme Prolog, et une partie contrôle chargée de l'allocation des travaux aux processeurs de la partie operative. Les principaux problèmes de ce type de systèmes sont d'une part le choix de représentation en mémoire de l'arbre ou ainsi que la gestion des liaisons multiples, et d'autre part, le contrôle de l'allocation des différentes branches de l'arbre aux machines abstraites qui effectuent des évaluations séquentielles. La technique de régulation de charge utilisée est fondée sur des méthodes heuristiques. L'ordonnanceur d'opera travaille sur une image approchée de l'état global du système obtenu par échantillonnage des états locaux de chaque unités de travail. Un prototype d'opera a été réalisé sur un réseau de transputers reconfigurable dynamiquement: le supernode. Cette propriété a ete mise a profit dans notre implantation pour réduire les couts de communication. Les communications sont effectuées en parallèle avec le calcul. Le prototype réalisé fournit des gains de performances importants et opera figure parmi les systèmes Prolog parallèles les plus efficaces a l'heure actuelle