October 06, 2004
Hilton Suites Toronto/Markham Conference Centre
Markham, ON
Associated with CASCON 2004
(http://www.cas.ibm.com/cascon)
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.