Colorado State University
Methodology for automated lookup table optimization of scientific applications, A.
Degree: PhD, Computer Science, 2012, Colorado State University
Tuning the performance of scientific codes is challenging because of their math-intensive nature. Applications such as climate modeling and molecular biology simulate the behavior of natural systems based on scientific equations. Translating these equations into code can often yield expressions that are expensive to evaluate. Trigonometric, logarithmic, and exponential elementary functions are especially problematic because of their high cost relative to ordinary arithmetic. Lookup table (LUT) transformation can expedite function evaluation by precomputing and storing function results, thereby allowing inexpensive memory lookups to replace costly function calls. Practical concerns limit the size and accuracy of LUT data, thus the technique represents a tradeoff between error and performance. Current practice has the programmer apply each LUT transform manually, thereby impacting productivity, obfuscating code, and limiting programmer control over accuracy and performance. The goal of our research is to help scientific programmers use LUT techniques in a more effective and productive manner. Our approach substantially automates the process of applying LUT transformation via a methodology and its implementation in the Mesa tool. Mesa incorporates algorithms that make adding a LUT transform easier for the programmer, including expression enumeration, domain profiling, error analysis, performance modeling, and code generation. In addition we introduce a novel algorithm for LUT optimization that analyzes application code and helps the programmer identify the most beneficial set of expressions to transform. We demonstrate the effectiveness of our algorithms by using Mesa to perform case studies of scientific applications. Mesa achieves performance speedups of 1.4X to 6.9X without significantly compromising application accuracy. Finally we present evidence that our methodology allows the scientific programmer to be more productive and effective.
Advisors/Committee Members: Strout, Michelle Mills (advisor), Bieman, James M. (advisor), Bohm, Anton P. W. (committee member), Turk, Daniel (committee member).
Subjects/Keywords: code generation; error analysis; lookup tables; performance optimization; scientific computing
to Zotero / EndNote / Reference
APA (6th Edition):
Wilcox, C. (2012). Methodology for automated lookup table optimization of scientific applications, A. (Doctoral Dissertation). Colorado State University. Retrieved from http://hdl.handle.net/10217/67659
Chicago Manual of Style (16th Edition):
Wilcox, Chris. “Methodology for automated lookup table optimization of scientific applications, A.” 2012. Doctoral Dissertation, Colorado State University. Accessed May 06, 2021.
MLA Handbook (7th Edition):
Wilcox, Chris. “Methodology for automated lookup table optimization of scientific applications, A.” 2012. Web. 06 May 2021.
Wilcox C. Methodology for automated lookup table optimization of scientific applications, A. [Internet] [Doctoral dissertation]. Colorado State University; 2012. [cited 2021 May 06].
Available from: http://hdl.handle.net/10217/67659.
Council of Science Editors:
Wilcox C. Methodology for automated lookup table optimization of scientific applications, A. [Doctoral Dissertation]. Colorado State University; 2012. Available from: http://hdl.handle.net/10217/67659