Premium
An optimization‐based approach to lookup table program transformations
Author(s) -
Wilcox Chris,
Strout Michelle Mills,
Bieman James M.
Publication year - 2014
Publication title -
journal of software: evolution and process
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.371
H-Index - 29
eISSN - 2047-7481
pISSN - 2047-7473
DOI - 10.1002/smr.1620
Subject(s) - lookup table , computer science , programmer , table (database) , transformation (genetics) , parallel computing , code (set theory) , computer engineering , algorithm , programming language , set (abstract data type) , data mining , biochemistry , chemistry , gene
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. Copyright © 2013 John Wiley & Sons, Ltd.