Sorbonne Université / LIP6
12 and 13 march 2018
Monday 12/03  

Time  Topic 
8:309h00  Welcome + coffee 
Core tools and libraries  
Polynomial approximation with real, fixedpoint, or floatingpoint 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 ParksMcClellan 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 pythonsollya (Ch. Lauter)
The development of certain applications using floatingpoint or fixedpoint 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 multipleprecision faithful rounding of composite expressions through multipleprecision 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 ComputerAlgebraSystem 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 faithfullyrounded and interval arithmetic evaluation machinery inside Sollya. 

Daisy  a framework for sound accuracy analysis and optimization of numerical programs (A. Izycheva)
Floatingpoint or fixedpoint 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 finiteprecision 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 finiteprecision programs. We will provide a highlevel view of its main features: roundoff error analysis as well as rewriting and mixedprecision optimization. 

Coffee break  
Industrial case studies and needs  
TBA


TBA


Lunch  
Current state of the Metalibm effort  
MetalibmLutetia (Ch. Lauter)
A typical floatingpoint 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 ondemand 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 nonstandard domains and accuracy/performance points. Second, writing libm code requires finetuned instruction selection and scheduling for performance, and sophisticated floatingpoint 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 opensource 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. 

MetalibmLugdunum: generating processorspecific C11 library function (N. Brunie)
TBA 

Metaimplementation of vectorized logarithm function in binary floatingpoint arithmetic


Coffee break  
Digital filters  
Reliable computation of the worstcase 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 (finiteimpulseresponse 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 DSLbased 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 highprecision software, before being implemented in lowprecision fixedpoint 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 lowprecision 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 lowprecision LTI filters in the Direct Form I implemented in FPGA logic. This approach is demonstrated by a fully automated and opensource architecture generator tool, and validated on a range of Infinite Impulse Response filters. 

Apero + dinner  
Tuesday 13/03  
Time  Topic 
8:309h00  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 metalibmlutetia tool is intended to be a code generation tool for openended mathematical functions. It might hence be used to respond in a such a case, when a user requires the implementation of some notyet implemented function. Alone, the metalibmlutetia 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 chickenandegg 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 metalibmlutetia 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 floatingpoint functions with fixedpoint operations (F. de Dinechin)
Elementary functions from the mathematical library input and output floatingpoint numbers. However it is possible to implement them purely using integer/fixedpoint arithmetic. This option was not attractive between 1985 and 2005, because mainstream processor hardware supported 64 bit floatingpoint, but only 32bit integers. This has changed in recent years, in particular with the generalization of native 64bit integer support. The purpose of this article is therefore to reevaluate the relevance of computing floatingpoint functions in fixedpoint. For this, several variants of the doubleprecision logarithm function are implemented and evaluated. Formulating the problem as a fixedpoint one is easy after the range has been (classically) reduced. Then, 64bit integers provide slightly more accuracy than 53bit mantissa, which helps speed up the evaluation. Finally, multiword 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 doubleprecision logarithm outperforms the previous state of the art, with the worstcase execution time reduced by a factor 5. This work also introduces variants of the logarithm that input a floatingpoint number and output the result in fixedpoint. These are shown to be both more accurate and more efficient than the traditional floatingpoint 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 