Studies On Data Locality And Compiler Optimization Techniques

With the progress of semiconductor and manufacture techniques and the fast development of processor architectures, the speed of processors has far exceeded the speed of memories, which leads to the occurrence of "Memory Wall". To solve this problem and reduce memory access latency, memory hierarchies in the form of one or more levels of cache have been used extensively in current computer systems. The effective use of caches in the memory hierarchy is determined to a great extent by the locality characteristics of the memory accesses, and therefore the techniques of optimizing locality for the memory hierarchy have become one of the key techniques for improving the performance of computer systems and solving the "Memory Wall" problem.This paper researches the problem of how to improve the locality of memory accesses from the aspect of compiler optimizing techniques. Cache locality optimizations and memory locality optimizations are two key problems in locality optimizations. Improving cache locality can effectively reduce cache miss rate, while improving memory locality can effectively reduce data communication overheads among processors. Besides locality, false sharing also greatly affects the performance of programs. Therefore, cache locality optimizations, memory locality optimizations and locality optimizations with false sharing elimination are lucubrated in this paper. Primary innovative work in this paper can be summarized as following:(i) In the aspect of cache locality optimizations based on data transformation techniques, most of current approaches can only optimize affine subscripts and are complex. Some approaches even constrain the kinds of data transformations. To overcome the above deficiencies, we discuss the essence of data transformations to improve locality and innovatively propose a new projection-delamination technique for optimizing spatial locality and a data transformation framework based on this technique. In this framework, projection technique is adopted to optimize the spatial locality of data access and delamination technique is used to solve the problem of data overlapping caused by projection. The framework can deal with not only arrays with affine subscripts, but also arrays with many complex non-affine subscripts. Moreover, the framework can make access stride as small as possible and determine the optimal storage layout of data and data transformation matrix for optimizing data access directly and easily. The experimental results show that the projection-delamination based data transformation framework is effective in optimizing spatial locality.(ii) In the aspect of cache locality optimizations based on non-singular loop transformation techniques, some of current approaches can not fully exploit temporal locality, some approaches are complex and some do not consider optimizing temporal locality and spatial locality simultaneously. To overcome the above deficiencies, we propose a new linear expressing based approach for optimizing locality using non-singular 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 is effective in optimizing temporal locality and spatial locality.(iii) In the aspect of cache locality optimizations based on the combination of loop transformation and data transformation techniques, current approaches can only deal with perfectly nested loops. Furthermore, some approaches constrain the kinds of data transformations, some rely on heuristics and some are only effective...