Description
Date depot: 1 janvier 1900
Titre: Conception et implantation d'algorithmes efficaces pour la résolution du dilemme du fabriquant de tables
Directeur de thèse:
Stef GRAILLAT (LIP6)
Directeur de thèse:
Jean-Claude BAJARD (IMJ)
Encadrant :
Pierre FORTIN (CRISTAL)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
TITRE Conception et implantation d’algorithmes efficaces pour la résolution du dilemme du fabriquant de tables
ATTENTION LE SOUS THEME NE CORRESPOND PAS MAIS AUCUN NE CORRESPONDAIT
Domaine :
En arithmétique à virgule flottante, le fait d’avoir des opérations complètement spécifiées est une exigence-clé, si
on veut développer des logiciels portables au comportement prévisible. Depuis 1985 et la norme IEEE-754 (revisée
en 2008), les quatre opérations arithmétiques (+;􀀀;; =) sont spécifiées (elles doivent être correctement arrondies :
le système doit renvoyer le nombre à virgule flottante le plus proche du résultat exact). Ce n’est pas le cas des
fonctions mathématiques de base : la même fonction pourra renvoyer des résultats significativement différents
suivant l’environnement, avec deux conséquences pour les logiciels utilisant ces fonctions :
– il est presque impossible d’estimer leur précision,
– leur portabilité est délicate à garantir.
Ce manque de spécification est dû à un problème appelé le Dilemme du fabricant de tables. Pour calculer f(x)
dans un format donné, on calcule une approximation de f(x) qu’on arrondit au nombre à virgule flottante le plus
proche. Le problème est alors : quelle doit être la précision de l’approximation pour que le résultat obtenu soit
toujours égal à f(x) arrondi au plus proche nombre à virgule flottante ?
Description du sujet :
Pour résoudre ce problème, on doit déterminer, pour chaque format et fonction considérés quel est le point le plus
dur à arrondir , i.e., le nombre à virgule flottante x tel que f(x) est le plus proche du milieu de 2 nombres à virgule
flottante consécutifs. Les algorithmes actuels permettant de calculer ces points dur à arrondir sont exponentiels en
le nombre de bits du format. Le but de la thèse est donc d’obtenir tous ces points les plus durs pour la double
précision et d’obtenir des premiers résultats pour les formats supérieurs (précision étendue, quadruple précision).
Le travail à réaliser est double :
– il s’agit tout d’abord de participer, dans le cadre du Dilemme du fabricant de tables, à l’élaboration d’une version
optimisée des algorithmes sous-jacents (algorithme LLL en particulier) ;
– il s’agit ensuite de concevoir puis implanter et optimiser les algorithmes parallèles correspondants sur un certain
nombre d’architectures massivement parallèles (grappes de CPU multicoeurs, GPU, grille, etc.) en prenant en
compte les problématiques de vectorisation, de multi-précision et de factorisation des calculs redondants.
Afin d’obtenir des résultats en quadruple précision, ce qui constitue actuellement un réel challenge, les implantations
réalisées devront pouvoir exploiter efficacement les machines pétaflopiques actuelles et à venir.
À long terme, ces travaux doivent permettre d’exiger l’arrondi correct de certaines fonctions dans les prochaines
versions de la norme IEEE 754, ce qui permettra de spécifier complètement l’ensemble des 'briques de base' du
calcul numérique.
Compétences souhaitées : formation associant mathématiques et informatique. Des connaissances en algorithmique
parallèle et en arithmétique des ordinateurs, ainsi qu’une bonne maîtrise du langage C, seront un plus.
Doctorant.e: Gouicem Mourad