Past Events

PhD Defense

Novel Polynomial Approximation Methods for Generating Correctly Rounded Elementary Functions

 

Download as iCal file

Wednesday, August 18, 2021, 01:00pm - 03:00pm
 

Speaker: Jay Lim

Location : Remote via Zoom

Committee: 

Prof. Santosh Nagarakatte (chair)

Prof. Ulrich Kremer

Prof. Richard Martin

Prof. Zachary Tatlock (external committee)

Event Type: PhD Defense

Abstract: All endeavors in science use math libraries to approximate elementary functions. Unfortunately, mainstream math libraries for floating point (FP) do not produce correctly rounded results for all inputs. In addition, given the importance of FP performance in numerous domains, several new variants of FP and its alternatives have been proposed, which do not yet have correctly rounded math libraries. This dissertation proposes the RLibm approach, a collection of novel techniques for generating polynomial approximations that produces correctly rounded results of an elementary function f(x). Existing approaches generate polynomials that approximate the real value of f(x) using the minimax approach. In contrast, the RLibm approach makes a case for generating polynomials that approximate the correctly rounded result of f(x) (i.e., the exact value of f(x) computed in reals and rounded to the target representations). This approach provides more freedom in generating efficient polynomials that produce correctly rounded results for all inputs. Additionally, this dissertation makes the following contributions. First, we show that the problem of generating polynomials that produce correctly rounded results can be structured as a linear programming problem. Second, the RLibm approach accounts for numerical errors that occur from range reduction by automatically adjusting the amount of freedom available to generate polynomials. The generated polynomial with RLibm produces the correctly rounded results for all inputs. Third, we propose a set of techniques to develop correctly rounded elementary functions for 32-bit types. Specifically, we generate efficient piecewise polynomials using counterexample guided polynomial generation and bit-pattern based domain splitting. Finally, we extend the RLibm approach to generate a single polynomial approximation that produces the correctly rounded results for multiple rounding modes and multiple precision configurations. To generate correctly rounded elementary functions for n-bit type, our key idea is to generate a polynomial approximation for a (n+2)-bit representation using the round-to-odd mode. We provide formal proof that the resulting polynomial will produce the correctly rounded results for all standard rounding modes and for multiple representations with k bits where k is less than or equal to n. Using the RLibm approach, we have developed several implementations of elementary functions for various representations and rounding modes. Our elementary functions produce the correctly rounded results for all inputs in the target representation. These functions are faster than state-of-the-art math libraries which have been optimized for decades. Our prototype is the first 32-bit float library that produces the correctly rounded results with all standard rounding modes in the IEEE-754 standards for all inputs, Additionally, we provide the first correctly rounded 32-bit posit32 library.

: 

 

Join Zoom Meeting
https://rutgers.zoom.us/j/97268701847?pwd=L1BlVFdDcXlPUWdYZE9BdFZWVFJNQT09
Join by SIP

Meeting ID: 972 6870 1847
Password: 643815
One tap mobile
+13126266799,,97268701847# US (Chicago)
+16465588656,,97268701847# US (New York)
Join By Phone
+1 312 626 6799 US (Chicago)
+1 646 558 8656 US (New York)
+1 301 715 8592 US (Washington DC)
+1 346 248 7799 US (Houston)
+1 669 900 9128 US (San Jose)
+1 253 215 8782 US (Tacoma)
Meeting ID: 972 6870 1847
Find your local number: https://rutgers.zoom.us/u/aIaZDfnGy
Join by Skype for Business
https://rutgers.zoom.us/skype/97268701847