An optimization-based approach to lookup table program transformations

Scientific programmers can improve the performance of function evaluation by precomputing and storing results in a lookup table (LUT), thereby replacing costly evaluation code with an inexpensive memory access. A code transformation that replaces computation with LUT code can improve performance; however, accuracy is reduced because of error inherent in reconstructing values from LUT data. LUTs are commonly used to approximate expensive elementary functions. The current practice is for software developers to: (i) manually identify expressions that can benefit from an LUT; (ii) modify the code by hand to implement the LUT transformation; and (iii) run experiments to determine if the resulting error is within application requirements. This approach reduces productivity, obfuscates code, and limits programmer control over accuracy and performance. We propose source code analysis and program transformation to substantially automate LUT transformations. Our approach uses a novel optimization algorithm that selects Pareto optimal sets of expressions that benefit most from an LUT, on the basis of the error and performance estimates. We demonstrate our methodology with the Mesa tool, which achieves speedups of 1.4-6.8× on scientific codes with an acceptable loss of accuracy. Our tool makes the programmer more productive and facilitates finding effective LUT transformations.