Direction de recherche : Jean-Claude BAJARD

Co-encadrement : FORTIN Pierre et GRAILLAT Stef

Conception et implantation d'algorithmes efficaces pour la résolution du dilemme du fabricant de tables sur architectures parallèles

Depuis sa normalisation en 1985, l'arithmétique flottante permet d'approcher les calculs en nombres réels de manière portable et prévisible. Cette deuxième propriété est due à une exigence forte sur les opérateurs dont l'implantation est exigée par la norme : leur résultat doit être correctement arrondi. Bien que la norme IEEE 754, dans sa dernière révision de 2008, exige l'implantation des opérations de base, elle ne fait que recommander l'implantation des fonctions mathématiques élémentaires. Ceci est principalement dû à un problème calculatoire difficile nommé le dilemme du fabricant de tables.
Dans cette thèse, nous fournissons des algorithmes ainsi que leurs déploiements sur architectures massivement parallèles, notamment les GPU (Graphics Processing Units), résolvant ce dilemme pour certains formats de nombres flottants en pratique. Ces déploiements permettent une accélération des performances d'un facteur supérieur à 50 sur GPU par rapport à une exécution séquentielle sur CPU (supérieur à 7 par rapport à une exécution parallèle sur CPU hexa-cœur). Le principal outil algorithmique que nous utilisons sont les systèmes de numération à base de développements en fraction continue. Ces derniers permettent alors de détecter les cas difficiles pour l'arrondi correct via de l'arithmétique sur les nombres réels modulo 1.
Nous généralisons ensuite l'utilisation de ces systèmes de numération à l'arithmétique modulaire en nombres entiers. Cela permet alors d'obtenir des algorithmes de multiplication et division modulaires ne reposant que sur l'utilisation de l'algorithme d'Euclide pour le calcul de PGCD. ion et implantation d'algorithmes efficaces pour la résolution du dilemme du fabricant de tables

Publications 2012-2016

• 2016
  • P. Fortin, M. Gouicem, S. Graillat : “GPU-Accelerated Generation of Correctly Rounded Elementary Functions”, ACM Transactions on Mathematical Software, vol. 43 (3), pp. 22:1-22:26, (Association for Computing Machinery) (2016)
  • Ch. Avenel, P. Fortin, M. Gouicem, Z. Samia : “Solving the Table Maker’s Dilemma on Current SIMD Architectures”, Scalable Computing : Practice and Experience, vol. 17 (3), pp. 237-249, (West University of Timisoara) (2016)
• 2013
  • M. Gouicem : “Conception et implantation d’algorithmes efficaces pour la résolution du dilemme du fabricant de tables sur architectures parallèles”, soutenance de thèse, soutenance 14/10/2013, direction de recherche Bajard, Jean-Claude, co-encadrement : Fortin, Pierre et GRAILLAT Stef (2013)
  • M. Gouicem : “New modular multiplication and division algorithms based on continued fraction expansion”, (2013)
• 2012
  • P. Fortin, M. Gouicem, S. Graillat : “Solving the Table Maker’s Dilemma by reducing divergence on GPU”, Proceedings of the 15^th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Verified Numerical Computations, Novosibirsk, Russian Federation, pp. 45-46 (2012)
  • P. Fortin, M. Gouicem, S. Graillat : “Towards solving the Table Maker’s Dilemma on GPU”, 20^th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, Garching, Germany, pp. 407-415, (IEEE Computer Society) (2012)