The Scholarship

Design and Implementation of Efficient Algorithms for the Table Maker’s Dilemma Solving

Funded by the french TaMaDi ANR project (Table Maker’s Dilemma: LIP-Arénaire, LIP6-PEQUAN and INRIA-Marelle), we have an open PhD position on the following subject. Candidates should send by email a CV resume and a cover letter to Pierre Fortin and Stef Graillat.

Contacts :
Pierre Fortin (Pierre.Fortin@lip6.fr)
Stef Graillat (Stef.Graillat@lip6.fr)

Laboratory :
LIP6, Université Pierre et Marie Curie (Paris 6),
Scientific Computing Department, PEQUAN team

Beginning: (around) October 2010

Net Salary: around 1400 e per month (1700 e with teaching). Basic health insurance is included in the salary.

Domain :
In floating-point (FP) arithmetic, having fully-specified operations is a key-requirement, if one wants portable and predictable numerical software. Since 1985 and the IEEE-754 norm (revised in 2008), the four arithmetic operations are specified (they must be correctly rounded: the system must return the FP number nearest the exact result). This is not fully the case for the basic mathematical functions. The same function may return significantly different results depending on the environment. Hence, numerical programs using these functions suffer from various problems:
 it is almost impossible to estimate their accuracy;
 their portability is difficult to guarantee.

This lack of specification is due to a problem called the Table Maker’s Dilemma. To compute f(x) in a given format, where x is a FP number, we first compute an approximation to f(x) and then we round it to the nearest FP number. The problem is: what must the accuracy of the approximation be to ensure that the obtained result is always equal to f(x) rounded to the nearest FP number?

Subject Description :
To solve that problem, we must locate, for each considered FP format & function, what is the hardest to round (HR) point, i.e., the FP number x such that f(x) is closest to the exact middle of two consecutive FP numbers.
Current algorithms to compute such HR points present an exponential complexity with the number of bits of the format. The aim of this PhD thesis is therefore to obtain all these HR points in double precision, as well as to obtain first results for larger formats (extended precision, quadruple precision). Two steps will have to be considered.
 First, in the context of the Table Maker’s Dilemma context, an optimization of underlying algorithms will have to be considered (especially for the LLL algorithm).
 Secondly, the corresponding parallel algorithms will have to be designed, implemented and optimized on several massively parallel architectures (cluster of multicore CPUs, GPU, grid. . . ), taking into consideration issues such as vectorization, mixed-precision and factoring of redundant computations.
In order to obtain results in quadruple precision, which is currently a real challenge, these implementations should be able to efficiently operate on current and forthcoming petaflops systems.
In the long term, this work should enable to require the correct rounding of some functions in the next versions of the IEEE-754 norm, which will allow to completely specify all the components of numerical softwares.
Required Skills : strong mathematical and computer science background. Skills in parallel algorithmics and computer arithmetic will be considered as assets.

Application Deadline : 30 August 2010