Modèles de la beta-reduction pour les implantations.

  • By: Frederic Lang
  • Number: PhD1999-01
  • Date: December 1998
  • Abstract:

    The thesis addresses the issue of defining models to implement the beta-reduction in the lambda-calculus. We focus especially on two kinds of models: explicit substitution calculi, and interaction nets. Explicit substitution calculi are studied in several contexts. On the one hand, they are studied in the context of automatic provers, where it is interresting to have a calculus confluent and preserving strong normalization, that allows the representation of incomplete proofs. We discuss these properties, and give important contributions to an open problem in this field. On the other hand, explicit substitution calculi are applied to functional programming and weak reduction which is the fundamental concept. It is then essential to have tools which can express the sharing provided by implementations, particularly for lazy languages. To illustrate this, we give a very precise and formal proof of the correctness of KP, an abstract machine for lazy reduction of the lambda-calculus, using a calculus of explicit substitution and global adresses. We then propose an optimization to this machine. Interaction nets are usually associated to optimal reduction a la Levy, as described by Lamping's algorithm. However, this algorithm is known as rather complex. We study in our thesis a reducer based on some ideas due to Lamping, but leaving out some constraints introduced for optimality. Thus, we obtain a non optimal algorithm that we compare to Lamping's algorithm (implementation of Asperti) and KP. The results show as expected that our algorithm provides quite a good amount of sharing, without the bureaucracy that one finds in optimal interpreters.
  • Abstract (in french):

    La thèse aborde le problème de la définition de modèles adaptés aux implantations de l'opération de beta-reduction en lambda-calcul. Nous nous intéressons particulierement à deux types de modèles : les calculs de substitution explicite, et les réseaux d'interaction. Les calculs de substitution explicite sont etudiés sous différents points de vue, d'une part dans le cadre de la démonstration automatique, ou il s'avère interessant de disposer d'un calcul confluent et preservant la forte normalisation, qui permet de représenter des preuves incomplètes. Nous discutons ces propriétés et apportons d'importantes contributions à un problème ouvert dans ce domaine. D'autre part, les calculs de substitution explicite sont appliqués à la programmation fonctionnelle, et à la réduction faible qui en est le concept fondamental. Il est alors important de disposer d'outils pour exprimer le partage mis en oeuvre par les implantations, notamment pour les langages paresseux. Dans ce cadre, nous donnons une preuve de correction tres précise de KP, une machine abstraite de réduction paresseuse du lambda-calcul, en nous appuyant sur un calcul avec substitution explicite et adresses globales. Nous proposons ensuite une optimisation pour cette machine. Les réseaux d'interaction sont habituellement utilisés pour la définition de réducteurs optimaux, au sens de Levy. C'est le cas de l'algorithme de Lamping. Cependant, cet algorithme s'avère complexe. Nous étudions dans cette thèse un réducteur basé sur quelques idées proposées par Lamping, mais en relachant quelque peu les contraintes qui permettaient d'obtenir l'optimalité. Nous obtenons ainsi un algorithme non optimal que nous comparons avec l'algorithme de Lamping (implantation d'Asperti) et avec KP. Les résultats sont encourageants et montrent que notre algorithme réalise un assez bon partage sans avoir la lourdeur de la gestion de ce partage que l'on trouve dans les interpretes optimaux.
  • Keywords:

    Lambda-Calculus, Explicit Substitution, Interaction Nets, Functional Programming, Sharing, abstract Machines.
  • Keywords (in french):

    Lambda-Calcul, Substitution Explicite, Réseaux d'Interaction, Programmation Fonctionnelle, Partage, Machines Abstraites.
  • Availability: Paper copy available.
  • Size: 154p
  • Format: Compressed PostScript
  • Get it

Algorithmes génétiques hybrides en optimisation combinatoire.

  • By: Pascal Rebreyend
  • Number: PhD1999-02
  • Date: January 1999
  • Abstract:

    In this thesis, we are interested in solving combinatorial problems with genetic algorithms. These algorithms are interested but they often need a lot of computations. Thus, we are focused on hybrid algorithms. Hybrids algorithms are algorithms built using several different methods. In our work, we build such algorithms by merging genetic algorithms and heuristics. There is two ways to do it. One is called the direct representation scheme and the other the indirect representation scheme. This two ways are studied by using them on three different problems: Multiprocessor tasks graph scheduling, VLSI cells placements, optimisation of cellular networks. For each of these problems, hybrids algorithms have shown their efficiency. For the probklem of optimisation of cellular networks, a new modelization have been made. This new approach allows us to do in one step the choice of emitters and the frequency's allocations.
  • Abstract (in french):

    Cette thèse aborde le problème de la résolution des problèmes combinatoires à l'aide d'algorithmes génétiques. Ce type d'algorithme présente en effet nombres d'avantages. Cependant, ils sont généralement relativement lents. Cette thèse est donc centrée sur les algorithmes hybrides, c'est-à-dire des algorithmes construits à l'aide de plusieurs méthodes différentes. Dans notre cas, nous étudions les algorithmes qui réunissent algorithmes génétiques et heuristiques. Il existe deux méthodes pour générer de tels algorithmes qui sont la représentation directe et la représentation indirecte. Ces deux méthodes sont étudiés au travers de trois problèmes distincts : l'ordonnancement statique de programmes parallèles, le placement de composants électroniques et la planification de réseaux cellulaires. Pour chacun des trois problèmes, les algorithmes hybrides ont montrés leur efficacité. Pour le problème de la planification de réseaux cellulaires, une nouvelle modélisation a été faite. Cette modélisation permet d'effectuer en même temps le placement des émetteurs et l'allocation de fréquences.
  • Keywords:

    Genetic Algorithms, Hybrid Algorithms, Scheduling, Placement, Cellular Networks, Combinatorial Optimization.
  • Keywords (in french):

    Algorithmes Génétiques, Algorithmes Hybrides, Ordonnancement, Placement, Réseaux Cellulaires, Optimisation Combinatoire.
  • Availability: Paper copy available.
  • Size: 134p
  • Format: Compressed PostScript
  • Get it

Aspects algorithmiques des triangulations minimales des graphes.

  • By: Ioan Todinca
  • Number: PhD1999-03
  • Date: January 1999
  • Abstract:

    In this thesis, we are interested in computing the treewidth of graphs, which consists in finding a minimal triangulation of minimum cliquesize of the graph. The problem in NP-complete for arbitrary graphs. Nevertheless, polynomial algorithms exist for particular classes of graphs having a polynomial number of minimal separators. We defined the potential maximal cliques of a graph as the vertex sets inducing a maximal clique in at least one minimal triangulation of the graph. We showd that if all potential maximal cliques of a graph are computable in polynomial time, then the treewidth of that graph is tractable in polynomial time. We also proved that all the existing algorithms, computing the treewidth for particular classes of graphs, compute actually the potential maximal cliques of the input graph. This gives a unified version of the cited algorithms. We also gave an polynomial time algorithm listing the potential maximal cliques of weakly triangulated graphs, for which the treewidth problem was open. All our algorithms can be extended to compute another graph parameter, namely the minimum fill-in.
  • Abstract (in french):

    Nous nous sommes intéressés dans cette thèse au calcul de la largeur arborescente des graphes, qui consiste à trouver une triangulation minimale du graphe, tout en minimisant la taille de la clique maximum de la triangulation. Ce problème est NP-difficile en général. Il existe toutefois des algorithmes polynomiaux spécifiques, calculant la largeur arborescente pour certaines classes de graphes ayant un nombre polynomial de séparateurs minimaux. Nous avons défini les cliques maximales potentielles d'un graphe comme étant les ensembles de sommets induisant une clique maximale dans au moins une triangulation minimale du graphe. Nous avons prouvé que si l'on sait calculer en temps polynomial toutes les cliques maximales potentielles d'un graphe, la largeur arborescente de ce graphe se calcule en temps polynomial. Nous avons montré que pour toutes les classes de graphes pour lesquelles il existait des algorithmes calculant la largeur arborescente, les algorithmes respectifs calculent de manière implicite les cliques maximales potentielles des graphes donnés. Nous unifions ainsi tous ces algorithmes. Nous avons donné un algorithme énumérant en temps polynomial les cliques maximales potentielles des graphes faiblement triangulés, classe pour laquelle le calcul de la largeur arborescente était un problème ouvert. Tous ces algorithmes se généralisent au calcul d'un autre paramètre de graphes, à savoir la complétion minimale.
  • Keywords:

    Algorithms, Graphs, Chordal Graphs, Treewidth, Potential Maximal Cliques.
  • Keywords (in french):

    Algorithmes, Graphes, Graphes Triangules, Largeur Arborescente, Cliques Maximales Potentielles.
  • Availability: Paper copy available.
  • Size: 101p
  • Format: Compressed PostScript
  • Get it

Complexité algorithmique des systèmes dynamiques continus et hybrides.

  • By: Olivier Bournez
  • Number: PhD1999-04
  • Date: January 1999
  • Abstract:

    This thesis presents a study of the algorithmic complexity of properties of continuous and hybrid dynamical systems. In a first part, we study the decidability of the automatic verification of properties of dynamical systems with a continuous space: we start by proving that the stability problem for saturated linear dynamical systems is undecidable. Then we study the frontier between decidability and undecidability for low dimensional dynamical systems by discussing the existence of an algorithm to decide the mortality of two by two matrices. In a second part, we study the representation of polyhedra by their vertices: we propose several representations for orthogonal polyhedra and we prove that these representations allow efficient realizations of classical automatic verification algorithms. We generalize later these representations to polyhedra used by algorithms on timed automata. In a third part, we present a full characterization of the computational power of a particular class of dynamical systems with continuous space and time: we prove that the computational power of piecewise constant derivative systems is related to the classes of the hyperarithmetical hierarchy.
  • Abstract (in french):

    Cette thèse présente une étude de la complexité algorithmique de la vérification automatique de propriétés pour les systèmes dynamiques continus et hybrides. Dans un premier temps nous étudions la décidabilité de la vérification automatique de propriétés des systèmes dynamiques à espace continu: nous prouvons tout d'abord l'indécidabilité du problème de la stabilité des systèmes dynamiques linéaires seuillés, puis nous étudions la frontière entre décidabilité et indécidabilité pour les systèmes de basses dimensions en discutant l'existence d'un algorithme pour décider la mortalité des matrices deux par deux. Dans un second temps, nous étudions la représentation des polyèdres par leurs sommets: nous proposons plusieurs représentations pour les polyèdres orthogonaux et prouvons que ces représentations permettent une réalisation efficace des algorithmes classiques de vérification automatique. Nous généralisons ensuite ces représentations aux polyèdres manipulés par les algorithmes de vérification de propriétés des automates temporisés. Dans un troisième temps, nous présentons une caractérisation complète de la puissance de calcul d'une classe particulière de systèmes dynamiques à espace et à temps continus: nous prouvons que la puissance de calcul des systèmes dynamiques définis par une équation différentielle constante par morceaux se relie aux classes de langages de la hiérarchie hyperarithmétique.
  • Keywords:

    Orthogonal Polyhedra, Timed Polyhedra, Computational Models, Analog Computations, Computability.
  • Keywords (in french):

    Polyèdres Orthogonaux, Polyèdres Temporisés, Modèles de calcul, Calculs Analogiques, Calculabilité.
  • Availability: Paper copy available.
  • Size: 170p
  • Format: Compressed PostScript
  • Get it

Estimation et amélioration des performances de code C.

  • By: Thomas Peugeot
  • Number: PhD1999-05
  • Date: March 1999
  • Availability: Not available.
  • Size: p

Du parallélisme des modèles connexionnistes à leur implantation parallèle.

  • By: Bernard Girau
  • Number: PhD1999-06
  • Date: March 1999
  • Abstract:

    This thesis sets out a study of artificial neural considered as practically exploitable models of parallel computation. Neurons may work in a concurrent way thanks to their interconnection scheme. Nevertheless, most works about fast parallel implementations of neural networks come up against the fact that this connectionist parallelism does not fit the available parallel devices. The present work shows that a specific study of the connectionist parallelism lies beyond the apparent structure of neural networks: in order to make the most of connectionist parallelism, neurons must no longer be considered as the atomic unit of connectionist structures in neural computation algorithms. This approach is first applied to the parallelization of on-line gradient-based learning on a MIMD parallel computer with shared memory. It is then applied within a general method for the implementation of multilayer perceptrons on reconfigurable hardware. It is finally applied through a decomposition of the very connections within a study mainly dedicated to digital hardware parallel implementations: some configurable hardware principles are applied in a connectionist context, so that a new approach of neural computations allows to simplify the topology of standard neural networks without having any significant loss of approximation capability. The main part of this thesis includes the definition, the theoretical study, the applications and the implementations of the connectionist models that use this new neural computation paradigm. This work attains the central objective of the thesis through a direct and efficient exploitation of the connectionist parallelism.
  • Abstract (in french):

    Cette thèse présente une étude des réseaux de neurones en tant que modèles de calcul parallèle concrètement exploitables. Le schéma d'interconnexion des neurones leur permet de travailler de façon concurrente. Néanmoins les travaux d'implantation rapide de calculs neuronaux se heurtent généralement à une absence d'adéquation de ce parallélisme connexionniste aux contraintes des supports parallèles disponibles. Les travaux présentés ici montrent qu'une étude spécifique du parallélisme des réseaux de neurones doit dépasser la structure apparente de ces modèles, et qu'une exploitation approfondie du parallélisme connexionniste passe par une algorithmique des calculs induits qui ne considère plus le neurone comme une unité atomique de la structure connexionniste. Cette démarche est d'abord utilisée dans le cadre d'une parallélisation d'apprentissage en-ligne à base de gradient sur machine parallèle MIMD à mémoire distribuée. Elle apparaît ensuite dans une méthode d'implantation générale de perceptrons multicouches sur matériel reconfigurable. Elle aboutit enfin à une décomposition des connexions elles-mêmes, dans le cadre d'un travail plus spécifiquement applicable à des implantations parallèles sur circuits numériques~: l'utilisation de principes du matériel programmable dans un contexte connexionniste introduit une nouvelle conception du calcul neuronal qui permet de simplifier les topologies des réseaux de neurones classiques sans perte significative en capacité d'approximation. La définition, l'étude théorique, les applications pratiques et les implantations des modèles connexionnistes issus de ce nouveau principe de calcul neuronal constituent la partie principale de cette thèse et réalisent son objectif essentiel par l'exploitation directe et efficace du parallélisme connexionniste.
  • Keywords:

    Artificial Neural Networks, Connectionist Models, Parallelism, Configurable Hardware, FPGA, MIMD.
  • Keywords (in french):

    Réseaux de Neurones Artificiels, Modèles Connexionnistes, Parallélisme, Matériel Configurable, FPGA, MIMD.
  • Availability: Electronic copy only.
  • Size: 206p
  • Format: Compressed PostScript
  • Get it

Support d'exécution parallèle fondé sur des mécanismes de Mémoire Distribuée Virtuellement Partagée.

  • By: Olivier Reymann
  • Number: PhD1999-07
  • Date: July 1999
  • Abstract:

    Distributed Shared Memory (DSM) systems allow a transparent manipulation of programming data spread over distributed memory parallel architectures. Hence, DSM systems take into charge all the communications required for accessing the shared data with respect to some consistency model. Unfortunately, most of DSM systems show limited performance and lack from development tools. In this framework, the aim of this thesis is to formalize and to propose an integrated programming environment and execution support based on distributed shared memory mechanisms providing application structuration tools, compilation and porting tools, monitoring tools. Thus, the DOSMOS (Distributed Objects Shared MemOry System) programming environment, which is discussed in this thesis, proposes several original functionalities: hierarchic structuration of the shared memory space by the definition of groups according to the application structure, possibility to split shared variables into sub-variables in order to mitigate or even suppress the problem of false-sharing, use of a weak consistency model and multi-level cache management protocols, integration of a flexible and distributed monitoring tool specially designed for DSM aplications. Two versions of this runtime support have been modelled and implemented, one based on UNIX processes, the other one based on distributed threads. Experiments and case studies highlight the good performance of the system (e.g. remote access time of 70us on a Myrinet LAN). So, DOSMOS appears as one of the most efficient DSM system while providing a powerful and integrated programming interface.
  • Abstract (in french):

    Les systèmes de Mémoire Distribuée Virtuellement Partagée (MDVP) permettent de manipuler des données réparties de manière transparente au-dessus d'architectures parallèles à mémoire distribuée. Ainsi, le rôle des systèmes de MDVP consiste à prendre en charge toutes les communications nécessaires pour accéder aux données partagées en respectant un certain modèle de cohérence entre les copies de ces données. La plupart de ces systèmes affichent malheureusement des performances limitées et souffrent d'un manque important d'outils de développement. Dans ce cadre, l'objectif de cette thèse est de formaliser et de proposer un environnement de programmation et d'exécution parallèle fondé sur des mécanismes de MDVP intégré (c'est-à-dire associant outils de structuration d'applications, outils de compilation et de portage, outils de traçage d'exécution). Ainsi, l'environnement DOSMOS (Distributed Objects Shared MemOry System) présenté dans cette thèse propose un certain nombre de fonctionnalités originales: structuration hiérarchique de l'espace mémoire partagé via la création de groupes de processus fondés sur la structure de l'application, possibilité de découper des variables partagées en sous-variables afin de limiter voire de supprimer le problème du faux-partage, mise en oeuvre d'un modèle de cohérence faible et de protocoles de gestion de cache à plusieurs niveaux, environnement de traçage d'exécution extensible et distribué spécialement adapté aux applications utilisant une MDVP en vue d'optimiser leurs implémentations. Deux versions de ce support d'exécution ont été modélisées et développées, l'une à base de processus lourds, l'autre à base de processus légers distribués. Des expérimentations et plusieurs études de cas complètent ce manuscrit. Les performances obtenues placent DOSMOS parmi les systèmes de MDVP les plus performants, tout en bénéficiant d'une interface de programmation particulièrement riche.
  • Keywords:

    Distributed Shared Memory, Programming Environment, Distributed Systems, Monitoring.
  • Keywords (in french):

    Mémoire Distribuée Virtuellement Partagée, Environnement de Programmation, Systèmes Répartis, Traçage d'Exécution.
  • Availability: Electronic copy only.
  • Size: 182p
  • Format: Compressed PostScript
  • Get it

Allocation de graphes de tâches paramétrés et génération de code.

  • By: Emmanuel Jeannot
  • Number: PhD1999-08
  • Date: October 1999
  • Abstract:

    The task graph model is a widely used model for performance prediction and scheduling of parallel applications. However it presents two major drawbacks. The size of a task graph depends on the parameter values of the application. A scheduling algorithm takes a task graph and assign each task a processor and a starting time. As a result the task graph could become very large and increase the memory and computational requirements. Therefore, scheduling task graphs to multiprocessors is not scalable with the parameters values. Moreover, it is not an adaptive method since the scheduling solution has to be recomputed when target machine or program parameters change. In this thesis we address these two problems for regular task graphs by using an an intermediate model called parameterized task graph (PTG). A PTG is a compact and symbolic representation of some scientific applications task graphs. It uses parameters that have to be instantiated when building the task graph. Our contributions are in three areas: (1) We have designed an algorithm for scheduling the PTG. The memory cost of the scheduling is then greatly reduced. We have integrated this algorithm in a dynamic scheme in order to be able to build generic programs. (2) We present a heuristic called SLC for symbolically allocating PTGs. We guarantee that the found allocation is made of linear clusters. The time and memory cost of the allocation is then independent of to the parameter values. (3) A code generator prototype that builds a multi-threaded program which executes the allocation found by SLC has been carried out. Thus, we obtain a generic portable parallel code that works for all the program parameter values.
  • Abstract (in french):

    Le graphe de tâches (GdT) est un modèle très utilisé pour la prédiction de performance et l'optimisation d'applications parallèles. Il presente cependant deux désavantages. La taille d'un GdT dépend de la valeur des paramètres de l'application qu'il modélise. Un algorithme d'ordonnancement statique prend en entrée un GdT et affecte, à chaque tâche, un processeur et une date de début d'exécution. La durée du calcul de l'ordonnancement ainsi que le coût mémoire dépendent de la taille du graphe et donc de la valeur des paramètres de l'application. Une telle approche n'est pas extensible car pour les grandes valeurs des paramètres le graphe de tâches correspondant peut ne pas tenir en mémoire. Cette méthode n'est pas non plus adaptative car un changement de machine cible ou des paramètres du programme impose de recalculer l'ordonnancement. Pour apporter une réponse à ces deux problèmes nous avons étudié un modèle intermédiaire : le graphe de tâches paramétré (GTP). Un GTP est une représentation compacte et symbolique des graphes de tâches issus de certaines applications de calcul scientifique. Il utilise les paramètres du programme qui doivent être instanciés pour construire le GdT. Nos travaux se décomposent en trois volets. (1) Nous avons conçu un algorithme d'ordonnancement du GTP. Le coût mémoire de l'ordonnancement se trouve alors grandement réduit. Cet algorithme est intégré dans un schéma dynamique pour permettre la construction de programmes génériques. (2) Nous présentons une heuristique d'allocation symbolique du GTP appelée SLC. Nous garantissons que cette allocation forme des grappes linéaires. Le temps et le coût mémoire de l'allocation sont alors indépendants de la valeur des paramètres. (3) Nous avons réalisé un prototype de générateur de code qui produit un programme multithreadé se conformant à l'allocation trouvée par SLC. Nous obtenons ainsi un code parallèle portable et générique qui fonctionne pour toutes les valeurs des paramètres du programme.
  • Keywords:

    Parameterized Task Graphs, Dynamic Scheduling, Symbolic Allocation, Distributed Memory Parallel Computers, Task Parallelism, Code Generation.
  • Keywords (in french):

    Graphes de Tâches Paramétrés, Ordonnancement Dynamique, Allocation Symbolique, Ordinateurs Parallèles à Mémoire Distribuée, Parallélisme de Tâches, Génération de Code.
  • Availability: Electronic copy only.
  • Size: 132p
  • Format: Compressed PostScript
  • Get it

Interprétation de l'analyse statique en théorie des types.

  • By: Frederic Prost
  • Number: PhD1999-09
  • Date: December 1999
  • Abstract:

    Static analyses of functional programs such as dead code or binding time are important to perform valuable program optimizations. Many type inference based systems have been proposed to perform those analyses. The idea is to use types as skeletons where annotations are added. Although all these systems share common features, there is not yet a generic framework being able to give a uniform approach to this field. This lack of understanding leads to problems due to the fact that typing constraints hamper accurate analyses. Moreover, only simply typed calculus are considered~: it shortens severely the range of these techniques. This thesis is a theoretical study of relations between typing and analysis of programs. We show how to formalize program dependencies in type theory. We propose a generic system that can be instantiated into several analyses. Our type system is more powerful and more accurate than previous ones. Moreover, by the means of Pure Type Systems, we give a canonical formalization of the techniques used. It allows a generalization of our results to the $\lambda$-cube.
  • Abstract (in french):

    Une manière courante de faire de l'analyse statique de programmes fonctionnels typés consiste à modifier le système de typage en ajoutant des annotations aux types. Les annotations décrivent diverses propriétés intentionnelles ou extensionnelles de la sémantique du programme. Les types servent de squelettes sur lesquels on pose les annotations. Il existe dans la littérature un grand nombre de systèmes utilisant les types pour l'analyse. Leur diversité tient à la fois au fait que les systèmes de types sous-jacents sont différents, et au fait qu'il existe de nombreux types d'analyses. Bien que tous ces systèmes partagent des points communs, il n'existe pas de formalisme permettant d'en donner une vision unifiée. Ce manque de compréhension sur les interactions entre typage et analyse induit des limitations sur la finesse des analyses produites, car le typage engendre des contraintes qui vont à l'encontre de la précision des analyses. De plus, dans la majorité des cas seuls des langages simplement typés sont étudiés, ce qui limite le champ d'application de ce type de technique. Cette thèse est une étude théorique des relations qui existent entre le typage et l'analyse d'un programme. Nous y montrons comment modéliser les dépendances internes d'un programme dans la théorie des types. Nous y proposons un système de types générique qui peut s'instancier en différentes analyses précédemment étudiées. Le système de types obtenu se révèle à la fois plus expressif (il contient le système $F$), et plus précis (certaines analyses impossibles à effectuer auparavant sont possibles). Enfin, au travers des systèmes de types purs (Pure Type Systems), une formalisation canonique des techniques employées permet de délimiter précisément le champ du possible pour les analyses basées sur le typage.
  • Keywords:

    Type Theory, Statical Analysis, Functional Programming, Dead-Code Analysis, Pure Type Systems, Logic, Curry-Howard isomorphism, Non interference.
  • Keywords (in french):

    Théorie des Types, Analyse statique, Programmation Fonctionnelle, Code Mort, Pure Type Systems, Sémantique. $\lambda$-calcul, Annotations, Logique, Isomorphisme de Curry-Howard, Non-Interférence.
  • Availability: Electronic copy only.
  • Citation: .
  • Size: 135p
  • Format: Compressed PostScript
  • Get it

Compilation des langages à parallélisme de données : gestion de l'équilibrage de charge par un exécutif à base de processus légers.

  • By: Christian Perez
  • Number: PhD1999-10
  • Date: December 1999
  • Abstract:

    Data parallel languages are suitable for architecture independent parallel programs. Thus, they offer a better portability to applications. However, these languages offer very little support for load balancing problems. In High Performance Fortran, a user has to explicitly insert data redistribution in the application code. Besides, data redistributions are expensive operations. Last, there is no standard for taking into account machine and network heterogeneity. The contribution of this thesis is the design and implementation of a solution that allows generic load balancing policies to be integrated into the execution of data parallel programs. The interface is designed by considering data parallel programs as a set of medium grain-size communicant activities. The integration is performed without interference with the application code thanks to non intrusive load balancing policies. Our task is to let activities to be preemptively moved. Our choice has been to implement activities using threads. The reasons are the possibility of a fast implementation and the very good performances obtained by threads. Also, we felt encouraged to investigate this approach thanks to the existence of environments like PM2, that provides thread migration. We have implemented our proposal within an HPF compiler (Adaptor) and a C* compiler (UNH-C*). These two implementations have mainly needed runtime modifications but also source-to-source compiler modifications for the UNH-C* compiler. Last, we have validated our design and implementation with four application kernels: the Partial Gaussian elimination, the Mandelbrot application, a flame combustion simulation and an imagery application (the dividing cubes). The performances reported show the relevance of our proposal.
  • Abstract (in french):

    Les langages à parallélisme de données offrent une opportunité d'écrire des programmes parallèles qui ne dépendent pas d'un modèle particulier d'architectures. Ils permettent ainsi une meilleure portabilité des applications. Malheureusement, ces langages n'offrent pas ou peu de support pour les problèmes d'équilibrage de charge. Dans le langage High Performance Fortran, l'utilisateur doit explicitement insérer dans son code des redistributions de données. De plus, les redistribution sont des opérations coûteuses. Enfin, il n'a pas de moyen standard de prendre en compte l'hétérogénéité des machines et des réseaux. La contribution de cette thèse est de proposer et de mettre en oeuvre une solution qui permette d'intégrer les politiques d'équilibrage de charge génériques à l'exécution de programme à parallélisme de données. L'interface est réalisée en considérant les programmes à parallélisme de données comme un ensemble d'activités communicantes de grain moyen. L'intégration est réalisée sans interférence avec le code utilisateur. Le mérite en revient aux politiques d'équilibrage de charge non intrusives. Pour notre part, nous devons permettre aux activités d'être déplacées préemptivement. Notre choix a été d'implanter les activités par des processus légers. Les raisons ont été la possibilité d'une mise en oeuvre rapide et les performances que permettent les processus légers. La dernière raison a été l'existence d'environnements fournissant la migration de processus légers comme PM2. Nous avons implanté la proposition dans un compilateur HPF (Adaptor) et compilateur C* (UNH-C*). Ces deux implantations ont nécessité essentiellement des modifications de l'exécutif mais aussi du compilateur source à source pour le cas du compilateur C*. Enfin, nous avons validé la proposition ainsi que la chaîne de compilation sur quatre noyaux applications~: le pivot partiel de Gauss, l'application de Mandelbrot, une simulation de combustion et une application d'imagerie (les dividing cubes). Les mesures réalisées montrent la pertinence de la proposition.
  • Keywords:

    Parallelism, Data Parallel Languages, Load Balancing, Compiler, Runtime, Thread Migration, Distributed Memory Machines.
  • Keywords (in french):

    Parallélisme, Langage à Parallélisme de Données, Equilibrage de Charge, Compilateur, Exécutif, Migration de Processus Légers, Machines à Mémoire Distribuée.
  • Availability: Electronic copy only.
  • Size: 161p
  • Format: Compressed PostScript
  • Get it

Algorithmique sur graphes d'automates: election d'un chef, simulations.

  • By: Codrin Nichitiu
  • Number: PhD1999-11
  • Date: December 1999
  • Abstract:

    We present a few contributions to Graph Automata (GA) algorithmics, mainly for the problem of Leader Election, and for the study of GA simulations, in order to advance the study of some questions of complexity. A GA is a (regular, infinite) graph with vertices having each a copy of the same (fixed) Finite State Automaton (FSA). The FSA's are synchronized, their input alphabet is the set of d-uples of the states of the neighbors, where d is the degree of the graph, and a configuration is the function giving the current state of each vertex. The Leader Election consists in finding a set of states and a transition function of the FSA such that starting from a configuration where all vertices are in the same state, by iterating the GA a number of steps, we reach a configuration where one and only one vertex is in a special state called leader, and the others, in special states called soldiers. We present algorithms for some euclidien and hyperbolic graph classes, in linear and quadratic time. A GA simulation by another GA represents the capability of ``mimicking'' its behaviour, that is the existence of a bijection between the evolution graph (a part of it) of the simulating GA and the evolution graph of the simulated GA. The evolution graph of a GA is the graph whose vertices are the configurations of the GA, and whose arcs represent the one-step iterations from a configurations to another one. We show equivalence links between the existence of particular types of simulations and isomorphims properties of the graphs, and give effective simulations for a class of regular hyperbolic graphs, to study a possible complexity hierarchy.
  • Abstract (in french):

    Dans cette thèse, nous présentons quelques contributions à l'algorithmique sur des graphes d'automates, notamment pour le problème dit d'élection d'un chef, ainsi que pour l'étude de simulations d'un graphe par un autre, afin d'aider à éclaircir des questions de complexité. Un graphe d'automates est un graphe (régulier, infini) dont les sommets sont munis d'une copie d'un même automate fini fixé. Les automates finis sont synchrones, leur alphabet d'entrée est l'ensemble de $d$-uplets des états des voisins, avec $d$ le degré du graphe, et une configuration est la fonction donnant l'état courant pour chaque sommet. L'élection du chef consiste à trouver un ensemble d'états et une fonction de transition de l'automate fini afin qu'à partir d'une configuration où tous les sommets sont dans le même état, on aboutisse par itérations à une configuration où un seul sommet est dans un état spécial nommé chef, et les autres, dans des états spéciaux nommés soldats. Nous présentons des algorithmes pour quelques classes de graphes euclidiens et hyperboliques, en temps linéaire et en temps quadratique. Une simulation d'un graphe d'automates par un autre représente le fait de <> son comportement, c'est-à-dire le fait de pouvoir envoyer le graphe d'évolution d'un des graphes sur celui de l'autre, bijectivement. Le graphe d'évolution est un graphe dont les sommets sont les configurations du graphe d'automates et les arcs donnent les itérations d'une configuration à une autre. Nous prouvons des liens d'équivalence entre l'existence des simulations de types particuliers et des propriétés d'isomorphisme de graphes, et donnons des simulations effectives pour une classe de graphes réguliers hyperboliques, en vue de l'étude d'une hiérarchie de complexité.
  • Availability: Electronic copy only.
  • Size: 86p
  • Format: Compressed PostScript
  • Get it

Parallélisation automatique par insertion de directives.

  • By: Georges Silber
  • Number: PhD1999-12
  • Date: December 1999
  • Abstract:

    The context of this work is automatic parallelization by directives insertion, that is to say high level code source transformations where parallelism is expressed by directives given to the compiler. This text exposes three contributions to this domain. The first two contributions are extensions to the polyedric model used to represent loop nests. The first contribution extends the objective function to the research of fully permutable loops, preliminary step before the appliance of a transformation called tiling used to modify the grain of parallelization. The second extension is a new type of graph, the Mixed Dependence Graph, allowing the representation of non static control codes, where an expression contained into a control structure (if or do) is involved into a data dependence. We present a method using this graph to suppress anti dependences involving a control structure by adding extra memory. The third contribution of this thesis is a tool called Nestor aimed at easing the implantation of source to source Fortran code transformations. An extension of Allen, Callahan, and Kennedy's parallelisation algorithm using the mixed dependence graph has been implemented in our tool.
  • Abstract (in french):

    Dans cette thèse, nous nous sommes placés dans le cadre de la parallélisation automatique par insertion de directives, c'est-à-dire des transformations de code au niveau du code source où le parallélisme est exprimé par des directives données au compilateur. Ce document expose trois apports à ce domaine. Les deux premiers apports sont des extensions au modèle polyédrique de représentation des nids de boucles imbriquées. La première extension se situe au niveau de la fonction objective. Notre objectif est la recherche de boucles complètement permutables, transformation nécessaire à une transformation appelée tiling permettant de modifier le grain de la parallélisation. La deuxième extension présente un nouveau type de graphe, le graphe des dépendances mixte, permettant de traiter les codes à contrôle non statique, c'est-à-dire les codes où des expressions de structures de contrôle (if ou do) sont impliquées dans des dépendances de données. En utilisant ce graphe, nous présentons une méthode pour introduire de la mémoire temporaire, ce qui permet de << casser >> les anti dépendances impliquant des structures de contrôle. Le troisième apport de cette thèse est un outil appelé Nestor destiné à faciliter l'implantation de transformations source à source de programmes Fortran. Une extension de l'algorithme de parallélisation d'Allen, Callahan et Kennedy utilisant le graphe des dépendances mixte a été implantée dans notre outil.
  • Availability: Electronic copy only.
  • Size:160p
  • Format: Compressed PostScript
  • Get it