Fonctions Elémentaires : algorithmes et implémentations efficaces pour l'arrondi correct en double précision.

  • By: David Defour
  • Number: PhD2003-01
  • Date: September 2003
  • Abstract:

    The representation formats and behaviors of floating point arithmetics available in computers are defined by the IEEE-754 standard. This standard imposes the system to return as a result of one of the four basic operations (+, X, /,V), the rounding of the exact result. This property is called "correct rounding",this warranties the quality of the result. It enables construction of proof that this particular algorithms can be manipulated independently of the machine. However, due to the "table makers dilemma", elementary functions (sine, cosine, exponential...) are absent in the IEEE-754 standard. Contrary to basic operations, it is difficult to discover the necessary accuracy required to guarantee correct rounding for elementary functions. However if the representation format is set, it is possible that an exhaustive search will help determine this bound: it was Lefevre's work for the double precision. The objectives of this thesis is to exploit these bounds for each functions and rounding modes, to certify correct rounding in double precision. Thanks to this bound we have defined an evaluation within 2 steps: a quick phase which is based on the property of the IEEE standard that often proves satisfactory and an accurate step based on multiprecision operations which is precise all the time. For the second step we have designed a multiprecision library which was optimized in order to acquire precision corresponding to the bound, and the caracteristics of processors in 2003.
  • Abstract (in french):

    Le codage et le comportement de l'arithmétique à virgule flottante disponible dans les ordinateurs sont spécifiés par la norme IEEE-754. Cette norme impose au système de rendre comme résultat de l'une des quatre opérations (+, X, /, V), l'arrondi du résultat exact. Cette propriété que l'on appelle "arrondi correct", permet de garantir la qualité du résultat. Elle permet également la construction de preuves d'algorithmes, quelles que soient les machines sur lesquelles l'opération est executée. Toutefois cette norme présente des limites, puisque les fonctions élémentaires (sinus, cosinus, exponentielle...) en sont absentes. Cette abscence est liée au "dilemme du fabricant de tables" : il est, contrairement aux opérations de base, difficile de connaître la précision nécessaire pour garantir l'arrondi correct des fonctions élémentaires. Cependant, si l'on fixe le format de représentation, il est alors possible par une recherche exhaustive de déterminer cette borne; ce fut le travail de thèse de Lefèvre pour la double précision. L'objectif de ce mémoire est d'exploiter les bornes associées à chaque fonction, pour certifier l'arrondi correct des fonctions élémentaires en double précision pour les quatre modes d'arrondi. A cet effet, nous avons implémenté les évaluations en deux étapes : l'une rapide et juste la plupart du temps, basée sur les propriétés de l'arithmétique IEEE double précision, et l'autre juste tout le temps, composé d'opérateurs multiprécision. Pour cette deuxième phase, nous avons développé une bibliothèque d'opérateurs multiprécision optimisés pour les précisions données par ces bornes et les caractéristiques des processeurs en 2003.
  • Keywords:

    Computer Arithmetic, IEEE-754 standard, Elementary functions, Correct rounding, Range reduction, Multiprecision.
    Keywords (in french):

    Arithmétique des ordinateurs, Norme IEEE-754, Fonctions élémentaires, Arrondi correct, Réduction d'arguments, Multiprécision.
  • Availability: Electronic copy only.
  • Size: 143p
  • Format: Compressed PostScript
  • Get it

Design, Analysis and Validation of Router Assisted Reliable Multicast Protocols in Wide Area Networks.

  • By: Moufida Maimour
  • Number: PhD2003-02
  • Date: November 2003
  • Abstract:

    In the Internet, multi-point communications (multicast) allow for the exchange of data between different members that belong to the same group. At the network level, a new communication model called "IP Multicast" is introduced, and a given number of membership management and routing protocols are proposed. At the transport level, another class of problems is to be addressed such as reliability, congestion control and the accommodation of the co-existence of heterogeneous receivers in the same multicast session. The purpose of this thesis is to investigate the potential contribution of router-assisted approaches in solving some of the multicast transport level problems. We adopt the active networking technology where routers are able to perform customized services on packets they receive, to validate our proposals. As a first step, some analytical evaluations are performed to evaluate different router-based services that contribute to solve the problem of reliable multicast. Afterwards, a reliable multicast protocol called DyRAM is proposed and then extensively evaluated using simulations. In DyRAM, a dynamic congruent tree is implicitly built with the assistance of the routers via the election of repliers on a per-packet basis. This allows DyRAM to satisfy both congruence and adaptability requirements of a tree-based reliable multicast protocol. A first implementation of DyRAM is available and some measurements on a local test-bed are performed. Other experiments have also been conducted in the context of a grid computing environment. Afterwards, a multicast congestion avoidance protocol called AMCA, is proposed to limit data losses due to buffers overflow at the routers. In AMCA, a hop-by-hop measurements are performed with the assistance of the routers in order to learn about network congestion status. The routers are also used to aggregate feedback messages sent by the receivers such that the source ends up by adapting its rate to the most congested member in the group. Simulations showed that AMCA converges, makes use of the available bandwidth and reacts rapidly to dynamic changes in the multicast tree while being fair with TCP. Finally, a receiver-based replication scheme is proposed to implement a fine-grained multi-rate congestion control in order to accommodate heterogeneity and thus improving the overall receivers' satisfaction. Mainly, a partitioning algorithm is provided to split the set of the receivers into subgroups of similar capacities. Although simple, it achieves or at least approximates the optimal partitioning without requiring the prior knowledge of the receivers' capacities. We show that receiver-based replication compared to single-rate multicast or source-based replication, is fairer and more scalable. Moreover, an extension of AMCA is performed and mainly showed the rapid convergence of the partitioning algorithm when implementing the receiver-based replication scheme.
  • Abstract (in french):

    Dans l'Internet, les communications multipoint (multicast) permettent l'échange de données entre plusieurs membres appartenant au même groupe. Au niveau réseau, un nouveau modèle de communication appelé "Multicast IP" a été proposé ainsi qu'un certain nombre de protocoles de routage et de gestion de groupes. Au niveau transport, une autre classe de problèmes se pose. Cette classe comprend en particulier la fiabilité, le contrôle de congestion ainsi que la prise en charge de l'hétérogénéité des récepteurs qui appartiennent au même groupe. L'objectif de cette thèse est d'étudier l'apport de l'implication des routeurs dans la solution de certains problèmes du niveau transport. Pour valider nos propositions nous adoptons la technologie des réseaux actifs où les routeurs sont capables d'exécuter des services personnalisés en fonction des paquets reçus. En premier lieu, quelques analyses sont faites pour évaluer différents services au niveau des routeurs pour le multicast fiable. Ensuite, un protocole de multicast fiable appelé DyRAM est proposé et évalué par simulations. Dans DyRAM, un arbre dynamique proche de l'arbre de multicast, est construit implicitement avec l'assistance des routeurs via l'élection d'un retransmetteur par paquet perdu. Une première implémentation de DyRAM est disponible et quelques mesures sur une plate-forme locale ont été réalisées. D'autres expérimentations ont été aussi menées dans un environnement de grille de calcul. Ensuite, un protocole d'évitement de congestion en multicast appelé AMCA, est proposé pour limiter les pertes de paquets dues à des débordements au niveau des routeurs. Dans AMCA, des mesures sont faites avec l'assistance des routeurs pour connaître l'état de congestion du réseau. Les routeurs sont aussi utilisés pour agréger les messages de contrôle émis par les récepteurs de telle sorte que la source finit par adapter son débit au récepteur le plus congestionné du groupe. Des simulations ont montré que AMCA converge, utilise la bande passante disponible et réagit rapidement aux changements dynamiques de l'arbre de multicast tout en étant équitable avec TCP. Enfin, un schéma de réplication par les récepteurs est proposé pour implémenter un protocole multi-débits, finement contrôlé, afin de prendre en considération l'hétérogénéité. En particulier, un algorithme de partitionnement est fourni pour distribuer les récepteurs sur des groupes de capacités similaires. Malgré sa simplicité, cet algorithme atteint ou au moins approche la solution optimale sans avoir besoin d'une connaissance préalable de la capacité des récepteurs. Nous montrons que cette réplication par les récepteurs comparée à un multicast à un débit ou une réplication par la source, est plus équitable et permet plus de passage à l'échelle. Une extension de AMCA a été réalisée et a montré la convergence rapide de l'algorithme de partitionnement lors de l'implémentation de la réplication par les récepteurs.
  • Keywords:

    Multicast, Reliability, Congestion control, Heterogeneity, Active networks, Analysis, Simulation, Implementation.
    Keywords (in french):

    Multicast, Fiabilité, Contrôle de congestion, Hétérogénéité, Réseaux actifs, Analyse, Simulation, Implémentation.
  • Availability: Electronic copy only.
  • Size: 203p
  • Format: Compressed PostScript
  • Get it

Vers la conception d'une architecture de réseaux actifs apte à supporter les débits des réseaux gigabits.

  • By: Jean-Patrick Gelas
  • Number: PhD2003-03
  • Date: December 2003
  • Abstract:

    The aim of active networks is to use data transport networks cleverly by injecting dynamically customized services in networks equipments. Despite their attractiveness, active networks concept raise many problems in terms of performances, security, equipment heterogeneity support and services deployment.

    This thesis work focused on the performance problem in active equipments. We propose a set of original ideas to design a high performance software based active router able to support gigabits networks.

    We define a new generic active network architecture spreadable over the Internet. Two dynamic service deployment mechanism. We proposed a high performance active node architecture splitted in logical layers. This architecture provide a service classification in terms of cpu cycle consumption and memory space resources to run them in the best suited layer.

    This architecture has been experimentally validated with the Tamanoir software suite. We propose an open and efficient Execution Environment, a library of experimental services and developement tools to ensure remote equipments visualization and generate active traffic. Experiments over very high throughputs local platforms and gigabits long distance network (RNRT VTHD++) show the efficiency of the Tamanoir environment. Moreover we deploy Tamanoir in a national computing grid (RNTL E-Toile) to support efficiently grid middleware and grid applications.

  • Abstract (in french):

    L'objectif des réseaux actifs est d'exploiter les réseaux de transport de données de manière plus "intelligente" par l'injection dynamique de services personnalisés dans les équipements réseaux. Le concept de réseaux actifs bien que séduisant soulève de nombreuses problématiques en termes de performances, de sécurité, de support de l'hétérogénéité des équipements et de déploiement de services.

    Ces travaux de thèse se sont principalement concentrés sur le problème de la performance dans les équipements actifs. Nous avons apporté un ensemble d'idées originales pour la conception d'un routeur actif logiciel hautes performances apte à supporter les débits des réseaux gigabits.

    Nous avons défini une nouvelle architecture de réseau actif générique déployable dans une infrastructure Internet. Deux mécanismes de déploiement dynamique de services ont été intégrés. Nous avons proposé une architecture de noeud actif hautes performances découpée en couches logiques. Cette architecture supporte une classification des services actifs, en termes de consommation de cycles processeur et ressources mémoire, afin de les exécuter dans la couche la plus appropriée.

    Cette architecture a été validée expérimentalement avec l'implémentation de la suite logicielle Tamanoir. Nous proposons un Environnement d'Exécution ouvert et performant, une bibliothèque de services expérimentaux et des outils de développement assurant la visualisation d'équipements distants et la génération de trafic actif. Des expérimentations sur des plateformes locales très haut débit et des liaisons longue distance Gigabits (RNRT VTHD++) ont démontré l'efficacité de l'environnement Tamanoir. Nous avons par ailleurs déployé Tamanoir dans une grille de calcul nationale (RNTL E-Toile) afin de supporter efficacement les middlewares et applications de grille.

  • Keywords:

    Active Networks, High Performance networks, Network services, Tamanoir.
    Keywords (in french):

    Réseaux actifs, Réseaux haute performance, Services réseaux, Tamanoir.
  • Availability: Electronic copy only.
  • Size: 147p
  • Format: Compressed PostScript
  • Get it

Découverte automatique des caractéristiques et capacités d'une plate-forme de calcul distribué.

  • By: Martin Pierre QUINSON
  • Number: PhD2003-04
  • Date: December 2003
  • Abstract:

    This thesis is devoted to the monitoring of modern computational platforms in order to obtain relevant, up to date and accurate information about them. Often called Grids, those environments differ from the preceding parallel machines by their intrinsic heterogeneity and high dynamicity. This document is organized in three parts. The first one presents the specific difficulties introduced by this platform, highlighting them in a selection of grid infrastructure projects and detailing the existing solutions. The second part shows how to get efficiently quantitative informations about the grid capacities and their suitability to the needs of the routines to schedule. After a discussion of the problems encountered, we detail our approach which we call macro-benchmarking. We then present FAST, a tool implementing this methodology. We eventually detail how FAST is used in several other projects. The third part introduces how to get a more qualitative view of the grid characteristics such as the topology of the network interconnecting the hosts. After a study of the existing solutions in this domain, we present ALNeM our solution to automatically map the network without relying on specific execution privileges on the platform. This tool is based on GRAS, our framework for the development of grid infrastructure. .
  • Abstract (in french):

    Ce mémoire traite de l'obtention d'informations pertinentes, récentes et précises sur l'état courant des plates-formes de calcul modernes. Souvent dénommés grilles, ces environnements se différencient des machines parallèles les ayant précédés par leur nature intrinsèquement hétérogène et fortement dynamique. Ce document est découpé en trois parties. La première présente les difficultés spécifiques à la grille en se basant sur une sélection de projets d'infrastructures pour la grille et en détaillant les solutions proposées dans ce cadre. La seconde partie montre comment obtenir efficacement des informations quantitatives sur les capacités de la grille et leur adéquation aux besoins des routines à ordonnancer. Après avoir détaillé les problèmes rencontrés dans ce cadre, nous explicitons notre approche, nommée macro-benchmarking. Nous présentons ensuite l'outil FAST, développé dans le cadre de cette thèse et mettant cette méthodologie en oeuvre. Nous étudions également comment cet outil est utilisé dans différents projets. La troisième partie traite de l'obtention d'une vision plus qualitative des caractéristiques de la grille, telle que la topologie d'interconnexion des machines la constituant. Après une étude des solutions classiques du domaine, nous présentons ALNeM, notre solution de cartographie automatique ne nécessitant pas de privilège d'exécution particulier. Cet outil est basé sur l'environnement GRAS, développé dans le cadre de ces travaux pour la mise au point des constituants de la grille. .
  • Keywords:

    Performance forecasting, topology mapping, metacomputing, grid computing, distributed application development. .
    Keywords (in french):

    Prédiction de performances, cartographie automatique, metacomputing, grille de calcul, développement d'applications distribuées. .
  • Availability: Electronic copy only.
  • Size: 159p
  • Format: pdf
  • Get it

Algorithmique parallèle hétérogène et techniques d'ordonnancement : approches statiques et dynamiques.

  • By: Arnaud LEGRAND
  • Number: PhD2003-05
  • Date: December 2003
  • Abstract:

    The results summarized in this document deal with the algorithmic difficulties raised by the heterogeneity of modern parallel and distributed computing platforms. The contributions of this work are divided in three parts: 1) Parallel algorithms: efficient heterogeneous distributions for most dense linear algebra kernels (matrix product, LU decomposition), lightweight redistribution techniques to cope with load variations; 2) Simulation and modeling: the genuine instability of wide-area distributed computing platforms forbids the use of real experiments to to test the behavior of an algorithm or of a scheduling policy. Therefore we have proposed simple models and have developed a realistic simulator to cope with this problem; 3) Scheduling: lots of applications are constituted of a very large number of independent identical tasks. We have established some complexity results and have proposed some approximations for different models of this situation.
  • Abstract (in french):

    Les travaux présentés dans cette thèse portent sur les difficultés algorithmiques soulevées par l'introduction de l'hétérogénéité des plates-formes modernes dans le calcul parallèle et distribué. Les contributions de cette thèse se situent à trois niveaux : 1) Algorithmique Parallèle : distributions hétérogènes pour les noyaux d'algèbre linéaire denses (produit de matrice, décomposition LU), technique de rééquilibrage, légère et efficace en cas de petites variations de charge des processeurs ; 2) Modélisation et simulation : l'instabilité latente des plates-formes de calcul distribuées à grande échelle interdit toute validation expérimentale grandeur nature d'un algorithme ou d'une politique d'ordonnancement. Nous avons proposé des modèles simples et un simulateur réaliste pour palier ce problème; 3) Ordonnancement : un certain nombre d'applications sont constituées d'un grand nombre de tâches indépendantes et de caractéristiques identiques. Nous avons établi des résultats de complexité et proposé des approximations pour différentes modélisation de ce problème.
  • Keywords:

    Parallel algorithms, scheduling, heterogeneity, steady-state, simulation and modeling of computing platforms.
    Keywords (in french):

    Algorithmique parallèle, ordonnancement, hétérogénéité, régime permanent, simulation et modélisation de plates-formes de calcul.
  • Availability: Electronic copy only.
  • Size: 238p
  • Format: pdf
  • Get it

Traitement différencié et marquage adaptatif de paquets pour le transport des flux hétérogènes dans l'Internet.

  • By: Benjamin Gaidioz
  • Number: PhD2003-06
  • Date: December 2003
  • Abstract:

    With a wider and wider size and a growing number of users, the Internet appears obviously both as a technical and popular success. Its interconnection protocol meets however some limits today. The network layer fits well the needs of classic flows like "file transfers" but uses change: phone, video, etc. appear today as applications running on the Internet. These new types of flows are quite badly supported by the network. Architectures were proposed to solve this question but they meet some deployment issues due to implementation of priviledged flows, pricing, control, etc. They are actually not deployed today. This report proposes a simple architecture which does not have these limits. By lying on a simple network layer but a rather complex transport protocols participation, the architecture allows the cohabitation and improvement of these new types of application.
  • Abstract (in french):

    Avec une étendue de plus en plus vaste et un nombre d'utilisateurs de plus en plus important, Internet est clairement une réussite aussi bien technique que populaire. Mais les limites de son protocole d'interconnexion se font sentir aujourd'hui. Le réseau est adapté aux flux classiques de type « transfert de fichier » mais les usages évoluent: téléphonie, vidéo, etc., apparaissent aujourd'hui. Ces types de flux sont en fait relativement mal servis par le réseau. Les architectures proposées pour remédier à ce blocage rencontrent de nombreuses difficultés de déploiement à l'échelle d'Internet: mise en place de classes de trafic privilégiées, facturation, plan contrôle à grande échelle, etc. Cette thèse présente une architecture sans garanties fortes et qui n'a pas ces limites. S'appuyant sur un système réseau simple et la participation des protocoles de transport, l'architecture proposée permet la cohabitation et l'amélioration de la performance de ces différents types d'application.
  • Keywords:

    Quality of Service, Internet, Diffserv, Service Differenciation, Transport Protocols, Linux.
    Keywords (in french):

    Qualité de Service, Internet, Diffserv, Différenciation de Service, Protocoles de Transport, Linux.
  • Availability: Electronic copy only.
  • Size: 156p
  • Format: pdf
  • Get it