Partage de bande passante et plan de contr?le optique dans les grilles.
By: Sébastien Soudan
Number: DEA2006-01
Date: June 2006
Abstract:
Dans ce rapport, nous nous intéressons au problème de partage de bande passante dans les réseaux de grilles. Le concept de plan ``contrôle'' unifié permet la création et la réservation de tunnels à bande passante garantie au travers des réseaux locaux Ethernet et des réseaux de coeur optique. Nous étudions comment il peut être utilisé dans les réseaux de grilles. Ce rapport propose une modélisation intégrant les particularités de cette approche ainsi que l'étude du problème de partage de bande passante pour les transferts de fichiers massifs dans ce modèle. Plusieurs algorithmes d'allocation basés sur les travaux de QoS routing sont proposés et comparés.
Keywords:
grille, partage de bande passante, GMPLS, plan ``contrôle'' unifié.
L'évaluation de fonctions élémentaires reste un problème important
en arithmétique des ordinateurs. Evaluer une telle fonction revient
généralement à évaluer un polynôme qui l'approche au mieux. La
méthode la plus utilisée, la méthode de Horner, permet d'évaluer un
polynôme de degré n en n multiplications et n additions. Il existe par
ailleurs d'autres méthodes, qui permettent d'évaluer des polynômes
plus rapidement en nombre d'opérations que Horner. Cependant, ces
méthodes nécessitent un préconditionnement préalable des
polynômes à évaluer.
Pourquoi ne pas utiliser ces méthodes dans l'implantation de fonctions
mathématiques ? Peut-on être plus rapide tout en restant aussi précis
que Horner ?
Ce rapport montre que sous certaines conditions, ces méthodes
peuvent fournir des erreurs comparables à celles obtenues par la méthode
de Horner.
Keywords:
arithmétique flottante, polynômes d'approximation, évaluation,
préconditionnement, stabilité numérique, analyse d'erreurs et
de complexité, fonctions élémentaires.
Polynômes de meilleure approximation à coefficients flottants.
By: Sylvain Chevillard
Number: DEA2006-03
Date: June 2006
Abstract:
Lorsqu'on a besoin de calculer des valeurs approchées d'une fonction f en de nombreux points d'un intervalle [a,b], on remplace généralement f par un approximant plus simple à évaluer. Les polynômes sont souvent utilisés car leur évaluation ne nécessite que des additions et des muliplications. L'erreur commise en remplaçant la fonction f par le polynôme p est égale à p-f. Dans le pire cas, remplacer f par p conduit donc à faire une erreur de max {|p(x)-f(x)|, x dans [a,b]}. Cette quantité est appelée la norme infinie de p-f. Le problème général de la recherche d'un polynôme à coefficients réels de degré inférieur ou égal à n minimisant la norme infinie de p-f a été largement étudié au début du XXe siècle. Cependant tous les réels ne sont pas exactement représentables dans la mémoire d'un ordinateur et on utilise généralement les nombres flottants comme approximation des nombres réels. Lorsqu'on implémente une fonction dans une bibliothèque logicielle, on utilise donc en pratique des polynômes à coefficients flottants. Il apparaît que le polynôme à coefficients flottants minimisant la norme infinie de f-p ne peut pas être directement déduit du polynôme de meilleure approximation à coefficients réels, ce qui relance donc le problème. Nous proposons une heuristique pour trouver un polynôme à coefficients flottants approchant bien une fonction f en norme infinie. Nous décrivons la méthode (qui s'appuie sur la théorie des réseaux et de leur reduction) et nous illustrons son efficacité à travers un exemple détaillé.
Les applications parallèles utilisent généralement le standard
MPI pour réaliser leurs communications. La plupart des implémentations
de MPI sont destinées aux grappes homogènes. Avec l'apparition des
grilles de calcul, il est nécessaire de faire évoluer ces
implémentations pour les adapter efficacement aux contraintes de ces
nouvelles plateformes que sont la gestion de l'hétérogénéité et la prise
en compte des liens réseau longue distance permettant l'interconnexion
des sites de la grille. Aucune implémentation actuelle ne prend en
compte efficacement ces deux paramètres.
Après une étude des implémentations existantes, cet article analyse le
comportement sur la grille de l'une d'entre elles, MPICH-Madeleine, qui
propose une gestion efficace de l'hétérogénéité des réseaux rapides de
grappe. A partir de nos premières expérimentations, nous proposons des
optimisations permettant d'améliorer les performances d'exécution sur la
grille.
Elles nous ont permis d'augmenter très sensiblement la bande passante
lors de l'exécution d'un ping-pong MPI : en passant de 40Mb/s à 300Mb/s
sur la longue distance. Les expérimentations ont été réalisées sur la
grille française Grid'5000.
Scheduling and data redistribution strategies on star platforms.
By: Veronika Rehn
Number: DEA2006-05
Date: June 2006
Abstract:
In this work we are interested in the problem of scheduling and redistributing data on master-slave platforms. We consider the case were the workers possess initial loads, some of which having to be redistributed in order to balance their completion times. We examine two different scenarios. The first model assumes that the data consists of independent and identical tasks. We prove the NP-completeness in the strong sense for the general case, and we present two optimal algorithms for special platform types. Furthermore we propose three heuristics for the general case. Simulations consolidate the theoretical results. The second data model is based on Divisible Load Theory. This problem can be solved in polynomial time by a combination of linear programming and simple analytical manipulations.
Le langage CRP est une extension de C destiné à l'écriture
de programmes de type "`traitement de signal"', en particulier de flux vidéo pour systèmes
embarqués. Par rapport au C standard, il comporte des processus, des canaux et des ports.
L'objectif à long terme du projet est d'utiliser un programme (CRP) comme spécification d'un
accélérateur matériel réalisé à l'aide d'un FPGA (ou d'un ASIC...).
Le sujet principal du stage est de réaliser un outil logiciel permettant de transformer un
programme CRP en un programme C++ utilisant les threads et ayant le même fonctionnement.
Pour vérifier le bon fonctionnement de cet outil logiciel, on sera amené à enrichir la base
d'exemples du projet syntol, par exemple en important et en adaptant des benchmarks postés
sur le web par des projets analogues (StreamIt...).
Dans ce rapport, nous étudions l’ordonnancement de l’envoi de fichiers à
travers un switch. Ce problème est souvent utilisé pour modéliser le réseau
utilisé par une grille de calcul, où le switch représente le coeur du réseau qui
relie les différents clusters composant la grille. Nous établissons différents ré-
sultats de complexité, avant d’étudier plusieurs algorithmes, tant d’un point
de vue théorique que d’un point de vue pratique.
Keywords:
Ordonnancement, réseaux, complexité, grilles de calcul.
Dissémination de données en ligne en présence de dépendances.
By: Julien Robert
Number: DEA2006-08
Date: July 2006
Abstract:
La plupart des problèmes algorithmiques sont NP-difficiles et il est donc
impossible de les résoudre exactement (à moins que P=NP). On recherche donc
dans
ce cas des algorithmes d´approximation dont l´analyse mathématique des
performances garantit que le ratio entre le coût de la solution produite et le
coût optimal est borné. L´objet de ce stage d´informatique théorique est de
concevoir des algorithmes d´approximation pour un problème de
télécommunications
: la dissémination en-ligne de journaux électroniques personnalisés sur un
canal
partagé. Contexte: La dissémination de données (Data Broadcast) est un
protocole
de diffusion d´information qui tire profit du caractère naturellement
diffusant
des média tels que les réseaux sans fils (GSM, satellite), Ethernet, Radio ou
Télévision, où chaque message émis peut être reçu simultanément par un
nombre
arbitraire de clients. L'objectif dans ce stage est d'étudier la minimisation
du
temps de réponse d'un tel système lorsque les utilisateurs émettent dans le
temps différentes requêtes pour différents sous-ensembles des messages
disponibles sur le serveur. Le temps de réponse du système étant défini
comme la
moyenne sur l'ensemble des requêtes de leurs temps de réponse (c'est-à-dire
du
temps écoulé de l'émission de la requête jusqu'à la diffusion du dernier
des
messages demandés). Ce problème d´ordonnancement en-ligne est connu pour
être
NP-difficile même si les ensembles requis sont des singletons. Il s'agira dans
ce stage d'étudier comment les dépendances modifient la complexité de ce
problème et tout particulièrement comment construire des algorithmes
compétitifs
(à un facteur borné de la solution optimale hors ligne) pour gérer les
dépendances. Description détaillée du travail: Le stage proposé est un stage
d´algorithmique. Le problème proposé étant NP-difficile, l'objet du stage
sera
de proposer un/des algorithmes d'approximation pour lesquels il s'agira
d'obtenir des bornes sur les garanties de performances. Après une étude
bibliographique des travaux antérieurs (portant sur le cas en-ligne sans
dépendance), le stagiaire commencera par l'étude de cas particuliers simples
(mais pour l'instant inexplorés) du cas avec dépendances; l'étude du cas
général
ne se fera qu'ensuite. Une étude des performances par simulations pourra être
envisagée mais ne constituera pas le coeur du stage.
Le modèle d'architecture des grilles repose sur une vision qui consiste à distribuer
la puissance de calcul et plus généralement les ressources, afin d'exploiter au mieux
les applications. Cependant, la plupart des plateformes Grid actuelles ne supportent
pas l’isolation de performances, ce qui ne leur permet pas d’assurer les exigences
de l’utilisateur en termes de qualités de services. Ce problème peut être résolu en
permettant aux clients autorisés des Grilles de déployer des clusters virtuels établis
par des machines virtuelles configurées pour répondre à leurs besoins en termes de
matériels et de logiciels. Toutefois, les clusters virtuels doivent passer à l'échelle en
résolvant plusieurs problèmes relatifs aux ressources physiques et virtuels.
Notamment, ils assurent la correspondance ou mapping entre ressources virtuelles
et physiques, l’ordonnancement et la réservation des ressources en minimisant
l’overhead de la virtualisation.
