3rd Workshop on Compiler-Driven Performance

October 06, 2004
Hilton Suites Toronto/Markham Conference Centre
Markham, ON

Associated with CASCON 2004


Second-Order Predictive Commoning

Arie Tal - IBM Toronto Lab

Many compiler optimization technologies are designed towards reducing memory access latency in application software. Memory access latency is most apparent in loops - iterating program code - that read from or write to a large number of memory addresses (cells). Due to the slow access to memory, the processor is usually forced to stall until the required data is retrieved from memory. Second-Order Predictive Commoning is the identification of sub-expressions and combinable sub-expressions - expressions that can be combined together (possibly through re-association) to form a sub-expression. such that the results of their computation can be reused in immediately subsequent iterations. Then, instead of just reducing the number of memory accesses, we may save computations such as multiplications, additions, function calls. Second-Order Predictive Commoning as described here was designed to handle very general forms of indexed expressions including calls to functions with parameters that are expressions based on the loop induction variable., etc. Three dimensional stencil codes contain opportunities for Second-Order Predictive Commoning to save computations of combinable sub-expressions. These sub-expressions carry the combined sum of certain memory elements over to the following iterations. For example, the subroutine "psinv" in mgrid (from the SPEC2000 benchmark) contains such an opportunity. Similar opportunities exist in subroutine "resid" in the same benchmark, tomcatv benchmark from spec92 and others.

Presentation Slides.