Loop transformation techniques have matured to the point where the
techniques are well integrated into production optimizing
compilers~\cite{kaixpert:97}. However, we believe that new and
aggressive techniques are necessary because: $i$) computer system
manufacturers have announced their plans for forthcoming processors
with over 1GHz clock frequency, wherein the miss penalties can be very
high, and $ii$) transformation techniques have saturated in that they
have delivered majority of the benefit that can be obtained with
perfectly nested loops.  The new techniques must target improvement of
coverage, that is the classes of loops that can be optimized for
locality of data access.  In this paper, we present a new technique
called size-reduction transformation to improve data access locality
in a class of non-perfectly nested loops.  The new technique is very
effective, when existing techniques, namely, linear loop and array
transformations, fail to improve locality of reference.
Size-reduction transformations are implemented in IBM's Fortran 90
optimizing compiler released recently, and have contributed
significantly to the high performance of the compiler.


<p><hr>

The author's web site:
<a href="mailto:dkulki@vnet.ibm.com">dkulki@vnet.ibm.com</a>