Optimizing inter-nest data locality in imperfect stencils based on loop blocking

With the interesting growth in high-performance computing, the performance of data-driven programs is becoming more and more dependent on fast memory access, which can be improved by data locality. Data locality between a pair of loop nest is called inter-nest data locality. A very important class of loop nests that shows a significant inter-nest data locality is stencils. In this paper, we have proposed a method to optimize inter-nest data locality in stencils and named it EALB. In the proposed method, two “compute” and “copy” loop nests within the time loop nest of stencils are partitioned into blocks and these blocks are executed interleaved. Determining the optimum block size in the proposed method is based on an evolutionary algorithm which uses cache miss rate and cache eviction rate. The experimental results show that the EALB is significantly effective compared to the original programs and has better results compared to the results of the state-of-the-art approach, Pluto.