GOUICEM Mourad

PhD student at Sorbonne University
Team : PEQUAN
https://lip6.fr/Mourad.Gouicem

Supervision : Jean-Claude BAJARD

Co-supervision : FORTIN Pierre et GRAILLAT Stef

Conception and deployment of efficient algorithms for solving the table maker's dilemma on parallel architectures

Since its standardization in 1985, floating-point arithmetic is commonly used to approximate computations over the real numbers in a portable and predictable way. This predictability of the result is enabled thanks to a strong requirement on the functions specified by the IEEE Std 754: they must return a correctly rounded result. Even though the implementation of basic operations is made mandatory, that of elementary functions is only recommended. This is mainly due to a computationally hard to solve problem called the table maker's dilemma (TMD).

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.

Defence : 10/14/2013

Jury members :

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

Departure date : 10/14/2013

2012-2016 Publications