Many floating-point formats are available, providing all different levels of precision. By mixing several of these formats in the same program, it is possible to achieve good performance while maintaining an acceptable level of output accuracy. Therefore various tools have been designed to adapt the precision of computations in floating-point programs for performance and accuracy purposes. However most of them do not consider the iterative nature of these programs. This article presents a tool that enables to adapt the precision of floating-point computations in iterative routines, at the iteration level. This tool is based on multiple-precision computations to evaluate the impact of some format adaptations on the output accuracy, and it uses the delta-debugging to isolate the most relevant instruction set to be tuned. The originality of our approach is that it relies on static loop transformations to duplicate loop body instructions, and thus to increase the number of possible instructions that can be targeted. These transformations include especially the loop splitting and unrolling, which enable to allocate different precisions for different iterations, and thus to improve the tuning process. We show the advantages of this approach on a representative set of iterative programs.

The amount of floating-point computations in numerical programs is ever increasing. In order to improve their performance, the current trend is to carefully adapt the precision of some floating-point operations, to take advantage of new features of modern architectures. Such adaptation process requires tools to evaluate the impact of these transformations on the accuracy of the output. This article presents an analysis tool to help developers in evaluating the impact of adapting the precision in floating-point programs, with a particular focus on iterative programs. This tool is implemented in the LLVM compilation framework, and it includes two main modules: fp2mp that instruments floating-point programs with multiple-precision computations, and a loop splitter that splits the iteration space of a loop into several subspaces. We illustrate the interest of this tool on various examples, and particularly how it enables to evaluate automatically the impact of adapting the precision of floating-point operations in loops by considering different precisions over the iteration space.

Polynomial evaluation is a critical part of the efficient floating-point approximation of elementary functions, in software as well as in FPGA-based systems. Designing an optimized polynomial evaluation scheme is a complex and tedious task, due to multitudes of choices in numerous dimensions: the evaluation scheme, like Horner or Estrin, needs to be selected based on implementation goals (latency, throughput, accuracy. . . ) and be adapted to a given architecture, for example by adapting the level of parallelism to the architecture capabilities. For each operation, a fixed-point or floating-point format needs to be chosen, e.g. between formats such as binary32, binary64. Furthermore some schemes and formats induce compromises, in particular when it comes to vectorized evaluation schemes. As part of a longer automated code generation toolchain, polynomial evaluation gains to be used repeatedly. Several aspects of polynomial evaluation have been presented before, such as code generation for Horner schemes with floating-point expansions or optimization of polynomial evaluation schemes. In this work we study both combination and extension of these techniques, striving for their integration in a code generator. In particular, we present an algorithm within the Metalibm-ludgdunum code generation framework, based on input by Metalibm-lutetia. Our intent is to offer state of the art multi-word evaluation with polynomial scheme space exploration with CGPE, Gappa correctness proof and advanced code generation, suited for High-Level Synthesis.

Besides scalar instructions, modern micro-architectures also provide support for vector instructions. They enable to treat packed inputs (typically 4 or 8) in a single instruction. The challenge is now to write vector programs to support mathematical functions like sin, cos, exp, log, ... which efficiently exploit those vector instructions. This article focuses on the design of vectorized implementation of log(x) function, and more particularly on its automation for different formats and micro-architectures. First it rewrites a classic range reduction in a branchless fashion so as to use at best recent micro-architecture features, like rcp (reciprocal) instruction, and to treat all inputs in the same flow. Second it details rigorously how to achieve “faithfully rounded” implementations. Third it shows how to automate this implementation process using the MetaLibm framework, on SSE/AVX and AVX2 supporting micro-architectures. Finally we illustrate that this process enables to achieve high throughput implementations for the binary32 and binary64 formats in a fully automated way.

Elementary mathematical functions are pervasively used in many applications such as electronic calculators, computer simulations, or critical embedded systems. Their evaluation is always an approximation, which usually makes use of mathematical properties, precomputed tabulated values, and polynomial approximations. Each step generally combines error of approximation and error of evaluation on finite-precision arithmetic. When they are used, tabulated values generally embed rounding error inherent to the transcendence of elementary functions. In this article, we propose a general method to use error-free values that is worthy when two or more terms have to be tabulated in each table row. For the trigonometric and hyperbolic functions, we show that Pythagorean triples can lead to such tables in little time and memory usage. When targeting correct rounding in double precision for the same functions, we also show that this method saves memory and floating-point operations by up to 29 and 42 percent, respectively.

Nowadays the automated design of efficient floating-point implementations of correctly rounded elementary functions like cos, sin, log, exp, · · · is a real challenge. Indeed, the variety of hardware architectures and floating-point formats makes such implementation process tedious and error-prone. This article focuses on the particular case of floating-point logb(x) functions on integer processors. First it proposes a unified range reduction for logb(x), that enables to reduce the evaluation of these functions to a single well-chosen polynomial. Second it gives some sufficient conditions on the approximation and evaluation errors to guarantee correct rounding. And third it shows how to automate the implementation process on integer processors, when b ∈ {2, exp(1), 10}. Finally we illustrate how this automated approach enables to speedup the design of efficient implementations of logb(x) for standard floating-point formats.

Software evaluation of elementary functions usually requires three steps: a range reduction, a polynomial evaluation, and a reconstruction step. These evaluation schemes are designed to give the best performance for a given accuracy, which requires a fine control of errors. One of the main issues is to minimize the number of sources of error and/or their influence on the final result. The work presented in this article addresses this problem as it removes one source of error for the evaluation of trigonometric functions. We propose a method that eliminates rounding errors from tabulated values used in the second range reduction for the sine and cosine evaluation. When targeting correct rounding, we show that such tables are smaller and make the reconstruction step less expensive than existing methods. This approach relies on Pythagorean triples generators. Finally, we show how to generate tables indexed by up to 10 bits in a reasonable time and with little memory consumption.

We consider the problem of computing IEEE floating-point squares by means of integer arithmetic. We show how to exploit the specific properties of squaring in order to design and implement algorithms that have much lower latency than those for general multiplication, while still guaranteeing correct rounding. Our algorithms are parameterized by the floating-point format, aim at high instruction-level parallelism (ILP) exposure, and cover all rounding modes. We show further that their C implementation for the binary32 format yields efficient codes for targets like the ST231 VLIW integer processor from ST Microelectronics, with a latency at least 1.75x smaller than that of general multiplication in the same context.

Designing an efficient floating-point implementation of a function based on polynomial evaluation requires being able to find an accurate enough evaluation code, exploiting at most the target architecture features. This article introduces CGPE, a tool dealing with the generation of fast and certified codes for the evaluation of bivariate polynomials. First we discuss the issue underlying the evaluation scheme combinatorics before giving an overview of the CGPE tool. The approach we propose consists in two steps: the generation of evaluation schemes by using some heuristics so as to quickly find some of low latency, and the selection that mainly consists in automatically checking their scheduling on the given target and validating their accuracy. Then, we present on-going development and ideas for possible improvements of the whole process. Finally, we illustrate the use of CGPE on some examples, and show how it allows us to generate fast and certified codes in a few seconds and thus to reduce the development time of libms like FLIP.

In this paper, we show how to reduce the computation of correctly rounded square roots of binary floating-point data to the fixed-point evaluation of some particular integer polynomials in two variables. By designing parallel and accurate evaluation schemes for such bivariate polynomials, we show further that this approach allows for high instruction-level parallelism (ILP) exposure, and thus, potentially low-latency implementations. Then, as an illustration, we detail a C implementation of our method in the case of IEEE 754-2008 binary32 floating-point data (formerly called single precision in the 1985 version of the IEEE 754 standard). This software implementation, which assumes 32-bit unsigned integer arithmetic only, is almost complete in the sense that it supports special operands, subnormal numbers, and all rounding-direction attributes, but not exception handling (that is, status flags are not set). Finally, we have carried out experiments with this implementation on the ST231, an integer processor from the STMicroelectronics' ST200 family, using the ST200 family VLIW compiler. The results obtained demonstrate the practical interest of our approach in that context: for all rounding-direction attributes, the generated assembly code is optimally scheduled and has indeed low latency (23 cycles).

Most current square root implementations for FPGAs use a digit recurrence algorithm which is well suited to their LUT structure. However, recent computing-oriented FPGAs include embedded multipliers and RAM blocks which can also be used to implement quadratic convergence algorithms, very high radix digit recurrences, or polynomial approximation algorithms. The cost of these solutions is evaluated and compared, and a complete implementation of a polynomial approach is presented within the open-source FloPoCo framework. This polynomial approach allows a shorter latency and higher frequency than the digit recurrence approach, and improves over previous multiplicative approaches. However, the cost of IEEE-compliant correct rounding is shown to be very high.

This paper deals with the design and implementation of low latency software for binary floating-point division with correct rounding to nearest. The approach we present here targets a VLIW integer processor of the ST200 family, and is based on fast and accurate programs for evaluating some particular bivariate polynomials. We start by giving approximation and evaluation error conditions that are sufficient to ensure correct rounding. Then we describe the heuristics used to generate such evaluation programs, as well as those used to automatically validate their accuracy. Finally, we propose, for the binary32 format, a complete C implementation of the resulting division algorithm. With the ST200 compiler and compared to previous implementations, the speed-up observed with our approach is by a factor of almost 1.8.