Tool support for software lookup table optimization

Chris Wilcox, Michelle Mills Strout, James M. Bieman

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

A number of scientific applications are performance-limited by expressions that repeatedly call costly elementary functions. Lookup table (LUT) optimization accelerates the evaluation of such functions by reusing previously computed results. LUT methods can speed up applications that tolerate an approximation of function results, thereby achieving a high level of fuzzy reuse. One problem with LUT optimization is the difficulty of controlling the tradeoff between performance and accuracy. The current practice of manual LUT optimization adds programming effort by requiring extensive experimentation to make this tradeoff, and such hand tuning can obfuscate algorithms. In this paper we describe a methodology and tool implementation to improve the application of software LUT optimization. Our Mesa tool implements source-to-source transformations for C or C++ code to automate the tedious and error-prone aspects of LUT generation such as domain profiling, error analysis, and code generation. We evaluate Mesa with five scientific applications. Our results show a performance improvement of 3.0× and 6.9× for two molecular biology algorithms, 1.4× for a molecular dynamics program, 2.1× to 2.8× for a neural network application, and 4.6× for a hydrology calculation. We find that Mesa enables LUT optimization with more control over accuracy and less effort than manual approaches.

Original languageEnglish (US)
Pages (from-to)213-229
Number of pages17
JournalScientific Programming
Volume19
Issue number4
DOIs
StatePublished - 2011
Externally publishedYes

Keywords

  • code generation
  • error analysis
  • fuzzy reuse
  • Lookup table
  • memoization
  • performance optimization
  • scientific computing

ASJC Scopus subject areas

  • Software
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Tool support for software lookup table optimization'. Together they form a unique fingerprint.

Cite this