Cette thèse vise à définir et à valider un modèle de programmation intégrant la description d'architectures logicielles et un ordonnancement dynamique de tâches dans un contexte de haute performance. Par exemple, il s'agit de combiner les avantages de modèles tels que L²C et StarPU. L'objectif final est de proposer un modèle capable de supporter des applications telles que Gysela5D sur les architectures parallèles actuelles et futures (tel que des clusters très variés et supercalculateurs comportant des accélérateurs). / This thesis aims to define and validate a programing model that combines the description of software architecture with dynamic task scheduling in a high performance context. For example by integrating the advantages of the L²C and StarPU models. The final goal is to propose a model that enables the description of applications such as Gysela5D on current and future parallel architectures (such as various clusters and supercomputers including accelerators).

Le cloud computing est l’accomplissement du rêve de nombreux informaticiens désireux de transformer et d’utiliser leurs logiciels comme de simples services, rendant ces derniers plus attractifs et séduisants pour les utilisateurs. Dans le cadre de cette thèse, les technologies du cloud computing sont présentées, ainsi que les principaux défis que ce dernier va rencontrer dans un futur proche, notamment pour la gestion et l’analyse des données. A partir de la théorie moderne d'ordonnancements des tâches, nous avons proposé une gestion hiérarchique d’ordonnancements des tâches qui satisfait aux différentes demandes des cloud services. D’un point de vue théorique, nous avons principalement répondu à trois questions cruciales de recherche. Premièrement, nous avons résolu le problème de l'allocation des ressources au niveau de l’utilisateur. Nous avons en particulier proposé des algorithmes basés sur la théorie des jeux. Avec une méthode Bayésienne d’apprentissage, l'allocation des ressources atteint l'équilibre de Nash parmi les utilisateurs en compétition malgré une connaissance insuffisante des comportements de ces derniers. Deuxièmement, nous avons abordé le problème d'ordonnancements des tâches au niveau du système. Nous avons trouvé un nouveau seuil pour l'utilisation d’ordonnancements des tâches en ligne, considérant le dispositif séquentiel de MapReduce. Ce seuil donne de meilleurs résultats que les méthodes existantes dans l’industrie. Troisièmement, nous avons défini un critère de comparaison pour les tests d’ordonnancements de tâches en ligne. Nous avons proposé un concept de fiabilité d'essai pour évaluer la probabilité qu'un ensemble de tâches aléatoires passe un essai donné. Plus la probabilité est grande, plus la fiabilité est élevée. Un test présentant une grande fiabilité garantit une bonne utilisation du système. D’un point de vue pratique, nous avons développé un simulateur basé sur le concept de MapReduce. Ce simulateur offre un environnement directement utilisable par les chercheurs familiers avec SimMapReduce, leur permettant de s’affranchir des aspects informatiques d’implémentations et leur permettant notamment de se concentrer sur les aspects algorithmiques d’un point de vue théorique. / Cloud computing, the long-held dream of computing as a utility, has the potential to transform a large part of the IT industry, making software even more attractive as a service and shaping the way in which hardware is designed and purchased. In this thesis, we reviewed the new cloud computing technologies, and indicated the main challenges for their development in future, among which resource management problem stands out and attracts our attention. Combining the current scheduling theories, we proposed cloud scheduling hierarchy to deal with different requirements of cloud services. From the theoretical aspects, we have accomplished three main research issues. Firstly, we solved the resource allocation problem in the user-level of cloud scheduling. We proposed game theoretical algorithms for user bidding and auctioneer pricing. With Bayesian learning prediction, resource allocation can reach Nash equilibrium among non-cooperative users even though common knowledge is insufficient. Secondly, we addressed the task scheduling problem in the system-level of cloud scheduling. We proved a new utilization bound for on-line schedulability test, considering the sequential feature of MapReduce. We deduced the relationship between cluster utilization bound and the ratio of Map to Reduce. This new schedulable bound with segmentation uplifts classic bound which is most used in industry. Thirdly, we settled the comparison problem among on-line schedulability tests in cloud computing. We proposed a concept of test reliability to evaluate the probability that a random task set could pass a given schedulability test. The larger the probability is, the more reliable the test is. From the aspect of system, a test with high reliability can guarantee high system utilization. From the practical aspects, we have developed a simulator to model MapReduce framework. This simulator offers a simulated environment directly used by MapReduce theoretical researchers. The users of SimMapReduce only concentrate on specific research issues without getting concerned about finer implementation details for diverse service models, so that they can accelerate study progress of new cloud technologies.

Ce travail propose une approche originale pour l'ordonnancement de tâches sous contraintes de temps et de ressources. Les méthodes et techniques développées s'inscrivent dans la problématique de l'"Analyse Sous Contraintes" (A.S.C.) des problèmes d'ordonnancement. Cette A.S.C. vise à caractériser les ordonnancements admissibles de manière à proposer au décideur un choix d'actions cohérentes vis-à-vis des contraintes, tout en lui offrant une certaine flexibilité face à des aléas éventuels. L'A.S.C. est décrite comme un processus d'inférence mettant en interaction une base de règles et une base de faits temporels et séquentiels représentant les caractéristiques des ordonnancements admissibles. Un logiciel (MASCOT) écrit en Prolog-II a été réalisé selon ce principe. Une nouvelle approche pour l'A.S.C. et plus particulièrement pour le raisonnement temporel sous contraintes de ressources a été développée. L'originalité de cette approche réside essentiellement dans la prise en compte du couplage temps/ressource à l'aide du concept d'intervalle temps-ressource qui conduit à utiliser un raisonnement énergétique. L'intervalle temps-ressource permet de représenter à la fois les tâches ou intervalles consommateurs et les intervalles de temps alloués sur lesquels des ressources sont disponibles, appelés intervalles fournisseurs. Le problème de l'ordonnancement de tâches amène à étudier l'interaction entre intervalles consommateurs et fournisseurs sur la base de considérations énergétiques. Le logiciel MASCOT met en jeu un processus de déduction symbolique. Ce type de déduction a été amélioré par la prise en compte de l'énergie obligatoirement consommée ou consommation obligatoire d'intervalles consommateurs sur un intervalle fournisseur. De nouvelles règles de déduction ont été écrites et intégrées dans MASCOT. D'autre part, un processus de déduction basé sur un raisonnement purement énergétique a été élaboré et implémenté (logiciel REPORT) en Prolog-II. Il utilise un autre type de déduction, la déduction numérique, qui permet d'affiner les bornes temporelles d'un intervalle fournisseur en considérant la consommation obligatoire des autres intervalles consommateurs. En d'autres termes, ces résultats consistent à actualiser des dates limites et correspondent à des conditions nécessaires d'admissibilité ; ils permettent ainsi de détecter des infaisabilités éventuelles. L'outil de modélisation utilisé est le graphe potentiels-bornes qui permet de représenter des contraintes numériques (sur la durée des tâches par exemple) et des contraintes symboliques entre intervalles. Il sert de support à un processus d'inférence par propagation numérique des contraintes.

L'architecture des ordinateurs est maintenant dans l'ère des multiprocesseurs permettant le calcul en parallèle. Les systèmes embarqués les plus récents s'appuient sur plusieurs processeurs DSP (Digital Signal Processor) ou MPSoC (Multiprocessor System-on-Chip). Corrélativement, les algorithmes des applications de traitement du signal et de l'image deviennent de plus en plus sophistiqués. La mise en oeuvre de telles applications sur un système embarqué devient complexe. Aussi, les approches de prototypage rapide et de co-conception matérielle/logicielle sont souvent utilisées pour faciliter ce travail. Le problème de l'ordonnancement des tâches, étape importante du prototypage rapide, est discuté et traité dans cette thèse. Nous cherchons des modèles d'ordonnancement des tâches en considérant précisément les communications entre les tâches. Nous modélisons ainsi l'algorithme de l'application comme un graphe acyclique orienté (Directed Acyclic Graph ou DAG), et nous proposons un modèle avancé décrivant de façon appropriée l'architecture du système embarqué parallèle. Après la formalisation du problème de l'ordonnancement des tâches avec ce modèle d'architecture, nous présentons plusieurs heuristiques d'ordonnancement basées sur la méthode de la liste (list scheduling) pour améliorer les performances de l'ordonnancement. Nos résultats expérimentaux attestent d'une accélération de l'application dans un contexte de moyenne ou de forte communication. Comme le poids des communications va en croissant dans les applications les plus récentes, que ce soient en communication numérique ou en compression vidéo, nos méthodes s'avèrent efficaces dans la mise en oeuvre de ces applications sur systèmes embarqués parallèles. Nos méthodes d'ordonnancement sont intégrées dans PREESM, environnement de prototypage rapide basé sur Eclipse en "open source".

La puissance de calcul des plus grands calculateurs ne fait qu'augmenter: de quelques centaines de cœurs de calculs dans les années 1990, on en est maintenant à plusieurs millions! Leur infrastructure évolue aussi: elle n'est plus linéaire, mais complètement hiérarchique. Les applications de calcul intensif, largement utilisées par la communauté scientifique, doivent donc se munir d'outils permettant d'utiliser pleinement l'ensemble de ces ressources de manière efficace. La simulation numérique repose bien souvent sur d'importants calculs dont le coût, en termes de temps et d'accès mémoire, peut fortement varier au cours du temps: on parle de charge de calcul variable. Dans cette Thèse, on se propose d'étudier les outils actuels de répartition des données et des calculs, afin de voir les raisons qui font que de tels outils ne sont pas pleinement adaptés aux fortes variations de charge ainsi qu'à la hiérarchie toujours plus importante des nouveaux calculateurs. Nous proposerons alors un nouveau modèle d'ordonnancement et de partitionnement, basé sur des interactions physiques, particulièrement adapté aux applications basées sur des maillages réguliers et présentant de fortes variations de charge au cours du temps. Nous validerons alors ce modèle en le comparant à des outils de partitionnement de graphes reconnus et largement utilisés, et verrons les raisons qui le rendent plus performant pour des applications aussi bien parallèles que distribuées. Enfin, nous proposerons une interface nous permettant d'utiliser cette méthode d'ordonnancement dans des calculateurs toujours plus hiérarchiques. / Computing capability of largest computing centers is still increasing: from a few hundred of cores in the90's, they can now exceed several million of cores! Their infrastructure also evolves: it is no longerlinear, but fully hierarchical.High Performance applications, well used by the scientific community, require on tools that allow themto efficiently and fully use computing resources.Numerical simulations mostly rely on large computations chains for which the cost (computing load), either acomputing time or a memory access time, can strongly vary over time: it is referred to as dynamic computing loadevolution.In this thesis, we propose to study actual data partitioning and computing scheduling tools, and to explore theirlimitations with regards to strong and repetitive load variation as well as the still increasing cluster hierarchy.We will then propose a new scheduling and partitioning model, based on physical interactions, particularlysuitable to regular mesh based applications that produce strong computing load variations over time.We will then compare our model against well-known and widely used graph partitioning tools and we will see thereasons that make this model more reliable for such parallel and distributed applications.Lastly, we will propose a multi-level scheduling interface that is specially designed to allow to use ourmodel in even more hierarchical clusters.

Le problème étudié est celui de l'ordonnancement d'applications dans lessystèmes parallèles et distribués avec plusieurs utilisateurs. Les nouvellesplates-formes de calcul parallèle et distribué offrent des puissances trèsgrandes qui permettent d'envisager la résolution d'applications complexesinteractives. Aujourd'hui, il reste encore difficile d'utiliser efficacementcette puissance par manque d'outils de gestion de ressources. Le travaileffectué dans cette thèse se place dans cette perspective d'analyser etdévelopper des algorithmes efficaces pour gérer efficacement des ressources decalcul partagées entre plusieurs utilisateurs. On analyse les scénarios avecplusieurs soumissions lancées par multiples utilisateurs au cours du temps. Cessoumissions ont un ou plus de processus et l'ensemble de soumissions estorganisé en successifs campagnes. Les processus d'une seule campagnesont séquentiels et indépendants, mais les processus d'une campagne ne peuventpas commencer leur exécution avant que tous les processus provenant de ladernière campagne sont completés. Chaque utilisateur est intéressé à minimiserla somme des temps de réponses des campagnes. On définit un modèle théorique pour l'ordonnancement des campagnes et on montreque, dans le cas général, c'est NP-difficile. Pour le cas avec un utilisateur,on démontre qu'un algorithme d'ordonnancement $ho$-approximation pour le(classique) problème d'ordonnancement de tâches parallèles est aussi un$ho$-approximation pour le problème d'ordonnancement de campagnes. Pour lecas général avec $k$ utilisateurs, on établis un critère de emph{fairness}inspiré par partage de temps. On propose FairCamp, un algorithmed'ordonnancement qu'utilise dates limite pour réaliser emph{fairness} parmiles utilisateurs entre consécutifes campagnes. On prouve que FairCamp augmentele temps de réponse de chaque utilisateur par a facteur maximum de $kho$ parrapport un processeur dédiée à l'utilisateur. On prouve aussi que FairCamp estun algorithme $ho$-approximation pour le maximum emph{stretch}.On compare FairCamp contre emph{First-Come-First-Served} (FCFS) parsimulation. On démontre que, comparativement à FCFS, FairCamp réduit le maximal{em stretch} a la limite de $3.4$ fois. La différence est significative dansles systèmes utilisé pour plusieurs ($k>5$) utilisateurs.Les résultats montrent que, plutôt que juste des tâches individuelle etindépendants, campagnes de tâches peuvent être manipulées d'une manièreefficace et équitable. / We study the problem of scheduling in parallel and distributedsystems with multiple users. New platforms for parallel and distributedcomputing offers very large power which allows to contemplate the resolution ofcomplex interactive applications. Nowadays, it is still difficult to use thispower efficiently due to lack of resource management tools. The work done inthis thesis lies in this context: to analyse and develop efficient algorithmsfor manage computing resources shared among multiple users. We analyzescenarios with many submissions issued from multiple users over time. Thesesubmissions contain one or more jobs and the set of submissions are organizedin successive campaigns. Any job from a campaign can not start until allthe jobs from the previous campaign are completed. Each user is interested inminimizing the sum of flow times of the campaigns.In the first part of this work, we define a theoretical model for Campaign Scheduling under restrictive assumptions andwe show that, in the general case, it is NP-hard. For the single-user case, we show that an$ho$-approximation scheduling algorithm for the (classic) parallel jobscheduling problem is also an $ho$-approximation for the Campaign Schedulingproblem. For the general case with $k$ users, we establish a fairness criteriainspired by time sharing. Then, we propose FairCamp, a scheduling algorithm whichuses campaign deadlines to achieve fairness among users between consecutivecampaigns. We prove that FairCamp increases the flow time of each user by afactor of at most $kho$ compared with a machine dedicated to the user. Wealso prove that FairCamp is an $ho$-approximation algorithm for the maximumstretch.We compare FairCamp to {em First-Come-First-Served} (FCFS) by simulation. We showthat, compared with FCFS, FairCamp reduces the maximum stretch by up to $3.4$times. The difference is significant in systems used by many ($k>5$) users.Our results show that, rather than just individual, independent jobs, campaignsof jobs can be handled by the scheduler efficiently and fairly.

Cette thèse s'intéresse aux architectures contenant des FPGAs reconfigurables dynamiquement et partiellement. Dans ces architectures, la complexité et la difficulté de portage des applications sont principalement dues aux connections étroites entre la gestion de la reconfiguration et le calcul lui-même. Nous proposons 1) un nouveau niveau d'abstraction, appelé gestionnaire de composants matériels (HCM) et 2) un mécanisme de communication scalable (SCM), qui permettent une séparation claire entre l'allocation d'une fonction matérielle et la procédure de reconfiguration. Cela réduit l'impact de la gestion de la reconfiguration dynamique sur le code de l'application, ce qui simplifie grandement l'utilisation des plateformes FPGA. Les application utilisant le HCM et le SCM peuvent aussi être portées de manière transparentes à des systèmes multi-FPGA et/ou multi-utilisateurs. L'implémentation de cette couche HCM et du mécanisme SCM sur des plateformes réalistes de prototypage virtuel démontre leur capacité à faciliter la gestion du FPGA tout en préservant les performances d'une gestion manuelle, et en garantissant la protection des fonctions matérielles. L'implémentation du HCM et du mécanisme SCM ainsi que leur environnement de simulation sont open-source dans l'espoir d'une réutilisation par la communauté.

Cette thèse s'intéresse aux architectures contenant des FPGAs reconfigurables dynamiquement et partiellement. Dans ces architectures, la complexité et la difficulté de portage des applications sont principalement dues aux connections étroites entre la gestion de la reconfiguration et le calcul lui-même. Nous proposons 1) un nouveau niveau d'abstraction, appelé gestionnaire de composants matériels (HCM) et 2) un mécanisme de communication scalable (SCM), qui permettent une séparation claire entre l'allocation d'une fonction matérielle et la procédure de reconfiguration. Cela réduit l'impact de la gestion de la reconfiguration dynamique sur le code de l'application, ce qui simplifie grandement l'utilisation des plateformes FPGA. Les application utilisant le HCM et le SCM peuvent aussi être portées de manière transparentes à des systèmes multi-FPGA et/ou multi-utilisateurs. L'implémentation de cette couche HCM et du mécanisme SCM sur des plateformes réalistes de prototypage virtuel démontre leur capacité à faciliter la gestion du FPGA tout en préservant les performances d'une gestion manuelle, et en garantissant la protection des fonctions matérielles. L'implémentation du HCM et du mécanisme SCM ainsi que leur environnement de simulation sont open-source dans l'espoir d'une réutilisation par la communauté. / This thesis shows that in FPGA-based dynamic reconfigurable architectures, the complexity and low portability of application developments are mainly due to the tight connections between reconfiguration management and computation. By proposing 1) a new abstraction layer, called Hardware Component Manager (HCM) and 2) a Scalable Communication Mechanism (SCM), we clearly separate the allocation of a hardware function from the control of a reconfiguration procedure. This reduces the dynamic reconfiguration management impact on the application code, which greatly simplifies the use of FPGA platforms. Applications using the HCM and the SCM can also be transparently ported to multi-user and/or multi-FPGA systems. The implementation of this HCM layer and the SCM mechanism on realistic simulation platforms demonstrates their ability to ease the management of FPGA flexibility while preserving performance and ensuring hardware function protection. The HCM and SCM implementations and their simulation environment are open-source in the hope of reuse by the community.

Les problèmes d'optimisation en variables mixtes sont souvent résolus par décomposition quand ils sont de grande taille, avec quelques inconvénients : difficultés de garantir la qualité voire l'admissibilité des solutions et complexité technique des projets de développement. Dans cette thèse, nous proposons une approche directe, en utilisant la recherche locale, pour résoudre des problèmes d'optimisation mixte. Notre méthodologie se concentre sur deux points : un vaste ensemble de mouvements et une évaluation incrémentale basée sur des algorithmes approximatifs, travaillant simultanément sur les dimensions combinatoire et continue. Tout d'abord, nous présentons un problème d'optimisation des stocks de banches sur chantiers. Ensuite, nous appliquons cette technique pour optimiser l'ordonnancement des mouvements de terre pour le terrassement d'autoroutes et de voies ferrées. En n, nous discutons d'un problème de routage de véhicules avec gestion des stocks. Les coûts logistiques sont optimisés pour livrer un produit fluide par camion dans des zones géographiques d'une centaine de clients, avec la gestion de l'inventaire con ée au fournisseur.

De part leur capacité de reconfiguration et les performances qu’ils offrent, les FPGAs sont de bons candidats pour accélérer des applications dans le Cloud. Cependant, les FPGAs présentent certaines caractéristiques qui font obstacle à leur utilisation dans le Cloud et leur adoption par les clients : premièrement, la programmation des FPGAs se fait à bas niveau et demande une certaine expertise, que n’ont pas nécessairement les clients habituels du Cloud. Deuxièmement, les FPGAs ne présentent pas de mécanismes natifs permettant leur intégration dans le modèle de gestion dynamique d’une infrastructure Cloud.Dans ce travail, nous proposons d’utiliser des architectures overlay afin de faciliter l’adoption, l’intégration et l’exploitation de FPGAs dans le Cloud. Les overlays sont des architectures reconfigurables elles-mêmes implémentée sur FPGA. En tant que couche d’abstraction matérielle placée entre le FPGA et les applications, les overlays permettent de monter le niveau d’abstraction du modèle d’exécution présenté aux applications et aux utilisateurs, ainsi que d’implémenter des mécanismes facilitant leur intégration et leur exploitation dans une infrastructure Cloud.Ce travail présente une approche verticale adressant tous les aspects de la mise en œuvre d’overlays dans le Cloud en tant qu’accélérateurs reconfigurables par les clients : de la conception et l’implémentation des overlays, leur intégration sur des plateformes FPGA commerciales, la mise en place de leurs mécanismes d’exploitation, jusqu’à la réalisationde leurs outils de programmation. L’environnement réalisé est complet, modulaire et extensible, il repose en partie sur différents outils existants, et démontre la faisabilité de notre approche. / Due to their reconfigurable capability and the performance they offer, FPGAs are good candidates for accelerating applications in the cloud. However, FPGAs have some features that hinder their use in the Cloud as well as their adoption by customers : first, FPGA programming is done at low level and requires some expertise that usual Cloud clients do not necessarily have. Secondly, FPGAs do not have native mechanisms allowing them to easily fit in the dynamic execution model of the Cloud.In this work, we propose to use overlay architectures to facilitate FPGA adoption, integration, and operation in the Cloud. Overlays are reconfigurable architectures synthesized on FPGA. As hardware abstraction layers placed between the FPGA and applications, overlays allow to raise the abstraction level of the execution model presented to applications and users, as well as to implement mechanisms making them fit in a Cloud infrastructure.This work presents a vertical approach addressing all aspects of overlay operation in the Cloud as reconfigurable accelerators programmable by tenants : from designing and implementing overlays, integrating them on commercial FPGA platforms, setting up their operating mechanisms, to developping their programming tools. The environment developped in this work is complete, modular and extensible, it is partially based on several existing tools, and demonstrate the feasibility of our approach.