141 |
Parallélisme et équilibrage de charges dans le traitement de la jointure sur des architectures distribuées.Al Hajj Hassan, Mohamad 16 December 2009 (has links) (PDF)
L'émergence des applications de bases de données dans les domaines tels que le data warehousing, le data mining et l'aide à la décision qui font généralement appel à de très grands volumes de données rend la parallélisation des algorithmes des jointures nécessaire pour avoir un temps de réponse acceptable. Une accélération linéaire est l'objectif principal des algorithmes parallèles, cependant dans les applications réelles, elle est difficilement atteignable : ceci est dû généralement d'une part aux coûts de communications inhérents aux systèmes multi-processeur et d'autre part au déséquilibre des charges des différents processeurs. En plus, dans un environnement hétérogène multi-utilisateur, la charge des différents processeurs peut varier de manière dynamique et imprévisible. Dans le cadre de cette thèse, nous nous intéressons au traitement de la jointure et de la multi-jointure sur les architectures distribuées hétérogènes, les grilles de calcul et les systèmes de fichiers distribués. Nous avons proposé une variété d'algorithmes, basés sur l'utilisation des histogrammes distribués, pour traiter de manière efficace le déséquilibre des données, tout en garantissant un équilibrage presque parfait de la charge des différents processeurs même dans un environnement hétérogène et multi-utilisateur. Ces algorithmes sont basés sur une approche dynamique de redistribution des données permettant de réduire les coûts de communication à un minimum tout en traitant de manière très efficace le problème de déséquilibre des valeurs de l'attribut de jointure. L'analyse de complexité de nos algorithmes et les résultats expérimentaux obtenus montrent que ces algorithmes possèdent une accélération presque linéaire.
|
142 |
Supervisory control of infinite state systems under partial observation / Contrôle supervisé des systèmes à états infinis sous observation partielleKalyon, Gabriel 26 November 2010 (has links)
A discrete event system is a system whose state space is given by a discrete set and whose state transition mechanism is event-driven i.e., its state evolution depends only on the occurrence of discrete events over the time. These systems are used in many fields of application (telecommunication networks, aeronautics, aerospace,...). The validity of these systems is then an important issue and to ensure it we can use supervisory control methods. These methods consist in imposing a given specification on a system by means of a controller which runs in parallel with the original system and which restricts its behavior. In this thesis, we develop supervisory control methods where the system can have an infinite state space and the controller has a partial observation of the system (this implies that the controller must define its control policy from an imperfect knowledge of the system). Unfortunately, this problem is generally undecidable. To overcome this negative result, we use abstract interpretation techniques which ensure the termination of our algorithms by overapproximating, however, some computations. The aim of this thesis is to provide the most complete contribution it is possible to bring to this topic. Hence, we consider more and more realistic problems. More precisely, we start our work by considering a centralized framework (i.e., the system is controlled by a single controller) and by synthesizing memoryless controllers (i.e., controllers that define their control policy from the current observation received from the system). Next, to obtain better solutions, we consider the synthesis of controllers that record a part or the whole of the execution of the system and use this information to define the control policy. Unfortunately, these methods cannot be used to control an interesting class of systems: the distributed systems. We have then defined methods that allow to control distributed systems with synchronous communications (decentralized and modular methods) and with asynchronous communications (distributed method). Moreover, we have implemented some of our algorithms to experimentally evaluate the quality of the synthesized controllers. /
Un système à événements discrets est un système dont l'espace d'états est un ensemble discret et dont l'évolution de l'état courant dépend de l'occurrence d'événements discrets à travers le temps. Ces systèmes sont présents dans de nombreux domaines critiques tels les réseaux de communications, l'aéronautique, l'aérospatiale... La validité de ces systèmes est dès lors une question importante et une manière de l'assurer est d'utiliser des méthodes de contrôle supervisé. Ces méthodes associent au système un dispositif, appelé contrôleur, qui s'exécute en parrallèle et qui restreint le comportement du système de manière à empêcher qu'un comportement erroné ne se produise. Dans cette thèse, on s'intéresse au développement de méthodes de contrôle supervisé où le système peut avoir un espace d'états infini et où les contrôleurs ne sont pas toujours capables d'observer parfaitement le système; ce qui implique qu'ils doivent définir leur politique de contrôle à partir d'une connaissance imparfaite du système. Malheureusement, ce problème est généralement indécidable. Pour surmonter cette difficulté, nous utilisons alors des techniques d'interprétation abstraite qui assurent la terminaison de nos algorithmes au prix de certaines sur-approximations dans les calculs. Le but de notre thèse est de fournir la contribution la plus complète possible dans ce domaine et nous considèrons pour cela des problèmes de plus en plus réalistes. Plus précisement, nous avons commencé notre travail en définissant une méthode centralisée où le système est contrôlé par un seul contrôleur qui définit sa politique de contrôle à partir de la dernière information reçue du système. Ensuite, pour obtenir de meilleures solutions, nous avons défini des contrôleurs qui retiennent une partie ou la totalité de l'exécution du système et qui définissent leur politique de contrôle à partir de cette information. Malheureusement, ces méthodes ne peuvent pas être utilisées pour contrôler une classe intéressante de systèmes: les sytèmes distribués. Nous avons alors défini des méthodes permettant de contrôler des systèmes distribués dont les communications sont synchrones (méthodes décentralisées et modulaires) et asynchrones (méthodes distribuées). De plus, nous avons implémenté certains de nos algorithmes pour évaluer expérimentalement la qualité des contrôleurs qu'ils synthétisent.
|
143 |
Optimisation énergétique des transmissions coopératives pour les réseaux de capteurs sans filTran, Le-Quang-Vinh 06 December 2012 (has links) (PDF)
Dans cette thèse, nous avons proposé un nouveau schéma de transmission basé sur l'échange de données entre relais (fDSTC). Via des simulations numériques et des analyses mathématiques, le protocole fDSTC est comparé en termes de taux d'erreur, de probabilité de coupure, de diversité et d'efficacité énergétique avec les schémas plus classiques de codes spatio-temporel distribués (cDSTC), en utilisant des relais non-régénératif (NR-relais) et des relais régénératif (R-relais). De plus, le protocole fDSTC est exploité dans un système multi-antennes et son efficacité énergétique est montrée en utilisant un modèle d'énergie typique largement utilisé dans la littérature, ainsi qu' un modèle réaliste basé sur la plate-forme de réseaux de capteurs PowWow. Bien que peu considéré dans la littérature sur les techniques de relais coopératifs , le protocole MAC a une grande influence sur la consommation d'énergie totale des réseaux. Cela conduit à une grande motivation pour concevoir un protocole MAC coopératif, MAC-RIC, en combinant les techniques d'échantillonnage de préambule et relais coopératifs. Les résultats analytiques confirment encore l'intérêt d'utiliser les techniques de relais coopératif, mais leur efficacité énergétique peut être affectée par les charges de trafic et la latence désirée.
|
144 |
Un système d'aide à la régulation d'un réseau de transport multimodal perturbé : réponse au problème de congestionMejri, Hinda 22 June 2012 (has links) (PDF)
Les réseaux de transport se sont amplifiés par l'accroissement du nombre des véhicules et des stations ainsi que l'apparition de nouvelles notions essentiellement la multimodalité et l'intermodalité. Ainsi, la tâche de gestion des réseaux de transport collectif est devenue très complexe et difficile pour les régulateurs. Pour faire face à ces difficultés, on note le développement des systèmes d'aide à la décision comme solution efficace de régulation de la circulation. Ils permettent de transmettre en temps réel les informations concernant le trafic sur les réseaux de transport.Notre travail se base sur la conception d'un système de régulation des réseaux de transport multimodal. Il peut se révéler comme un outil primordial pour apporter des solutions efficaces et en temps réel à la problématique de la congestion routière. Il peut communiquer l'information nécessaire à l'usager afin de prendre sa décision de déplacement avec ou sans sa voiture. Le système proposé est une approche hybride entre une modélisation par graphes du réseau et un système multi-agents. Ceci sera appuyé par une approche évolutionniste pour la génération d'une solution de régulation optimale. Ce choix est justifié par le caractère ouvert, distribué et complexe des réseaux de transport multimodal.
|
145 |
Modèle hydrostatique pour les écoulements à surface libre tridimensionnels et schémas numériquesDecoene, Astrid 24 May 2006 (has links) (PDF)
Cette thèse a pour objectif l'approfondissement de l'étude des équations régissant les écoulements à surface libre en dimension trois.<br />Nous proposons d'une part une nouvelle formulation variationnelle du problème hydrostatique aboutissant à un problème semi-discretisé en temps bien posé. Nous en faisons l'analyse mathématique et nous montrons quelques résultats numériques obtenus après programmation de l'approximation de ce problème dans le logiciel Telemac-3D développé au Laboratoire National d'Hydraulique et Environnement (LNHE) d'edf.<br />D'autre part, nous étudions la réinterprétation dans le cadre ALE de la méthode de discrétisation verticale de domaines tridimensionnels appelée transformation sigma, et nous en proposons une généralisation permettant d'améliorer la représentation des stratifications dans un écoulement<br />Finalement, nous présentons un schéma ALE-MURD conservatif pour la résolution des équations de convection linéaires posées sur un domaine mobile. Une condition particulière doit être vérifiée afin que le schéma soit conservatif lorsque le domain bouge effectivement. Nous montrons comment assurer cette contrainte dans le cas particulier où le domaine est tridimensionnel et ne bouge que selon la verticale. Ce résultat est illustré dans le cadre des écoulements à surface libre en dimension trois.
|
146 |
Réduction des systèmes à paramètres distribués. Application à la commande optimale robuste des canaux d'irrigationOuarit, Hicham 07 May 2004 (has links) (PDF)
Ce travail concerne la commande optimale robuste des systèmes hydrauliques à surface libre<br />(canaux d'irrigation). Nous nous sommes intéressés à deux approches de synthèse de<br />commande optimale. La première approche consiste à synthétiser une loi de commande<br />optimale LQG /H2-LTR (de dimension finie) avec pondérations fréquentielles robuste vis-àvis<br />des erreurs engendrées par la réduction à un modèle de dimension finie des équations de<br />Saint Venant. Le modèle réduit est obtenu par collocation orthogonale à partir du modèle<br />linéarisé tangent de Saint Venant. Un observateur est également proposé qui permet de<br />reconstruire l'état du système à partir des seuls états mesurés à l'amont et à l'aval de chaque<br />bief. Le régulateur optimal robuste et l'observateur ont été testés sur différents modèles de<br />référence ainsi que sur un micro-canal expérimental réel. Ils sont comparés aux résultats<br />obtenus par d'autres méthodes de régulation connues. La seconde approche de synthèse<br />consiste à faire l'approximation en dimension finie d'une loi de commande (de dimension<br />infinie) obtenue à partir des équations de Saint Venant linéarisées mais non réduites. Nous<br />présentons dans ce rapport des résultats liés à l'analyse et à la synthèse du régulateur optimal<br />LQ en dimension infinie appliquée aux équations de Saint Venant. Nous décrivons ensuite le<br />moyen d'obtenir une approximation en dimension finie du régulateur LQ sur la base de<br />l'équation de Riccati d'opérateurs associée au problème.
|
147 |
Conception et technologie de diodes laser GaAlAs/GaAs émettant par la surface au moyen de réflecteurs de Bragg distribuésArguel, Philippe 13 December 1995 (has links) (PDF)
Les travaux reportés dans ce mémoire concernent la conception et la réalisation technologique de diodes laser à émission surfacique de type DBR (Distributed Bragg Reflector), dans la filière GaAlAs/GaAs. Dans une première partie, l'étude porte sur la modélisation et la conception de diodes laser à réflecteurs de Bragg distribués du second ordre. Il est présenté un modèle global qui regroupe, de façon consistante, les propriétés spectrales de la cavité DBR et celles de la structure à puits quantique, notamment en ce qui concerne le gain dans les régions pompées et l'absorption dans les régions non pompées. Ce modèle est mis en œuvre pour analyser, de façon systématique, l'influence des paramètres géométriques du composant sur ses performances en courant de seuil, rendement différentiel, diagramme de rayonnement et spectre d'émission. On en déduit le choix des paramètres permettant un fonctionnement optimal et on démontre que, compte tenu de la position aléatoire de la première dent des réseaux de Bragg par rapport à la zone de gain, il est impossible de prévoir, dans l'état de l'art actuel, la valeur du rendement différentiel ou la forme du diagramme de rayonnement. La seconde partie de l'étude concerne la définition d'un processus de fabrication, la réalisation technologique et la caractérisation de diodes laser DBR à émission surfacique. Il est présenté une étude détaillée de la mise en œuvre d'un banc d'insolation holographique destiné à la réalisation de réseaux diffractants sur semiconducteur. On établit ensuite un procédé complet d'élaboration de la diode DBR qui tient compte à la fois des critères de conception et des conditions particulières imposées par le principe de la structure. Les diodes laser réalisées présentent une émission surfacique selon des performances qui démontrent à la fois la validité de l'approche théorique et la qualité du procédé d'élaboration proposé
|
148 |
Architecture de transport multimedia à connexions d'ordre partielChassot, Christophe 21 December 1995 (has links) (PDF)
Les travaux présentés dans ce mémoire ont pour cadre la recherche de nouveaux services et protocoles de Transport, aptes à supporter le transfert de données multimédia en tenant compte des exigences applicatives en termes de hauts débits et de synchronisation. L'approche proposée repose sur la définition et le développement d'un nouveau concept: la connexion d'ordre partiel (POC - Partial Order Connection), établissant un lien conceptuel entre les modes de service/protocole orientés-connexion tels que TCP, et sans connexion tels que UDP. Une POC est une connexion de bout en bout permettant de définir et de mettre en œuvre tous les services et protocoles d'ordre partiel entre deux entités communicantes ; dans une POC, la délivrance des données à l'utilisateur récepteur peut être effectuée dans un ordre différent de l'ordre de soumission de ces données par l'utilisateur émetteur: la différence (acceptable) entre ces deux ordres résulte de la définition, par l'utilisateur, d'un ordre partiel de délivrance lors de l'ouverture de la connexion. Une formalisation des mécanismes correspondants est proposée au moyen de la technique de description formelle Estelle. Les caractéristiques intrinsèques des différents média d'un flux multimédia ont conduit ces dernières années au développement d'architectures de communication intégrant la prise en compte des contraintes applicatives à différents niveaux conceptuels, et notamment au niveau Transport du modèle OSI ; à partir d'une modélisation de ces contraintes utilisant le formalisme des réseaux de Petri (le modèle TSPN), l'auteur propose d'intégrer le concept de POC dans une architecture de Transport multimédia autorisant une prise en compte globale des contraintes d'ordre et de fiabilité d'un flux multimédia. Les mécanismes de gestion de l'ordre et de la fiabilité qui sont proposés permettent de définir un service de Transport multimédia offrant une hypothèse nouvelle aux utilisateurs vis à vis de la problématique de la synchronisation. Une étude de la faisabilité d'un protocole multimédia d'ordre partiel à l'aide des procédures XTP est finalement présentée: elle conclut en la possibilité d'une telle réalisation
|
149 |
Une architecture parallèle distribuée et tolérante aux pannes pour le protocole interdomaine BGP au cœur de l’InternetHamzeh, Wissam 12 1900 (has links)
L’augmentation du nombre d’usagers de l’Internet a entraîné une croissance exponentielle dans les tables de routage. Cette taille prévoit l’atteinte d’un million de préfixes dans les prochaines années. De même, les routeurs au cœur de l’Internet peuvent facilement atteindre plusieurs centaines de connexions BGP simultanées avec des routeurs voisins. Dans une architecture classique des routeurs, le protocole BGP s’exécute comme une entité unique au sein du routeur. Cette architecture comporte deux inconvénients majeurs : l’extensibilité (scalabilité) et la fiabilité. D’un côté, la scalabilité de BGP est mesurable en termes de nombre de connexions et aussi par la taille maximale de la table de routage que l’interface de contrôle puisse supporter. De l’autre côté, la fiabilité est un sujet critique dans les routeurs au cœur de l’Internet. Si l’instance BGP s’arrête, toutes les connexions seront perdues et le nouvel état de la table de routage sera propagé tout au long de l’Internet dans un délai de convergence non trivial. Malgré la haute fiabilité des routeurs au cœur de l’Internet, leur résilience aux pannes est augmentée considérablement et celle-ci est implantée dans la majorité des cas via une redondance passive qui peut limiter la scalabilité du routeur. Dans cette thèse, on traite les deux inconvénients en proposant une nouvelle approche distribuée de BGP pour augmenter sa scalabilité ainsi que sa fiabilité sans changer la sémantique du protocole. L’architecture distribuée de BGP proposée dans la première contribution est faite pour satisfaire les deux contraintes : scalabilité et fiabilité. Ceci est accompli en exploitant adéquatement le parallélisme et la distribution des modules de BGP sur plusieurs cartes de contrôle. Dans cette contribution, les fonctionnalités de BGP sont divisées selon le paradigme « maître-esclave » et le RIB (Routing Information Base) est dupliqué sur plusieurs cartes de contrôle. Dans la deuxième contribution, on traite la tolérance aux pannes dans l’architecture élaborée dans la première contribution en proposant un mécanisme qui augmente la fiabilité. De plus, nous prouvons analytiquement dans cette contribution qu’en adoptant une telle architecture distribuée, la disponibilité de BGP sera augmentée considérablement versus une architecture monolithique. Dans la troisième contribution, on propose une méthode de partitionnement de la table de routage que nous avons appelé DRTP pour diviser la table de BGP sur plusieurs cartes de contrôle. Cette contribution vise à augmenter la scalabilité de la table de routage et la parallélisation de l’algorithme de recherche (Best Match Prefix) en partitionnant la table de routage sur plusieurs nœuds physiquement distribués. / The increasing number of end users has led to an exponential growth in the Internet routing table. The routing table is expected to reach a size of one million prefixes within the coming few years. Besides, current core routers may easily attain hundreds of connected BGP peers simultaneously. In classical monolithic architecture, the BGP protocol runs as a single entity inside the router. This architecture suffers from two drawbacks: scalability and reliability. BGP scalability can be measured in terms of the number of connected peers that can be handled and the size of the routing table. On the other hand, the reliability is a critical issue in core routers. If the BGP instance inside the router fails, all peers’ connections will shutdown and the new reachability state will be propagated across the Internet in a non trivial convergence delay. Although, in current core routers, the resiliency is increased considerably, it’s mainly implemented via a primary-backup redundancy scheme which limits the BGP scalability. In this thesis we address the two mentioned BGP drawbacks by proposing a novel distributed approach to increase both scalability and reliability of BGP without changing the semantic of the protocol. The BGP distributed architecture in the first paper is built to satisfy both requirements: scalability and reliability by adequately exploiting parallelism and module separation. In our model, BGP functionalities are split in a master-slave manner and the RIB (Routing Information Base) is replicated to multiple controller cards, to form a cluster of parallel computing entities. In the second paper, we address the fault tolerance of BGP within the distributed architecture presented in the first paper. We prove analytically that, by adopting the distributed architecture of BGP the availability of BGP will be increased considerably versus a monolithic architecture. In the third paper we propose a distributed parallel scheme called DRTP to partition the BGP routing table on multiple controller cards. DRTP aims at increasing the BGP scalability and the parallelization of the Best Match Prefix algorithm.
|
150 |
Modélisation et analyse des systèmes à paramètres distribués non linéaires par la méthode de Boltzmann sur réseau : application aux écoulements à surface libreAnda Ondo, Diemer 09 July 2013 (has links) (PDF)
Nous étudions dans cette thèse, composée de deux parties, la modélisation des écoulements en eaux peu profondes par la méthode de Boltzmann sur réseau et l'analyse des propriétés de commandabilité et d'observabilité des modèles obtenus. Dans la première partie, nous nous consacrons d'abord à la modélisation par la méthode de Boltzmann sur réseau des équations de Saint-Venant. En utilisant une linéarisation autour d'un profil d'équilibre, une représentation sous forme d'état des modèles de Boltzmann sur réseau est définie. Cette représentation incorpore les termes de force, et permet une définition complète des entrées (commandes) et des sorties (mesures). Nous représentons ensuite les phénomènes de sédimentation dans les écoulements en eaux peu profondes avec la méthode de Boltzmann sur réseau. Ce modèle défini en une dimension est validé numériquement en le comparant avec un modèle de volumes finis qui résout les équations de Saint-Venant-Exner. Le modèle LB défini est moins gourmand en temps de calcul et plus facile à manipuler que les modèles traditionnels. Dans la deuxième partie, nous traitons de l'analyse des propriétés de commandabilit é et d'observabilité des modèles LB obtenus. La première analyse est faite sur les critères algébriques de Kalmann et permet d'établir la non conservation des propriétés de commandabilité et d'observabilité lorsque l'ordre de réduction du système est augmenté. Une analyse plus approfondie basée sur la détermination les grammiens de commandabilit é et d'observabilité montre également que le constat reste valide pour les méthodes de discrétisation classique. La résolution des grammiens est faite avec des méthodes particulièrement adaptées aux structures creuses et de grande dimension que sont les matrices de la dynamique, de commande et/ou d'observation des modèles LB. Enfin, nous établissons que pour une commande aux frontières classique des canaux d'irrigation en débit et hauteur, la famille de systèmes des modèles LB d'ordre réduit n'est pas uniformément commandable alors qu'avec l'utilisation des variables de scattering comme variables de commande, cette famille devient uniformément commandable.
|
Page generated in 0.2388 seconds