Automates cellulaires, information et chaos.

  • By: Bruno MARTIN
  • Number: PhD2001-01
  • Date: January 2001
  • Abstract:

    Starting from the available classifications of cellular automata, we improve the best one. Thanks to a measure on the set of configurations and to a shift-invariant pseudo-distance, we introduce the notion of $\mu$-sensitivity to initial conditions. This notion allows us to show that some rules are chaotic or non chaotic depending on the initial configuration. We also introduce the apparent entropy notion which explains why the evolution of cellular automata looks complex. Finally, we prove new results on algebraic classifications by pointing out a conservation law for the particles in Wolfram's rule $54$.
  • Abstract (in french):

    En nous appuyant sur les classifications des automates cellulaires déjà proposées, nous affinons la plus élaborée. Grâce à une mesure sur l'ensemble des classifications et à une pseudo-distance invariante par décalage, nous introduisons la notion de $\mu$-sensibilité aux conditions initiales. Cela permet de montrer que certaines règles sont à la fois chaotiques et non chaotiques selon la configuration de départ. Nous introduisons également la notion d'entropie apparente qui exprime pourquoi en observant l'évolution d'un automate cellulaire, on la ressent comme complexe. Enfin, nous poursuivons l'étude des classifications algébriques existantes en mettant en évidence une loi de conservation des particules dans la règle $54$ de Wolfram.
  • Keywords:

    Cellular Automata, Classification, Chaos.
  • Keywords (in french):

    Automate Cellulaire, Classification, Chaos.
  • Availability: Electronic copy only.
  • Size: 125p
  • Format: Compressed PostScript
  • Get it

Influence du réseau spatial sur le comportement d'un système dynamique : la fourmi de Langton.

  • By: Anahi GAJARDO-SCHULZ
  • Number: PhD2001-02
  • Date: June 2001
  • Abstract:

    In this thesis, the interest is centered in a particular dynamical system: the Langton's ant, which has been principally studied in statistical physics. From more than a thenth of years, many curious ans interesting phenomena has been remarked, but there is still a lack of exact results. The system consists of an automaton (the ant) that walks over a planar graph whose vertices (cells) can be in one of two states, white or black. The ant's movement is entirely determined by the cell's state, and this state is switched by the ant presence. In our approach, we consider several graphs to evaluate the system complexity dependence; We have proved, through combinatory methods, that in the hexagonal grid, the ant comes back to its starting point an infinite number of times, if at the beginning all the cells are in the same state. We have studied the ant in graphs corresponding to the tessealtions of the hyperbolic and Euclidean plane by regular k-gons, the Gamma(k,d) graphs. In the Gamma(k,d) graphs, if the degree is larger than 5, we have proved that for a fixed initial position, the ant cannot reach all the cells of the graph, no matter what the states are; and that when starting with a finite amount of black cells, its trajectory eventually becomes regular. We have shown the Turing universality of the system in the case of the square an hexagonal grids. We have described the system in terms of Symbolic Dynamics. We have proved properties such as transitivity, soficity, etc... The highest complexity is attained on the square and hexagonal grids, while on the triangular grid and the Gamma(k,d) graphs of degree larger than 5, the system's behavior is simpler.
  • Abstract (in french):

    Dans cette thèse, nous nous intéressons à un système dynamique particulier, la fourmi de Langton, introduit dans le cadre de la physique statistique. Depuis plus d'une dizaine d'années ce système est très étudié, des phénomènes curieux et intéressants ont été mis en évidence, mais beaucoup d'eux restent mal compris. Il s'agit d'un graphe dont les sommets sont munis d'un état (balc ou noir), plus un automate (la fourmi) qui se déplace sur les sommets d'état. Le mouvement de la fourmi est entièrement déterminé par l'état des sommets qu'elle visite. L'objet principal de notre travail de thèse a été de faire varier le graphe sur lequel se déplace la fourmi pour voir comment la complexité du système en dépendait. Par des méthodes combinatoires, nous avons montré que sur le réseau hexagonal, partant d'une configuration vide, la fourmi revenait un nombre infini de fois à son point de départ. En outre, dans le cas des graphes Gamma(k,d) avec d plus grand que 5, la fourmi ne pouvait pas atteindre tous les sommets du graphe et que si au départ il n'y a qu'un nombre fini de sommets en état noir, sa trajectoire devenait régulière au bout d'un moment. Nous avons montré que ce système était universel pour le calcul dans le cas de la grille carrée et du réseau hexagonal. La preuve se fonde sur la simulation de portes et circuits logiques. Finalement, le système a été étudié du point de vue des systèmes dynamiques symboliques, en classifiant les graphes Gamma(k,d) selon des propriétés du système comme la transitivité, régularité du langage, etc. Notre travail confirme le fait que ce système est plus complexe lorque le graphe sous-jacent est la grille carrée et le réseau hexagonal. Le cas des graphes Gamma(k,d) ou d est plus grand que 5, est plus simple.
  • Keywords:

    .
  • Keywords (in french):

    .
  • Availability: Electronic copy only.
  • Size: 126p
  • Format: Compressed PostScript
  • Get it

Preuves et algorithmes utilisant l'arithmétique flottante normalisée IEEE.

  • By: Claire FINOT-MOREAU
  • Number: PhD2001-03
  • Date: July 2001
  • Abstract:

    Floating point numbers are used by computers to approximate real numbers. Thanks to the IEEE 754 standard, we know exactly how they are stored and used. We are thus able to elaborate computer-independant algorithms. In this thesis, we present three libraries. Two of them use an arbitrary precision which is set beforehand. The third library is adaptable in the sense that it dynamically changes the precision of each intermediate operation to deliver the target accuracy. The libraries proposed here are available on the Internet. Using the IEEE standard, we have built a general formalism on floating point numbers and derived properties on this notation. We then proove the validity of our algorithms.
  • Keywords:

    Computer Arithmetic, Floating Point Numbers, IEEE 754 Standard, Multiple Precision, Computation Library, Expansions, Adaptable Computation, Elementary Functions.
  • Keywords (in french):

    Arithmétique des Ordinateurs, Virgule Flottante, Norme IEEE 754, Multi-Précision, Bibliothèque Arithmétique, Expansions, Calcul Adaptatif, Fonctions Elémentaires.
  • Availability: Electronic copy only.
  • Size: 129p
  • Format: Compressed PostScript
  • Get it

Conception d'un système de stockage distribué et tolérant aux pannes, pour un serveur de vidéo à la demande.

  • By: Alice BONHOMME
  • Number: PhD2001-04
  • Date: October 2001
  • Abstract:

    Recent technological progress about network and storage technology, enabled the emergence of multimedia applications. Such applications handle new data types such as audio or video. Dynamic data are different from static data (text, image, etc.): they are characterized by their large volume and their real-time constraint. They impose new requirements about storage, access techniques, etc.\ on servers. Regular data storage systems do not fulfill these requirements. Hence, new techniques for storing and managing dynamic data have been proposed. In this thesis, we specifically focus on storage issues for video data. A storage system for video data must be efficient (in order to serve several clients), scalable (adding a storage element must allow the support of new clients), economically profitable. It should moreover support the failure of components, in order to protect the clients from perturbation. This thesis introduces the design of such a system called CFS (Cluster File System). It studies its behavior and evaluates its performance. The underlying hardware architecture is a cluster of commodity PCs connected by a Myrinet high speed network. This enhances profitability and scalability. The software architecture is fully distributed among the cluster nodes. Fault tolerance management is entirely integrated within the solution. It is thus transparent to the user. We provide an extensive experimental evaluation of a preliminary prototype. The various design tradeoffs are discussed. Derived versions of the CFS system have been integrated in various industrial projects.
  • Abstract (in french):

    L'avancée technologique enregistrée ces dernières années concernant les réseaux et les technologies de stockage a permis l'émergence d'applications multimédias manipulant de nouveaux types de données tels que l'audio ou la vidéo. Ces données dynamiques sont sémantiquement différentes des données statiques (texte, images, etc.) et se caractérisent par leur volume important et leur contrainte temps-réel. Ainsi, elles imposent aux serveurs de nouveaux besoins en terme de stockage, de techniques d'accès, etc. Les serveurs de données classiques ne permettant pas de répondre à ces besoins, de nouvelles approches de stockage et de gestion pour les données dynamiques ont été proposées. Nous nous intéressons ici plus particulièrement aux aspects de stockage pour des données vidéo. Un système de stockage pour la vidéo doit être performant (pour pouvoir servir plusieurs clients), extensible (le rajout d'un élément de stockage doit permettre le support de nouveaux clients), économiquement rentable et enfin tolérer les pannes de ses composants afin de ne pas interrompre les flux des clients. L'objectif de cette thèse est de concevoir un tel système, d'étudier son fonctionnement et d'évaluer ses performances. Afin d'avoir un système économiquement rentable et extensible, l'architecture matérielle choisie est une grappe de PC connectés par le réseau haut débit Myrinet. L'architecture logicielle est totalement distribuée sur les noeuds de la grappe. La gestion de la tolérance aux pannes est entièrement intégrée dans la solution et donc transparente à l'utilisateur. Un prototype appelé CFS (Cluster File System) construit selon cette approche est présenté et évalué. L'étude expérimentale approfondie permet d'évaluer les divers compromis de conception.
  • Keywords:

    Video Server, Storage System, Fault Tolerance, Performance Study.
  • Keywords (in french):

    Serveur Vidéo, Système de Stockage, Tolérance aux Pannes, Etude de Performance.
  • Availability: Electronic copy only.
  • Size: 137p
  • Format: Compressed PostScript
  • Get it

DSM-PM2: une plate-forme portable pour l'implémentation de protocoles de cohérence multithreads pour systèmes à mémoire virtuellement partagée.

  • By: Gabriel ANTONIU
  • Number: PhD2001-05
  • Date: November 2001
  • Abstract:

    In their traditional flavor, Distributed Shared Memory (DSM) libraries allow a number of separate processes to share a common address space using a consistency protocol according to a semantics specified by some given consistency model: sequential consistency, release consistency, etc. The processes may usually be physically distributed among a number of computing nodes interconnected through some communication library. Most approaches to DSM programming assume that the DSM library and the underlying architecture are fixed, and that it is up to the programmer to fit his program with them. This static view does not allow experimentations with alternative implementations. The contribution of this thesis consists in proposing a generic impementation and experimentation platform called DSM-PM2, which allows both the application and the underlying DSM consistency protocol to be co-designed and tuned for performance. This platform is entirely implemented in software, in user-space. It is portable across a large number of cluster architectures. It provides the basic blocks for implementing and evaluating a large number of multithreaded consistency protocols within a unified framework. Three consistency models are currently supported: sequential consistency, release consistency and Java consistency. Several performances studies have been carried out with multiple multithreaded applications on different clusters, in order to evaluate the proposed consistency protocols. The platform has been validated as a target for a Java compiling system for distributed architectures, called Hyperion.
  • Abstract (in french):

    Dans leur présentation traditionnelle, les systèmes à mémoire distribuée virtuellement partagée (MVP, en anglais DSM) permettent à des processus de partager un espace d'adressage commun selon un modèle de cohérence fixé: cohérence séquentielle, à la libération, etc. Les processus peuvent habituellement être distribués sur des noeuds physiquement distincts et leurs interactions par la mémoire commune sont implémentées (de manière transparente) par la MVP, en utilisant une bibliothèque de communication. Dans la plupart de travaux dans ce domaine, il est sous-entendu que la MVP et l'architecture sous-jacente sont données. Le programmeur doit alors adapter son application à ce cadre fixe, afin d'obtenir une exécution efficace. Cette approche impose des limitations statiques et ne permet pas de comparer des approches alternatives. La contribution de cette thèse consiste à proposer une plate-forme générique d'implémentation et d'expérimentation appelée DSM-PM2, qui permet de développer et d'optimiser conjointement les applications distribuées et le(s) protocole(s) de cohérence de la MVP sous-jacente. Cette plate-forme, implémentée entièrement au niveau logiciel, est portable sur plusieurs architectures de grappes hautes performances. Elle fournit les briques de bases nécessaires pour implémenter et évaluer une large classe de protocoles de cohérence multithreads dans un cadre unifié. Trois modèles de cohérence sont actuellement supportés: la cohérence séquentielle, la cohérence à la libération et la cohérence Java. Plusieurs études de performance ont été effectuées à l'aide d'applications multithreads pour l'ensemble des protocoles proposés, sur différentes plates-formes. DSM-PM2 a été validé par son utilisation en tant que cible d'un système de compilation Java pour des grappes appelé Hyperion.
  • Keywords:

    Parallelism, threads, DSM, PM2, iso-address, migration, Hyperion, Java compiling.
  • Keywords (in french):

    Parallélisme, processus légers, threads, mémoire virtuellement partagée, DSM, PM2, iso-adresse, migration, Hyperion, compilation Java.
  • Availability: Electronic copy only.
  • Size: 134p
  • Format: Compressed PostScript
  • Get it

Algorithmique du décalage d'instructions.

  • By: Guillaume HUARD
  • Number: PhD2001-06
  • Date: December 2001
  • Abstract:

    The constant evolution of processors architectures, with superscalar, instruction-level parallelism, prediction and speculation capabilities and the multiple number of levels in the memory hierarchy give an increasing importance to the work of the compiler. In this thesis we deal with source program transformations, intended to optimization within the compilation process, and especially with a transformation known as loop shifting. This transformation is used as a basis for software pipelining, it has an incidence on the instruction level parallelism and registers usage. It is also involved as a component of loop parallelization techniques based on affine schedules. In this thesis we have tried to reach a better understanding of the possibilities that loop shifting has to offer, to know which goals it is able to score, and which problems remain hard. To this intent, we have studied loop shifting within a variety of contexts, more or less close to each other, and we provide a contribution for each of them.
    In the context of software pipelining, we give a polynomial algorithm to find the loop shifting leading to as much instruction-level parallelism as possible, and we perform an experimental study of its absolute efficiency, with the help of PASTAGA (french translation of ``Platform for statistical analysis and algorithms testing on random graphs''), a tool we developed for this purpose. In the contexts of register usage (stage scheduling), loop parallelization and locality, we give answers in each case to loop shifting problems: complexity, exact solutions and heuristics.
  • Abstract (in french):

    L'évolution constante des processeurs vers des architectures proposant des capacités superscalaires, de parallélisme au niveau des instructions, de prédiction, de spéculation et la multiplication des niveaux de hiérarchie mémoire donnent de plus en plus d'importance au travail du compilateur. Dans cette thèse, nous nous intéressons aux transformations du programme source destinées à l'optimisation dans la chaîne de compilation, et plus particulièrement à une transformation appelée décalage d'instructions. Cette transformation sert de base au pipeline logiciel, elle a une influence sur le parallélisme au niveau des instructions et l'utilisation des registres. Elle intervient également comme composante des techniques de parallélisation de boucles par ordonnancement affine. Nous avons voulu mieux comprendre les perspectives offertes par le décalage d'instructions, savoir quels objectifs il permettait d'atteindre mais aussi savoir quels problèmes de décalage restaient difficiles. Pour cela nous avons étudié le décalage d'instructions dans plusieurs contextes plus ou moins proches, et apporté des contributions à chacun d'entre eux.
    Dans le cadre du pipeline logiciel, nous proposons un algorithme polynomial pour déterminer le décalage le plus à même de produire un maximum de parallélisme au niveau des instructions, et une étude expérimentale de l'efficacité absolue de la technique à l'aide de l'outil logiciel que nous avons réalisé dans ce but : PASTAGA (pour Plate-forme d'Analyse Statistique et de Tests d'Algorithmes sur Graphes Aléatoires). Dans le cadre de l'utilisation des registres (stage scheduling), de la parallélisation de boucle et de la localité, nous apportons des réponses aux problèmes de décalage d'instructions associés : complexité, solutions exactes, approximations.
  • Keywords:

    Compilation, Program Transformations, Parallelism, Loop Shifting, Retiming, Software Pipelining, Scheduling, Automatic Parallelization.
  • Keywords (in french):

    Compilation, Transformations de Programme, Parallélisme, Décalage d'Instructions, Retiming, Pipeline Logiciel, Ordonnancement, Parallélisation Automatique.
  • Availability: Electronic copy only.
  • Size: 184p
  • Format: Compressed PostScript
  • Get it

Complexité et expressibilité sur les réels.

  • By: Hervé FOURNIER
  • Number: PhD2001-07
  • Date: December 2001
  • Abstract:

    This thesis aims at understanding some fundamental aspects of algorithmics over the real numbers. The first part deals with the Blum, Shub and Smale model of computation over the reals. As in the boolean case, the question P=NP seems difficult over the real field, but also over the reals with addition and order. Being unable to solve these problems, we try to relate them to each other: such results are called transfer theorems. We obtain several results relating the real and boolean classes. For example we show the equivalence between P=NP over the reals with addition and order and the non-uniform version of the boolean hypothesis P=NP. The existence of sparse NP-complete problems over the reals is also studied. The second part deals with finite models embbeded in infinite structures. This work is motivated by the constraint databases model. We study the quantifier rank needed to express some parity and connexity queries for a finite graph embedded in the reals or complex numbers with various operations. We also study under which condition the quantification over the the underlying structure, the natural domain, and quantification over the finite model, the active domain, give the same expressive power. We show that strongly minimal structures and differentially closed fields have these properties. The proofs are effective in that they yield an algorithm to transform a natural formula into an active equivalent one.
  • Abstract (in french):

    Le but de cette thèse est de comprendre certains aspects fondamentaux de l'algorithmique sur les nombres réels. La première partie de la thèse a pour cadre le modèle de calcul proposé par Blum, Shub et Smale. Comme dans le cas booléen, la question P=NP semble difficile sur le corps des réels, mais aussi sur les réels avec addition et ordre ou encore sur le corps des complexes. À défaut d'être en mesure de résoudre ces problèmes, on essaie de les relier entre eux : ce sont les théorèmes de transfert. Nous obtenons des résultats reliant des hypothèses de complexité structurelle réelle à des hypothèses de complexité booléenne. Nous montrons en particulier l'équivalence de P=NP sur les réels avec addition et ordre et de la version non-uniforme de l'hypothèse booléenne P=NP. La question de l'existence de problèmes NP-complets creux, ici de petite dimension, est également discutée pour diverses réductions. La seconde partie se place dans le contexte d'un modèle fini plongé dans une structure infinie. Les problèmes étudiés sont motivés par le modèle des bases de données contraintes. Nous étudions le rang de quantification de certaines requêtes de parité et de connexité pour un graphe plongé dans les réels ou les complexes munis de diverses opérations. Nous étudions aussi à quelle condition quantifier sur le modèle fini, le domaine actif, ou quantifier sur le domaine de la structure sous-jacente, le domaine naturel, donnent le même pouvoir d'expression. Nous énonçons une propriété suffisante pour qu'une telle situation se produise, et nous démontrons que les structures fortement minimales, ainsi que les corps différentiellement clos, ont cette propriété. Les démonstrations sont effectives au sens où elles permettent de construire un algorithme transformant une formule naturelle en une formule active équivalente.
  • Keywords:

    Computation over the Reals, BSS Model, Structural Complexity, Embedded Finite Models, Constraint Databases.
  • Keywords (in french):

    Calcul sur les Réels, Modèle BSS, Complexité Structurelle, Modèle Fini Plongé dans une Structure, Bases de Données Contraintes.
  • Availability: Electronic copy only.
  • Size: 102p
  • Format: Compressed PostScript
  • Get it

Recouvrement des communications~: du matériel au logiciel.

  • By: Frédérique CHAUSSUMIER-SILBER
  • Number: PhD2001-08
  • Date: December 2001
  • Abstract:

    In this thesis we study communication overlap on distributed memory parallel machines. Communication overlap is very often used to reduce execution times of parallel programs. We first study a fast implementation of the communication library MPI on a pile of PCs interconnected with a fast network. To begin with, we show that using the available hardware overlapping data transfer over the network is possible. Secondly, we explain why, despite of the overlap provided by the hardware and basic communication software the available MPI interface does not provide any overlap. In a second time we validate equations modelising software pipelining gain given by Zory, through the Sweep3D application. Using this application we showed that using software pipelining on $P$ processors on large data sets can reduce the execution time nearly $P$ times. The last part of this thesis tackles the problem of determining before execution the best processor configuration (mono, bi or tri-dimensional space) for wavefront applications. We modelise the problem with solvable time equations of wavefront for each processor configuration.
  • Abstract (in french):

    Le but de cette thèse est l'étude des recouvrements des communications sur des machines parallèles à mémoire distribuée. Les recouvrements des communications sont des techniques très utilisées dans le but d'accélérer les exécutions de programmes parallèles. Notre première contribution est l'étude détaillée d'une implantation efficace de la bibliothèque de communication MPI sur une grappe de PC interconnectée par un réseau rapide. Cette étude montre tout d'abord que le matériel permet de recouvrir le transfert des données sur le réseau. Dans un deuxième temps, nous montrons pourquoi le logiciel de communication inter-processus, MPI, empêche le recouvrement des communications par le calcul. La sémantique des communications et l'implication du processeur de calcul dans la communication en sont les principales causes. Notre deuxième contribution est la validation des équations de gain d'un pipeline modélisées par Zory, par l'intermédiaire de l'application Sweep3D. Cette application nous a permis de montrer que sur des données de grande taille, l'utilisation de pipelines logiciels sur $P$ processeurs, peut apporter un gain en temps d'exécution s'approchant d'un facteur $P$. Notre troisième contribution est l'évaluation a priori de la meilleure configuration de l'espace des processeurs, c'est-à-dire mono, bi ou tridimensionnel. En établissant les équations des temps d'exécution d'une application par vague pour ces trois types de distribution en fonction des paramètres de la machine cible et de l'application, nous pouvons déterminer la distribution qui donnera le plus petit temps d'exécution.
  • Keywords:

    MPI, Pile of PCs, Communication Overlap, Software Pipelining.
  • Keywords (in french):

    Parallélisme, MPI, Grappe de PC, Recouvrements des Communications, Pipelines Logiciels.
  • Availability: Electronic copy only.
  • Size: 190p
  • Format: Compressed PostScript
  • Get it

Stratégies statiques (algorithmes et ordonnancement) pour plates-formes hétérogènes.

  • By: Vincent BOUDET
  • Number: PhD2001-09
  • Date: December 2001
  • Abstract:

    The main goal of parallelism is to use several resources simultaneously. When trying to transform a sequential program into a parallel one, several problems arise, including alignment, distribution, data partitioning and task scheduling. These problems become even more complex when the physical resources are heterogeneous. In this thesis, we investigate static strategies in order to build linear algebra libraries targeted to heterogeneous platforms. In the first part of the thesis, we show that the alignment step should not be conducted without considering the distribution. We provide an efficient algorithm that handles simultaneously alignment and data/computation distribution to ensure that the potential parallelism is preserved. When we search a good distribution scheme, we are confronted to the load balancing problem. First we study this problem in the case of grids. For 1D grid, we give an optimal solution for this problem. However, in the case of a 2D grid, this problem is NP-complete, but we propose an efficient heuristic. Next, we relax the grid constraint in order to find an optimal data partitioning. In this case, depending upon the objective function, we propose either optimal algorithms or guaranteed heuristics. In a last part, we study the scheduling and allocation problems. In the context of the standard communication model, we propose a new efficient heuristic that generates fewer communications than the classical heuristics from the literature. Finally, we introduce a more realistic communication mode: we establish some complexity results before proposing an efficient scheduling heuristic.
  • Abstract (in french):

    En parallélisme, l'objectif consiste à utiliser différentes ressources simultanément, afin de diminuer autant que possible le temps d'exécution d'un calcul et de permettre de traiter des problèmes de plus grande taille. Lorsque nous voulons paralléliser de manière automatique un programme séquentiel, de nombreux problèmes se posent à nous, comme par exemple l'alignement, la distribution, le partitionnement des données ou bien l'ordonnancement des calculs. Ces problèmes liés à la parallélisation automatique se posent de manière encore plus complexe lorsque les ressources dont nous disposons sont hétérogènes. Dans ce contexte, nous proposons ici des stratégies statiques de manière à constituer des bibliothèques de calculs linéaires pour plates-formes hétérogènes. Ainsi, dans une première partie, nous montrerons qu'il est plus judicieux de ne pas séparer l'étude de l'alignement de celui de la distribution quitte à faire un compromis entre les deux pour nepas séquentialiser l'exécution de notre programme. Nous présenterons donc un nouvel algorithme qui résout ces deux problèmes simultanément et ceci de manière polynomiale dans de nombreux cas. Dans les chapitres~3 et~4, nous étudierons les problèmes d'équilibrages de charges liés à la recherche d'une bonne distribution des données. Dans un premier temps, nous nous contraindrons à ne considérer que des découpages en grille. Dans le cas d'une grille 1D, nous donnerons une solution optimale à ce problème. Dans le cas d'une grille bidimensionnelle, le problème s'avère être NP-complet et nous proposerons une heuristique efficace pour en donner une solution approchée. Dans un second temps, nous supprimerons la contrainte de grille afin de chercher un partitionnement libre des données. Nous étudierons ce problème dans différents modèles de réseaux et nous en proposerons des solutions optimales ou des heuristiques garanties. Enfin, dans une dernière partie, nous nous interesserons au problème de l'ordonnancement et de l'allocation. Dans le cadre d'une modélisation simple du réseau, nous proposerons une nouvelle heuristique efficace générant moins de communications. Puis, dans le cadre d'un modèle plus réaliste, nous établirons plusieurs résultats de complexité avant de proposer une heuristique efficace.
  • Keywords:

    Automatic Parallelization, Alignment, Distribution, Heterogeneous Resources, Algorithmic, Complexity, Optimisation Problems, Tasks Graph, Scheduling, Mapping, Communication Model, Matrix-Matrix Multiplication, LU and QR Decomposition, Linear Algebra.
  • Keywords (in french):

    Parallélisation Automatique, Alignement, Distribution, Ressources Hétérogènes, Algorithmique, Complexité, Problèmes d'Optimisation, Graphe de Tâches, Ordonnancement, Partitionnement, Allocation, Modèle de Communication, Produit de Matrices, Décomposition LU, Décomposition QR, Algèbre Linéaire.
  • Availability: Electronic copy only.
  • Size: 163p
  • Format: Compressed PostScript
  • Get it