Les variabilités du processus de fabrication des technologies avancées (typ. < 32nm) sont de plus en plus difficile à maîtriser. Elles impactent plus sévèrement la fréquence de fonctionnement et la consommation d'énergie, et induisent de plus en plus de défaillances dans le circuit. Ceci est particulièrement vrai pour les MPSoCs, où le nombre de coeurs de calculs est très important. Les besoins (performances, fonctionnalités, faible consommation, tolérance aux fautes) ne cessent de croître et les caractéristiques hétérogènes (fréquence, énergie, défaillances) rendent difficile la mise en oeuvre de systèmes répondant à ces exigences. Ces travaux s'inscrivent dans l'optique de traiter ces problèmes pour des systèmes MPSoCs massivement parallèles, basés sur une topologie en maille 2D. Cette thèse propose une méthodologie automatisée qui permet le placement et l'ordonnancement d'applications dans les systèmes ciblés. Les aspects variabilité, consommation et performance sont pris en compte. D'autre part, cette thèse propose une technique de placement adaptatif tolérant aux fautes basée sur une stratégie de recouvrement des erreurs. Cette stratégie permet de garantir la terminaison de l'application en présence de défaillances, sans avoir recours à la prise de « check-points ». Cette technique est complété par des algorithmes adaptatifs distribués, prenant en compte la variabilité et la consommation d'énergie. / With the advanced technologies (typ. < 32nm), it is more and more difficult to control the manufacturing variabilities. It impacts more severely the working frequency and the consumed energy, and induces more and more failure inside the device. This is particularly true for MPSoC with a large number of computing cores. With the increasing needs (performance, functionalities, low power, fault tolerance) and heterogeneous characteristics (frequency, energy, failures) it becomes difficult to apply to systems able to meet these requirements. This work focus on this perspective to deal with these issues for the massively parallel MPSoC, based on 2D mesh topology. This thesis proposes an automated methodology, allowing the mapping and scheduling of application on the targeted system. It takes into account the variability, energy and computing power. Furthermore, this thesis proposes a fault tolerant adaptive mapping technique, paired with an original failure recovering strategy. This strategy allows to guarantee the termination of the application in the presence of failures, without the check-point requirement. The technique has been extended with an adaptive distributed algorithm, taking into account the manufacturing variability and aimed at reducing the consumed energy.

La complexité croissante des systèmes embarqués nécessite des formalismes de modélisation qui peuvent être simulés et analysés pour explorer l'espace des alternatives de conception. Cette thèse décrit le développement d'un formalisme de modélisation et des outils pour l'exploration de l'espace de design au plus tôt dans le flot de conception. Nous étendons le model-checking classique au pire cas pour les automates temporisés à l'analyse stochastique basée sur un raffinement des intervalles d'incertitude temporelle par des distributions sur les délais. D'une part, nous introduisons le formalisme des Duration Probabilistic Automata (DPA) à partir duquel nous pouvons réaliser de l'analyse ainsi que de l'optimisation. D'autre part nous présentons DESPEX (Design Space Explorer), un outil d'évaluation de performance de modèles de haut niveau des applications qui s'exécutent sur les plates-formes multi-coeurs. Nous montrons également son utilisation sur plusieurs cas d'étude. / The growing complexity of embedded systems calls for modeling formalisms that can be simulated and analyzed to explore the space of design alternatives. This thesis describes the development of a modeling formalism and tools for design space exploration at early design stage.We extend the classical worst-case model checking for timed automata to stochastic analysis based on a refinement of temporal uncertainty intervals into delay distribution. On one hand we introduce the formalism of Duration Probabilistic Automata (DPA) supporting analysis as well as optimization. On the other hand we provide DESPEX (DEsign SPace EXplorer), a tool for performance evaluation of high-level models of applications running on multi-core platforms. We also show its usage on several case studies.

Cette thèse propose une approche originale d’ordonnancement de la production de plates-formes de machines hétérogènes et distribuées, utilisées en parallèle pour fournir un service global commun. L’originalité de la contribution réside dans la proposition de modifier les conditions opératoires des machines au cours de leur utilisation. Il est supposé qu'utiliser une machine avec des performances dégradées par rapport à un fonctionnement nominal permet d'allonger sa durée de vie avant maintenance. L’étude s’inscrit dans la partie décisionnelle du PHM (Prognostics and Health Management), au sein duquel une étape de pronostic permet de déterminer les durées de vie résiduelles des machines. Le problème d’optimisation consiste à déterminer à chaque instant l’ensemble des machines à utiliser et un profil de fonctionnement pour chacune d’entre elles de manière à maximiser l’horizon de production de la plate-forme avant maintenance. Deux modèles sont proposés pour la définition des profils de fonctionnement. Le premier traduit le comportement à l'usure de machines pouvant fournir un nombre discret de performances. Pour ce cas, la complexité de plusieurs variantes du problème d'optimisation est étudiée et plusieurs méthodes de résolution optimales et sous-optimales sont proposées pour traiter le problème d'ordonnancement. Plusieurs méthodes de résolution sous-optimales sont ensuite proposées pour le second modèle, qui s'applique à des machines dont le débit peut varier de manière continue entre deux bornes. Ces travaux permettent de déterminer la durée maximale d’utilisation avant défaillance d’un système à partir des durées de vie résiduelles des équipements qui le composent. / This thesis addresses the problem of maximizing the production horizon of a heterogeneous distributed platform composed of parallel machines and which has to provide a global production service. Each machine is supposed to be able to provide several throughputs corresponding to different operating conditions. It is assumed that using a machine with degraded performances compared to nominal ones allows to extend its useful life before maintenance. The study falls within the decisional step of PHM (Prognostics and Health Management), in which a prognostics phase allows to determine remaining useful lives of machines. The optimization problem consists in determining the set of machines to use at each time and a running profile for each of them so as to maximize the production horizon before maintenance. Machines running profiles are defined on the basis of two models. First one depicts the behavior of machines used with a discrete number of performances. For this case, the problem complexity is first studied considering many variants of the optimization problem. Several optimal and sub-optimal resolution methods are proposed to deal with the scheduling problem. Several sub-optimal resolution methods are then proposed for the second model, which applies to machines whose throughput rate can vary continuously between two bounds. These research works allow to determine the time before failure of a system on the basis of its components remaining useful lives.

Les ressources de calcul à haute performance (High-Performance Computing—HPC), telles que les supercalculateurs, les grappes, les grilles de calcul ou les Clouds HPC, sont gérées par des gestionnaires de ressources (Resource Management System—RMS) qui multiplexent les ressources entre plusieurs utilisateurs et décident comment allouer les nœuds de calcul aux applications des utilisateurs. Avec la multiplication de machines péta-flopiques et l’arrivée des machines exa-flopiques attendue en 2020, l’optimisation de l’allocation des ressources aux applications est essentielle pour assurer que leur exécution soit efficace. Cependant, les RMSs existants, tels que les batch schedulers, n’offrent qu’une interface restreinte. Dans la plupart des cas, l’application doit choisir les ressources « aveuglément » lors de la soumission sans pouvoir adapter son choix à l’état des ressources ciblées, ni avant, ni pendant l’exécution.Le but de cette Thèse est d’améliorer la gestion des ressources, afin de permettre aux applications d’allouer des ressources efficacement. Pour y parvenir, nous proposons des architectures logicielles qui favorisent la collaboration entre les applications et le gestionnaire de ressources, permettant ainsi aux applications de négocier les ressources qu’elles veulent utiliser. À cette fin, nous analysons d’abord les types d’applications et leurs besoins en ressources, et nous les divisons en plusieurs catégories : rigide, modelable, malléable et évolutive. Pour chaque cas, nous soulignons les opportunités d’amélioration de la gestion de ressources. Une première contribution traite les applications modelables, qui négocient les ressources seulement avant leur démarrage. Nous proposons CooRMv1, une architecture RMS centralisée, qui délègue la sélection des ressources aux lanceurs d’application. Des simulations montrent qu’un tel système se comporte bien en termes d’extensibilité et d’équité. Les résultats ont été validés avec un prototype déployé sur la plate-forme Grid’5000. Une deuxième contribution se focalise sur la négociation des allocations pour des ressources géographiquement distribuées qui appartiennent à plusieurs institutions. Nous étendons CooRMv1 pour proposer distCooRM, une architecture RMS distribuée, qui permet aux applications modelables de co-allouer efficacement des ressources gérées par plusieurs agents indépendants. Les résultats de simulation montrent que distCooRM se comporte bien et passe à l’échelle pour un nombre raisonnable d’applications. Ensuite, nous nous concentrons sur la négociation des ressources à l’exécution pour mieux gérer les applications malléables et évolutives. Nous proposons CooRMv2, une architecture RMS centralisée, qui permet l’ordonnancement efficace des applications évolutives, et surtout celles dont l’évolution n’est pas prévisible. Une application peut faire des « pré-allocations » pour exprimer ses pics de besoins en ressources. Cela lui permet de demander dynamiquement des ressources, dont l’allocation est garantie tant que la pré-allocation n’est pas dépassée. Les ressources pré-allouées mais inutilisées sont à la disposition des autres applications. Des gains importants sont ainsi obtenus, comme les simulations que nous avons effectuées le montrent.Enfin, nous partons de logiciels utilisés en production pour illustrer l’intérêt, mais aussi la difficulté, d’améliorer la collaboration entre deux systèmes existants. Avec GridTLSE comme application et DIET comme RMS, nous avons trouvé un cas d’utilisation mal supporté auparavant. Nous identifions le problème sous-jacent d’ordonnancement des calculs optionnels et nous proposons une architecture pour le résoudre. Des expériences réelles sur la plate-forme Grid’5000 montrent que plusieurs métriques peuvent être améliorées, comme par exemple la satisfaction des utilisateurs, l’équité et le nombre de requêtes traitées. En outre, nous montrons que cette solution présente une bonne extensibilité. / High-Performance Computing (HPC) resources, such as Supercomputers, Clusters, Grids and HPC Clouds, are managed by Resource Management Systems (RMSs) that multiple resources among multiple users and decide how computing nodes are allocated to user applications. As more and more petascale computing resources are built and exascale is to be achieved by 2020, optimizing resource allocation to applications is critical to ensure their efficient execution. However, current RMSs, such as batch schedulers, only offer a limited interface. In most cases, the application has to blindly choose resources at submittal without being able to adapt its choice to the state of the target resources, neither before it started nor during execution. The goal of this Thesis is to improve resource management, so as to allow applications to efficiently allocate resources. We achieve this by proposing software architectures that promote collaboration between the applications and the RMS, thus, allowing applications to negotiate the resources they run on. To this end, we start by analysing the various types of applications and their unique resource requirements, categorizing them into rigid, moldable, malleable and evolving. For each case, we highlight the opportunities they open up for improving resource management.The first contribution deals with moldable applications, for which resources are only negotiated before they start. We propose CooRMv1, a centralized RMS architecture, which delegates resource selection to the application launchers. Simulations show that the solution is both scalable and fair. The results are validated through a prototype implementation deployed on Grid’5000. Second, we focus on negotiating allocations on geographically-distributed resources, managed by multiple institutions. We build upon CooRMv1 and propose distCooRM, a distributed RMS architecture, which allows moldable applications to efficiently co-allocate resources managed by multiple independent agents. Simulation results show that distCooRM is well-behaved and scales well for a reasonable number of applications. Next, attention is shifted to run-time negotiation of resources, so as to improve support for malleable and evolving applications. We propose CooRMv2, a centralized RMS architecture, that enables efficient scheduling of evolving applications, especially non-predictable ones. It allows applications to inform the RMS about their maximum expected resource usage, through pre-allocations. Resources which are pre-allocated but unused can be filled by malleable applications. Simulation results show that considerable gains can be achieved. Last, production-ready software are used as a starting point, to illustrate the interest as well as the difficulty of improving cooperation between existing systems. GridTLSE is used as an application and DIET as an RMS to study a previously unsupported use-case. We identify the underlying problem of scheduling optional computations and propose an architecture to solve it. Real-life experiments done on the Grid’5000 platform show that several metrics are improved, such as user satisfaction, fairness and the number of completed requests. Moreover, it is shown that the solution is scalable.

La consommation énergétique des centres de calculs et de données, aussi appelés « data centers », représentait 2% de la consommation mondiale d'électricité en 2012. Leur nombre est en augmentation et suit l'évolution croissante des objets connectés, services, applications, et des données collectées. Ces infrastructures, très consommatrices en énergie, sont souvent sur-dimensionnées et les serveurs en permanence allumés. Quand la charge de travail est faible, l'électricité consommée par les serveurs inutilisés est gaspillée, et un serveur inactif peut consommer jusqu'à la moitié de sa consommation maximale. Cette thèse s'attaque à ce problème en concevant un data center ayant une consommation énergétique proportionnelle à sa charge. Nous proposons un data center hétérogène, nommé BML pour « Big, Medium, Little », composé de plusieurs types de machines : des processeurs très basse consommation et des serveurs classiques. L'idée est de profiter de leurs différentes caractéristiques de performance, consommation, et réactivité d'allumage, pour adapter dynamiquement la composition de l'infrastructure aux évolutions de charge. Nous décrivons une méthode générique pour calculer les combinaisons de machines les plus énergétiquement efficaces à partir de données de profilage de performance et d'énergie acquis expérimentalement considérant une application cible, ayant une charge variable au cours du temps, dans notre cas un serveur web.Nous avons développé deux algorithmes prenant des décisions de reconfiguration de l'infrastructure et de placement des instances de l'application en fonction de la charge future. Les différentes temporalités des actions de reconfiguration ainsi que leur coûts énergétiques sont pris en compte dans le processus de décision. Nous montrons par simulations que nous atteignons une consommation proportionnelle à la charge, et faisons d'importantes économies d'énergie par rapport aux gestions classiques des data centers. / The increasing number of data centers raises serious concerns regarding their energy consumption. These infrastructures are often over-provisioned and contain servers that are not fully utilized. The problem is that inactive servers can consume as high as 50% of their peak power consumption.This thesis proposes a novel approach for building data centers so that their energy consumption is proportional to the actual load. We propose an original infrastructure named BML for "Big, Medium, Little", composed of heterogeneous computing resources : from low power processors to classical servers. The idea is to take advantage of their different characteristics in terms of energy consumption, performance, and switch on reactivity to adjust the composition of the infrastructure according to the load evolutions. We define a generic methodology to compute the most energy proportional combinations of machines based on hardware profiling data.We focus on web applications whose load varies over time and design a scheduler that dynamically reconfigures the infrastructure, with application migrations and machines switch on and off, to minimize the infrastructure energy consumption according to the current application requirements.We have developed two different dynamic provisioning algorithms which take into account the time and energy overheads of the different reconfiguration actions in the decision process. We demonstrate through simulations based on experimentally acquired hardware profiles that we achieve important energy savings compared to classical data center infrastructures and management.

L'utilisation massive des services connectés dans les entreprises et les foyers a conduit à un développement majeur des "Ciouds" ou informatique en nuage. Les Clouds s'imposent maintenant comme un modèle économique attractif où le client paye pour utiliser des ressources ou des services à la demande sans avoir à se préoccuper de la maintenance ou du coût réel de l'infrastructure. Ce développement rencontre cependant un obstacle majeur du point de vue des fournisseurs de ce type d'architecture : la consommation électrique des moteurs du cloud, les "datacenters" ou centre de données.Cette thèse s'intéresse à l'efficacité énergétique des Clouds en proposant un framework d'ordonnancement extensible et multi-critères dans le but d'augmenter le rendement d'une infrastructure hétérogène d'un point de vue énergétique. Nous proposons une approche basée sur un curseur capable d'aggréger les préférences de l'opérateur et du client pour la création de politiques d'ordonnancement. L'enjeu est de dimensionner au plus juste le nombre de serveurs et composants actifs tout en respectant les contraintes d'exploitation, et ainsi réduire les impacts environnementaux liés à une consommation superflue.Ces travaux ont été validés de façon expérimentale sur la plateforme Grid'SOOO par leur intégration au sein de l'intergiciel DIET et font l'objet d'un transfert industriel au sein de la plateforme NUVEA que nous proposons. Cette plate-forme fournit un accompagnement pour l'opérateur et l'utilisateur allant de l'audit à l'optimisation des infrastructures. / Modern society relies heavily on the use of computational resources. Over the last decades, the number of connected users and deviees has dramatically increased, leading to the consideration of decentralized on-demand computing as a utility, commonly named "The Cloud". Numerous fields of application such as High Performance Computing (HPC). medical research, movie rendering , industrial facto ry processes or smart city management , benefit from recent advances of on-demand computation .The maturity of Cloud technologies led to a democratization and to an explosion of connected services for companies, researchers, techies and even mere mortals, using those resources in a pay-per-use fashion.ln particular, since the Cloud Computing paradigm has since been adopted in companies . A significant reason is that the hardware running the cloud andprocessing the data does not reside at a company physical site, which means thatthe company does not have to build computer rooms (known as CAPEX, CAPitalEXpenditures) or buy equipment, nor to fill and mainta in that equipment over a normal life-cycle (known as OPEX, Operational EXpenditures).This thesis revolves around the energy efficiency of Cloud platforms by proposing an extensible and multi-criteria framework, which intends to improve the efficiency of an heterogeneous platform from an energy consumption perspective. We propose an approach based on user involvement using the notion of a cursor offering the ability to aggregate cloud operator and end user preferences to establish scheduling policies . The objective is the right sizing of active servers and computing equipments while considering exploitation constraints, thus reducing the environmental impactassociated to energy wastage.This research work has been validated on experiments and simulations on the Grid'SOOO platform, the biggest shared network in Europe dedicated to research.lt has been integrated to the DIET middleware, and a industrial valorisation has beendone in the NUVEA commercial platform, designed during this thesis . This platform constitutes an audit and optimization tool of large scale infrastructures for operatorsand end users

Le but de cette thèse est d'exploiter efficacement le parallélisme présent dans les applications informatiques séquentielles afin de bénéficier des performances fournies par les multiprocesseurs, en utilisant une nouvelle méthodologie pour la parallélisation automatique des tâches au sein des compilateurs. Les caractéristiques clés de notre approche sont la prise en compte des contraintes de ressources et le caractère statique de l'ordonnancement des tâches. Notre méthodologie contient les techniques nécessaires pour la décomposition des applications en tâches et la génération de code parallèle équivalent, en utilisant une approche générique qui vise différents langages et architectures parallèles. Nous implémentons cette méthodologie dans le compilateur source-à-source PIPS. Cette thèse répond principalement à trois questions. Primo, comme l'extraction du parallélisme de tâches des codes séquentiels est un problème d'ordonnancement, nous concevons et implémentons un algorithme d'ordonnancement efficace, que nous nommons BDSC, pour la détection du parallélisme ; le résultat est un SDG ordonnancé, qui est une nouvelle structure de données de graphe de tâches. Secondo, nous proposons une nouvelle extension générique des représentations intermédiaires séquentielles en des représentations intermédiaires parallèles que nous nommons SPIRE, pour la représentation des codes parallèles. Enfin, nous développons, en utilisant BDSC et SPIRE, un générateur de code que nous intégrons dans PIPS. Ce générateur de code cible les systèmes à mémoire partagée et à mémoire distribuée via des codes OpenMP et MPI générés automatiquement. / This thesis intends to show how to efficiently exploit the parallelism present in applications in order to enjoy the performance benefits that multiprocessors can provide, using a new automatic task parallelization methodology for compilers. The key characteristics we focus on are resource constraints and static scheduling. This methodology includes the techniques required to decompose applications into tasks and generate equivalent parallel code, using a generic approach that targets both different parallel languages and architectures. We apply this methodology in the existing tool PIPS, a comprehensive source-to-source compilation platform. This thesis mainly focuses on three issues. First, since extracting task parallelism from sequential codes is a scheduling problem, we design and implement an efficient, automatic scheduling algorithm called BDSC for parallelism detection; the result is a scheduled SDG, a new task graph data structure. In a second step, we design a new generic parallel intermediate representation extension called SPIRE, in which parallelized code may be expressed. Finally, we wrap up our goal of automatic parallelization in a new BDSC- and SPIRE-based parallel code generator, which is integrated within the PIPS compiler framework. It targets both shared and distributed memory systems using automatically generated OpenMP and MPI code.

À partir du moteur d’annotation sémantique Excom, nous avons élaboré un systèmede recherche d’informations qui repose sur des catégories sémantiques issues d’analyses linguistiquesautomatiques afin de proposer une approche de fouille textuelle innovante. Les annotationssont obtenues par la méthode d’Exploration Contextuelle faisant appel à une modélisationdes connaissances linguistiques sous forme de marqueurs et de règles. Le traitement des requêtesselon des points de vue de fouille se trouve au coeur de la stratégie de recherche d’informations.Pour cela, notre approche s’appuie sur des catégories d’annotation organisées en ontologies linguistiquessous forme de graphes. Afin d’offrir à l’utilisateur des résultats pertinents, nous avonsmis en place des algorithmes d’ordonnancement des réponses et de gestion de la redondance.Ces algorithmes reposent principalement sur la structure des ontologies linguistiques utiliséespour l’annotation. Nous avons proposé une évaluation de la pertinence des résultats en tenantcompte de la spécificité de l’approche. Les interfaces que nous avons développées permettent laconstruction de nouveaux produits documentaires tels que les fiches de synthèse offrant une extractiond’informations structurées selon des critères sémantiques. Cee approche a égalementpour vocation de proposer des outils dédiés à la veille stratégique et à l’intelligence économique. / Using the Excom engine for semantic annotation, we have constructed an InformationRetrieval System based on semantic categories from automatic language analyses in order topropose a new approach to text search. e annotations are obtained by the Contextual Explorationmethod which is a knowledge based linguistic approach using markers and disambiguationrules. e queries are formulated according to search viewpoints which are at the heart of theInformation Retrieval strategy. Our approach uses the annotation categories which are organisedin linguistic ontologies structured as graphs. In order to provide relevant results to the user,we have designed algorithms for ranking and paraphrase identification. ese algorithms exploitprincipally the structure of the linguistic ontologies for the annotation. We have carriedout an evaluation of the relevance of the system results taking into account the specificity ofour approach. We have developed user interfaces allowing the construction of new informationproducts such as structured text syntheses using information extraction according to semanticcriteria. is approach also aims to offer tools in the field of economic intelligence.

Dans le cadre du projet PAJERO, nous présentons dans cette thèse une parallélisation externe d'un solveur de Programmation Par Contraintes (PPC) basée sur des méthodes de parallélisation de la search et Portfolio. Cela, afin d'améliorer la performance de la résolution des problèmes de satisfaction et d'optimisation sous contraintes. La parallélisation de la search que nous proposons est adaptée pour une exécution en mode opportuniste et déterministe, suivant les besoins des clients. Le principe consiste à partitionner à la demande l'arbre de recherche unique généré par une seule stratégie de recherche en un ensemble de sous-arbres, pour ensuite affecter chaque sous-arbre à un coeur de calcul. Une stratégie de recherche est un algorithme qui choisit pour chaque noeud dans l'arbre de recherche la variable à assigner et choisi également l'ordonnancement de la recherche. En PPC, il existe plusieurs stratégies de recherche, certaines sont plus efficaces que d'autres, mais cela dépend généralement de la nature des problèmesde contraintes. Cependant la difficulté reste de choisir la bonne stratégie. Pour bénéficier de la variété des stratégies et de la disponibilité des ressources de calcul, un autre type de parallélisation est proposé, appelé Portfolio. La parallélisationPortfolio consiste à exécuter en parallèle N stratégies de recherche, ensuite la première stratégie qui trouve une solution met fin à toutes les autres. La nouveauté que nous proposons dans la parallélisation Portfolio consiste à adapterl'ordonnancement des N stratégies entre elles afin de privilégier la stratégie la plus prometteuse. Cela en lui donnant plus de coeurs que les autres. Pour ceci nous appliquons soit une fonction d'estimation pour chaque stratégie afin de sélectionner la stratégie qui a le plus petit arbre de recherche, soit un algorithme d'apprentissage qui permet de prédire quelle est la meilleure stratégie suivant le résultat d'un apprentissage effectué sur des instances déjà résolues. Afin d'ordonnancer plusieurs applications de PPC, nous proposons également un nouveau système d'allocation de ressources basé sur une stratégie d'ordonnancement combinée avec un modèle économique. Les applications de PPC sont résolues avec des solveurs parallèles dans une infrastructure cloud computing. L'originalité du system d'allocation est qu'il détermine automatiquement le nombre de ressources à affecter pour chaque application suivant la classe économique du client. Les performances obtenues avec nos méthodes de parallélisation sont illustrées par la résolution des problèmes de contraintes en portant le solveur Google OR-Tools au-dessus de notre framework parallèle Bobpp / In the context of the PAJERO project, we propose in this thesis an external parallelization of a Constraint Programming (CP) solver, using both search and Portfolio parallelizations, in order to solve constraint satisfaction and optimization problems. In our work the search parallelization is adapted for deterministic and non-deterministic executions, according to the needs of the user. The principle is to partition the unique search tree generated by one search strategy into a set of sub-trees, then assign each sub-tree to one computing core. A search strategy herein means an algorithm to decide which variable is selected to be assigned in each node of the search tree, and decide also the scheduling of the search. In CP, several search strategies exist and each one could be better than others for solving a specific problem. The difficulty lies in how to choose the best strategy. To benefit from the variety of strategies and the availability of computationalresources, another parallelization exists called the Portfolio parallelization. The principle of this Portfolio parallelization is to execute N search strategies in parallel. The first strategy which find a solution stops the others. The noveltyof our work in the context of the Portfolio is to adapt the schedule of the N strategies in order to favour the most promising strategy, which is a candidate to find a solution first, by giving it more cores than others. The promising strategyis selected using two methods. The first method is to use an estimation function which select the strategy with the smallest search tree. The second method is to use a learning algorithm which automatically determines the number of cores thatwill be allocated to each strategy according to the previous experiment. We have also proposed a new resource allocation system based on a scheduling strategy used with an economic model in order to execute several PPC applications. Thisapplications are solved using parallel solvers in the cloud computing infrastructure. The originality of this system is that the number of resources allocated to each PPC application is determined automatically according the economic classesof the users. The performances obtained by our parallelization methods are illustrated by solving the CP problems using the Google OR-Tools solver on top of the parallel Bobpp framework.

Les applications temps réel durs sont celles qui doivent exécuter en respectant des contraintes temporelles. L'ordonnancement temps réel a bien été étudié sur mono-processeurs depuis plusieurs années. Récemment, l'utilisation d'architectures multiprocesseurs a augmenté dans les applications industrielles et des architectures parallèles sont proposées pour que le logiciel devienne compatible avec ces plateformes. L'ordonnancement multiprocesseurs de tâches parallèles dépendantes n'est pas une simple généralisation du cas mono-processeur et la problématique d'ordonnancement devient plus complexe et difficile.
Dans cette thèse, nous étudions le problème d'ordonnancement temps réel de graphes de tâches parallèles acycliques sur des plateformes multiprocesseurs. Dans ce modèle, un graphe est composé d'un ensemble de sous-tâches dépendantes sous contraintes de précédence qui expriment les relations de précédences entre les sous-tâches. L'ordre d'exécution des sous-tâches est dynamique, c'est-à-dire que les sous-tâches peuvent s'exécuter en parallèle ou séquentiellement par rapport aux décisions de l'ordonnanceur temps réel. Pour traiter les contraintes de précédence, nous proposons deux méthodes pour l'ordonnancement des graphes : par transformation du modèle de graphe de sous tâches parallèles en un modèle de tâches séquentielles indépendantes, plus simple à ordonnancer et par ordonnancement direct des graphes en prenant en compte les relations de dépendance entre les sous-tâches. Nous proposons un ordonnancement des graphes en prenant directement en compte les paramètres temporels des graphes et un ordonnancement au niveau des sous-tâches, par rapport à des paramètres temporels attribués aux sous-tâches par un algorithme spécifique.
Enfin, nous prouvons que les deux méthodes d'ordonnancement de graphes ne sont pas comparables. Nous fournissons alors des résultats de simulation pour comparer ces méthodes en utilisant les algorithmes d'ordonnancement globaux EDF et DM. Nous avons développé un logiciel nommé YARTISS pour générer des graphes aléatoires et réaliser les simulations / The interest for multiprocessor systems has recently been increased in industrial applications, and parallel programming API's have been introduced to benefit from new processing capabilities. The use of multiprocessors for real-time systems, whose execution is performed based on certain temporal constraints is now investigated by the industry. Real-time scheduling problem becomes more complex and challenging in that context. In multiprocessor systems, a hard real-time scheduler is responsible for allocating ready jobs to available processors of the systems while respecting their timing parameters.
In this thesis, we study the problem of real-time scheduling of parallel Directed Acyclic Graph (DAG) tasks on homogeneous multiprocessor systems. In this model, a DAG task consists of a set of subtasks that execute under precedence constraints. At all times, the real-time scheduler is responsible for determining how subtasks execute, either sequentially or in parallel, based on the available processors of the system. We propose two DAG scheduling approaches to determine the execution form of DAG tasks. The first approach is the DAG Stretching algorithm, from the Model Transformation approach, which forces DAG tasks to execute as sequentially as possible. The second approach is the Direct Scheduling, which aims at scheduling DAG tasks while respecting their internal dependencies. We provide real-time schedulability analyses for Direct Scheduling at DAG-Level and at Subtask-Level.
Due to the incomparability of DAG scheduling approaches, we use extensive simulations to compare performance of global EDF with global DM scheduling using our simulation tool YARTISS