Team : PEQUAN

Departure date : 10/14/2013

In this thesis, we provides algorithms along with their deployment on massively parallel architectures, in particular GPUs (Graphics Processing Units), to solve this problem in practice for some elementary functions and floating-point formats. These deployments enable a speedup by a factor greater than 50 on GPU compared to a sequential execution on CPU (greater than 7 compared to an hexa-core parallel CPU implementation). The main algorithmic tool we use are the number systems based on continued fraction developments. The latter allows to efficiently perform arithmetic over the real numbers modulo 1, and to find the hard cases for correct rounding.

We then generalize the use of these number systems to modular arithmetic over integer numbers. This provide a framework to build algorithms for modular multiplication and modular division, based only on the classical Euclidean algorithm.

Marius Cornea, Intel [Rapporteur]

Florent de Dinechin, INSA Lyon [Rapporteur]

Raphaël Couturier, IUT Belfort-Montbelliard

David Defour, LIRMM/UPVD

Laura Grigori, INRIA/LJLL/UPMC

Jean-Claude Bajard, LIP6/UPMC

Pierre Fortin, LIP6/UPMC

Stef Graillat, LIP6/UPMC

Jean-Michel Muller, CNRS/LIP

- 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), (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”, these, defence 10/14/2013, supervision Bajard, Jean-Claude, co-supervision 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, Russia, 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) (2012)

- P. Fortin, M. Gouicem, S. Graillat : “Solving the Table Maker’s Dilemma by reducing divergence on GPU”, Proceedings of the 15