学位论文 > 优秀研究生学位论文题录展示

数据局部性及其编译优化技术研究

作　者: 夏军
导　师: 杨学军
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 编译优化数据局部性循环变换数据变换伪共享数据分布 0-1整数规划
分类号: TP332
类　型: 博士论文
年　份: 2004年
下　载: 293次
引　用: 3次
阅　读: 论文下载

内容摘要

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

全文目录

图索引  7-9
表索引  9-10
摘要  10-12
ABSTRACT  12-15
第一章绪论  15-30
  §1.1 课题研究背景  15-17
    1.1.1 处理器与存储器的性能差异  15-16
    1.1.2 层次存储系统  16-17
    1.1.3 局部性  17
  §1.2 课题研究内容  17-21
    1.2.1 课题来源  17
    1.2.2 课题研究重点  17-21
    1.2.3 课题研究难点  21
  §1.3 相关研究工作  21-26
    1.3.1 cache局部性优化方面的相关研究工作  21-23
    1.3.2 内存局部性优化方面的相关研究工作  23-25
    1.3.3 伪共享消除方面的相关研究工作  25-26
  §1.4 本文的主要工作和创新  26-28
  §1.5 基本术语  28-29
  §1.6 论文结构  29-30
第二章基于数据变换技术的cache局部性优化  30-58
  §2.1 数据访问轨迹  31-34
  §2.2 基于投影分层技术的数据变换框架  34-36
  §2.3 优化具有类仿射下标数组的空间局部性  36-51
    2.3.1 空间局部性优化问题求解  36-48
    2.3.2 时间局部性  48
    2.3.3 松耦合嵌套循环  48-49
    2.3.4 多个嵌套循环  49
    2.3.5 无冲突访问判别条件  49-51
    2.3.6 减少数据变换所需的额外存储空间  51
  §2.4 优化具有复杂下标数组的空间局部性  51-56
  §2.5 与相关工作的比较  56-57
  §2.6 本章小结  57-58
第三章基于循环变换技术的cache局部性优化  58-77
  §3.1 优化时间局部性  59-64
    3.1.1 优化单个数组访问的时间局部性  59-62
    3.1.2 优化多个数组访问的时间局部性  62-64
  §3.2 优化空间局部性  64-69
    3.2.1 优化单个数组访问的空间局部性  64-66
    3.2.2 优化多个数组访问的空间局部性  66-67
    3.2.3 优化已具有时间局部性的数组访问的空间局部性  67-69
  §3.3 同时优化数组访问的时间局部性与空间局部性  69-72
  §3.4 构造既满足数据相关性限制又能优化局部性的循环变换矩阵  72-75
  §3.5 与相关工作的比较  75-76
  §3.6 本章小结  76-77
第四章结合循环变换与数据变换技术的cache局部性优化  77-99
  §4.1 数据的最优存储布局  78-81
  §4.2 TMLG及其构造方法  81-88
    4.2.1 子嵌套循环  81-83
    4.2.2 RNG和RLG的构造  83-85
    4.2.3 TMLG  85-87
    4.2.4 结点代价  87-88
  §4.3 基于0-1整数规划的全局局部性优化问题求解  88-93
    4.3.1 问题描述  88
    4.3.2 整数变量与目标函数  88-89
    4.3.3 限制条件  89-91
    4.3.4 例子  91-93
    4.3.5 条件控制语句和动态数据布局  93
  §4.4 与相关工作的比较  93-94
  §4.5 本章小结  94-99
第五章内存局部性优化  99-161
  §5.1 基于数据空间融合的计算与数据划分方法总揽  100-104
  §5.2 划分计算空间  104-111
    5.2.1 求解距离向量空间  105-107
    5.2.2 线性计算划分  107-111
  §5.3 数据空间的划分与融合  111-132
    5.3.1 线性数据划分  111-114
    5.3.2 线性数据划分的标准形式  114-117
    5.3.3 数据复制  117-119
    5.3.4 数据空间的融合  119-125
    5.3.5 线性数据划分的相容标准形式  125-132
  §5.4 计算与数据到虚拟处理器空间的映射  132-141
    5.4.1 情形一  132-134
    5.4.2 情形二  134-137
    5.4.3 情形三  137-138
    5.4.4 举例  138-141
  §5.5 多个嵌套循环的计算与数据划分方法  141-152
  §5.6 代码变换  152-156
  §5.7 与相关工作的比较  156-159
  §5.8 本章小结  159-161
第六章提高局部性并同时消除伪共享  161-176
  §6.1 优化空间局部性  162
  §6.2 消除伪共享  162-173
    6.2.1 并行外层循环  163-170
    6.2.2 并行最内层循环  170-173
  §6.3 多个数组的局部性提高与伪共享消除  173-174
  §6.4 与相关工作的比较  174-175
  §6.5 本章小结  175-176
第七章数据局部性编译器原型系统及实验结果  176-195
  §7.1 数据局部性编译器原型系统  176-180
    7.1.1 SUIF2编译器简介  176-177
    7.1.2 Pass编程简介  177-178
    7.1.3 原型系统  178-180
  §7.2 实验结果  180-194
    7.2.1 第二章实验结果  180-182
    7.2.2 第三章实验结果  182-184
    7.2.3 第四章实验结果  184-189
    7.2.4 第五章实验结果  189-192
    7.2.5 第六章实验结果  192-194
  §7.3 本章小结  194-195
第八章结束语  195-198
  §8.1 工作总结  195-196
  §8.2 研究展望  196-198
攻读博士学位期间发表的论文  198-199
攻读博士学位期间参与的科研项目  199-200
致谢  200-201
参考文献  201-207

数据局部性及其编译优化技术研究

内容摘要

全文目录

相似论文