In this paper, we study how array contraction can enhance locality and improve performance. In our previous work, we have
developed a memory minimization scheme, SFC, which is a combination of loop shifting, loop fusion and array contraction. SFC
focuses on reducing the memory requirement, and as a by-product, it may enhance cache locality. In this paper, we study how
array contraction can contribute to cache locality and performance enhancement. We develop a memory cost model for SFC. We
also present a fusion algorithm so that the predicted locality enhancement can be realized. Experimental results on both a
real machine and a simulator demonstrate the effectiveness of array contraction on cache locality enhancement and performance
improvement.
This work is sponsored in part by National Science Foundation through grants CCR-9975309, ACI/ITR-0082834 and MIP-9610379,
by Indiana 21st Century Fund, by Purdue Research Foundation, and by a donation from Sun Microsystems, Inc.