Data locality optimization of interference graphs based on polyhedral computations

作者：Motallebi Hassan^*; Parsa Saeed

来源：Journal of Supercomputing, 2012, 61(3): 935-965.

DOI：10.1007/s11227-011-0660-y

• Locality optimization
• Scanning constraint
• Spatial and temporal locality
• Conflict resolving
• Eigenvalues and eigenspaces
• Parameterized polyhedra

In achieving high performance on modern architectures it is critical to make effective use of the memory hierarchy. There are compiler-directed locality enhancement techniques that allow the transformation of program to achieve a higher locality: loop transformations, which are constrained by data dependences and data layout transformations, which have a global impact on the program locality. Due to these drawbacks, there must be a unification of the two techniques to achieve the benefits of both. In this paper, a novel unification of these techniques is presented. Using a model based on parameterized polyhedra and introducing new concepts, we propose a data locality optimization algorithm.
In comparison with the other approaches, the technique proposed is capable of solving more conflicts and optimizing more references, a subtle way is proposed to optimize incompatible references to the same array, in the same loop, and also references in a cycle in the interference graph. Using parameterized cost functions, our technique estimates the importance of each sub-graph and optimizes data locality. Our experimental results show a significant improvement over the prior approaches.

• 出版日期2012-9