随着工艺水平的进步和处理器体系结构的发展，处理器的速度已远远超过了存储器的速度，从而导致了“存储墙”的出现。为了解决“存储墙”问题，减少存储访问延迟，当前的计算机大都采用层次存储系统。层次存储系统中各级存储器的有效利用依赖于程序存储访问的局部性特性，因此针对层次存储系统的局部性优化技术成为了充分发挥计算机系统性能，解决“存储墙”问题的关键技术之一。 本文着重研究了如何通过编译优化来改善程序存储访问的局部性问题。cache局部性优化和内存局部性优化是局部性优化中的关键问题。改善cache局部性可以有效减少cache失效，而改善内存局部性可以有效减少处理器间的数据通信。除了局部性之外，伪共享也对程序的执行性能有着重要的影响。因此，本文主要针对cache局部性优化、内存局部性优化和提高局部性并同时消除伪共享的问题进行了深入的研究。本文所做的创新工作主要体现在以下几点： (1) 在利用数据变换技术来优化cache局部性方面，当前的方法大都仅考虑了对仿射下标的优化，并且优化方法相对来说比较复杂，有的还限制了数据变换的种类，存在着一定的不足之处。针对这些不足之处，本文深入探讨了用数据变换来改善数据访问局部性的本质，创造性地提出了一种新的优化数据访问的投影分层技术及其基于它的数据变换框架。该框架主要利用投影技术来优化数据访问的空间局部性，并同时利用数据分层技术来解决因投影而带来的数据重叠问题。该框架不仅能处理仿射数组下标，而且还能处理许多非仿射的更复杂的数组下标，同时它还能简单直接地确定数组元素的最优存储布局以及优化数组访问的数据变换矩阵，并能使得访问间距尽量小。实验结果表明基于投影分层技术的数据变换框架能有效地提高数据访问的空间局部性。 (2) 在利用非奇异循环变换技术来优化cache局部性方面，当前的方法有的优化时间局部性不够充分，有的优化方法较为复杂，还有些未系统地考虑对程序同时进行时间局部性和空间局部性优化的问题，存在着一些不足之处。针对这些不足之处，本文提出了一种新的基于线性表出的非奇异循环变换局部性优化方法。该方法利用一组最少的线性无关向量组来线性表出数组访问的下标表达式，并据此构造非奇异变换矩阵来优化数组访问的时间局部性和空间局部性。该方法能充分开发嵌套循环中数组访问的时间局部性，能很简便地确定是否能对单个数组访问或同时对多个数组访问进行时间或空间局部性优化，并能对给定嵌套循环同时进行时间局部性和空间局部性优化。实验结果表明基于线性表出的非奇异循环变换局部性优化方法能有效提高数据访问的时间和空间局部性。 (3) 在同时利用循环变换与数据变换技术来优化cache局部性方面，当前的方法都只能对紧耦合嵌套循环进行处理，并且有的方法使用的数据变换种类有限，有的依赖于万一国防科学技术大学研究生院学位论文启发式规则，还有的仅对简单的数据访问模式有效，存在着一些不足之处。针对这些不足之处，本文结合循环变换与数据变换，提出了一种基于树形存储布局图、利用O一1整数规划来求解全局局部性优化问题的方法。在该方法中，我们用树形存储布局图来描述程序的局部性特征，并将求解局部性优化问题转化为求解树形存储布局图中最优路径集的问题，从而使我们可以用0一1整数规划来求解全局局部性优化问题。另外，利用0一1整数规划来求解局部性优化问题可以使该方法不依赖于任何启发式搜索规则。在我们限定的代价模型和循环变换与数据变换空间中，该方法可以求出最优解。该方法既能对紧藕合嵌套循环进行处理又能对一般的松藕合嵌套循环进行处理，且既适合处理数据访问是沿某维进行访问的情况又适合处理数据访问是沿斜对角线进行访问的情况。实验结果说明了该方法能显著改善局部性，并且0一1整数规划的使用并未显著增加编译时间。 (4)在优化内存局部性方面，当前的方法有的对嵌套循环以及数组的访问形式作了一定的限制，有的没有考虑尽量最大化并行度的问题，有的虽然考虑了该问题，但却没有给出数据如何分布的方法，还有的没有考虑数据复制以及偏移常量对准等问题，从而不能使得数据通信量尽量地小。针对上述不足之处，本文深入研究了分布共享存储和分布存储计算环境中内存局部性优化问题，提出了一套关于数据空间融合的理论框架，并基于该框架给出了一种有效的全局计算与数据划分方法。该方法将计算空间划分成数量尽可能多的数据无关集合，以保证能尽量最大限度地开发程序的并行性，并根据对计算空间的划分、利用数据融合技术来组织数据，以使得计算与数据能够有效对准，达到尽可能多地开发并行度和减少通信的目的。该方法能对多个嵌套循环中任意维数组进行计算和数据划分，并且能尽量开发计算划分和数据划分的并行度，该方法还能很自然地与数据复制以及偏移常量的对准结合在一起，从而能使得数据通信量尽可能地小。实验结果表明基于数据空间融合的计算与数据划分方法能有效减少通信，提高程序执行性能。 (5)深入探讨了局部性与伪共享的关系，提出了利用数据变换和调度技术来提高局?