Search

Numerical validation enables one to improve the reliability of numerical computations that rely upon floating-point operations through obtaining trustful results. Discrete Stochastic Arithmetic (DSA) makes it possible to validate the accuracy of floating-point computations using random rounding. However, it may bring a large performance overhead compared with the standard floating-point operations. In this article, we show that with perturbed data it is possible to use standard floating-point arithmetic instead of DSA for the purpose of numerical validation. For instance, for codes including matrix multiplications, we can directly utilize the matrix multiplication routine (GEMM) of level-3 BLAS that is performed with standard floating-point arithmetic. Consequently, we can achieve a significant performance improvement by avoiding the performance overhead of DSA operations as well as by exploiting the speed of highly-optimized BLAS implementations. Finally, we demonstrate the performance gain using Intel MKL routines compared against the DSA version of BLAS routines.

International audience; We have recently started a research collaboration to explore the possibility of a new computing system with precision-tuning, in collaboration with RIKEN CCS, Sorbonne University, and University of Tsukuba. Our proposal, "minimal-precision computing," aims to achieve reliability (accuracy and reproducibility) as well as high-performance (speed and energy) by obtaining the computing results with the accuracy requested by users with the minimal-precision use. Our proposal involving both hardware and software stacks combines (1) a precision-tuning method through numerical validation by Discrete Stochastic Arithmetic (DSA), (2) arbitrary-precision arithmetic libraries, (3) fast and accurate numerical libraries, and (4) Field-Programmable Gate Array (FPGA) with high-level synthesis, and some important components that we develop. This poster introduces an overview of our ideas and our up-to-date contributions.

International audience; This paper focuses on the resolution of a large number of small symmetric linear systems and its parallel implementation on single precision on GPUs. The computations involved by each linear system are independent from the others and the number of unknowns does not exceed 64. For this purpose, we present the adaptation to our context of largely used methods that include: LDLt, House-holder reduction to a tridiagonal matrix, parallel cyclic reduction that is not a power of two and the divide and conquer algorithm for tridiagonal eigenprob-lems. We not only detail the implementation and optimization of each method but we also compare the sustainability of each solution and its performance which include both parallel complexity and cache memory occupation. In the context of solving a large number of small random linear systems on GPU with no information about their conditioning, we show that the best strategy seems to be the use of Householder tridiagonalization + PCR followed if necessary by a divide & conquer diagonalization.

International audience; In this article, we show how to perform a dynamical control of Newton's method for the computation of multiple roots of polynomials. Using Discrete Stochastic Arithmetic, root approximations are computed until the difference between two successive approximations is numerical noise. With such a stopping criterion, the optimal number of iterations in Newton's method are performed. Moreover it is possible to estimate in the result obtained which digits are in common with the exact root. Two strategies to estimate the multiplicity of polynomials roots are compared: one requires root approximations computed at different precisions and the other three successive iterates of Newton's method. We show that using such a strategy and then the modified Newton's method, multiple roots can be computed with a requested accuracy.

International audience; Nowadays, most floating-point computations in numerical simulations are performed in IEEE 754 binary64 precision (double precision). This means that a relative accuracy of about 10−16 is provided for every arithmetic operation. Indeed, in practice, programmers tend to use the highest precision available in hardware which is the double precision on current processors. This approach can be costly in termsof computing time, memory transfer and energy consumption [1]. A better strategy would be to use no more precision than needed to getthe desired accuracy on the computed result. The challenge of using mixed precision is to find some parts of codes (and so variables) thatmay be executed with lower precision. Unfortunately the amount of possible configurations is exponential in the number of variables. To overcome this difficulty, we propose an algorithm and a tool called PROMISE (PRecision OptiMISEd) based on the delta debugging search algorithm [2] that provide a mixed precision configurationwith a worst-case complexity quadratic in the number of variables. From an initial C or C++ program and a required accuracy on thecomputed result, PROMISE automatically modifies the precision of variables. To estimate the numerical quality of results, PROMISEuses Discrete Stochastic Arithmetic (DSA) [3] which controls round-off errors in simulation programs. Unlike Precimonious [4], PROMISEdoes not focus on performance constraints, it can rather be seen as a tool helping developers to reduce the cost of double precision variablesand improve the memory usage of their code. The PROMISE tool has been successfully tested on programs implementing several numericalalgorithms including linear system solving and also on an industrial code that solves the neutron transport equations [5].

International audience; On modern multi-core, many-core, and heterogeneous architectures, floating-point computations may become non-deterministic and thus non-reproducible mainly due to non-associativity of floating-point operations. We introduce an algorithm to compute a product of two floating-point matrices that delivers reproducible results with the best possible accuracy. Our multi-level algorithm relies on fast vectorized floating-point expansions and as well as superaccumulators in a high-radix carry-save representation. We present implementations on recent Intel Xeon Phi accelerators and both AMD and NVIDIA GPUs.

International audience; This paper presents a compensated algorithm for the evaluation of the k-th derivative of a polynomial in power basis. The proposed algorithm makes it possible the direct evaluation without obtaining the k-th derivative expression of the polynomial itself, with a very accurate result to all but the most ill-conditioned evaluation. Forward error analysis and running error analysis are performed by an approach based on the data dependency graph. Numerical experiments illustrate the accuracy and efficiency of the algorithm.

International audience

International audience

International audience

International audience

International audience; The Cell processor is a new processor [2], designed by IBM, Sony and Toshiba, with an innovative architecture based on 8 Synergistic Processor Elements on the same chip. Each SPE contains a synergetic processing unit (SPU), a local memory (256KB of memory for the code and the data) and a memory flow controller. The SPU [1] is composed of a 4-way SIMD single precision FPU (SpSPU) and a 1-way SIMD double precision (DpSPU). Today, the peak rate is around 200 Gflops. Each SpSPU can perform 25.6 GFlops whereas DpSPU can only do 1.8GFlops. But SpSPU has only the rounding mode toward zero and no underflow and overflow whereas the DpSPU is fully IEEE 754 compliant.In order to deal efficiently with interval arithmetic [3] with only rounding mode toward zero, we discuss different ways to represent intervals and compare them on the SpSPU and on the DpSPU.

International audience; The CELL processor [1] jointly developed by Sony, Toshiba, and IBM provides a great potential for scientific computing with a peak performance in single precision of 204.8 Gflop/s. But, this performance is obtained with an SIMD processor which uses single precision floating numbers with a rounding mode toward zero. The goal of our work is to develop extended precision library for this architecture.In this paper, we will study how to implement the double working precision library, named double-single on the SPEs (Synergistic Processing Element) which are the workhorse processors of the CELL. The approach is near from those used in [2] for the quad-double precision arithmetic. Firstly, algorithms based on error free transformations for the operators (+, −, ×, /) are proposed for the rounding mode toward zero. We also prove their exactitude and we provide error limits on the precision of the double-single floating-point arithmetic.The second part is devoted to the implementation on the SIMD processor by taking into account advantages of the characteristics of the SPE processor, among which the fully pipelined set of instructions in single precision and the FMA (Fused Multiply-Add) operator are the most important. We have managed to implement the error-free transformations very efficiently.In the last part, the performance of our implementation are presented. Even though the theoretic peak performance of the library is much less than the performance of the double precision of the machine, which is about 2.7 Gflop/s in comparison with the 14.4 Gflop/s of the double precision, the results of our test show that it is not such that bad. When the 8 SPE are used to compute operations on very large vectors, the performance of the double-single and the true double floating point number are nearly equal.In the future, with the same approach, we will promote our work to the quad-single precision. The quad-double precision will be reached with the next CELL processorwhich will provide a SIMD processor for double precision.

International audience; Several different techniques and softwares intend to improve the accuracy of results computed in a fixed finite precision. Here we focus on a method to improve the accuracy of the product of floating point numbers. We show that the computed result is as accurate as if computed in twice the working precision. The algorithm is simple since it only requires addition, subtraction and multiplication of floating point numbers in the same working precision as the given data. Such an algorithm can be useful for example to compute the determinant of a triangular matrix and to evaluate a polynomial when represented by the root product form. It can also be used to compute the power of a floating point number.

International audience; The pseudozero set of a polynomial p is the set of complex numbers that are roots of polynomials which are near to p. This is a powerful tool to analyze the sensitivity of roots with respect to perturbations of the coefficients. Some applications in algebraic computation and robust control theory have been proposed recently. In this paper, we establish some topological and geometric properties of the pseudozero set such as boundedness, compactness and convexity.

International audience; Several different techniques and softwares intend to improve the accuracy of results computed in a fixed finite precision. Here we focus on a method to improve the accuracy of polynomial evaluation via Horner’s scheme. Such an algorithm exists for polynomials with real floating point coefficients. In this paper, we provide a new algorithm which deals with polynomials with complex floating point coefficients. We show that the computed result is as accurate as if computed in twice the working precision. The algorithm is simple since it only requires addition, subtraction and multiplication of floating point numbers in the same working precision as the given data. Such an algorithm can be useful for example to compute zeros of polynomial by Newton-like methods.

International audience; Error-free transformation is a concept that makes it possible to compute accurate results within a floating point arithmetic. Up to now, it has only be studied for real floating point arithmetic. In this short note, we recall the known error-free transformations for real arithmetic and we propose some new error-free transformations for complex floating point arithmetic. This will make it possible to design some new accurate algorithms for summation, dot product and polynomial evaluation with complex entries.

International audience; The fused multiply and add (FMA) operation computes a floating point multiplication followed by an addition or a subtraction as a single floating point operation. Intel IA-64, IBM RS/6000 and PowerPC architectures implement this FMA operation. The aim of this talk is to study how the FMA improves the computation of dot product with classical and compensated algorithms. The latters double the accuracy of the former at the same working precision. Six algorithms are considered. We present associated theoretical error bounds. Numerical experiments illustrate the actual efficiency in terms of accuracy and running time. We show that the FMA does not improve in a significant way the accuracy of the result whereas it increases significantly the actual speed of the algorithms.