Global ETD Search

1	Processus concurrents et combinatoire des structures croissantes : analyse quantitative et algorithmes de génération aléatoire / Concurrent process and combinatorics of increasingly labeled structures : quantitative analysis and random generation algorithms Dien, Matthieu 22 September 2017 (has links) Un programme concurrent est composé de plusieurs unités logiques : les processus. Chaque processus a un comportement qui lui est propre : il exécute ses actions de façon séquentielle. Un objectif important est de s'assurer que de tels systèmes concurrents complexes soient cependant exempts de défaut. Cette problématique est étudiée dans le cadre de la théorie de la concurrence. Quand plusieurs processus s’exécutent en parallèle, l’ordre d’exécution des actions du programme global n’est plus déterminé. On assiste au fameux phénomène "d’explosion combinatoire" faisant référence au très grand nombre d’exécutions globales possibles. Les diverses techniques et méthodes d'analyse existantes (model checking, analyse statique, tests automatisés, etc) se heurtent irrémédiablement à cette "explosion". Cette thèse s'inscrit dans un projet à long terme d'étude quantitative de ce phénomène et de développement des techniques d’analyse statistique basées sur la génération aléatoire uniforme. Notre objectif dans cette thèse est de traiter une composante fondamentale de la concurrence : la synchronisation. Ce mécanisme permet aux processus de communiquer entre eux. Dans cette thèse nous proposons un modèle combinatoire de structures croissantes pour modéliser les exécutions de programmes concurrents synchronisés. Avec des outils de combinatoire analytique nous obtenons plusieurs résultats exacts et asymptotiques sur le nombre moyen d'exécutions dans des sous-classes de programmes concurrents. Nous présentons aussi plusieurs algorithmes de génération aléatoire uniforme de structures croissantes et de leurs étiquetages. / A concurrent program is a composition of several logical blocks: the processes. Each process has its own behavior, independent from the others: it sequentially runs its actions. An important goal is to ensure that such concurrent complex systems are faultless. This problem is studied in the field of concurrency theory. When several process are running in parallel, the running order of the actions of the total program is no more decided. This is the well-known "combinatorial explosion" phenomena, meaning that the number of possible runs of the global program is huge. The analysis techniques and methods existing (model checking, static analysis, automated testing, etc) are irremediably limited by this "explosion". This thesis is a part of a long-term project about the quantitative study of this phenomena and the development of statistic analysis methods based on the uniform random generation. Our specific goal is to study a fundamental principle of the concurrency theory: the synchronization. This mechanism allows communications between the processes. In this thesis we propose a combinatorial model of increasingly labeled structures to deal with runs of synchronized concurrent programs. Using the tools of analytic combinatorics we obtain close formulas and asymptotic equivalents for the average number of runs in several subclasses of concurrent programs. We also present algorithms of uniform random generation of increasingly labeled structures and for their increasing labelings. Combinatoire analytique Théorie de la concurrence Génération aléatoire Série-parallèle Structures croissantes Ordre partiel Random generation Analytic combinatorics Concurrency theory 004.3
2	L’analyse cinématique de manipulateurs parallèles et reconfigurables / Kinematic analysis of reconfigurable parallel manipulators Nayak, Abhilash 14 December 2018 (has links) Un manipulateur parallèle à mobilité réduite a moins de six degrés de liberté et présente généralement différents types de mouvement connus sous le nom de modes d'opération. Ainsi, ce type de manipulateur peut être classifié comme reconfigurable selon sa capacité de transition entre les différents modes d'opération. Cette thèse de doctorat s'articule principalement autour de l'analyse cinématique de manipulateurs parallèles à mobilité réduite, de manipulateurs parallèles en série obtenus à partir de leur empilement en série et de mécanismes conformes conçus à partir de leurs configurations singulières à contraintes. La transformation cinématique de Study est utilisée pour dériver les équations algébriques de contraintes. Ensuite, elles sont interprétées à l'aide d'outils de géométrie algébrique pour effectuer des analyses de mobilité, de cinématique et de singularité. Les techniques de ‘‘screw theory’’ et ‘‘line geometry’’ sont utilisées à côté de l'approche algébrique au besoin. / A lower mobility parallel manipulator has less than six degrees of freedom and usually exhibits different motion types known as operation modes. Thus, it can be classified as reconfigurable on account of its ability to transition between different operation modes. This doctoral thesis mainly revolves around the kinematic analysis of some lower-mobility parallel manipulators, series-parallel manipulators obtained from their serial stacking and compliant mechanisms designed using their constraint singular configurations. Study's kinematic mapping is used to derive the algebraic constraint equations. They are further interpreted using algebraic geometry tools to perform mobility, kinematic and singularity analysis. Screw theory and line geometry techniques are used adjacent to algebraic approach wherever necessary. Manipulateurs parallèles Manipulateurs série-parallèle Mécanismes conformes Transformation de Study Singularités Parallel manipulators Series-parallel manipulators Compliant mechanisms Study's kinematic mapping Singularities
3	Modélisation et optimisation de problèmes de synchronisation dans les documents hypermédia Bachelet, Bruno 24 February 2003 (has links) (PDF) Les formats actuels de diffusion de documents sur Internet apportent sans conteste de nouvelles possibilités par rapport aux supports traditionnels. Mais les exigences deviennent toujours plus grandes et de nouveaux langages font régulièrement leur apparition pour tenter d'améliorer encore la structure et l'interactivité des documents. Parmi ces langages, certains offrent la possibilité d'animer et synchroniser des composants multimédia. Mais la variété de ces composants (audio, vidéo, texte, image...) font de l'animation un problème compliqué. L'auteur d'un document synchronisé fournit une liste de contraintes temporelles sur les composants de manière à décrire le déroulement de la présentation. Ces composants ont chacun une durée de présentation qui est flexible dans une certaine limite. Tout le problème consiste à trouver un bon ajustement des durées pour que la présentation se déroule au plus proche de ce que souhaite l'auteur tout en évitant les pauses. <br /><br />Le problème peut se modéliser, après quelques restrictions, comme un problème de tension de coût minimal dans un graphe. Pour le résoudre avec des coûts convexes linéaires par morceaux, nous avons étudié différentes approches (programmation linéaire, mise à conformité - out-of-kilter, mise à l'échelle du dual - cost-scaling). Nous proposons également une adaptation de la mise à conformité pour des coûts convexes dérivables. Toutes ces méthodes sont comparées sur des aspects théoriques et pratiques, en considérant des graphes quelconques. <br /><br />Les graphes représentant les contraintes temporelles sont en réalité très structurés et très proches de la classe des graphes appelés série-parallèles, et les méthodes élaborées pour une structure de graphe quelconque ne s'avèrent pas toujours très efficaces. Nous proposons une méthode polynômiale, en opérations, plus adaptée pour résoudre le problème sur des graphes série-parallèles, et que nous appelons agrégation. Mais ces graphes, bien que très proches de la réalité, restent encore une idéalisation. Nous proposons de mesurer l'aspect série-parallèle d'un graphe en définissant la notion de graphe presque série-parallèle, basée sur la décomposition du graphe en composantes série-parallèles. En exploitant l'efficacité de la méthode d'agrégation sur cette décomposition, nous proposons une méthode dite de reconstruction permettant de résoudre le problème pour des graphes presque série-parallèles plus efficacement que les méthodes étudiées précédemment. <br /><br />Lors de cette étude, nous avons développé une bibliothèque de composants réutilisables pour les problèmes de graphes. Nous expliquons en quoi ce type de développement ne peut pas toujours suivre les règles classiques du génie logiciel. Nous montrons comment le paradigme objet peut néanmoins être employé pour la création d'outils efficaces de recherche opérationnelle. Et nous proposons des patrons de conception pour élaborer des composants logiciels (algorithmes et structures de données) génériques, c'est-à-dire indépendants des structures de données qu'ils manipulent et des algorithmes qu'ils emploient, tout en étant fortement extensibles, et cela avec une perte d'efficacité minimale. synchronisation hypermédia graphe temporel tension de coût minimal graphe série-parallèle réutilisabilité logicielle approche orientée objet programmation générique
4	Etude, Commande et Mise en Oeuvre de Nouvelles Structures Multiniveaux Leredde, Alexandre 08 November 2011 (has links) (PDF) Les structures de conversion multiniveaux permettent de convertir en moyenne tension et forte puissance. Celles-ci sont construites à partir de cellules de commutations et permettent d'augmenter le courant et la tension en entrée ou en sortie. Ces structures sont appelées multiniveaux car les formes d'ondes des tensions en sortie permettent d'avoir plus de deux niveaux de tension différents. Les différentes structures peuvent être classées dans différentes catégories tel que la mise en série de pont en H, les convertisseurs multicellulaires série ou parallèle ou encore les structures utilisant le fractionnement du bus continu. Toutes ces structures ont des propriétés et applications différentes, même si certaines structures ont des propriétés communes. Il est aussi possible de créer de nouvelles structures en mixant les différentes structures de bases des différentes familles de convertisseurs multiniveaux ou en assemblant les structures de base de la conversion statique. Même si l'utilisation de structure de conversion multiniveaux permet de convertir à forte puissance, celle-ci n'est pas toujours aisée. En effet l'augmentation du nombre de niveaux ou de la tension d'entrée implique également une augmentation du nombre de composants semi-conducteurs. Ceci peut être un frein à l'utilisation de convertisseur multiniveaux. Pour cela une nouvelle structure utilisant des composants partagés entre les différentes phases est proposée afin de limiter leur nombre. Un autre problème important lié aux convertisseurs multiniveaux est l'équilibrage des tensions des condensateurs du bus continu si celui-ci est composé de plus de deux condensateurs mis en série. Pour cela plusieurs solutions sont possibles : soit en utilisant une commande spécifique utilisant la modulation vectorielle, soit en utilisant des structures auxiliaires qui ont pour but d'équilibrer les différentes tensions des condensateurs. Dans une dernière partie ont été proposées de nouvelles structures qui permettent à la fois d'augmenter le courant de sortie et la tension en entrée en utilisant les principes des structures de base des convertisseurs multicellulaires série et parallèle. De plus, ces structures ont des propriétés intéressantes sur les formes d'ondes de sortie. De ces structures a été conçu un prototype permettant de valider les résultats de simulation. Une commande numérique implantée sur FPGA a été réalisée et a permis d'avoir des résultats expérimentaux intéressants. Electronique de puissance Equilibrage du bus continu Conversion Statique Structure à Partage de Composants Convertisseurs Multiniveaux Etude de Nouvelles Structures Contrôle Numérique par FPGA
5	Etude, commande et mise en œuvre de nouvelles structures multiniveaux / Study and Design of Multilevel Converters for High Power Application Leredde, Alexandre 08 November 2011 (has links) Les structures de conversion multiniveaux permettent de convertir en moyenne tension et forte puissance. Celles-ci sont construites à partir de cellules de commutations et permettent d’augmenter le courant et la tension en entrée ou en sortie. Ces structures sont appelées multiniveaux car les formes d’ondes des tensions en sortie permettent d’avoir plus de deux niveaux de tension différents. Les différentes structures peuvent être classées dans différentes catégories tel que la mise en série de pont en H, les convertisseurs multicellulaires série ou parallèle ou encore les structures utilisant le fractionnement du bus continu. Toutes ces structures ont des propriétés et applications différentes, même si certaines structures ont des propriétés communes. Il est aussi possible de créer de nouvelles structures en mixant les différentes structures de bases des différentes familles de convertisseurs multiniveaux ou en assemblant les structures de base de la conversion statique. Même si l’utilisation de structure de conversion multiniveaux permet de convertir à forte puissance, celle-ci n’est pas toujours aisée. En effet l’augmentation du nombre de niveaux ou de la tension d’entrée implique également une augmentation du nombre de composants semiconducteurs. Ceci peut être un frein à l’utilisation de convertisseur multiniveaux. Pour cela une nouvelle structure utilisant des composants partagés entre les différentes phases est proposée afin de limiter leur nombre. Un autre problème important lié aux convertisseurs multiniveaux est l’équilibrage des tensions des condensateurs du bus continu si celui-ci est composé de plus de deux condensateurs mis en série. Pour cela plusieurs solutions sont possibles : soit en utilisant une commande spécifique utilisant la modulation vectorielle, soit en utilisant des structures auxiliaires qui ont pour but d’équilibrer les différentes tensions des condensateurs. Dans une dernière partie ont été proposées de nouvelles structures qui permettent à la fois d’augmenter le courant de sortie et la tension en entrée en utilisant les principes des structures de base des convertisseurs multicellulaires série et parallèle. De plus, ces structures ont des propriétés intéressantes sur les formes d’ondes de sortie. De ces structures a été conçu un prototype permettant de valider les résultats de simulation. Une commande numérique implantée sur FPGA a été réalisée et a permis d’avoir des résultats expérimentaux intéressants. / This PhD Thesis deals with the study of new multilevel structures. At the beginning of this work, a new methodology to create new multilevel structures has been conceived. To evaluate the performances of these structures, there are many possibilities: number of output voltage levels, number of components, and the quality of the converters’ output waveforms. The list of criteria is not exhaustive. One technique to obtain an output multilevel waveform is to split the DC link in several capacitors. There is a limitation since putting more than two capacitors in serial connection leads to an unbalancing of these voltage capacitors. Several solutions are possible to balance these voltages. The first one uses the control of the structure in a three phase application, using a space vector modulation and minimizing the energy stored in the DC link. The second solution consists in using auxiliary circuits, which realize an energy transfer between one capacitor to another through an inductor. The drawback of this method is the high number of components. This problem can be reduced sharing some components between the three phases of the converter. The third part of this study is related to multicell converters, structures with very interesting good properties. New converter structures mix serial and parallel multicell converters, to obtain a hybrid converter with similar performances to the two basic converters. An experimental prototype was built to validate the results of the PhD. The digital control of this hybrid structure was made with a FPGA where two DSP processors were implemented. Electronique de puissance Equilibrage du bus continu Conversion statique Structure à partage de composants Convertisseurs multiniveaux Etude de nouvelles structures Contrôle numérique par FPGA Power Electronic Active Control of the DC link High Power Static Conversion Shared Components topologies Multilevel Converters Hybrid Multicell Converter Study of new topologies Digital Implementation (FPGA)
6	Energy-aware scheduling : complexity and algorithms / Ordonnancement sous contrainte d'énergie : complexité et algorithmes Renaud-Goud, Paul 05 July 2012 (has links) Dans cette thèse, nous nous sommes intéressés à des problèmes d'ordonnancement sous contrainte d'énergie, puisque la réduction de l'énergie est devenue une nécessité, tant sur le plan économique qu'écologique. Dans le premier chapitre, nous exhibons des bornes strictes sur l'énergie d'un algorithme classique qui minimise le temps d'exécution de tâches indépendantes. Dans le second chapitre, nous ordonnançons plusieurs applications chaînées de type « streaming », et nous étudions des problèmes contraignant l'énergie, la période et la latence. Nous effectuons une étude de complexité exhaustive, et décrivons les performances de nouvelles heuristiques. Dans le troisième chapitre, nous étudions le problème de placement de répliques dans un réseau arborescent. Nous nous plaçons dans un cadre dynamique, et nous bornons à minimiser l'énergie. Après une étude de complexité, nous confirmons la qualité de nos heuristiques grâce à un jeu complet de simulations. Dans le quatrième chapitre, nous revenons aux applications « streaming », mais sous forme de graphes série-parallèles, et nous tentons de les placer sur un processeur multi-cœur. La découverte d'un algorithme polynomial sur un problème simple nous permet la conception d'heuristiques sur le problème le plus général dont nous avons établi la NP-complétude. Dans le cinquième chapitre, nous étudions des bornes énergétiques de politiques de routage dans des processeurs multi-cœurs, en comparaison avec le routage classique XY, et développons de nouvheuristiques de routage. Dans le dernier chapitre, nous étudions expérimentalement le placement d'applications sous forme de DAG sur des machines réelles. / In this thesis we have tackled a few scheduling problems under energy constraint, since the energy issue is becoming crucial, for both economical and environmental reasons. In the first chapter, we exhibit tight bounds on the energy metric of a classical algorithm that minimizes the makespan of independent tasks. In the second chapter, we schedule several independent but concurrent pipelined applications and address problems combining multiple criteria, which are period, latency and energy. We perform an exhaustive complexity study and describe the performance of new heuristics. In the third chapter, we study the replica placement problem in a tree network. We try to minimize the energy consumption in a dynamic frame. After a complexity study, we confirm the quality of our heuristics through a complete set of simulations. In the fourth chapter, we come back to streaming applications, but in the form of series-parallel graphs, and try to map them onto a chip multiprocessor. The design of a polynomial algorithm on a simple problem allows us to derive heuristics on the most general problem, whose NP-completeness has been proven. In the fifth chapter, we study energy bounds of different routing policies in chip multiprocessors, compared to the classical XY routing, and develop new routing heuristics. In the last chapter, we compare the performance of different algorithms of the literature that tackle the problem of mapping DAG applications to minimize the energy consumption. Minimisation d'énergie Puissance Ordonnancement Complexité Heuristique Algorithmes optimaux Algorithme glouton Travaux indépendants Processeurs parallèles Placement Applications concurrentes Plate-forme hétérogène Partage de ressources Énergie Latence Période Placement de répliques Réseau arborescent Stratégies de mise à jour Algorithme de programmation dynamique Graphe série-parallèle Routage Multiprocesseur Manhattan Chemin unique Chemin multiples DAG Energy minimization Power Scheduling Complexity Makespan Heuristics Optimal algorithms Greedy algorithm Independent jobs Parallel processors Mapping Concurrent streaming applications Heterogeneous platforms Resource sharing Energy Latency Period Workflow Replica placement Tree networks Update strategies Dynamic programming algorithms Series-parallel graph Routing Chip multiprocesseur Manhattan Single path Multiple paths Slack reclamation DAG

1

Page generated in 0.0534 seconds