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.

2012-2016 Publications

• 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”, thesis, phd 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, 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)