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é.
Réseaux rapides et stockage distribué dans les grappes de calculateurs : propositions pour une interaction efficace.
By: Brice Goglin
Number: PhD2005-02
Date: Octobre 2004
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.
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.
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.
É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é.
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.
