• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • 1
  • Tagged with
  • 2
  • 2
  • 2
  • 2
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

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.
2

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.

Page generated in 0.0607 seconds