Spelling suggestions: "subject:"parallèle distribués"" "subject:"parrallèle distribués""
41 |
PaVo Un tri parallèle adaptatifDurand, Marie 25 October 2013 (has links) (PDF)
Les joueurs exigeants acquièrent dès que possible une carte graphique capable de satisfaire leur soif d'immersion dans des jeux dont la précision, le réalisme et l'interactivité redoublent d'intensité au fil du temps. Depuis l'avènement des cartes graphiques dédiées au calcul généraliste, ils n'en sont plus les seuls clients. Dans un premier temps, nous analysons l'apport de ces architectures parallèles spécifiques pour des simulations physiques à grande échelle. Cette étude nous permet de mettre en avant un goulot d'étranglement en particulier limitant la performance des simulations. Partons d'un cas typique : les fissures d'une structure complexe de type barrage en béton armé peuvent être modélisées par un ensemble de particules. La cohésion de la matière ainsi simulée est assurée par les interactions entre elles. Chaque particule est représentée en mémoire par un ensemble de paramètres physiques à consulter systématiquement pour tout calcul de forces entre deux particules. Ainsi, pour que les calculs soient rapides, les données de particules proches dans l'espace doivent être proches en mémoire. Dans le cas contraire, le nombre de défauts de cache augmente et la limite de bande passante de la mémoire peut être atteinte, particulièrement en parallèle, bornant les performances. L'enjeu est de maintenir l'organisation des données en mémoire tout au long de la simulation malgré les mouvements des particules. Les algorithmes de tri standard ne sont pas adaptés car ils trient systématiquement tous les éléments. De plus, ils travaillent sur des structures denses ce qui implique de nombreux déplacements de données en mémoire. Nous proposons PaVo, un algorithme de tri dit adaptatif, c'est-à-dire qu'il sait tirer parti de l'ordre pré-existant dans une séquence. De plus, PaVo maintient des trous dans la structure, répartis de manière à réduire le nombre de déplacements mémoires nécessaires. Nous présentons une généreuse étude expérimentale et comparons les résultats obtenus à plusieurs tris renommés. La diminution des accès à la mémoire a encore plus d'importance pour des simulations à grande échelles sur des architectures parallèles. Nous détaillons une version parallèle de PaVo et évaluons son intérêt. Pour tenir compte de l'irrégularité des applications, la charge de travail est équilibrée dynamiquement par vol de travail. Nous proposons de distribuer automatiquement les données en mémoire de manière à profiter des architectures hiérarchiques. Les tâches sont pré-assignées aux cœurs pour utiliser cette distribution et nous adaptons le moteur de vol pour favoriser des vols de tâches concernant des données proches en mémoire.
|
42 |
Algorithms for Deterministic Parallel Graph ExplorationPajak, Dominik 13 June 2014 (has links) (PDF)
Nous étudions dans cette thèse le problème de l'exploration parallèle d'un graphe à l'aide des multiples, synchronisés et mobiles agents. Chaque agent est une entité individuelle qui peut, indépendamment des autres agents, visitez les sommets du graphe ou parcourir ses arêtes. Le but de ensemble des agents est de visiter tous les sommets de graphe. Nous étudions d'abord l'exploration du graphe dans un modèle où chaque agent est équipé de mémoire interne, mais les nœuds n'ont pas de mémoire. Dans ce modèle les agents sont autorisés à communiquer entre eux en échangeant des messages. Nous présentons des algorithmes qui s'exécutent dans un minimum de temps possible pour polynomiale nombre d'agents (polynomiale en nombre de sommets du graphe). Nous étudions aussi quelle est l'impacte de différent méthodes des communications. Nous étudions des algorithmes où les agents peuvent se communiquer à distance arbitraire, mais aussi où communication est possible seulement entre les agents situés dans le même sommet. Dans les deux cas nous présentons des algorithmes efficaces. Nous avons aussi obtenu des limites inférieures qui correspondent bien à la performance des algorithmes. Nous considérons également l'exploration de graphe en supposant que les mouvements des agents sont déterminés par le soi-disant rotor-router mécanisme. Du point de vue d'un sommet fixé, le rotor- router envoie des agents qui visitent les sommet voisins dans un mode round-robin. Nous étudions l'accélération défini comme la proportion entre le pire des cas de l'exploration d'un agent unique et des plusieurs agents. Pour générales graphes, nous montrerons que le gain de vitesse en cas de multi-agent rotor-router est toujours entre fonction logarithmique et linéaire du nombre d'agents. Nous présentons également des résultats optimaux sur l'accélération de multi-agent rotor-router pour cycles, expanseurs, graphes aléatoires, cliques, tores de dimension fixé et une analyse presque optimale pour hypercubes. Finalement nous considérons l'exploration sans collision, où chaque agent doit explorer le graphe de manière indépendante avec la contrainte supplémentaire que deux agents ne peuvent pas occuper le même sommet. Dans le cas où les agents sont donnés le plan de graphe, on présente un algorithme optimal pour les arbres et un algorithme asymptotiquement optimal pour générales graphes. Nous présentons aussi des algorithmes dans le cas de l'exploration sans collision des arbres et des générales graphes dans la situation où les agents ne connaissent pas le graphe. Nous fermons la thèse par des observations finales et une discussion de problèmes ouverts liés dans le domaine de l'exploration des graphes.
|
43 |
Verification of communicating recursive programs via split-widthCyriac, Aiswarya, Cyriac, Aiswarya 28 January 2014 (has links) (PDF)
This thesis investigates automata-theoretic techniques for the verification of physically distributed machines communicating via unbounded reliable channels. Each of these machines may run several recursive programs (multi-threading). A recursive program may also use several unbounded stack and queue data-structures for its local-computation needs. Such real-world systems are so powerful that all verification problems become undecidable. We introduce and study a new parameter called split-width for the under-approximate analysis of such systems. Split-width is the minimum number of splits required in the behaviour graphs to obtain disjoint parts which can be reasoned about independently. Thus it provides a divide-and-conquer approach for their analysis. With the parameter split-width, we obtain optimal decision procedures for various verification problems on these systems like reachability, inclusion, etc. and also for satisfiability and model checking against various logical formalisms such as monadic second-order logic, propositional dynamic logic and temporal logics. It is shown that behaviours of a system have bounded split-width if and only if they have bounded clique-width. Thus, by Courcelle's results on uniformly bounded-degree graphs, split-width is not only sufficient but also necessary to get decidability for MSO satisfiability checking. We then study the feasibility of distributed controllers for our generic distributed systems. We propose several controllers, some finite state and some deterministic, which ensure that the behaviours of the system have bounded split-width. Such a distributedly controlled system yields decidability for the various verification problems by inheriting the optimal decision procedures for split-width. These also extend or complement many known decidable subclasses of systems studied previously.
|
44 |
Allocation de ressources et ordonnancement multi-utilisateurs : une approche basée sur l'équitéMedernach, Emmanuel 06 May 2011 (has links) (PDF)
Les grilles de calcul et le "cloud computing" permettent de distribuer un ensemble de ressources informatiques, telles que du stockage ou du temps de calcul, à un ensemble d'utilisateurs en fonction de leurs demandes en donnant l'illusion de ressources infinies. Cependant, lorsque l'ensemble de ces ressources est insuffisant pour satisfaire les exigences des utilisateurs, des conflits d'intérêts surgissent. Ainsi, un libre accès à des ressources limitées peut entraîner une utilisation inefficace qui pénalise l'ensemble des participants. Dans de tels environnements, il devient nécessaire d'établir des procédures d'arbitrage afin de résoudre ces conflits en garantissant une distribution équitable aux différents utilisateurs. Nous présentons une nouvelle classe de problèmes : celle des ordonnancements multi-utilisateurs. Cette thèse aborde la notion d'équité au travers de problèmes d'allocation de ressources sous incertitudes et d'ordonnancement de tâches périodiques.
|
45 |
Autonomic and Energy-Efficient Management of Large-Scale Virtualized Data CentersFeller, Eugen 17 December 2012 (has links) (PDF)
Large-scale virtualized data centers require cloud providers to implement scalable, autonomic, and energy-efficient cloud management systems. To address these challenges this thesis provides four main contributions. The first one proposes Snooze, a novel Infrastructure-as-a-Service (IaaS) cloud management system, which is designed to scale across many thousands of servers and virtual machines (VMs) while being easy to configure, highly available, and energy efficient. For scalability, Snooze performs distributed VM management based on a hierarchical architecture. To support ease of configuration and high availability Snooze implements self-configuring and self-healing features. Finally, for energy efficiency, Snooze integrates a holistic energy management approach via VM resource (i.e. CPU, memory, network) utilization monitoring, underload/overload detection and mitigation, VM consolidation (by implementing a modified version of the Sercon algorithm), and power management to transition idle servers into a power saving mode. A highly modular Snooze prototype was developed and extensively evaluated on the Grid'5000 testbed using realistic applications. Results show that: (i) distributed VM management does not impact submission time; (ii) fault tolerance mechanisms do not impact application performance and (iii) the system scales well with an increasing number of resources thus making it suitable for managing large-scale data centers. We also show that the system is able to dynamically scale the data center energy consumption with its utilization thus allowing it to conserve substantial power amounts with only limited impact on application performance. Snooze is an open-source software under the GPLv2 license. The second contribution is a novel VM placement algorithm based on the Ant Colony Optimization (ACO) meta-heuristic. ACO is interesting for VM placement due to its polynomial worst-case time complexity, close to optimal solutions and ease of parallelization. Simulation results show that while the scalability of the current algorithm implementation is limited to a smaller number of servers and VMs, the algorithm outperforms the evaluated First-Fit Decreasing greedy approach in terms of the number of required servers and computes close to optimal solutions. In order to enable scalable VM consolidation, this thesis makes two further contributions: (i) an ACO-based consolidation algorithm; (ii) a fully decentralized consolidation system based on an unstructured peer-to-peer network. The key idea is to apply consolidation only in small, randomly formed neighbourhoods of servers. We evaluated our approach by emulation on the Grid'5000 testbed using two state-of-the-art consolidation algorithms (i.e. Sercon and V-MAN) and our ACO-based consolidation algorithm. Results show our system to be scalable as well as to achieve a data center utilization close to the one obtained by executing a centralized consolidation algorithm.
|
46 |
Calculs de processus: observations et inspectionsHirschkoff, Daniel 08 December 2009 (has links) (PDF)
Le document traite du raisonnement sur les processus. Les chapitres principaux sont: - Équivalences comportementales : caractérisation logique, axiomatisation et congruence - Inspections et équivalences intensionnelles - Calculs avec localités
|
47 |
Concurrency in Interaction Nets and Graph RewritingDorman, Andrei 20 June 2013 (has links) (PDF)
Ce travail est une étude approfondie de la concurrence dans les extensions non-déterministes des réseaux d'interaction de Lafont (langage graphique qui représente, lui, le calcul fonctionnel). Ces extensions sont de trois sortes : les réseaux multirègles, multiports et multifils, et leurs combinaisons donnent ainsi sept types de réseaux. Un premier travail consiste à déterminer une bonne sémantique pour pouvoir comparer ces extensions. On cherche à définir un sémantique opérationnelle structurelle sur les réseaux en se basant sur des technique connues de réécriture des graphes, plus particulièrement celle de " double-pushout with borrowed contexts ". Nous définissons à partir de cette méthode un système d'étiquetage des transitions donné par des règles de dérivations dans le style des langages de processus qui sont le paradigme principal pour étudier les systèmes de calcul concurrents. Nous définissons de plus une sémantique observationnelle sur les réseaux basée sur une notion paramétrique de barbe, qui permet enfin de donner avec précision une notion de traduction entre systèmes. On considère qu'une extension est plus expressive qu'une autre si tout langage de la seconde peut être traduit dans un langage de la première. Ceci nous permet de classer l'ensemble des extensions de manière hiérarchique en trois groupe selon la possibilité de traduire un système de réseau dans un autre. Du plus fort au plus faible : les réseaux contenant des multiports ; ensuite ceux contenant des multifils; enfin les réseaux multirègles. Ceci nous permet de donner un langage universel pour les réseaux dont l'étude donne un point de vue neuf sur les briques fondamentales de la concurrence.
|
48 |
Contributions à la flexibilité et à l'efficacité énergétique des systèmes distribués à grande échelleLefevre, Laurent 14 November 2013 (has links) (PDF)
Les systèmes distribués à grande échelle (Datacenters, Grilles, Clouds, Réseaux) sont des acteurs incontournables dans notre société de communication et d'échanges électroniques. Ces infrastructures doivent faire face à de nombreux challenges qui limitent leur déploiement : sécurité, qualité de service, extensibilité, programmabilité, consommation électrique... Cette habilitation retrace les travaux menés sur les domaines de la flexibilité des grands systèmes en se focalisant sur la mise en oeuvre de solutions dynamiques de déploiement de services afin d'augmenter la valeur ajoutée des infrastructures existantes et de proposer de nouveaux services à valeur ajoutée. Cette habilitation se penche aussi sur la consommation électrique de ces infrastructures et les différents moyens d'améliorer leur efficacité énergétique afin de les placer dans une perspective de développement durable.
|
49 |
Détection de Collision pour Environnements Large Échelle : Modèle Unifié et Adaptatif pour Architectures Multi-coeur et Multi-GPUAvril, Quentin 16 September 2011 (has links) (PDF)
Les environnements de réalité virtuelle devenant de plus en plus complexes et de très grandes dimensions, un niveau d'interaction temps-réel devient impossible à garantir. En effet, de par leur complexité, due à une géométrie détaillée et aux propriétés physiques spécifiques, ces environnements large échelle engendrent un goulet d'étranglement calculatoire critique sur les algorithmes de simulation physique. Nous avons focalisé nos travaux sur la première étape de ces algorithmes qui concerne la détection de collision, car les problématiques font partie intégrante de ce goulet d'étranglement et leur complexité peut parfois se révéler quadratique dans certaines situations. Le profond bouleversement que subissent les architectures machines depuis quelques années ouvre une nouvelle voie pour réduire le goulet d'étranglement. La multiplication du nombre de cœurs offre ainsi la possibilité d'exécuter ces algorithmes en parallèle sur un même processeur. Dans le même temps, les cartes graphiques sont passées d'un statut de simple périphérique d'affichage graphique à celui de supercalculateur. Elles jouissent désormais d'une attention toute particulière de la part de la communauté traitant de la simulation physique. Afin de passer au large échelle et d'être générique sur la machine d'exécution, nous avons proposé des modèles unifiés et adaptatifs de correspondance entre les algorithmes de détection de collision et les architectures machines de type multi-coeur et multi-GPU. Nous avons ainsi défini des solutions innovantes et performantes permettant de réduire significativement le temps de calcul au sein d'environnements large échelle tout en assurant la pérennité des résultats. Nos modèles couvrent l'intégralité du pipeline de détection de collision en se focalisant aussi bien sur des algorithmes de bas ou de haut niveau. Nos modèles multi-coeur, GPU et multi-GPU allient différentes techniques de subdivision spatiale à des algorithmes basés topologie ainsi que des techniques d'équilibrage de charge basées sur le vol de données. Notre solution hybride permet d'accroitre l'espace et le temps de calcul ainsi que le passage au large échelle. L'association de ces nouveaux algorithmes nous a permis de concevoir deux modèles d'adaptation algorithmique dynamique basés, ou non, sur des scénarios de pré-calcul hors-ligne. Enfin, il nous est apparu indispensable d'ajouter au pipeline de détection de collision une nouvelle dimension révélant la prise en compte des architectures pour une exécution optimale. Grâce à ce formalisme, nous avons proposé un nouveau pipeline de détection de collision offrant une granularité de parallélisme sur processeurs multi-coeur. Il permet une exécution simultanée des différentes étapes du pipeline ainsi qu'un parallélisme interne à chacune de ces étapes.
|
50 |
Déterminisme et Confluence dans des systèmes concurrents et synchronesDogguy, Mehdi 27 January 2012 (has links) (PDF)
Dans cette thèse, nous étudions les notions de déterminisme et de confluence dans des systèmes concurrents et synchrones. Ces derniers sont des variantes du pi-calcul qui ont été étendues avec une notion de temps. Le premier modèle étudié, le S-pi-calcul, est une extension du modèle SL où la réaction à l'absence d'un signal se fait à la fin de l'instant et où les signaux sont considérés comme des valeurs de première classe. Ce modèle utilise les signaux comme mécanisme de communication de base. Dans le cadre du S-pi-calcul, nous avons cherché à développer une théorie compositionnelle de l'équivalence des programmes basée sur la notion de bisimulation. Ensuite, nous avons conçu un système de types en se basant sur une notion d'usage affine pour les signaux que nous avons introduit. Dans ce système, nous avons montré que tout programme typable est déterministe. Le second modèle, TAPIS, est une autre variante du pi-calcul où les canaux sont utilisés pour la communication. Dans ce cadre, nous avons adapté la théorie des types précedemment introduite pour le S-pi-calcul au cas des canaux et montré que les programmes typables sont confluents. Le système développé dans ce contexte ainsi que la preuve du lemme de préservation du typage ont été formalisés dans Coq.
|
Page generated in 0.0544 seconds