Les travaux de recherche concernant l'ordonnancement mobilisent un nombre important de chercheurs. Cette forte émulation est principalement due au large panorama des problématiques d'ordonnancement. Parmi elles, le problème d'atelier à cheminement multiple, communément appelé " Job-Shop ", tient une place particulièrement prépondérante tant ce problème est rencontré dans le milieu industriel. De nombreux sujets de recherche, en France et à l'étranger, sont issus de cette problématique. Les problèmes de Job-Shop peuvent souvent être simplifiés en les considérant comme des problèmes cycliques. L'ordonnancement des tâches devient ainsi cyclique et son objectif est d'organiser les activités de production en répétant un cycle de base que l'on a optimisé. De nombreux paramètres entrent en jeu dans l'optimisation du cycle de base tels que la période du cycle choisie, l'ordre des opérations élémentaires pour réaliser un travail, la durée de ces opérations, le nombre de produits à réaliser par cycle, etc. Plusieurs approches ont été utilisées pour résoudre ce problème. Parmi elles, nous pouvons citer l'approche par réseaux de Petri et plus particulièrement par graphes d'événements temporisés, l'approche par les graphes, l'approche par la programmation linéaire et l'approche par la théorie des tas. L'approche par les graphes permet une représentation graphique du problème sous forme d'un graphe où les noeuds représentent les différentes opérations et où les arcs illustrent les contraintes du problème d'ordonnancement cyclique, un tel problème admet une solution réalisable si, et seulement si, le graphe associé est consistant. Cette propriété de consistance d'un problème d'ordonnancement cyclique et de son graphe permet d'élaguer l'arbre de recherche de la procédure de séparation et d'évaluation proposée pour cette approche. Concernant l'approche par la théorie des tas, le sous-problème de l'évaluation d'une solution peut être résolu aisément avec l'aide de la théorie des tas. En effet, en traduisant le problème dans une structure mathématique adaptée, l'évaluation du taux de production du cycle revient au calcul d'une valeur propre d'un produit de matrices dans lequel chacune des matrices représente une opération élémentaire. Cette propriété s'avère particulièrement intéressante dans le cas de l'évaluation successive d'un grand nombre d'ordonnancement. En outre, la théorie des tas permet une représentation très intuitive d'un ordonnancement, puisque celui-ci s'illustre comme un empilement de plusieurs briques (en fait, un " tas " de briques) dont le contour supérieur correspond aux dates de fin des dernières opérations des machines.

Dans cette thèse nous développons de nouvelles techniques pour résoudre les problèmes d'optimisation multi-critère. Ces problèmes se posent naturellement dans de nombreux domaines d'application (sinon tous) où les choix sont évalués selon différents critères conflictuels (coûts et performance par exemple). Contrairement au cas de l'optimisation classique, de tels problèmes n'admettent pas en général un optimum unique mais un ensemble de solutions incomparables, aussi connu comme le front de Pareto, qui représente les meilleurs compromis possibles entre les objectifs conflictuels. La contribution majeure de la thèse est le développement d'algorithmes pour trouver ou approximer ces solutions de Pareto pour les problèmes combinatoires difficiles. Plusieurs problèmes de ce type se posent naturellement lors du processus de placement et d'ordonnancement d'une application logicielle sur une architecture multi-coeur comme P2012, qui est actuellement développé par STMicroelectronics.

Cette thèse est consacrée à l'étude de plusieurs problèmes d'optimisation combinatoire qui se présentent dans le domaine du calcul parallèle embarqué. En particulier, la gestion optimale de la mémoire et des problèmes d'ordonnancement pour les applications flot de données exécutées sur des processeurs massivement multicœurs sont étudiés. Deux techniques d'optimisation d'accès à la mémoire sont considérées : la réutilisation des données et le préchargement. La gestion des accès à la mémoire est déclinée en trois problèmes d'optimisation combinatoire. Dans le premier problème, une stratégie de préchargement pour les applications flot de données est étudiée, de façon à minimiser le temps d'exécution de l'application. Ce problème est modélisé comme un flow shop hybride sous contraintes de précédence, un problème \mathcal{NP}\text{-difficile} . Un algorithme de résolution heuristique avec deux bornes inférieures sont proposés afin de faire une estimation conservatrice, quoique suffisamment précise, de la distance à l'optimum des solutions obtenues. Le deuxième problème traite de l'exécution conditionnelle dépendante des données et de la gestion optimale du préchargement pour les structures de branchement. Quelques fonctions économiques, ainsi que des techniques de préchargement, sont examinées. Dans tous ces cas des algorithmes de résolution polynomiaux sont proposés. Le troisième problème consiste à ordonner un ensemble de tâches de façon à maximiser la réutilisation des données communes. Ce problème étant \mathcal{NP}\text{-difficile} , ce que nous avons établi, nous avons proposé deux algorithmes heuristiques. La distance à l'optimum des solutions est estimée en utilisant des solutions exactes. Ces dernières sont obtenues à l'aide d'une méthode branch-and-bound que nous avons proposée.

Les avancées technologiques ont conduit les grandes organisations telles que les entreprises,les universités et les instituts de recherche à se doter d'intranets constitués de plusieurs serveurs etd'un grand nombre de postes de travail. Cependant dans certaines de ces organisations, les postes detravail sont très peu utilisés pendant la nuit, les week-ends et les périodes de congés, libérant ainsiune grande puissance de calcul disponible et inutilisée.Dans cette thèse, nous étudions l'exploitation de ces temps de jachère afin d'exécuter desapplications de calcul haute performance. A cet effet, nous supposons que les postes acquis sontrebootés et intégrés à des grappes virtuelles constituées dynamiquement. Toutefois, ces temps dejachère ne permettent pas toujours d'exécuter les applications jusqu'à leur terme. Les mécanismes desauvegarde/reprise (checkpointing) sont alors utilisés pour sauvegarder, dans un certain délai, lecontexte d'exécution des applications en vue d'une éventuelle reprise. Il convient de noter que lasauvegarde de tous les processus dans les délais impartis n'est pas toujours possible. Nousproposons un modèle d'ordonnancement des sauvegardes en parallèle, qui tient compte descontraintes temporelles imposées et des contraintes liées aux bandes passantes (réseau et disque),pour maximiser les temps de calcul déjà effectués pour les applications candidates à la sauvegarde.

Le passage de l'échelle des nouvelles plates-formes de calcul parallèle et distribué soulève de nombreux défis scientifiques. À terme, il est envisageable de voir apparaître des applications composées d'un milliard de processus exécutés sur des systèmes à un million de coeurs. Cette augmentation fulgurante du nombre de processeurs pose un défi de résilience incontournable, puisque ces applications devraient faire face à plusieurs pannes par jours. Pour assurer une bonne exécution dans ce contexte hautement perturbé par des interruptions, de nombreuses techniques de tolérance aux pannes telle que l'approche de sauvegarde et reprise (checkpoint) ont été imaginées et étudiées. Cependant, l'intégration de ces approches de tolérance aux pannes dans le couple formé par l'application et la plate-forme d'exécution soulève des problématiques d'optimisation pour déterminer le compromis entre le surcoût induit par le mécanisme de tolérance aux pannes d'un coté et l'impact des pannes sur l'exécution d'un autre coté. Dans la première partie de cette thèse nous concevons deux modèles de performance stochastique (minimisation de l'impact des pannes et du surcoût des points de sauvegarde sur l'espérance du temps de complétion de l'exécution en fonction de la distribution d'inter-arrivées des pannes). Dans la première variante l'objectif est la minimisation de l'espérance du temps de complétion en considérant que l'application est de nature préemptive. Nous exhibons dans ce cas de figure tout d'abord une expression analytique de la période de sauvegarde optimale quand le taux de panne et le surcoût des points de sauvegarde sont constants. Par contre dans le cas où le taux de panne ou les surcoûts des points de sauvegarde sont arbitraires nous présentons une approche numérique pour calculer l'ordonnancement optimal des points de sauvegarde. Dans la deuxième variante, l'objectif est la minimisation de l'espérance de la quantité totale de temps perdu avant la première panne en considérant les applications de nature non-préemptive. Dans ce cas de figure, nous démontrons tout d'abord que si les surcoûts des points sauvegarde sont arbitraires alors le problème du meilleur ordonnancement des points de sauvegarde est NP-complet. Ensuite, nous exhibons un schéma de programmation dynamique pour calculer un ordonnancement optimal. Dans la deuxième partie de cette thèse nous nous focalisons sur la conception des stratégies d'ordonnancement tolérant aux pannes qui optimisent à la fois le temps de complétion de la dernière tâche et la probabilité de succès de l'application. Nous mettons en évidence dans ce cas de figure qu'en fonction de la nature de la distribution de pannes, les deux objectifs à optimiser sont tantôt antagonistes, tantôt congruents. Ensuite en fonction de la nature de distribution de pannes nous donnons des approches d'ordonnancement avec des ratios de performance garantis par rapport aux deux objectifs.

Ce travail s'intéresse à la caractérisation hors ligne d'ensembles de solutions en ordonnancement destinés à offrir une certaine flexibilité. Il s'inscrit dans le champ de l'ordonnancement robuste pour lequel on désire construire un ensemble d'ordonnancements relativement insensible, du point de vue de ses performances, aux événements imprévus survenant lors de la mise en Suvre en environnement perturbé. L'approche robuste proposée est de type proactif-réactif. Elle s'appuie sur les notions de structures d'intervalles et de conditions de dominance (ou de conditions suffisantes) vis-à-vis de l'admissibilité ou de l'optimalité de solutions en ordonnancement. Ce travail s'est particulièrement focalisé sur la phase proactive où il s'agit d'anticiper la mise en Suvre de l'ordonnancement, en construisant au plus tôt une organisation relativement insensible aux perturbations, tout en disposant d'indicateurs relatifs à la performance temporelle. Dans ce cadre, nous montrons en particulier l'intérêt de certains ordres partiels, établis sur la base de corps d'hypothèses restreints, permettant d'une part la détermination d'une performance au mieux et au pire de l'ensemble de solutions caractérisé, et d'autre part, le calcul d'indicateurs de flexibilité. Dans un premier temps, le problème d'ordonnancement à une machine est étudié. Pour ce problème, un ordre partiel dominant basé sur une analyse de structure d'intervalles est décrit. Cet ordre partiel caractérise un ensemble dominant de solutions de cardinalité calculable, dont la performance au mieux et au pire, en terme de retard algébrique, peut être déterminée en temps de calcul polynomial. Deux approches d'ordonnancement robuste sont ensuite proposées permettant soit de caractériser toutes les séquences optimales contenues dans l'ensemble dominant initial, soit de trouver un compromis flexibilité / performance acceptable. Dans un deuxième temps, les problèmes d'ordonnancement sur plusieurs machines sont considérés. Un ordre partiel suffisant est d'abord proposé pour le problème flow shop de permutation à deux machines. Deux algorithmes, utilisant les résultats obtenus pour le problème à une machine, sont ensuite présentés dans le cadre de problèmes de type job shop.

Cette thèse présente nos travaux de recherche qui ont comme principal objectif d'assurer la portabilité des performances et le passage à l'échelle des applications scientifiques complexes exécutées sur des plates-formes multi-coeurs parallèles et hiérarchiques. La portabilité des performances est obtenue lorsque l'ordonnancement des tâches d'une application permet de réduire les périodes d'inactivité des coeurs de la plate-forme. Cette portabilité des performances peut être affectée par différents problèmes tels que des déséquilibres de charge, des communications coûteuses et des surcoûts provenant de l'ordonnancement des tâches. Le déséquilibre de charge est la conséquence de comportements de charges irrégulières et dynamiques, où le volume de calcul varie dynamiquement en fonction de la tâche et de l'étape de simulation. Les communications coûteuses sont provoquées par un ordonnancement qui ne prend pas en compte les différents temps de c! ommunication entre tâches sur une plate-forme hiérarchique. Cela est accentué par des communications non uniformes et asymétriques au niveau mémoire et réseau. Enfin, ces surcoûts peuvent être générés par des algorithmes de placement trop complexes dont les coûts ne seraient pas compensés par les gains de performance. Pour atteindre cet objectif de portabilité des performances, notre approche repose sur une récolte d'informations précises sur la topologie de la machine qui vont aider les algorithmes d'ordonnancement de tâches à prendre les bonnes décisions. Dans ce contexte, nous avons proposé une modélisation générique de la topologie des plates-formes parallèles. Le modèle comprend des latences et des bandes passantes mesurées de la mémoire et du réseau qui mettent en évidence des asymétries. Ces informations sont utilisées par nos trois algorithmes d'équilibrage de charge nommés NucoLB, HwTopoLB, et HierarchicalLB. De plus, ces algorithmes utilisent des informations provenant de l'exécution de l'application. NucoLB se concentre sur les aspects non uniformes de plates-formes parallèles, alors que HwTopoLB considère l'ensemble de la hiérarchie pour ses décisions, et HierarchicalLB combine ces algorithmes hiérarchiquement pour réduire son surcoût d'ordonnanceme! nt de tâches. Ces algorithmes cherchent à atténuer le déséquilibre de charge et des communications coûteuses tout en limitant les surcoûts de migration des tâches. Les résultats expérimentaux avec les trois régulateurs de charge proposés ont montré des améliorations de performances sur les meilleurs algorithmes de l'état de l'art: NucoLB a présenté jusqu'à 19% d'amélioration de performances sur un noeud de calcul; HwTopoLB a amélioré les performances en moyenne de 19%, et HierarchicalLB a surclassé HwTopoLB de 22% en moyenne sur des plates-formes avec plus de dix noeuds de calcul. Ces résultats ont été obtenus en répartissant la charge entre les ressources disponibles, en réduisant les coûts de communication des applications, et en gardant les surcoûts d'équilibrage de charge faibles. En ce sens, nos algorithmes d'équilibrage de charge permettent la portabilité des performances pour les applications scientifiques tout en étant indépendant de l'application et de l'architecture du système.

Les travaux de recherche de ce mémoire portent sur la contribution à l'ordonnancement et à la robustesse d'ateliers de traitement de surface pour une production mono-robot/multi-produits.Une ligne de traitement de surface est constituée d'une succession de cuves dans lesquelles une opération chimique, de durée définie sur un intervalle de temps, appelé fenêtre, doit être réalisée. Ce type de ligne est en particulier contraint par un robot, se déplaçant sur un rail au dessus des cuves et assurant le transport du produit à traiter. Ce problème d'ordonnancement traité, appelé SHMP (Single-Hoist/Multi-Products) est connu pour être NP-difficile, même avec un seul produit et une seule ressource de transport. Basé sur les techniques de satisfaction de contraintes, un algorithme a été développé et mis en œuvre avec succès pour l'atelier de traitement de surfaces étudié. L'utilisation de l'hybridation de ce même algorithme avec d'autres méthodes s'est avérée intéressante et efficace pour déterminer des solutions de meilleure qualité. Nous avons également montré que le recours aux algorithmes génétiques pour l'optimisation du problème job shop mono-robot/multi-produits étudié conduit à des résultats encore plus intéressants et significatifs.La robustesse a aussi été considérée pour l'étude de l'influence des perturbations sur l'ordonnancement. Pour cela, la distinction de divers scénarii a été nécessaire pour l'étude de l'influence d'une perturbation au niveau du chariot. La détermination systématique d'un ordonnancement robuste a été ensuite menée, avec succès, par application d'une méthode d'évaluation multi-critères

Les machines multicœurs équipées d'accélérateurs deviennent de plus en plus populaires dans le domaine du Calcul Haute Performance. Les architectures hybrides réduisent la consommation énergétique de manière significative et sont donc amenées à se généraliser dans l'ère du manycœur. Cependant, la complexité induite par ces architectures a un impact direct sur leur programmabilité. Il est donc indispensable de fournir des abstractions portables afin de tirer pleinement parti de ces machines. Les approches qui consistent à exécuter une application sur des processeurs généralistes et à ne déporter que certaines parties prédéterminées du calcul sur des accélérateurs ne sont pas suffisantes. Le véritable défi consiste donc à concevoir des environnements où les applications sont réparties sur l'intégralité de la machine, c'est-à-dire où les différents calculs sont ordonnancés dynamiquement sur la totalité des unités de calcul disponibles. Dans cette thèse, nous proposons donc un nouveau modèle de support exécutif fondé sur une abstraction de tâche et spécifiquement conçu pour répondre aux nombreux défis en termes d'ordonnancement de tâches et de gestion de données. La plate-forme StarPU a été conçue lors de cette thèse afin de démontrer la pertinence de ce modèle. StarPU propose une interface expressive permettant d'accéder à un ordonnancement flexible, fortement couplé à une gestion de données efficace. À l'aide de cet environnement et en associant les différentes tâches avec des modèles de performance auto-calibrés, il devient par exemple très simple de concevoir des stratégies d'ordonnancement prenant en compte les temps de calcul et les surcoûts liés aux mouvements de données. Nous montrons que notre modèle fondé sur un paradigme de tâche est suffisamment puissant pour exploiter les grappes de calcul d'une part, et les architectures manycœurs hybrides d'autre part. Nous analysons les performances obtenues non seulement grâce à des tests synthétiques, mais aussi à l'aide d'applications réelles. Nous obtenons ainsi des accélérations substantielles, ainsi qu'une très bonne efficacité parallèle sur différents types de plates-formes multicœurs, dotées d'accélérateurs.

Thèse (de doctorat)--Université Laval, 2008. / Titre de l'écran-titre (visionné le 12 janvier 2009). Bibliogr.