Scientific computing presents an insatiable demand for more performance, motivating the search
for effective tuning methods. Lookup table (LUT) optimization is a tuning approach that works
by reducing the amount of computation performed by a scientific application. LUT optimizations
precompute and store the results of complex expressions in a table, allowing a memory access to
replace evaluation of those expressions during program execution. The result is a gain in
performance, assuming that:
- Access to LUT data is significantly faster than evaluation of the expression
- Reuse of LUT data is sufficient to amortize the LUT initialization.
LUT optimizations have generally been incorporated into applications by hand due to a lack of
support methodology and tools. As a result, programmers must inspect program source to identify
candidate expressions, then develop custom LUT code for each optimization. Measurement of LUT
accuracy and performance characteristics is usually ad-hoc as well. In this paper we present a
standalone software tool called Mesa, which incorporates error analysis and code generation to
partially automate the LUT optimization process.
We have evaluated the LUT code generated by Mesa for a representative molecular biology
application and several additional scientific expressions. Our LUT optimizations realize a serial
performance improvement of up to 5X for the application and 45X for the expressions, while tightly
controlling error. Our research provides a methodology and tool for incorporating LUT optimizations
into existing scientific code.
