Madeleine: une interface de communication performante et portable pour exploiter les interconnexions hétérogènes de grappes.

  • By: Olivier AUMAGE
  • Number: PhD2002-01
  • Date: September 2002
  • Abstract:

    The quality of the communication management in a runtime for high-performance applications running on top of distributed computing architectures is one of the most influent factors on the effective performance of such applications. The design of a communication support for distributed computation and processing requires to solve many untrivial problems at various levels. Among these problems are the quest for both high efficiency and portability and the dynamic communication requests optimization.

    The Madeleine communication library designed and developped during this thesis, brings new answers to distributed computing communication scheme problems in the context of cluster and multi-cluster architecture support. Madeleine aims at providing the application or programming environment programmer with the optimal virtualization and automation level for allowing both short development time, good efficiency and a high optimization potential.

  • Abstract (in french):

    La qualité de la gestion des communications au sein d'un exécutif destiné aux applications dites «hautes performances» sur des architectures de calcul distribuées est essentielle : le support de communication est sans aucun doute un des facteurs d'influence les plus décisifs sur les performances effectives de telles applications. Or, la conception d'un support de communication pour le calcul ou le traitement d'information distribué implique l'apport de solutions à de nombreux problèmes non triviaux, à des niveaux très divers : la quête simultanée d'un haut degré d'efficacité et de réactivité à concilier avec des impératifs stricts de portabilité ; la gestion du déploiement de session sur des réseaux hétérogènes de grappes ou encore l'optimisation dynamique des requêtes de communication en sont quelques exemples.

    La bibliothèque de communication Madeleine présentée dans ce manuscrit a été conçue et développée durant cette thèse. Elle propose des réponses originales et pertinentes à ces divers problèmes liés au support des schémas de communication propres aux environnements de programmation et aux applications fonctionnant sur les architectures de calcul distribuées telles que les grappes et les grappes de grappes. Au premier plan se trouve le souci de proposer au programmeur d'applications le niveau de virtualisation et d'automatisme optimal permettant à la fois un temps de développement très court, de bonnes performances d'ensemble et un potentiel d'optimisation élevé.

  • Keywords:

    High-Performance Computing, Distributed Architecture, Genericity, Adaptivity.
  • Availability: Electronic copy only.
  • Size: 154p
  • Format: Compressed PostScript
  • Get it

Parallélisme mixte et prédiction de performances sur réseaux hétérogènes de machines parallèles.

  • By: Frédéric SUTER
  • Number: PhD2002-02
  • Date: November 2002
  • Abstract:

    Thanks to the Internet, numerical computation users can now access the most powerful computer from their workstation. At a large scale this remote access is named metacomputing. My PhD work was first focused on the parallelization of the Scilab tool, following a computational server based approach. Drawbacks of existing environments raised. One of these was the bottleneck problem due to the centralized agent. To solve that problem and propose a scalable environment, we followed a hierarchical approach to develop DIET (Distributed Interactive Engineering Toolbox). One of the critical issue of such environments is the capacity to estimate the execution time of a routine on a given computer and the communication cost of data transfers from a client, or a server, to the server chosen for the resolution. We also extended FAST (Fast Agent's System Timer) library to handle parallel routines. >From an algorithmic point of view we ran a theoretical and experimental study of the simultaneous exploitation of data and task parallelism, so called mixed parallelism. After applying this paradigm on fast matrix multiplication algorithms (Strassen and Winograd), we proposed a mixed data and task parallel scheduling algorithm in which data can not be replicated. This algorithm allocates and schedules tasks in one step and based on cost models given by our FAST extension and a set of possible distributions.
  • Abstract (in french):

    Avec la généralisation de l'Internet, il est désormais possible pour les utilisateurs de calcul numérique d'accéder aux machines les plus puissantes disponibles de par le monde, et ce depuis leur station de travail. A grande échelle, ce type d'accès distant est appelé metacomputing. Les travaux effectués au cours de cette thèse ont tout d'abord concerné la parallélisation du logiciel Scilab, en suivant, entre autres, une approche basée sur des serveurs de calcul. Au cours de ces développements, les lacunes des environnements de ce type ont été exhibées, notamment le problème de goulot d'étranglement posé par la présence d'un agent centralisé. Afin de pallier ce problème, et donc de proposer un environnement extensible, nous avons suivi une approche hiérarchique pour développer le logiciel DIET (Distributed Interactive Engineering Toolbox). Un des points cruciaux des environnements de ce type concerne la capacité à estimer le temps d'exécution d'une routine sur machine donnée et les coûts de transfert des données depuis un client ou un serveur vers le serveur choisi pour la résolution. La bibliothèque FAST (Fast Agent's System Timer), que nous avons étendue afin de gérer les routines parallèles, permet d'acquérir ce type d'informations. D'un point de vue algorithmique, nous avons mené une étude à la fois théorique et expérimentale du parallélisme mixte, i.e., l'exploitation simultanée des parallélismes de tâches et données. Après avoir appliqué ce paradigme aux algorithmes rapides de produit de matrices de Strassen et Winograd, nous avons proposé un algorithme d'ordonnancement en parallélisme mixte dans le cas où les données ne peuvent pas être dupliquées. Cet algorithme effectue simultanément le placement et l'ordonnancement des tâches d'un graphe en se basant sur les modèles de coûts fournis par notre extension de FAST et sur un ensemble de distributions possibles.
  • Keywords:

    Mixed data and task parallelism, metacomputing, performance forecasting, scheduling, linear algebra, Strassen, Winograd, PSE, ASP.
    Keywords (in french):

    Parallélisme mixte, metacomputing, prédiction de performances, ordonnancement, algèbre linéaire, Strassen, Winograd, PSE, ASP.
  • Availability: Electronic copy only.
  • Size: 131p
  • Format: Compressed PostScript
  • Get it

Graphes d'automates finis : Reconnaissance et Calcul.

  • By: Christophe Papazian
  • Number: PhD2002-03
  • Date: November 2002
  • Abstract:

    Graph automata is a synchronous dynamical system that allows to modelize numerous phenomena and to fundamentaly study what is the distributed computing. At first we show how to generalize the previous studies on the recognizing of geometrical properties by graph automata. Then, we present some results about the study of complexity and computability of distributed computing and some links with classical complexity classes.
  • Abstract (in french):

    Les graphes d'automates sont un système dynamique synchrone qui permet de modéliser de nombreux phénomènes et d'étudier d'un point de vue fondamental la nature du calcul distribué. Dans une première partie on a montré comment généraliser les travaux précédents (A.Wu et A.Rosenfeld) sur la reconnaissance de propriétés géométriques par des graphes d'automates. On s'est particulièrement intéressé au problème du plongement dans des réseaux infinis réguliers, comme la grille ou des réseaux hyperboliques. Dans une seconde partie, on a étudié le modèle des graphes d'automates finis comme un modéle de calcul : quelles sont les classes de complexité en temps qui apparaissent naturellement et à quoi elles correspondent et quels sont les liens avec la complexité classique.
  • Keywords:

    Graph Automata, Recognizing, Hyperbolic networks.
    Keywords (in french):

    Graphes d'automates, Reconnaissance, Réseaux hyperboliques.
  • Availability: Electronic copy only.
  • Size: 88p
  • Format: Compressed PostScript
  • Get it

Calculs et Infinis.

  • By: Gregory Lafitte
  • Number: PhD2002-04
  • Date: December 2002
  • Abstract:

    We introduce a hierarchy of notions of generalized computation. The idea is to almagamate in one concept all that we could qualify of "computability", to study those notions and ultimately to have transfer theorems between those notions. Those notions correspond also in some cases to computation models obtained by means of concrete machines. We obtain in this way a new computation model, "infinite time cellular automata", which are more homogeneous than Turing machines (lack of head). The notion of computational complexity (according to a certain notion of computation) is also generalized and studied. Finally, we obtain notions of random reals that are finer than the classical notion of Martin-Löf (or Kolmogorov) and yet more and more refinable. All of this leads to a notion of generalized Kolmogorov complexity which opens up interesting prospects..
  • Abstract (in french):

    Nous introduisons une hiérarchie de notions de calcul généralisé. L'idée est de regrouper en une notion tout ce que l'on pourrait qualifier de «calculabilité», de pouvoir étudier ces notions et en fin de compte d'établir des théorèmes de transfert entre elles. Ces notions correspondent certaines fois aussi à des modèles de calcul obtenues par le biais de machines concrètes. Nous avons ainsi un nouveau modèle de calcul avec les « automates cellulaires à temps infini » qui ont l'avantage sur les machines de Turing d'être plus homogènes (absence de tête). La notion de complexité de calcul (selon une certaine notion de calcul) est également généralisée et étudiée. Enfin, nous obtenons des notions de réels aléatoires plus fines que la notion classique de Martin-Löf (ou Kolmogorov) que l'on peut affiner de plus en plus. Tout ceci mène à la notion de complexité de Kolmogorov généralisée qui ouvre des perspectives intéressantes.
  • Keywords:

    Generalized Computability, Computational omplexity, Kolmogorov Complexity.
    Keywords (in french):

    Calcul Généralisé, Complexité de Calcul, Complexité de Kolmogorov.
  • Availability: Not available.
  • Size: 110p
  • Format:Compressed Postscript
  • Get it

Automates cellulaires : structures.

  • By: Nicolas Ollinger
  • Number: PhD2002-05
  • Date: December 2002
  • Abstract:

    Cellular automata provide a uniform framework to study an important problem of "complex systems" theory: how and why do system with a easily understandable -- local -- microscopic behavior can generate a more complicated -- global -- macroscopic behavior? Since its introduction in the 40s, a lot of work has been done to understand the links between local and global properties of the cellular automata model. These last 20 years appeared a new trail through the search of meaningful classifications of cellular automata. Several formal classifications have been proposed to describe the kind of "chaotic" behavior, usually with topological tools. However, another kind of complex cellular automata -- cellular automata for which local structures, particles, seems to emerge and interact according to complex rules -- still remain to study. To our knowledge, the grouping classification proposed by I. Rapaport, a classification based on algebraic tools, is the only classification driven by this particular kind of complexity. Our work is involved into generalizing this classification, in order to take into account several interesting notions like intrinsic universality and to strengthen the algebraic structure behind this tool -- still keeping its geometrical nature.
  • Abstract (in french):

    Les automates cellulaires fournissent un cadre agréable et uniforme pour aborder une des problématiques majeures de l'étude des «systèmes complexes» : comprendre comment et pourquoi des systèmes qui possèdent un comportement microscopique -- local -- facile à décrire peuvent avoir un comportement macroscopique -- global -- beaucoup plus compliqué. Depuis leur introduction dans les années 40, de nombreux travaux ont été entrepris afin de comprendre les liens existant entres les propriétés locales et globales des automates cellulaires. Ces vingt dernières années est apparue une nouvelle approche à travers la recherche de classifications pertinentes des automates cellulaires. Ainsi, de nombreuses classifications formelles ont été proposées pour mieux cerner les comportements de type «chaotique», principalement à l'aide d'outils de nature topologique. Cependant, une autre forme d'automates cellulaires complexes -- les automates cellulaires pour lesquels semblent émerger des structures locales, des particules, qui interagissent selon des schémas complexes -- reste peu étudiée. A notre connaissance, seuls les travaux d'I. Rapaport proposent une classification -- le groupage -- de nature algébrique, inspirée par cette forme de complexité. Nos travaux consistent en la généralisation de cette classification, afin d'une part de prendre en compte certaines notions intéressante comme l'universalité intrinsèque et d'autre part de renforcer la structure algébrique qui fait la force de cet outil -- tout en conservant sa nature géométrique.
  • Keywords:

    Cellular Automata, Classification, Bulking, Universality.
    Keywords (in french):

    Automate Cellulaire, Classification, Groupage, Universalité.
  • Availability: Electronic copy only.
  • Size: 126p
  • Format: Format: PDF
  • Get it