Conception et mise en oeuvre d'un serveur parallèle de séquences audiovisuelles.

  • By: Ahmed Mostefaoui
  • Number: PhD2000-01
  • Date: January 2000
  • Abstract:

    Technological advances over the past years have made it possible to build new applications handling continuous data (audio and video). Because of their huge volume and their continuous delivery requirement, storing and accessing continuous data has been a major issue. The purpose of this thesis is to address this issue, in the News-On-Demand context, by designing and implementing a high scalable multimedia server. This thesis starts with a large presentation of the state-of-the-art techniques and approaches used in the video server domain. This presentation is completed by a description of some prototypes from academic origin as well as commercial one. After presenting the design of the video server (logical model), we concentrate on three key points which have a direct effect on the target application (News-On-Demand) : (a) Firstly, we tackled the problem of cache management in the server by proposing a novel approaches. These approaches include, in addition to run-time information (e.g., access frequencies), semantic relations between the accessed objets. The performances results show clearly the effectiveness of the proposed approaches (the improvement is about 18% compared to classical approaches). (b) Secondly, we addressed the problem of multi-clips query optimization at the server side. We proposed a new heuristic which take advantage from sharing clips (biggybacking). Compared to a traditional approach, the proposed heuristic save up to 20% of the video server bandwidth. This result allows the server to support more concurrent queries. (c) Thirdly, we implemented, using a parallel multithreaded environment (PM2), a video server, called MINA, on top of a PC cluster interconnected by a large bandwidth Myrinet network. The experimental results, conducted on 8 PC, show an access latency time of 100 milliseconds and 168 simultaneous MPEG I (1.5 Mbps) clients.
  • Abstract (in french):

    Dans ma thèse, je me suis intéressé au stockage et à l'accès isochronique aux séquences audiovisuelles archivées. Cette problématique m'a conduit à concevoir et à mettre en oeuvre un serveur de séquences audiovisuelles. Après avoir proposé une architecture fonctionnelle de ce dernier qui tient compte à la fois des caractéristiques et des exigences de l'application cible, j'ai approfondi trois points clés du serveur : (a) la gestion de cache en proposant de nouvelles heuristiques basées sur des informations sémantiques et structurelles sur les objets manipulés. Les résultats des expérimentations ont montré un gain de près de 18 % par rapport aux techniques concurrentes. (b) la gestion des accès multi-séquences en développant une nouvelle heuristique. Cette dernière permet une réduction d'environ 20 % de la charge du serveur. (c) enfin, la mise en oeuvre du serveur vidéo, baptisé MINA, en choisissant une grappe de PC connectés via un réseau haut débit (Myrinet) comme plate-forme matérielle et en adoptant un environnement de développement parallèle multithreadé (pm2). Les premiers résultats d'expérimentations sur une grappe de 8 PC montrent des temps de latence d'accès de l'ordre de 165 millisecondes et une capacité totale de 168 flux vidéo (de type MPEG I) simultanés avec des disques à 6 Mo/s de bande passante.
  • Keywords:

    Video Server, Audiovisual Sequences, Parallel Multithreads Server, Multi-Clip Optimization, Cache Managment.
  • Keywords (in french):

    Serveur Vidéo, Séquences Audiovisuelles, Serveur Parallèle Multithreads, Optimisation Multi-Séquences, Gestion de Cache.
  • Availability: Electronic copy only.
  • Size: 174p
  • Format: Compressed PostScript
  • Get it

Moyens arithmétiques pour un calcul fiable.

  • By: Vincent Lefevre
  • Number: PhD2000-02
  • Date: January 2000
  • Abstract:

    In general, the result of a floating-point operation on a computer cannot be exactly represented: it must be rounded. The IEEE-754 standard requires that, when one of the four arithmetic operations is performed on numbers that can exactly be represented (called machine numbers), the system must behave as if the result were first computed exactly, then rounded. This requirement, called exact rounding, has many advantages: the results are more accurate, mathematical properties are preserved, numerical software is more portable, algorithms based on this property can be designed and proved, lower and upper bounds of results can be obtained. We aim at showing how to provide correctly rounded elementary functions (exponential, logarithm, sine, cosine...) at a reasonable cost. The result of an elementary function may be a priori very close to a machine number or the middle point of two consecutive machine numbers, and if intermediate calculations are not carried out with enough accuracy, one cannot know how to round the result. This problem is known as the Table Maker's Dilemma. We must know what precision is needed for the intermediate calculations so that the Table Maker's Dilemma never occurs. Theorems from number theory give us upper bounds on this precision, but they are much larger than the precision needed in practice. In the current state of knowledge, the only solution to find the best upper bounds is to perform exhaustive tests, which need to be parallelized because of the very large number of arguments that will be tested. We also worked on multiple precision arithmetic, which is used when the exhaustive tests would require too much computation time, and on the fast multiplication by an integer constant, useful for our tests and other fields.
  • Abstract (in french):

    Le résultat d'une opération sur ordinateur ne peut, en général, pas être représenté exactement: il doit être arrondi. La norme IEEE-754 impose que lorsque l'on effectue une des quatre opérations arithmétiques entre deux nombres représentables exactement en machine (appelés nombres machine), le système doit se comporter comme si on avait d'abord effectué le calcul exactement, puis arrondi celui-ci. Cette exigence, appelée arrondi exact, comporte de nombreux avantages: les résultats sont plus précis, les logiciels plus facilement portables, des propriétés mathématiques sont préservées, on peut construire et prouver des algorithmes en utilisant cette propriété, et obtenir des encadrements certains de résultats. Notre but est de montrer comment garantir l'arrondi exact des fonctions élémentaires (exponentielle, logarithme, sinus, cosinus, etc.) à coût raisonnable. Le résultat d'une fonction élémentaire peut être a priori très proche d'un nombre machine ou du milieu de deux nombres machine consécutifs, et si les calculs intermédiaires ne sont pas effectués avec suffisamment de précision, on ne saura pas comment arrondir. Ce problème est connu sous le nom du « Dilemme du Fabricant de Tables ». Nous cherchons donc à savoir avec quelle précision il faut effectuer les calculs intermédiaires de manière à ce que le Dilemme du Fabricant de Tables ne se produise jamais. Des théorèmes de théorie des nombres donnent des bornes sur cette précision, mais elles sont bien plus grandes que la précision nécessaire en pratique. Dans l'état actuel des connaissances, la seule solution pour trouver les meilleures bornes est d'effectuer des tests exhaustifs, qui doivent être parallélisés à cause du très grand nombre d'arguments à tester. Nous avons également travaillé sur la multiprécision, qui intervient dans les cas où les tests exhaustifs ne sont pas possibles, et sur la multiplication rapide par une constante entière, utile pour nos tests et pour d'autres domaines.
  • Keywords:

    Floating-Point Arithmetic, Elementary Functions, Rounding, Multiple Precision.
  • Keywords (in french):

    Arithmétique Virgule Flottante, Fonctions Elémentaires, Arrondis, Multiprécision.
  • Availability: Electronic copy only.
  • Size: 148p
  • Format: Compressed PostScript
  • Get it

Algorithmes d'approximation pour les télécommunications sans fil: Ordonnancement pour la dissémination de données et allocation statique de fréquences.

  • By: Nicolas Schabanel
  • Number: PhD2000-03
  • Date: January 2000
  • Abstract:

    This thesis deals with two problems issued from telecommunication: data dissemination and frequency planning.
    Data dissemination is an answer to reduce the load of information servers and networks. A fact is that most of the clients require most of the time the same information pages. In order to reduce the server and network loads due to the broadcast of the most popular pages, data dissemination reserves some special channels to broadcast systematically the most popular pages, obliviously from the effective requests. Those channels (typically wireless, cable TV,...) can be monitored simultaneously by all the clients. The problem is now to schedule the broadcasts of the different messages over these special channels. A client interested in one of these pages does not send a request but connects and monitors the special channels until the information he is interested in is broadcast. The problem consists in finding a schedule that minimizes the expected waiting time of the clients.
    This problem is a quadratic minimization problem that also models other scheduling problems such as machine maintenance scheduling or stocks supplying. In this thesis, this problem is shown to be NP-hard in general and we give approximation algorithms with proven performance guarantees: a polynomial approximation scheme for the case where all the messages have the same length, and two constant factor approximations for the case where the messages have different lengths, with and without preemption..

    Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interferes. In this thesis, we propose an approximation algorithm with proven performance guaranty for the NP-hard case where the transmitter are placed on the triangular lattice.
  • Abstract (in french):

    Cette thèse étudie deux problèmes issus des télécommunications: la dissémination de données et l'allocation de fréquences.
    La dissémination de données est une réponse apportée à la surcharge des réseaux et serveurs d'information. Le fait est que la plupart des clients demande la plupart du temps les mêmes informations. Aussi, afin d'éviter de saturer à la fois le serveur et le réseau avec la diffusion des pages les plus populaires, l'approche de la dissémination propose de réserver un certain nombre de canaux d'émission à la diffusion systématique des informations les plus populaires. Ces canaux (typiquement Hertzien, TV par câble,...) sont accessibles en simultané par tous les clients. Le problème est alors d'ordonnancer la diffusion des différentes pages d'information. Un client, intéressé par l'une de ces pages, n'émet pas de requête mais se connecte sur ces canaux réservés et attend que l'information qui l'intéresse soit diffusée. Il s'agit donc de trouver un ordonnancement qui minimise l'attente moyenne des clients.
    Ce problème est un problème de minimisation quadratique, qui modélise également d'autres problèmes d'ordonnancement tels la planification de maintenances de machines ou le réapprovisionnement de stocks. Cette thèse démontre que trouver un ordonnancement optimal est NP-dur en général, et propose des algorithmes d'approximation avec garanties de performance prouvées: un schéma d'approximation pour le cas des messages de longueur uniforme, et deux approximations à un facteur constant pour le cas où les messages ont des longueurs différentes, avec et sans préemption..

    L'allocation de fréquences consiste à allouer des fréquences aux transmetteurs d'un réseau cellulaire de sorte à ce que deux transmetteurs n'entrent jamais en interférence. Dans cette thèse, nous proposons un algorithme d'approximation avec garantie de performance pour le cas NP-dur où les transmetteurs sont disposés suivant la grille triangulaire.
  • Keywords:

    Algorithmic, Combinatorial Optimization, Approximation, Randomized Algorithms and Derandomization, Wireless Telecommunication, Data Dissemination and Push-Based Systems, Multicoloring.
  • Keywords (in french):

    Algorithmique, Optimisation Combinatoire, Approximation, Algorithmes Randomisés et Dérandomisation, Télécommunications sans Fil, Dissémination de Données, Multicoloriage. .
  • Availability: Electronic copy only.
  • Size: 238p
  • Format: Compressed PostScript
  • Get it

Optimisation des redistributions et allocation dynamique, en parallélisme de données.

  • By: Cyril Randriamaro
  • Number: PhD2000-04
  • Date: January 2000
  • Abstract:

    Programming large numerical applications on parallel distributed memory computers is rendered easier today by using high level libraries, such as ScaLAPACK, and compilers of data-parallel languages such as HPF. However, the user is responsible not only for the initial distribution of matrices across the processors, but also for the redistributions needed to maintain an even load across all processors. The objective of this thesis is to assist the user in computing automatically the initial matrix distribution at the start of processing as well as the distribution between the various subroutine calls, and also to minimize the cost of these redistributions. We propose, in a first part, an optimal schedule of communications for the distribution of matrices distributed in a "block-cyclic" manner on a processors grid. We then present an algorithm for the computation and minimization of redistributions for a graph of parallel linear algebra routine calls. We have validated these results by writing a semi-automatic tool for parallelization of Fortran applications, and testing it on clusters of workstations and parallel computers.
  • Abstract (in french):

    La programmation d'importantes applications numériques sur machines parallèles à mémoire distribuée est aujourd'hui facilitée par l'utilisation de bibliothèques de haut niveau, comme ScaLAPACK, et de compilateurs de langages data-parallèles, comme HPF. Cependant, l'utilisateur doit gérer lui-même non seulement la distribution initiale des matrices sur les processeurs, mais aussi les redistributions éventuellement nécessaires au maintien d'un équilibrage correct des charges. Cette thèse a pour objectifs d'une part, d'aider l'utilisateur en calculant automatiquement les distributions des matrices au début de l'application et entre les différents appels de routines et, d'autre part, de minimiser le coût de ces redistributions. Nous proposons, dans un premier temps, un ordonnancement optimal des communications pour la redistribution de matrices distribuées de manière bloc-cyclique sur une grille de processeurs. Nous présentons ensuite un algorithme de calcul des redistributions et de minimisation des redistributions pour un graphe d'appels de routines d'algèbre linéaire parallèle. Après le développement d'un outil de parallélisation semi- automatique d'applications Fortran, ces résultats ont été validés par des expérimentations sur grappes de stations et sur machines parallèles.
  • Keywords:

    Data-Parallelism, Distributed Matrix, Redistributions, Automatic Parallelization, ScaLAPACK, TransTool.
  • Keywords (in french):

    Parallélisme de Donnée, Matrice Distribuée, Redistribution, Parallélisation Automatique, ScaLAPACK, TransTool.
  • Availability: Electronic copy only.
  • Size: 137p
  • Format: Compressed PostScript
  • Get it

Partitionnement: optimisations de compilation et algorithmique hétérogène.

  • By: Fabrice Rastello
  • Number: PhD2000-05
  • Date: September 2000
  • Abstract:

    The goal of parallelization is to use several resources simultaneously, so as either to execute a given program faster, or to solve a larger problem. But communication overhead and load imbalance render the problem complicated. In order to increase both the locality of data references and the granularity of the computation, we aggregate neighboring tasks together inside tiles. This optimization technique is called loop tiling, and is dealt with in the first part of this thesis in three different contexts: (i) when the nested loop contains only internal dependences, we look for optimal tile size and shape that minimize the critical path length of the iteration space task graph; (ii) when the nested loop contains only external dependences, we look for a tile shape that optimizes the reuse of loaded data; (iii) we consider also tiling when removing the constraint of atomicity, and we look for a reordering of the execution of tasks within a tile, on which the latency is critically dependent.
    The difficulties of parallelization become even tougher when targeting heterogeneous computing platforms. The second part of this thesis is devoted to providing the required framework to build an extension of the ScaLAPACK library (linear algebra kernels), capable of running on top of heterogeneous networks of workstations or non-dedicated parallel machines. We investigate several algorithmic issues, we state several NP-complete results (related to some geometrical optimization problems), and we propose some guaranteed heuristics.
  • Abstract (in french):

    Le parallélisme consiste à faire usage de plusieurs ressources simultanément, afin de diminuer le temps d'exécution d'un calcul, ou de résoudre des problèmes de plus grande taille. Mais le temps de communication entre les processeurs ainsi que le déséquilibre de charge, rendent complexe la parallélisation d'un code. Ainsi, afin de réduire la latence et d'augmenter la localité, on va chercher à regrouper certains calculs, c'est à dire à; augmenter la granularité. C'est le principe du pavage, technique d'optimisation que nous abordons dans la première partie de cette thèse, dans différents contextes: soit le nid de boucles ne contient que des dépendances internes, et nous cherchons la taille et la forme de tuiles optimales minimisant le chemin critique du graphe des tâches; soit le nid de boucles ne contient que des dépendances externes, et nous cherchons la forme de tuiles qui optimise la réutilisation des données rapatriées; nous abordons aussi le problème de pavage pour des tuiles non atomiques dans lesquelles les tâches sont reordonnancées afin de minimiser la latence d'exécution.
    Les problèmes liés à la parallélisation se posent de manière encore plus complexe lorsque les ressources sont hétérogènes. Nous abordons ainsi dans une seconde partie le problème sous une approche plus algorithmique, visant la constitution de librairies de calculs linéaires sur ressources hétérogènes. Cela pose un certain nombre de problèmes d'optimisation géométrique, souvent montrés comme étant NP-complets, et pour lesquels nous proposons un certain nombre de solutions heuristiques avec garanties.
  • Keywords:

    Automatic Parallelization, Tiling, Loop Blocking, Heterogeneous Computing Platforms, Algorithmic, NP-Complete, Optimization Problems, Tasks Graph, Tiles, Bandwidth, Cache Memory, Hierarchical Tiling, VLSI Chip, Scheduling, Redundant Tasks, Dynamical Systems, Solitary Waves, Relaxation, Communication Models, LU Decomposition, QR Decomposition, Matrix Multiplication, Linear Algebra, Partitioning.
  • Keywords (in french):

    Parallélisation Automatique, Pavage, Ressources Hétérogènes, Algorithmique, NP-Complet, Problèmes d'Optimisation, Graphe des Tâches, Chemin Critique, Tuiles, Bande Passante, Mémoire Cache, Pavage Hiérarchique, Circuit VLSI, Ordonnancement, Calcul Redondant, Chaîne d'Oscillateurs, Relaxation, Modèle de Communication, Décomposition LU, Décomposition QR, Produit de Matrices, Algèbre Linéaire, Partitionnement.
  • Availability: Electronic copy only.
  • Size: 175p
  • Format: Compressed PostScript
  • Get it

Notion de préfixe dans la complexité de Kolmogorov et les modèles de calcul.

  • By: Jean-Christophe Dubacq
  • Number: PhD2000-06
  • Date: October 2000
  • Abstract:

    Kolmogorov complexity theory gives a definition of randomness for words on a finite alphabet. The notions involved led to the description of a subclass of computable machines: the prefix computable machines, whose domain is a prefix code (no word in the domain is prefix of another one).

    Beyond the matter of defining randomness for infinite words, this subclass has remarkable properties regarding computability theory. Three different definitions are given and compared. The case of comma free codes is also examined, but it doesn't yield anymore an additively optimal machine.

    The notion of prefix also interacts with the computational models. An examination of machines with no blank characters or of finite models with an infinite calculus space (such as the Turing machine, which uses an infinite tape) reveals a strong influence of the prefix notion on computational processes.

  • Abstract (in french):

    La complexité de Kolmogorov donne une interprétation de la notion d'aléatoire pour les mots sur un alphabet fini. Ces notions ont conduit à l'explicitation de classes de fonctions calculables possédant des caractéristiques provenant de la théorie des codes: la classe des machines préfixes &emdash; machines dont le domaine est codé de façon préfixe, c'est-à-dire qu'un mot du domaine n'est jamais le préfixe d'un autre mot du domaine.

    Outre la résolution du problème de l'aléatoire dans les mots infinis, cette classe de machine est stable vis-à-vis de la théorie de la calculabilité. On compare ici trois définitions distinctes de la notion de machine préfixe, mais remarquablement similaires. On étend ensuite les notions proposées aux codes comma free (sans facteurs). Certaines propriétés fondamentales sont alors non-vérifiées, comme l'existence d'une machine additivement optimale.

    Enfin, on étudie la façon dont la notion de préfixe intervient dans la théorie de la calculabilité. On regarde en particulier les machines dont on limite le nombre de caractères (sans caractères blancs) ou encore la modélisation des modèles finis plongés dans des espaces de calcul infinis (ce qui est le cas de la machine de Turing, dotée d'un ruban infini).

  • Keywords:

    Kolmogorov Complexity, Computability, Prefix Codes, Randomness, Computation Models.
  • Keywords (in french):

    Complexité de Kolmogorov, Modèles de Calcul, Codes Préfixes, Aléatoire.
  • Availability: Electronic copy only.
  • Size: 129p
  • Format: Compressed PostScript
  • Get it