Mesa: Automatic generation of lookup table optimizations

Chris Wilcox, Michelle Mills Strout, James M. Bieman

Research output: Contribution to journalConference articlepeer-review

9 Scopus citations


Scientific programmers strive constantly to meet performance demands. Tuning is often done manually, despite the significant development time and effort required. One example is lookup table (LUT) optimization, a technique that is generally applied by hand due to a lack of methodology and tools. LUT methods reduce execution time by replacing computations with memory accesses to precomputed tables of results. LUT optimizations improve performance when the memory access is faster than the original computation, and the level of reuse is sufficient to amortize LUT initialization. Current practice requires programmers to inspect program source to identify candidate expressions, then develop specific LUT code for each optimization. Measurement of LUT accuracy is usually ad hoc, and the interaction with multicore paral-lelization has not been explored. In this paper we present Mesa, a standalone tool that implements error analysis and code generation to improve the process of LUT optimization. We evaluate Mesa on a multi-core system using a molecular biology application and other scientific expressions. Our LUT optimizations realize a performance improvement of 5X for the application and up to 45X for the expressions, while tightly controlling error. We also show that the serial optimization is just as effective on a parallel version of the application. Our research provides a methodology and tool for incorporating LUT optimizations into existing scientific code.

Original languageEnglish (US)
Pages (from-to)1-8
Number of pages8
JournalProceedings - International Conference on Software Engineering
StatePublished - 2011
Externally publishedYes
Event4th International Workshop on Multicore Software Engineering, IWMSE 2011, Co-located with ICSE 2011 - Waikiki, Honolulu, HI, United States
Duration: May 21 2011May 21 2011


  • Error analysis
  • Lookup table
  • Performance optimization

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Mesa: Automatic generation of lookup table optimizations'. Together they form a unique fingerprint.

Cite this