Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 1-8 |
Number of pages | 8 |
Journal | Proceedings - International Conference on Software Engineering |
DOIs | |
State | Published - 2011 |
Externally published | Yes |
Event | 4th International Workshop on Multicore Software Engineering, IWMSE 2011, Co-located with ICSE 2011 - Waikiki, Honolulu, HI, United States Duration: May 21 2011 → May 21 2011 |
Keywords
- Error analysis
- Lookup table
- Performance optimization
ASJC Scopus subject areas
- Software