Elementary functions, digital filters and beyond:
Symbolic-numerical methods for code generation & transformation

Sorbonne Université / LIP6

12 and 13 march 2018

Location - How to get there

More details soon.

Tentative Programme (work in progress)

This tentative programme includes talks and demos . The sessions are still being defined. Feel free to contribute by sending title+abstract to the organizers below.
Monday 12/03
Time Topic
8:30-9h00 Welcome + coffee
Core tools and libraries
Polynomial approximation with real, fixed-point, or floating-point coefficients. A small review. (S. Chevillard)

Polynomial approximation, or more generally approximation in a vector space of functions of finite dimension, plays an important role in, e.g., the design of code for numerically evaluating mathematical functions, or the design of finite impulse response filters. In this talk, I will present Remez algorithm to find the best approximation to a function with respect to the sup norm with a polynomial of a given degree and I will describe its extensions to other spaces, like Parks-McClellan algorithm for trigonometric polynomials. Specific constraints appear in practice like fixing the value of some coefficients, or constraining the number of bits on which some coefficients should be stored. We will see how these constraints may be tackled, for instance with the fpminimax algorithm or linear programming techniques. The talk will be illustrated with practical examples studied with the software tool Sollya.

Sollya and python-sollya (Ch. Lauter)

The development of certain applications using floating-point or fixed-point arithmetic requires a safe and rigorous development toolbench. Such applications include for example mathematical (libm) functions (such as exp, sin, cos) as well as digital filters for signal processing. The tool needs to support, amongst other features, rigorous function (expression) evaluation through faithful rounding, simulation of the IEEE754 roundings and operations or polynomial approximation. In this talk, we present the Sollya 6.0 software tool that has been designed for that purpose. As its key feature, Sollya provides multiple-precision faithful rounding of composite expressions through multiple-precision interval arithmetic with dynamic precision adaption and interval arithmetic. This feature comes together with a fully developed scripting language, library and dynamic extension features, certain Computer-Algebra-System features, polynomial approximation algorithms and lots of other features. We shall start the talk with a live demo of the Sollya software tool, giving an overview on the its features. We shall then discuss in more detail some of the algorithms behind the faithfully-rounded and interval arithmetic evaluation machinery inside Sollya.

Daisy - a framework for sound accuracy analysis and optimization of numerical programs (A. Izycheva)

Floating-point or fixed-point computations are an integral part of many embedded and scientific computing applications, as are the roundoff errors they introduce. They expose an interesting tradeoff between efficiency and accuracy: the more precision we choose, the closer the results will be to the ideal real arithmetic, but the more costly the computation becomes. Unfortunately, the unintuitive and complex nature of finite-precision arithmetic makes manual optimization infeasible such that automated tool support is indispensable. This talk presents an overview of Daisy, a framework for sound accuracy analysis and optimization of finite-precision programs. We will provide a high-level view of its main features: roundoff error analysis as well as rewriting and mixed-precision optimization.

Coffee break
Industrial case studies and needs
TBA

TBA

Lunch
Current state of the Metalibm effort
Metalibm-Lutetia (Ch. Lauter)

A typical floating-point environment includes support for a small set of about 30 mathematical functions such as exponential, logarithm, trigonometric and hyperbolic functions. These functions are provided by mathematical software libraries (libm), typically in IEEE754 single, double and quad precision. This talk suggests to replace this libm paradigm by a more general approach: the on-demand generation of numerical function code, on arbitrary domains and with arbitrary accuracies. First, such code generation opens up the libm function space available to programmers. It may capture a much wider set of functions, and may capture even standard functions on non-standard domains and accuracy/performance points. Second, writing libm code requires fine-tuned instruction selection and scheduling for performance, and sophisticated floating-point techniques for accuracy. Automating this task through code generation improves confidence in the code while enabling better design space exploration, and therefore better time to market, even for the libm functions. This presentation discusses the new challenges of this paradigm shift, and presents the current state of open-source function code generators available on http://www.metalibm.org/. The presentation further opens up on a discussion whether code generation for other numerical objects, such as linear time invariant filters is possible and where the synergies between all these code generation projects are.

Metalibm-Lugdunum: generating processor-specific C11 library function (N. Brunie)

TBA

Meta-implementation of vectorized logarithm function in binary floating-point arithmetic

Coffee break
Digital filters
Reliable computation of the worst-case peak gain (Th. Hilaire)

TBA

Abstracting Vector Architectures in Library Generators: Case Study Convolution Filters (A. Stojanov)

We present FGen, a program generator for high performance convolution operations (finite-impulse-response filters). The generator uses an internal mathematical DSL to enable structural optimization at a high level of abstraction. We use FGen as a testbed to demonstrate how to provide modular and extensible support for modern SIMD vector architectures in a DSL-based generator. Specifically, we show how to combine staging and generic programming with type classes to abstract over both the data type (real or complex) and the target architecture (e.g., SSE or AVX) when mapping DSL expressions to C code with explicit vector intrinsics. Benchmarks shows that the generated code is highly competitive with commercial libraries.

Towards IIR filters computing just right (F. de Dinechin)

Linear Time Invariant (LTI) filters are often specified and simulated using high-precision software, before being implemented in low-precision fixed-point hardware. A problem is that the hardware does not behave exactly as the simulation due to quantization and rounding issues. This article advocates the construction of LTI architectures that behave as if the computation was performed with infinite accuracy, then rounded only once to the low-precision output format. From this minimalist specification, it is possible to deduce the optimal values of many architectural parameters, including all the internal data formats. This requires a detailed error analysis that captures not only the rounding errors but also their infinite accumulation in recursive filters. This error analysis then guides the design of hardware satisfying the accuracy specification at the minimal hardware cost. We detail this generic methodology for the case of low-precision LTI filters in the Direct Form I implemented in FPGA logic. This approach is demonstrated by a fully automated and open-source architecture generator tool, and validated on a range of Infinite Impulse Response filters.

Apero + dinner
Tuesday 13/03
Time Topic
8:30-9h00 Welcome + coffee
Elementary function case studies
A Sagenstein experience: implementing argerfi (Ch. Lauter)

When some special function is not defined by the classical mathematical system libraries, such as libm, researchers who need it, for example to run some physical experiment and handle the data it produces, may be in trouble. The metalibm-lutetia tool is intended to be a code generation tool for open-ended mathematical functions. It might hence be used to respond in a such a case, when a user requires the implementation of some not-yet implemented function. Alone, the metalibm-lutetia tool however can only cover compositions of base functions that are already known to the tool. As a matter of fact, code generation for some mathematical function requires code to evaluate that function: we have a classical chicken-and-egg problem. In this talk, we present a recent experience that shows how this problem can be overcome. The ore_algebra package, written for the Sage Computer Algebra system, allows functions defined by a certain family of differential equations to be evaluated. By binding metalibm-lutetia to Sage, we succeeded in implementing, on a very short timeframe, the argerfi special function that we were asked to implement by a scientific colleague in Physics.

Computing floating-point functions with fixed-point operations (F. de Dinechin)

Elementary functions from the mathematical library input and output floating-point numbers. However it is possible to implement them purely using integer/fixed-point arithmetic. This option was not attractive between 1985 and 2005, because mainstream processor hardware supported 64- bit floating-point, but only 32-bit integers. This has changed in recent years, in particular with the generalization of native 64-bit integer support. The purpose of this article is therefore to reevaluate the relevance of computing floating-point functions in fixed-point. For this, several variants of the double-precision logarithm function are implemented and evaluated. Formulating the problem as a fixed-point one is easy after the range has been (classically) reduced. Then, 64-bit integers provide slightly more accuracy than 53-bit mantissa, which helps speed up the evaluation. Finally, multi-word arithmetic, critical for accurate implementations, is much faster in fixed- point, and natively supported by recent compilers. Thanks to all this, a purely integer implementation of the correctly rounded double-precision logarithm outperforms the previous state of the art, with the worst-case execution time reduced by a factor 5. This work also introduces variants of the logarithm that input a floating-point number and output the result in fixed-point. These are shown to be both more accurate and more efficient than the traditional floating-point functions for some applications.

Exact Lookup Tables for the Evaluation of Trigonometric and Hyperbolic Functions

Coffee break
TBA
TBA

TBA

TBA

Lunch
Open issues, collaborations, and works in progress