A Linear Expressing Based Approach for Optimizing Locality Using Non-Singular Loop Transformations
Hua Dai · Chinese Journal of Computers · 2003
Exploiting programs’ locality is one of this most important problems in parallel compiling optimization and the program transformations are one of the most important approaches in exploiting programs’ temporal locality and spatial locality. The paper presents a new locality optimization approach using non-singular loop transformations to optimize programs’ locality, namely linear expressing based loop transformations. This approach uses a group of the least linearly independent vectors to express array accesses’ subscripts, and then constructs a non-singular loop transformation matrix to optimize array accesses’ temporal locality and spatial locality. The approach can fully exploit array accesses’ temporal locality, can easily determine whether array accesses’ temporal locality or spatial locality can be exploited, and can simultaneously optimize the given loop nest’s temporal locality and spatial locality. The experimental results show that the linear expressing based approach for optimizing locality using non-singular loop transformations presented in this paper is effective.