Du fait des énormes capacités de calculs des accélérateurs tels que les GPUs et les Xeon Phi, l’utilisation de machines multicoques pourvues d’accélérateurs est devenue commune dans le domaine du calcul haute performance (HPC). La complexité induite par ces accélérateurs a suscité le développement de systèmes d’exécution à base de tâches, dans lesquels les dépendances entre les applications sont exprimées sous la forme de graphe de tâches et où les tâches sont ordonnancées dynamiquement sur les ressources de calcul. La difficulté est alors de concevoir des stratégies d’ordonnancement qui font une utilisation efficace des ressources de calculs et le développement de telles stratégies, même pour un unique noeud hybride, est un enjeu essentiel de la performance des systèmes HPC. Nous considérons dans cette thèse l’ordonnancement de noyaux d’algèbre linéaire dense sur des noeuds complètement hétérogènes et constitués de CPUs et de GPUs. Les performances relatives des accélérateurs par rapport aux coeurs classique dépend très fortement du noyau considéré. Par exemple, les accélérateurs sont beaucoup plus efficaces pour les produits de matrices, par exemple, que pour les factorisations. Dans cette thèse, nous analysons les performances de stratégies statiques et dynamiques d’ordonnancement et nous proposons un ensemble de stratégies intermédiaires, en ajoutant des composantes statiques (respectivement dynamiques) à des stratégies d’ordonnancements dynamique (respectivement statiques). Récemment, une stratégie appelée HeteroPrio a été proposée, qui s’appuie sur les affinités entre les tâches et les ressources pour un petit ensemble de tâches différentes s’exécutant sur deux types de ressources. Nous avons étendu cette stratégie d’ordonnancement pour des graphes de tâches généraux pour deux types de ressources puis pour plus de deux types. De manière complémentaire, nous avons également démontré des facteurs d’approximation et des pires cas pour HeteroPrio dans le cas d’un ensemble de tâches indépendantes sur différents types de plates-formes. / Due to massive computation power of accelerators such as GPU, Xeon phi, multicore machines equipped with accelerators are becoming popular in High Performance Computing (HPC). The added complexity led to the development of different task-based runtime systems, which allow computations to be expressed as graphs of tasks and rely on runtime systems to schedule those tasks among all resources of the platform. The real challenge is to design efficient schedulers for such runtimes to make effective utilization of all resources. Developing good schedulers, even for a single hybrid node, and analyzing them can thus have a strong impact on the performance of current HPC systems. We consider the problem of scheduling dense linear algebra applications on fully hybrid platforms made of CPUs and GPUs. The relative performance of CPU and GPU highly depends on the sub-routine. For instance, GPUs are much more efficient to process matrix-matrix multiplications than matrix factorizations. In this thesis, we analyze the performance of static and dynamic scheduling strategies and we propose a set of intermediate strategies, by adding static (resp. dynamic) features into dynamic (resp. static) strategies. A resource centric dynamic scheduler, HeteroPrio, which is based on affinity between tasks and resources, has been proposed recently for a set of small independent tasks on two types of resources. We extend and analyze this scheduler for general task graphs first on two types of resources and then on more than two types of resources. Additionally, we provide approximation ratios and worst case examples of HeteroPrio for a set of independent tasks on different platform sizes.

La plupart des méthodes d'ordonnancement considèrent un environnement déterministe où les données du problème sont connues. Néanmoins, en réalité, plusieurs sortes d'aléas peuvent être rencontrées et l'ordonnancement robuste permet en tenir compte. Dans cette thèse, notre intuition initiale est que, d'une part, un ordonnancement non robuste deviendra rapidement inefficace avec les incertitudes qu'un ordonnancement robuste, et d'autre part, un ordonnancement robuste sera moins efficace qu'un ordonnancement non robuste en l'absence d'incertitudes. Dans ce cadre, nous avons proposé un algorithme génétique pour l'ordonnancement robuste. Un nouveau mécanisme de résolution et un nouveau critère de robustesse permettant de trouver une solution de bonne performance et peu sensible aux incertitudes ont été développés. Une phase expérimentale a été menée, d'une part, pour vérifier l'efficacité de l'algorithme génétique pour l'ordonnancement déterministe, sans tenir compte des incertitudes, et d'autre part, pour valider l'algorithme génétique pour l'ordonnancement robuste par la simulation afin de juger la qualité de la robustesse face aux incertitudes. Nous avons intégré cette approche de robustesse dans une démarche méthodologique générique intégrant des techniques d'optimisation et de simulation pour l'aide au dimensionnement des systèmes de production basé sur des ordonnancements robustes. Les différents modules de la démarche ont été développés sous forme d'un outil d'aide au dimensionnement, dans le cadre d'un cas applicatif réel, celui du bloc opératoire dans le secteur hospitalier.

Les systèmes temps réel sont des systèmes informatiques composés de tâches auxquelles sont associées des contraintes temporelles, appelées échéances. Dans notre étude, nous distinguons deux familles de tâches : les tâches temps réel dur et les tâches temps réel souple. Les premières possèdent une échéance stricte, qu'elles doivent impérativement respecter. Elles sont de nature périodique, ou sporadique, et l'étude analytique de leur comportement fait l'objet d'un état de l'art conséquent. Les secondes sont de nature apériodique. Aucune hypothèse sur leur modèle d'arrivéée ni sur leur nombre n'est possible. Aucune garantie ne saurait être donnée sur leur comportement dès lors que l'on ne peut écarter les situations de surcharge, où la demande de calcul peut dépasser les capacités du système. La problématique devient alors l'étude des solutions d'ordonnancement mixte de tâches périodiques et apériodiques qui minimisent les temps de réponse des tâches apériodiques tout en garantissant les échéances des tâches périodiques. De nombreuses solutions ont été proposées ces vingt dernières années. On distingue les solutions basées sur la réservation de ressources, les serveurs de tâches, des solutions exploitant les instants d'inactivité du système, comme les algorithmes de vol de temps creux. La spécification Java pour le temps réel (RTSJ) voit le jour dans les années 2000. Si cette norme répond à de nombreux problèmes liés à la gestion de la mémoire ou à l'ordonnancement des tâches périodiques, celui de l'ordonnancement mixte de tâches périodiques et apériodiques n'est pas abordé. Nous proposons dans cette thèse d'apporter les modifications nécessaires aux algorithmes principaux d'ordonnancement mixte, le Polling Server (PS), le Deferrable Server (DS) et le Dynamic Approximate Slack Stealer (DASS) en vue de leur implantation avec RTSJ. Ces algorithmes ne peuvent en effet être implantés directement tels qu'ils sont décrits, car ils sont trop liés à l'ordonnanceur du système. Nous proposons des extensions aux APIs RTSJ existantes pour faciliter l'implantation de ces mécanismes modifiés, et nous fournissons les interfaces utiles à l'ajout d'autres solutions algorithmiques. Nous proposons également des modifications sur les APIs existantes de RTSJ afin de répondre aux problèmes d'intégration et d'implantation d'algorithmes d'analyse de faisabilité. Nous proposons enfin un algorithme d'estimation des temps creux, le Minimal Approximate Slack Stealer (MASS), dont l'implantation au niveau utilisateur, permet son intégration dans RTSJ

Les travaux de cette thèse sont les fruits de collaboration depuis 2008 entre l'ICL et le Centre Ingénierie et Santé (CIS) de l'Ecole des Mines de Saint Etienne. CIS et ICL sont tous deux membres de l'Institut Fédératif de Recherche en Science, Ingénierie et Santé (IFRESIS) et participent tous deux aux travaux du Cancéropôle Lyon Auvergne Rhône-Alpes (CLARA) dont Franck Chauvin animait l'axe IV sur Epidémiologie, SHS, Information du Patient et Organisation des Soins. Cette thèse a été initiée avec la volonté de développer une recherche originale sur l'optimisation de la production de soins en cancérologie.Nous nous intéressons à différentes problématiques de la gestion de soins des patients dans un hôpital de jour en cancérologie. Nous visons à équilibrer au mieux les besoins journaliers en lits tout en prenant en compte l'adhérence aux protocoles de soins, les contraintes des oncologues et les aléas des flux de patients. Pour un hôpital de jour en oncologie, nous avons identifié et étudié les décisions suivantes : I. Le planning médical une fois par an afin de déterminer les périodes de travail des oncologues dans une semaine. Nous avons proposé une formulation originale sous forme d'un modèle de programmation linéaire en nombres mixtes (MIP) et une approche en 3-étapes. II. L'affectation des nouveaux patients qui détermine le jour de la chimiothérapie pour chaque patient entrant. Nous avons présenté trois stratégies de planification et nous avons décrit un algorithme de simulation pour évaluer ces stratégies de planification. Les stratégies de planification proposées exploitent les informations contenues dans les protocoles de soins des patients et utilisent l'optimisation Monte Carlo III. La planification des rendez-vous. Nous avons présenté deux méthodes pour la résolution de ce problème : une approche basée sur la relaxation Lagrangienne et une heuristique basée sur une optimisation par recherche localeIV. La planification des jours fériés : permet de remédier au problème des semaines comportant des jours fériés. Nous avons développé un modèle en programmation linéaire en nombres mixtes permettant de répartir rapidement la charge du jour férié sur les jours en amont et en aval sans trop dégradé l'efficacité du traitement, ni surcharger le travail de l'HDJ.

Ce document est la synthèse des travaux menés pour la résolution d'un problème d'ordonnancement, celui posé par le système temps-réel spectre (divers types de ressources, plusieurs ressources par type, relations de précedence, arrivées échelonnées, dates critiques...) La méthode utilisée pour parvenir a la solution et les réflexions successives y sont décrites et analysées. de plus, ce travail décrit l'algorithme solution depuis sa définition jusqu'à sa programmation, en passant par la démonstration de sa validité.

Cette thèse présente de nouveaux résultats liant la théorie des systèmes dits insensibles à la latence, à une sous-classe des réseaux de Pétri dénommée Marked Event Graph et son extension dite Synchronous Data Flow. Ces travaux sont intimement associés avec le problème d'ordonnancement général dénommé problème central répétitif. Nous introduisons les modèles synchrones, Marked Event Graphs, Synchronous Data Flow (SDF) et Latency Insensitive. Après, nous discutons des liens existants entre les modèles synchrones, Marked Event Graphs et Latency Insensitive ; nous montrons que le modèle Latency Insensitive est un cas particulier du modèle Marked Event Graph. Nous présentons ensuite une implémentation vérifiée formellement de Latency Insensitive. Après, nous rappelons un résultat connu : tout Marked Event Graph ayant au moins une partie fortement connexe (et s'évaluant avec une règle d'exécution As Soon As Possible (ASAP)) a un comportement ultimement répétitif : c'est à dire qu'il existe un ordonnancement statique. À partir de ce résultat, nous construisons une technique d'ordonnancement particulière dénommée Égalisation qui altère virtuellement la topologie des communications du système afin de ralentir des chemins trop rapides en rajoutant des "registres", tout en conservant les performances en terme de débit du système originel. Enfin, nous introduisons une notion de contrôle limité au modèle Latency Insensitive, avec des noeuds appelés select et merge dont les conditions sont connueset indépendantes des flots de données, plus exactement les conditions d'aiguillage des données sont dirigées par des mots binaires ultimement périodiques (comme dans le cadre de l'ordonnancement statique). Nous effectuons ensuite une abstraction sur le modèle SDF afin de déterminer si le modèle accepte un ordonnancement où la taille de toute place est bornée. Nous pouvons vérifier ensuite la vivacité du système grâce à une simulation, si le modèle originel disposait d'au moins d'une partie fortement connexe. Finalement, nous concluons et discutons des possibilités de travaux futurs.

Afin de résoudre les problèmes liés à l'intégration d'un nombre croissant d'appareils programmables, nous proposons un langage d'agents mobiles. Ces agents mobiles sont capables de migrer d'un appareil ou ordinateur à l'autre afin d'exploiter au mieux ses ressources, ce qui permet de profiter au mieux des capacités de chaque appareil à partir d'un unique programme. Ce langage est ULM: Un Langage pour la Mobilité. Nous présentons dans cette thèse ses fonctionnalités, ses particularités, ainsi que sa mise en œuvre. ULM est un dérivé du langage Scheme, auquel nous avons ajouté les fonctionnalités liées à la mobilité ainsi qu'à l'interaction entre les agents mobiles. ULM possède un ensemble de primitives permettant la création d'agents à mobilité forte, avec un ordonnancement coopératif déterministe, et des primitives de contrôles telles que la suspension ou la préemption faible. Nous présentons dans cette thèse l'intégration de ces primitives dans le langage Scheme, ainsi que leur interaction et l'ajout de certaines nouvelles primitives telles que la préemption forte ou la migration sûre. Nous présentons ensuite la sémantique dénotationnelle du langage et sa mise en œuvre au moyen d'un compilateur vers code-octet, et de deux machines virtuelles: une écrite en Bigloo Scheme pour exécution sur des ordinateurs traditionnels, l'autre écrite en Java ME pour les téléphones portables. Nous présentons ensuite l'utilisation possible d'ULM comme remplacement de programmes écrits pour des boucles d'évènements, l'interface entre ULM et des langages externes, quelques exemples d'utilisation d'ULM, puis les travaux futurs avant de conclure.

Le contexte de notre travail s'intéresse à l'ordonnancement des activités de maintenance dans les systèmes de production. L'objectif de la thèse concerne l'élaboration de méthodes de résolution minimisant un critère regroupant les deux aspects production et maintenance. Les règles de priorité ainsi que les algorithmes génétiques ayant fait leur preuve dans le domaine seront à la base de notre étude. Etude faite tout d'abord sur un problème à une machine puis étendue au cas du Flow Shop. Notre contribution comporte tois volets. Le premier volet prend appui sur les solutions générées à l'aide d'une règle de dominance reliant les tâches de production et les tâches de maintenance. Le deuxième volet propose un algorithme par séparation et évaluation permettant de générer des ordonnancements de permutation du problème conjoint de la production et de la maintenance au sein du FLow Shop à deux machines. Le troisième volet étend l'étude au cas du Flow Shop à plusieurs machines. Nous proposons dans ce cas un algorithme génétique avec un codage approprié. Cet algorithme a l'avantage de balayer tout l'espace de recherche et par conséquent de générer des ordonnancements de très bonne qualité. Nous optons pour la maintenance préventive systématique pour l'appliquer dans notre étude. L'une des difficultés majeures de ce type de maintenance est le choix des périodes d'interventions optimales. Nous proposons dans ce cadre une méthode de choix de périodes systématiques.

Le contexte de notre travail s'intéresse à l'ordonnancement d'un atelier de type job shop. L'objectif de la thèse concerne l'élaboration d'une méthode de résolution aussi bien dans le cas classique d'un ordonnancement relatif à la production que dans le cas beaucoup moins étudié touchant l'ordonnancement conjoint de la production et de la maintenance. Les algorithmes génétiques ayant fait leur preuve dans le domaine aussi bien mono objectif que multiobjectif seront à la base de notre étude. Etude faite tout d'abord sur un problème classique de job shop noté J / / Cmax , en ne tenant pas compte des contraintes de disponibilité des machines, puis en introduisant dans un deuxième temps l'aspect de maintenance préventive ayant des objectifs parfois antagonistes avec la production et qui nécessite une résolution multiobjectif. Notre contribution comporte deux volets. Le premier volet prend appui sur les solutions générées par un algorithme génétique qui sont étudiées par des méthodes d'apprentissage. Méthodes qui seront resituées dans le processus d'Extraction de Connaissance à partir des Données (ECD). Dans un soucis de validation et de comparaison par rapport aux travaux faits dans la communauté, la démarche proposée a été élaborée sur un problème classique de type J / / Cmax et sur des benchmarks connus. Le deuxième volet propose un algorithme génétique Pareto optimal résolvant le problème d'ordonnancement conjoint de la production et de la maintenance au sein du job shop. Cet algorithme génétique génère des solutions Pareto optimales. Solutions que nous validerons par des bornes inférieures. Nous optons pour la maintenance préventive systématique pour l'appliquer dans l'atelier de job shop. L'une des difficultés majeures de ce type de maintenance est le choix des périodes d'interventions. Nous proposons dans ce cadre deux méthodes de choix de périodes systématiques.

De par leur taille miniature, les capteurs sans fils sont fortement contraints en énergie, imposant une gestion raisonnée du réseau qu'ils peuvent former grâce à leur capacité de communication sans fil. Cette dernière, limitée, impose des portées réduites contraignant les informations à être relayées d'objet en objet avant d'atteindre leur destinataire. On parle alors de communications multi-sauts. Le déploiement de ces réseaux sur des zones sensibles ou distantes rend également impossible le rechargement ou le remplacement des batteries. Il est alors crucial d'ordonnancer l'activité des capteurs; Pendant qu'une partie des objets participe à l'application, les autres sont dans un mode passif, peu consommateur de ressources. Le critère retenu pour l'ordonnancement est celui de la couverture de surface: l'ensemble des capteurs actifs doit être capable d'observer une zone aussi large que celle couverte par l'ensemble des capteurs déployés. Nous souhaitons également que cet ensemble soit connecté, c'est à dire que les communications multi-sauts soient possibles entre toute paire d'éléments du réseau. <br />Nous avons choisi d'étudier des approches localisées uniquement, ne reposant sur aucune infrastructure. L'objectif est d'obtenir un comportement global cohérent à partir de décisions individuelles simples issues d'informations locales. Chaque noeud décide de sa propre activité en ne se basant que sur l'observation de ses propres voisins. Les changements de topologie du réseau (dus à la mobilité, aux pannes ou à des changements de statut) ne sont par conséquent vécus par les noeuds que comme de simples modifications de leurs voisinages. Ceci permet d'obtenir des solutions robustes, adaptables et surtout passables à l'échelle, aspect extrêmement important dans des réseaux où les densités évoquées peuvent être d'une centaine de noeuds par zone de communication. <br />Nos propositions se distinguent non seulement parce qu'elles considèrent les problèmes de connexité et de couverture de zone comme n'en étant qu'un seul, mais aussi de par leur faible coût en communication ainsi que par leur robustesse. Nous avons ensuite étudié diverses méthodes d'extension à la couverture multiple où tout point de la zone doit être couvert par un nombre fixé de capteurs actifs. Enfin, nous avons évalué toutes ces approches à l'aide de modèles de communication réalistes, montrant que nos solutions conservent toute leur cohérence, en termes de couverture et de connexité. En revanche, aux protocoles classiques souffrant de pertes de performances, nous avons proposé des mécanismes améliorerant leur comportement dans des environnements réalistes.