Optimizing Inter-Nest Data Locality Using Loop Splitting and Reordering

With the increasing gap between processor speed and memory latency, the performance of data-dominated programs are becoming more reliant on fast data access, which can be improved using data locality optimization. Most studies in this area focus on optimizing data locality in individual loop nests. However in many embedded applications, data access patterns exhibit a significant amount of inter-nest reuse. In this paper, we present a compiler strategy that optimizes inter-nest data locality using code restructuring and loop transformations. Our approach captures data reuse between all loop nests in the program and then splits and reorders the nests so that those sharing arrays are closer together. The transformed program is then further optimized using loop transformations. We improve on previous studies by using global program analysis and integer linear programming to find the best nest ordering. The approach has been tested on many data-intensive embedded kernels and our simulation results indicate promising performance improvements.