Thèse de doctorat : Informatique : INPL : 2007. / Titre provenant de l'écran-titre.

Thèse de doctorat : génie industriel : Ecole centrale de Paris : 2009. / Titre provenant de l'écran-titre. Bibliogr. 116 réf.

Dans cette thèse nous étudions le problème d'ordonnancement temps réel multiprocesseur préemptif avec prise en compte du coût exact du système d'exploitation. Ce coût est formé de deux parties : une partie facile à déterminer, correspondant au coût de l'ordonnanceur et une partie difficile à déterminer, correspondant au coût de la préemption. Cette difficulté est due au fait qu'une préemption peut en engendrer une autre, pouvant ainsi créer un phénomène d'avalanche. Dans un premier temps, nous avons étudié l'ordonnancement hors ligne multiprocesseur de tâches indépendantes avec prise en compte du coût exact de la préemption et proposé une analyse d'ordonnançabilité fondée sur une heuristique d'ordonnancement multiprocesseur. Cette heuristique utilise la stratégie d'ordonnancement multiprocesseur par partitionnement. Pour prendre en compte le coût exact de la préemption sur chaque processeur nous avons utilisé la condition d'ordonnançabilité proposée par Meumeu et Sorel. Cette condition d'ordonnançabilité pour des tâches à priorités fixes, est basée sur une opération binaire d'ordonnancement qui permet de compter le nombre exact de préemption et d'ajouter leur coût dans l'analyse d'ordonnançabilité des tâches. L'heuristique proposée permet de maximiser le facteur d'utilisation restant afin de répartir équitablement les tâches sur les processeurs et de réduire leur temps de réponse. Elle produit une table d'ordonnancement hors ligne. Dans un second temps, nous avons étudié l'ordonnancement hors ligne multiprocesseur de tâches dépendantes avec prise en compte du coût exact de la préemption. Puisque la condition d'ordonnançabilité utilisée pour ordonnancer les tâches indépendantes ne s'applique qu'à des tâches à priorités fixes, elle ne permet pas de gérer les inversions de priorités que peuvent entraîner les tâches dépendantes. Nous avons donc proposé une nouvelle condition d'ordonnançabilité pour des tâches à priorités dynamiques. Elle prend en compte le coût exact de la préemption et les dépendances sans aucune perte de données. Ensuite en utilisant toujours la stratégie d'ordonnancement par partitionnement, nous avons proposé pour des tâches dépendantes une heuristique d'ordonnancement multiprocesseur qui réutilise cette nouvelle condition d'ordonnançabilité au niveau de chaque processeur. Cette heuristique d'ordonnancement prend en compte les coûts de communication inter-processeurs. Elle permet aussi de minimiser sur chaque processeur le makespan (temps total d'exécution) des tâches. Cette heuristique produit pour chaque processeur une table d'ordonnancement hors ligne contenant les dates de début et de fin de chaque tâches et de chaque commmunication inter-processeur. En supposant que nous avons une architecture multiprocesseur de type dirigée par le temps (Time-Triggered) pour laquelle tous les processeurs ont une référence de temps unique, nous avons proposé pour chacun des processeurs un ordonnanceur en ligne qui utilise la table d'ordonnancement produite lors de l'ordonnancement hors ligne. Cet ordonnanceur en ligne a l'avantage d'avoir un coût constant qui de plus est facile à déterminer de manière exacte. En effet il correspond uniquement au temps de lecture dans la table d'ordonnancement pour obtenir la tâche sélectionnée lors de l'analyse d'ordonnançabilité hors ligne, alors que dans les ordonnanceurs classiques en ligne ce coût correspond à mettre à jour la liste des tâches qui sont dans l'état prêt à l'exécution puis à sélectionner une tâche selon un algorithme, par exemple RM, DM, EDF, etc. Il varie donc avec le nombre de tâches prêtes à s'exécuter qui change d'une invocation à l'autre de l'ordonnanceur. C'est ce coût qui est utilisé dans les analyses d'ordonnançabilités évoquées ci-dessus. Un autre avantage est qu'il n'est pas nécessaire de synchroniser l'accès aux mémoires de données partagées par plusieurs tâches, car cette synchronisation a été déjà effectuée lors de l'analyse d'ordonnançabilité hors ligne.

Thèse (M.Inf.) -- Université du Québec à Montréal, programme offert par extension à l'Université du Québec à Chicoutimi, 2008. / La p. de t. porte en outre: Mémoire présenté à l'Université du Québec à Chicoutimi comme exigence partielle de la maîtrise en informatique offerte à l'Université du Québec à Chicoutimi en vertu d'un protocole d'entente avec l'Université du Québec à Montréal. CaQQUQ Bibliogr.: f. 79-88. Publié aussi en version électronique. CaQQUQ

Nous nous intéressons à la mise en oeuvre effective d'applications temps réel dans une approche d'ordonnancementhors-ligne de systèmes de tâches périodiques. L'ordonnancement hors-ligne consiste à rechercher avantl'exécution de l'application une séquence pire cas, c'est-à-dire une suite de blocs indiquant une date de débutet de fin d'exécution d'une instance de tâche. Mettre en oeuvre une séquence suppose de spécifier ce qui doit sepasser quand les durées d'exécution réelles sont inférieures aux durées pire cas prévues par la séquence. Notrepremière contribution consiste en la proposition de deux politiques de mise en oeuvre : une politique inflexiblequi respecte strictement les dates de début des blocs ; et une politique flexible qui permet de les avancer. Nousprouvons que ces politiques préservent la validité des séquences. Nous proposons ensuite un modèle de coûtspour l'évaluation et la comparaison de techniques respectant les politiques proposées. La seconde contributionconcerne la proposition de techniques de mise en oeuvre. Dans un premier temps, nous proposons sept techniquesde mise en oeuvre dans un contexte de tâches indépendantes et séquences sans préemption. Nous étendonsensuite l'utilisation de ces techniques aux séquences avec préemption, et aux tâches partageant des ressourcescritiques ou soumises à des contraintes de précédence. La troisième contribution concerne la mise en oeuvresous Posix. Nous présentons des outils de génération de code issus de l'ingénierie dirigée par les modèles. Nousproposons également un outil d'observation de séquences effectives. Enfin, une étude de cas présente l'utilisationpratique de notre approche. / We address the implementation of periodic task sets for off-line scheduling. Off-line scheduling approach consistsin computing a worst-case schedule before runtime. Implementing a schedule requires to specify what must happenwhen the actual execution times of tasks are lower than the planned execution times. The first contributionconsist of the formalization of implementation policies. These policies consider the date by which a task maystart execution, which may or not occur before the planned start time. The inflexible policy does not allowa task to run before its planned start time, the flexible policy does. Since many implementations can complywith these two policies, we also propose a cost model which enables to perform some comparisons betweenthese implementations. The second contribution is the proposition and the presentation of a set of algorithmswhich implement the pre-computed schedules. We first deal with independent task sets in a non preemptivecontext. These algorithms are then adapted to be used in the context of preemptive scheduling, with sharedcritical ressources and precedence constraints. Using the model driven engeneering, we next provide a Posixcode generation tool. We also present a schedule observation tool. Finally, our work has been tested through apratical case study.

Bien que les accélérateurs fassent désormais partie intégrante du calcul haute performance, les gains observés ont un impact direct sur la programmabilité, de telle sorte qu'un support proposant des abstractions portables est indispensable pour tirer pleinement partie de toute la puissance de calcul disponible de manière portable, malgré la complexité de la machine sous-jacente. Dans cette thèse, nous proposons un modèle de support exécutif offrant une interface expressive permettant notamment de répondre aux défis soulevés en termes d'ordonnancement et de gestion de données. Nous montrons la pertinence de notre approche à l'aide de la plateforme StarPU conçue à l'occasion de cette thèse. / Multicore machines equipped with accelerators are becoming increasingly popular in the HighPerformance Computing ecosystem. Hybrid architectures provide significantly improved energyefficiency, so that they are likely to generalize in the Manycore era. However, the complexity introducedby these architectures has a direct impact on programmability, so that it is crucial toprovide portable abstractions in order to fully tap into the potential of these machines. Pure offloadingapproaches, that consist in running an application on regular processors while offloadingpredetermined parts of the code on accelerators, are not sufficient. The real challenge is to buildsystems where the application would be spread across the entire machine, that is, where computationwould be dynamically scheduled over the full set of available processing units.In this thesis, we thus propose a new task-based model of runtime system specifically designedto address the numerous challenges introduced by hybrid architectures, especially in terms of taskscheduling and of data management. In order to demonstrate the relevance of this model, we designedthe StarPU platform. It provides an expressive interface along with flexible task schedulingcapabilities tightly coupled to an efficient data management. Using these facilities, together witha database of auto-tuned per-task performance models, it for instance becomes straightforward todevelop efficient scheduling policies that take into account both computation and communicationcosts. We show that our task-based model is not only powerful enough to provide support forclusters, but also to scale on hybrid manycore architectures.We analyze the performance of our approach on both synthetic and real-life workloads, andshow that we obtain significant speedups and a very high efficiency on various types of multicoreplatforms enhanced with accelerators.

Des perturbations industrielles ont amené de profondes transformations des systèmes d'ordonnancement et de planification en temps réel, dans le contexte d'un environnement manufacturier de plus en plus dynamique coomme l'humain est au cœur de ces processus. Il est nécessaire d'assurer une synergie entre les opérateurs et les machines. En plus des objectifs comme la réduction des retards et des coûts, il serait essentiel de prendre en compte les aspects tels que l'équité de la charge de travail entre les opérateurs et la répétitivité des tâches. Toutefois dans la littérature, l'intégration de ces facteurs est peu abordée. Nous proposons dans ce projet d'appliquer des méthodes qui visent à réduire l'écart de charge de travail entre les opérateurs tout en favorisant la répétitivité des tâches assignées de manière à favoriser la prise d'habitudes - deux objectifs pouvant sembler contradictoires. Dans cet esprit, nous avons en premier lieu pris le temps de bien comprendre le modèle d'ordonnancement initial utilisé par le partenaire industriel, puis nous avons fait un survol de la littérature en relation avec l'allocation des tâches aux opérateurs dans le milieu manufacturier et la prise en compte des deux aspects : l'équité de la charge de travail et la répétitivité des tâches. En deuxième lieu, nous avons proposé deux familles de méthodes pour assurer l'équité de la charge de travail sans modifier le modèle d'ordonnancement déjà en place. La première famille fait le prétraitement des données en entrée du système de planification. La deuxième famille consiste à utiliser des approches de post-traitement pour ajuster le plan d'allocation. Des méthodes combinées ont aussi été testées. Les méthodes combinées avec des données réelles ont démontré une supériorité par rapport aux autres méthodes, avec une réduction de 70% de l'écart de charge de travail entre les opérateurs sur une semaine type de travail par rapport au modèle initial. En troisième lieu, nous avons proposé de nouvelles méthodes pour maximiser la répétitivité des tâches des opérateurs. Tenant compte de la complexité du modèle initial et la volonté de cibler plusieurs objectifs à la fois (retards, équité et répétitivité), un compromis entre l'équité et la répétitivité est recherché. Une étude expérimentale utilisant des données réelles collectées chez notre partenaire industriel démontre qu'en permettant seulement une dégradation de 10% du respect de l'équité, nous pouvons atteindre un niveau acceptable de répétitivité. / Industrial disruptions are leading to profound transformations in real-time scheduling and planning systems, in the context of an increasingly dynamic manufacturing environment. Humans are at the heart of these processes, and it is essential to ensure synergy between operators and machines. Although these systems often focus on objectives such as reducing delays and costs, it would be essential to take into account aspects such as workload equity between operators and task repeatability. However, the integration of these factors remains complex. In this project, we are proposing to apply methods that aim to reduce the difference in workloads between operators, while at the same time encouraging the repeatability of assigned tasks so as to promote operators' habits - two objectives that may seem contradictory. To this end, we first took the time to fully understand the initial scheduling model used by the industrial partner, then reviewed the literature in relation to the operator in new industrial eras and the two aspects in question. Second, we proposed two families of methods to ensure workload fairness without modifying the existing scheduling model. The first family involves preprocessing the data input to the scheduling system. The second family uses post-processing approaches to adjust the allocation plan. Combined methods were also tested. The combined methods demonstrated superiority over the other methods, with a 70% reduction in the difference in workload between operators over a typical working week compared with the initial model. Finally, new methods have been proposed to maximize the repeatability of tasks. Taking into account the complexity of the initial model and the desire to target several objectives at once (delays, fairness and repeatability), a compromise between fairness and repeatability is sought. An experimental study using real data collected from our industrial partner shows that by allowing only a 10% degradation in fairness compliance, we can achieve an acceptable level of repeatability.

L'environnement industriel concurrentiel auquel font face les entreprises manufacturières les pousse à se doter d'un système de production hautement réactif capable de pallier aux incertitudes et aux fluctuations imprévisibles de la demande. La classe des systèmes manufacturiers reconfigurables (RMS pour Reconfigurable Manufacturing System en anglais) fournit une solution efficace et prometteuse à ce défi. Contrairement aux systèmes classiques comme les lignes de fabrication dédiées (DML) et les systèmes de fabrication flexibles (FMS), qui n'arrivent pas à surmonter ces challenges à cause de leurs conceptions qui limitent les options pour mieux gérer les variations de la demande et adapter la capacité du besoin du marché, les RMS présentent une bonne alternative possédant la capacité d'adapter la configuration du système manufacturier au fil du temps afin de répondre aux exigences du marché. Cela est assuré par les machines-outils reconfigurables (RMT pour Reconfigurable Machine Tools en anglais) qui sont considérées comme la composante fondamentale pour un RMS. Ce mémoire propose une nouvelle approche d'ordonnancement de la production en considérant les machines-outils reconfigurables. L'objectif est de minimiser le makespan. Un modèle linéaire mixte en nombres entiers ainsi qu'une heuristique adaptée à deux phases ont été proposés afin de résoudre le problème. Les performances des deux méthodes de résolution sont analysées et comparées pour différentes instances générées aléatoirement. Une analyse de performance des méthodes suite aux variations de certains paramètres est présentée. Finalement, un contexte dynamique (des nouvelles commandes qui surviennent au cours de la production) est considéré où la performance de l'approche heuristique surpasse celle de la méthode exacte pour les instances considérées. / The competitive manufacturing environment faced by manufacturing companies requires a highly responsive production system capable of dealing with uncertainties and unpredictable fluctuations of demand. Reconfigurable Manufacturing Systems (RMS) provide an effective and promising solution to this challenge. Unlike conventional systems such as Dedicated Manufacturing Lines (DML) and Flexible Manufacturing Systems (FMS) which fail to overcome these challenges due to their designs which do not support variations in demand and changes in capacity, RMS present a good alternative with the ability to change the system configuration over time to meet market demands. This is ensured by reconfigurable machine tools (RMT) which are considered as the fundamental component for an RMS. This thesis proposes a new approach to production scheduling for manufacturing systems with reconfigurable machine tools. The objective is to minimize the makespan. A linear mixed-integer model based on the sequence of operations as well as an adapted two-phase heuristic are proposed to solve the problem. The performances of the two resolution methods are analyzed and compared for different randomly generated instances. An analysis of the performance of the methods following variations in certain parameters is presented. Finally, a dynamic context (new orders arise during production) is considered where the heuristic outperforms the exact method.

Aujourd'hui, les plates-formes hétérogènes et partagées que sont les grilles de calcul sont omniprésentes. De plus, le besoin d'exécuter des applications parallèles complexes est croissant. Cette thèse vise à ordonnancer des applications représentées par des graphes de tâches modelables (dont le nombre de processeurs est fixé par l'ordonnanceur) sur des grilles de calcul en exploitant le maximum de parallélisme, utilisant efficacement les ressources, gérant l'hétérogénéité et le partage des ressources. Nous avons pour cela opté pour des heuristiques pragmatiques car, bien qu'elles n'offrent pas de garantie de performance, elles peuvent néanmoins conduire à de bonnes performances moyennes tout en construisant des ordonnancements en des temps relativement courts. La plupart des heuristiques existantes n'ordonnancent les applications parallèles mixtes qu'en milieu homogène et utilisent parfois inefficacement les ressources. Nous avons donc tout d'abord étudié différentes heuristiques dans le cas de plates-formes homogènes et proposé des améliorations visant à améliorer le compromis entre réduction du temps de complétion et efficacité. Nous avons ensuite introduit la gestion de l'hétérogénéité dans l'heuristique proposée et comparé ses performances à celles d'un algorithme garanti. Enfin, nous avons tenu compte du caractère partagé des grilles en gérant la concurrence entre applications. L'approche retenue consiste à limiter la quantité de ressources que chaque application peut utiliser pour construire son ordonnancement. Nous avons également proposé plusieurs stratégies de détermination de cette contrainte de ressources.

Nous étudions dans cette thèse deux approches réduisant le temps de traitement nécessaire pour résoudre des problèmes de planification et d'ordonnancement dans un contexte de programmation par contraintes. Nous avons expérimenté avec plusieurs milliers de processeurs afin de résoudre le problème de planification et d'ordonnancement des opérations de rabotage du bois d'oeuvre. Ces problèmes sont d'une grande importance pour les entreprises, car ils permettent de mieux gérer leur production et d'économiser des coûts reliés à leurs opérations. La première approche consiste à effectuer une parallélisation de l'algorithme de résolution du problème. Nous proposons une nouvelle technique de parallélisation (nommée PDS) des stratégies de recherche atteignant quatre buts : le respect de l'ordre de visite des noeuds de l'arbre de recherche tel que défini par l'algorithme séquentiel, l'équilibre de la charge de travail entre les processeurs, la robustesse aux défaillances matérielles et l'absence de communications entre les processeurs durant le traitement. Nous appliquons cette technique pour paralléliser la stratégie de recherche Limited Discrepancy-based Search (LDS) pour ainsi obtenir Parallel Limited Discrepancy-Based Search (PLDS). Par la suite, nous démontrons qu'il est possible de généraliser cette technique en l'appliquant à deux autres stratégies de recherche : Depth-Bounded discrepancy Search (DDS) et Depth-First Search (DFS). Nous obtenons, respectivement, les stratégies Parallel Discrepancy-based Search (PDDS) et Parallel Depth-First Search (PDFS). Les algorithmes parallèles ainsi obtenus créent un partage intrinsèque de la charge de travail : la différence de charge de travail entre les processeurs est bornée lorsqu'une branche de l'arbre de recherche est coupée. En utilisant des jeux de données de partenaires industriels, nous avons pu améliorer les meilleures solutions connues. Avec la deuxième approche, nous avons élaboré une méthode pour minimiser les changements effectués à un plan de production existant lorsque de nouvelles informations, telles que des commandes additionnelles, sont prises en compte. Replanifier entièrement les activités de production peut mener à l'obtention d'un plan de production très différent qui mène à des coûts additionnels et des pertes de temps pour les entreprises. Nous étudions les perturbations causéees par la replanification à l'aide de trois métriques de distances entre deux plans de production : la distance de Hamming, la distance d'édition et la distance de Damerau-Levenshtein. Nous proposons trois modèles mathématiques permettant de minimiser ces perturbations en incluant chacune de ces métriques comme fonction objectif au moment de la replanification. Nous appliquons cette approche au problème de planification et ordonnancement des opérations de finition du bois d'oeuvre et nous démontrons que cette approche est plus rapide qu'une replanification à l'aide du modèle d'origine. / We study in this thesis two approaches that reduce the processing time needed to solve planning and ordering problems in a constraint programming context. We experiment with multiple thousands of processors on the planning and scheduling problem of wood-finish operations. These issues are of a great importance for businesses, because they can better manage their production and save costs related to their operations. The first approach consists in a parallelization of the problem solving algorithm. We propose a new parallelization technique (named PDS) of the search strategies, that reaches four goals: conservation of the nodes visit order in the search tree as defined by the sequential algorithm, balancing of the workload between the processors, robustness against hardware failures, and absence of communication between processors during the treatment. We apply this technique to parallelize the Limited Discrepancy-based (LDS) search strategy to obtain Parallel Limited Discrepancy-Based Search (PLDS). We then show that this technique can be generalized by parallelizing two other search strategies: Depth-Bounded discrepancy Search (DDS) and Depth-First Search (DFS). We obtain, respectively, Parallel Discrepancy-based Search (PDDS) and Parallel Depth-First Search (PDFS). The algorithms obtained this way create an intrinsic workload balance: the imbalance of the workload among the processors is bounded when a branch of the search tree is pruned. By using datasets coming from industrial partners, we are able to improve the best known solutions. With the second approach, we elaborated a method to minimize the changes done to an existing production plan when new information, such as additional orders, are taken into account. Completely re-planning the production activities can lead to a very different production plan which create additional costs and loss of time for businesses. We study the perturbations caused by the re-planification with three distance metrics: Hamming distance, Edit distance, and Damerau-Levenshtein Distance. We propose three mathematical models that allow to minimize these perturbations by including these metrics in the objective function when replanning. We apply this approach to the planning and scheduling problem of wood-finish operations and we demonstrate that this approach outperforms the use of the original model.