Techniques algébriques en calcul quantique.

  • By: Emmanuel Jeandel
  • Number: PhD2005-01
  • Date: Juillet 2005
  • Abstract:

    The main problem studied is the computation of the Zariski closure of algebraic groups and its applications on quantum computation. We give a polynomial time algorithm to decide whether a finitely generated subgroup of a given reductive group is Zariski-dense. A second algorithm, which computes precisely the Zariski-closure of a finitely generated group is given. These tools gives decidability results for several problems in quantum computing, mainly whether a set of gates is universal. We give also a separation between various models of quantum computing An other part of the thesis deals with finite automata. A new model of automata, topological automata, is defined. We then proved in a unified framework that all models of classical, probabilistic and quantum automata accept only regular languages with an isolated threshold. qsf.
  • Abstract (in french):

    Le principal problème étudié est le calcul de l'adhérence de Zariski de groupes algébriques, et leurs applications en calcul quantique. On donne ici un algorithme en temps polynomial qui décide si un sous-groupe finiment engendré d'un groupe reductif est dense dans ce groupe. On donne également un algorithme qui calcule précisément l'adhérence d'un groupe. Ces résultats sont utilisés afin de résoudre plusieurs problèmes en calcul quantique, en particulier liés aux circuits quantiques. Ainsi divers algorithmes qui décident si des jeux de portes sont universels, ou qui permettent de séparer les différentes notions d'universalité, sont donnés. Nous nous intéressons aussi ici aux automates finis. Nous introduisons ici un nouvel modèle, les automates topologiques, qui permet de généraliser les modèles existants. Nous montrons ainsi, dans un contexte unifié, que tous les modèles d'automates finis classiques, quantiques ou probabilistes ne reconnaissent que des langages rationnels par seuil isolé.
  • Keywords:

    Quantum computing, Algebraic groups, quantum automata, probabilistic automata.
  • Keywords (in french):

    Calcul quantique, groupes algébriques, automates quantiques, automates probabilistes.
  • Availability: Electronic copy only.
  • Size: 127p
  • Format: pdf
  • Get it

Réseaux rapides et stockage distribué dans les grappes de calculateurs : propositions pour une interaction efficace.

  • By: Brice Goglin
  • Number: PhD2005-02
  • Date: Octobre 2005
  • Abstract:

    This work aims at studying the exploitation of high-speed networks of clusters for distributed storage. Parallel applications running on clusters require both high-performance communications between nodes and efficient access to the storage system. Many studies on network technologies led to the design of dedicated architectures for clusters with very fast communications between computing nodes. Efficient distributed storage in clusters have been essentially developed by adding parallelization mechanisms so that the server(s) may sustain an increased workload. In this work, we propose to improve the performance of distributed storage systems in clusters by efficiently using the underlying high-performance network to access distant storage systems. The main question we are addressing is: do high-speed networks of clusters fit the requirements of a transparent, efficient and high-performance access to remote storage? We show that storage requirements are very different from those of parallel computation. High-speed networks of clusters were designed to optimize communications between different nodes of a parallel application. We study their utilization in a very different context, storage in clusters, where client-server models are generally used to access remote storage (for instance NFS, PVFS or Lustre). Our experimental study based on the usage of the GM programming interface of Myrinet high-speed networks for distributed storage did raised several interesting problems. Firstly, the specific memory utilization in the storage access system layers does not easily fit the traditional memory model of high-speed networks. Secondly, client-server models that are used for distributed storage have specific requirements on message control and event processing, which are not handled by existing interfaces. We propose different solutions to solve communication control problems at the file-system level. We show that a modification of the network programming interface is required. Data transfer issues need an adaptation of the operating system. We detail several propositions for network programming interfaces which make their utilization easier in the context of distributed storage. The integration of a flexible processing of data transfer in the new programming interface Myrinet/MX is finally presented. Performance evaluations show that its usage in the context of both storage and other types of applications is easy and efficient.
  • Abstract (in french):

    L'objectif de ce travail est d'étudier l'exploitation des réseaux haute performance des grappes dans le cadre du stockage distribué. Les applications parallèles s'exécutant sur les grappes nécessitent à la fois des communications performantes entre les différents noeuds et des accès efficaces au système de stockage. Les travaux menés sur les technologies réseau ont abouti à la conception d'architectures dédiées aux grappes qui permettent des communications très rapides entre les noeuds. Les travaux visant à obtenir un stockage distribué efficace dans les grappes se sont pour leur part principalement focalisés sur des mécanismes de parallélisation pour augmenter la charge de travail supportée par le (ou les) serveur. Nous proposons dans ce travail d'améliorer les performances du stockage distribué dans les grappes en utilisant au mieux le réseau haute performance sous-jacent pour accéder au stockage distant. La question générale que nous soulevons est~: est-ce que les réseaux rapides des grappes sont adaptés à un accès transparent, efficace et performant au stockage distant ? Nous montrons que les besoins du stockage sont très différents de ceux du calcul parallèle. Les réseaux des grappes ont été conçus pour optimiser les communications entre les différents noeuds d'une application parallèle. Nous étudions leur utilisation dans le cadre, très différent, du stockage dans les grappes, qui s'appuie généralement sur un modèle client/serveur d'accès aux fichiers distants (par exemple NFS, PVFS ou Lustre). Une étude expérimentale reposant sur l'utilisation de GM, l'interface de programmation du réseau rapide Myrinet, dans le contexte du stockage distribué révèle différents freins. Tout d'abord, l'utilisation mémoire particulière dans les couches système d'accès au stockage s'intègre difficilement dans l'habituelle gestion mémoire des réseaux rapides. Ensuite, les modèles client-serveur utilisés dans le stockage distribué présentent des besoins spécifiques pour la gestion des messages et des événements réseau, besoins non couverts par les interfaces actuelles. Nous proposons différentes solutions pour résoudre, au niveau du système de fichiers les problèmes liés au contrôle du réseau mais montrons qu'il est nécessaire de modifier l'interface de programmation réseau et le système d'explotation pour venir à bout des difficultés liées au transfert de données. Nous détaillons des propositions à mettre en oeuvre dans les interfaces de programmation du réseau pour faciliter leur utilisation dans le cadre du stockage. L'intégration dans une nouvelle interface de programmation, Myrinet/MX, d'une gestion souple des transferts de données est présentée. Les premiers résultats montrent que son utilisation dans le cadre du stockage distribué, mais aussi dans d'autres applications, se révèle aisée et efficace.
  • Keywords:

    Distributed Storage, Remote File Access, Cluster, High-Speed Network, Myrinet, Zero-copy, Memory Registration, Communication Control, Event Notification, Application Programming Interface.
  • Keywords (in french):

    Stockage distribué, accès distant aux fichiers, grappe de calcul, réseau haute performance, Myrinet, zéro-copie, enregistrement mémoire, contrôle des communications, notification d'événements, interface de programmation.
  • Availability: Electronic copy only.
  • Size: 194p
  • Format: pdf
  • Get it

Optimisation et analyse probabiliste de systèmes à évènements discrets.

  • By: Anne Bouillard
  • Number: PhD2005-03
  • Date: December 2005
  • Abstract:

    This thesis deals with the study of discrete event systems. Three different models are considered. In the first part, we are interested in the trace groups. After giving a simple Möbius-like formula for the generating series of the trace groups, we show the existence and the algebraicity of the asymptotic growth rate of the height of the traces. The second part is devoted to timed free-choice nets, an important sub-class of Petri nets. We define the notion of throughput in those nets and study the variation of the throughput in function of the conflict resolution policies. First, we show how to compute the throughput, then we are interested in the policy that maximizes or minimizes the throughput. Finally, we give an efficient method to generate a marking according to its exact distribution in order to numerically evaluate the throughput. In the last part, we study the computation of performance guarantees in networks thanks to Network Calculus techniques. We show the stability of the ultimately pseudo-periodic functions with the operations of the Network Calculus and give algorithms to compute these functions. These techniques are then applied to the study of performance guarantees in graphs with turn prohibition.
  • Abstract (in french):

    L'objet de cette thèse est l'étude des performances dans les systèmes à évènements discrets. Trois modèles différents de ces systèmes sont étudiés. Dans une première partie, nous nous intéressons aux groupes de traces. Après avoir donné une formule simple, semblable à la formule de Möbius pour les monoïdes de traces, de la série génératrice des groupes de traces, nous montrons l'existence et l'algébricité du taux de croissance asymptotique de la hauteur des traces. Une deuxième partie de cette thèse est consacrée aux réseaux à choix libres temporisés, une sous-classe importante de réseaux de Petri. Nous définissons une notion de débit dans ces réseaux et étudions la variation du débit en fonction de la politique de résolution de conflits choisie. Tout d'abord, nous montrons comment calculer ce débit. Ensuite, nous nous intéressons aux politiques qui le maximisent ou le minimisent. Enfin, nous donnons une méthode efficace de simulation exacte du processus des marquages pour l'évaluation numérique du débit. Enfin, nous étudions le calcul des garanties de performances dans les réseaux à l'aide des techniques du Network Calculus. Nous montrons la stabilité des fonctions ultimement pseudo-périodiques par les opérations du network calculus et donnons des algorithmes pour le calcul de ces fonctions. Ces techniques sont ensuite appliquées à l'étude des garanties de performances dans les graphes avec angles interdits.
  • Keywords:

    Discrete event systems, trace group, timed Petri nets, Network Calculus, performance evaluation.
  • Keywords (in french):

    Systèmes à évènements discrets, groupe de traces, réseaux de Petri temporisés, Network Calculus, évaluation de performances.
  • Availability: Electronic copy only.
  • Size: 208p
  • Format: compressed postscript
  • Get it

Algorithmes de routage et modèles aléatoires pour les graphes petits mondes.

  • By: Emmanuelle Lebhar
  • Number: PhD2005-04
  • Date: December 2005
  • Abstract:

    The purpose of this thesis is to study the algorithmic aspects of the small world phenomenon in large interaction networks. Experimental observations showed that large interactions networks (e.g. social or computer networks)share common global properties. One of them is the small world phenomenon which consists in the existence of very short paths between any pair of nodes, that can be discovered using only a partial knowledge of the network. We are interested in this algorithmic characteristic of the small world effect, its application to decentralized routing, and its emergence in real networks. We propose a new decentralized routing algorithm on the Kleinberg random graph model of small world, which computes paths of length $O(\log n.(\log\log n)^2)$, asymptotically shorter than those computed by existing algorithms ($O((\log n)^2)$). This algorithm could be used in peer-peer networks. We develop this study by comparing the edge load induced by the various algorithms proposed on this model. By trying to exhibit the minimal characteristics of a graph required to turn it into a small world by adding random shortcuts, we propose a new small world model which generalizes Kleinberg's one. It consists in adding a distribution of links depending on the ball sizes of the underlying graph metric. Furthermore, this model can be simply extended to produce any degree distribution, including in particular the famous power-law. Finally, we propose the first distributed scheme which turns a network into a small world by adding one link per node; this is a first step towards the understanding of the emergence of the small world phenomenon in real networks.
  • Abstract (in french):

    L'objet de cette thèse est l'étude des aspects algorithmiques de l'effet petit monde dans les grands réseaux d'interaction. Les observations expérimentales ont montré que les grands réseaux d'interactions (sociales, informatiques, biologiques), présentaient des propriétés macroscopiques communes. Une d'elles est l'effet petit monde qui consiste en l'existence de chemins très courts entre toutes les paires de noeuds qui peuvent être découverts en n'utilisant qu'une vue locale du réseau. Nous nous intéressons à cette caractéristique algorithmique de l'effet petit monde, à son application au routage informatique décentralisé, et à son émergence dans les réseaux réels. Nous proposons un nouvel algorithme de routage décentralisé sur le modèle aléatoire de petit monde de Kleinberg, qui calcule des chemins de longueur $O(\log n.(\log\log n)^2)$, asymptotiquement plus courts que ceux des algorithmes existants (en $O((\log n)^2)$). Cet algorithme pourrait également s'appliquer aux réseaux pair-à-pair. Nous précisons cette étude en comparant les charges induites pas les différents algorithmes proposés sur ce modèle. En tentant d'exhiber les caractéristiques minimales d'un graphe qui permettent de l'augmenter en un petit monde par l'ajout de raccourcis aléatoires, nous proposons un nouveau modèle de petit monde qui généralise celui de Kleinberg. Il s'agit d'ajouter une distribution de liens dépendant de la taille des boules de la métrique des distance sous-jacente. Ce modèle peut par ailleurs être étendu simplement pour produire toute distribution des degrés, dont en particulier la fameuse loi de puissance. Enfin, nous proposons le premier schéma distribué qui permette de transformer un réseau de diamètre quelconque en petit monde en ajoutant un seul nouveau lien par noeud, il s'agit d'un premier pas vers la compréhension de l'émergence naturelle du phénomène dans les réseaux réels.
  • Keywords:

    Small world graphs, routing algorithms, random models, distributed algorithms, large networks.
  • Keywords (in french):

    Graphes petits mondes, algorithmes de routage, modèles aléatoires, algorithmique distribuée, grands réseaux.
  • Availability: Electronic copy only.
  • Size: 182p
  • Format: pdf
  • Get it

Pavages et structures ordonnées.

  • By: Gilles Radenne
  • Number: PhD2005-05
  • Date: December 2005
  • Abstract:

    .
  • Abstract (in french):

    .
  • Keywords:

    .
  • Keywords (in french):

    .
  • Availability: Not available by ftp.
  • Size: p
  • Format:
  • Get it

Équilibrage de charge et redistribution de données sur plates-formes hétérogènes.

  • By: Hélène Renard
  • Number: PhD2005-06
  • Date: December 2005
  • Abstract:

    In this thesis, we study iterative algorithms onto heterogeneous platforms. These iterative algorithms operate on large data samples (recursive convolution, image processing algorithms, etc.). At each iteration, independent calculations are carried out in parallel, and some communications take place. An abstract view of the problem is the following: the iterative algorithm repeatedly operates on a large rectangular matrix of data samples. This data matrix is split into vertical (or horizontal) slices that are allocated to the processors. At each step of the algorithm, the slices are updated locally, and then boundary information is exchanged between consecutive slices. This (virtual) geometrical constraint advocates that processors be organized as a virtual ring. Then each processor will only communicate twice, once with its (virtual) predecessor in the ring, and once with its successor. Note that there is no reason a priori to restrict to a uni-dimensional partitioning of the data, and to map it onto a uni-dimensional ring of processors. But uni-dimensional partitionings are very natural for most applications, and, as will be shown in this thesis, the problem to find the optimal one is already very difficult. After dealing with the problems of mapping and load-balancing onto heterogeneous platforms, we consider the problem of redistributing data onto these platforms, an operation induced by possible variations in the resource performances (CPU speed, communication bandwidth) or in the system/application requirements (completed tasks, new tasks, migrated tasks, etc.). For homogeneous rings the problem has been completely solved. Indeed, we have designed optimal algorithms, and provided formal proofs of correctness, both for unidirectional and bidirectional rings. For heterogeneous rings there remains further research to be conducted. The unidirectional case was easily solved, but the bidirectional case remains open. Still, we have derived an optimal solution for light redistributions, an important case in practice.
  • Abstract (in french):

    Dans cette thèse, nous nous sommes intéressée à la mise en oeuvre d'algorithmes itératifs sur des grappes hétérogènes. Ces algorithmes fonctionnent avec un volume important de données (calcul de matrices, traitement d'images, etc.), qui sera réparti sur l'ensemble des processeurs. À chaque itération, des calculs indépendants sont effectués en parallèle et certaines communications ont lieu. Prenons l'exemple d'une matrice rectangulaire de données : l'algorithme itératif fonctionne répétitivement sur cette matrice, divisée en tranches verticales (ou horizontales) allouées aux processeurs. À chaque étape de l'algorithme, les tranches sont mises à jour localement et les informations frontières sont échangées entre tranches consécutives. Cette contrainte géométrique implique que les processeurs soient organisés en anneau virtuel. Chaque processeur communique seulement deux fois, une fois avec son prédécesseur (virtuel) dans l'anneau et une fois avec son successeur. Il n'existe pas de raison a priori de réduire le partitionnement des données à une unique dimension et de ne l'appliquer que sur un anneau de processeurs unidimensionnel. Cependant, un tel partitionnement est très naturel et nous montrerons que trouver l'optimal est déjà très difficile. Après cette étude sur le placement et l'équilibrage de charge pour plates-formes hétérogènes, nous nous sommes intéressée à la redistribution de données sur ces mêmes plates-formes, lorsque que les caractéristiques de ces dernières changent. En ce qui concerne les anneaux de processeurs homogènes, nous avons totalement résolu le problème : nous avons obtenu des algorithmes optimaux et prouvé leur exactitude dans le cas homogène et dans le cas hétérogène. En ce qui concerne les anneaux hétérogènes, le cas unidirectionnel a été totalement résolu, alors que le cas bidirectionnel reste ouvert. Cependant, sous l'hypothèse de redistribution légère, nous sommes capable de résoudre le problème de manière optimale.
  • Keywords:

    Iterative algorithms, load-balancing, heterogeneous platforms, shared communication links, data redistribution algorithms, heterogeneous rings, complexity.
  • Keywords (in french):

    Algorithmes itératifs, équilibrage de charge, plates-formes hétérogènes, partage de liens de communication, algorithmes de redistribution de données, anneaux hétérogènes, complexité.
  • Availability: Electronic copy only.
  • Size: 110p
  • Format: pdf
  • Get it

Automates cellulaires : un modèle de complexités.

  • By: Guillaume Theyssier
  • Number: PhD2005-07
  • Date: December 2005
  • Abstract:

    We study the model of cellular automata through two complementary aspects: local syntactic representations and global dynamics. We aim at establishing new links between these aspects using a set of approaches ranging from combinatorics to algebraic tools and computability theory. First, while studying local structures of transition rules, we introduce a new class of cellular automata (namely captive cellular automata) which are defined by an elementary local constraint. We establish a 0-1 law over that class and deduce that almost all captive cellular automata are intrinsically universal. However, we show that it is undecidable to determine whether a captive cellular automaton is intrinsically universal or not. In a second part, we focus on global properties of cellular automata while trying to disregard their syntactic representations. Our matter is then to study classifications and notions of complexity according to that global point of view. The key tool is the notion of simulation. We extend previous results from N. Ollinger concerning simulation pre-orders (with new relations of simulation and new properties inducing ideal or filter structures). We also study the Cartesian product over such structures. We establish a construction which can be considered as a limit of Cartesian products and allows us to exhibit infinite increasing chains of length omega+omega in one of the studied pre-orders. Finally, we focus on sequential dynamics and Turing-universal cellular automata. We construct an infinite lattice of Turing-universal cellular automata which are all infinitely far away from any intrinsically universal cellular automaton.
  • Abstract (in french):

    Nous étudions le modèle des automates cellulaires en adoptant successivement deux points de vue ---celui des représentations syntaxiques locales puis celui des dynamiques globales--- et en cherchant à établir des liens entre eux par différentes approches ou outils --- algébrique, combinatoire, et de la théorie de la calculabilité. Au cours de notre étude de la structure des règles de transition locales, nous introduisons une nouvelle classe d'automates (appelés automates cellulaires captifs) définie par une contrainte locale très simple. Nous établissons une loi 0-1 sur cette classe qui a pour corollaire que presque tous les automates cellulaires captifs sont intrinsèquement universels. En revanche, nous montrons qu'il est indécidable de savoir si un automate cellulaire captif est intrinsèquement universel ou pas. Dans une seconde partie, nous poursuivons l'étude des automates cellulaires en cherchant au contraire à nous affranchir le plus possible de leur représentation syntaxique pour insister sur leurs propriétés dynamiques globales. Notre problématique devient celle de la classification et de l'étude de notions de complexité selon ce point de vue global. L'outil fondamental est celui de simulation. Nous étendons les résultats de N. Ollinger sur les structures de pré-ordre (nouvelles relations de simulations et nouvelles propriétés induisant des structures d'idéal ou de filtre) et étudions également l'effet du produit cartésien sur ces structures. Nous établissons une construction qui peut s'interpréter comme un produit cartésien limite et nous permet d'exhiber des chaînes infinies croissantes de longueur $\omega+\omega$ dans l'un des pré-ordres étudiés. Enfin, nous nous intéressons aux dynamiques séquentielles et aux automates cellulaires universels pour le calcul Turing. Nous construisons un treillis infini d'automates cellulaires Turing-universels qui sont tous à distance infinie de tout automate cellulaire intrinsèquement universel.
  • Keywords:

    Cellular Automata, Classification, Universality, Complexity, Decidability, Dynamics, 0-1 Laws, Combinatorics.
  • Keywords (in french):

    Automates Cellulaires, Classification, Universalité, Complexité, Décidabilité, Dynamique, Lois 0-1 .
  • Availability: Electronic copy only.
  • Size: 177p
  • Format: pdf
  • Get it