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

利用程序分析和优化提高Cache性能

作　者: 付雄
导　师: 陈意云
学　校: 中国科学技术大学
专　业: 计算机软件与理论
关键词: Cache行为复用距离源代码级插桩数据布局空间局部性程序变换动态数组重组结构拆分
分类号: TP332.3
类　型: 博士论文
年　份: 2007年
下　载: 390次
引　用: 4次
阅　读: 论文下载

内容摘要

在近40年来，处理器运行速度的增长和存储器访问速度的增长之间存在着巨大的差距，这使得两者之间的速度差距越来越大，导致的“Memory Wall”问题变得越来越严重，已经成为整个系统性能最主要的瓶颈之一。现代计算机体系结构中广泛采用Cache来缓解这两者之间的速度差距，使得Cache已经成为影响处理器性能、能耗、价值的重要因素之一。Cache的充分利用很大程度上取决于程序自身的局部性，特别是访问数据的局部性，包括时间局部性和空间局部性。优化程序的数据局部性成为提高Cache性能的重要方法之一。由于无需硬件的支持，具有良好的跨平台性．利用程序分析和优化来改善程序的局部性，提高Cache性能成为当前研究的热点。过去在这方面的工作有两个重要的思路：一是针对程序运行时的访问数据，利用相关的Cache行为模型，建立一些程序分析工具，从源代码级给出程序Cache性能的瓶颈，指导程序员通过程序变换来优化程序的局部性，从而提高Cache性能；二是在编译器上开发编译优化过程，或者开发专门的程序优化工具，通过对程序进行分析，在此基础上自动进行程序变换，包括代码变换和数据变换两种，优化程序的局部性，从而提高Cache性能。本文根据上面的思路进行了下面的一些工作：(1)程序Cache行为模型的研究虽然复用距离已经成为程序Cache行为的一种重要度量标准，但是高复杂度和可能存在的内存溢出问题使得其难以被应用。在通过引入最大Cache大小，限制复用距离分析范围的基础上，本文提出了一种受限的复用距离模型。受限的复用距离舍弃少量访问的复用距离分析精度，有效地避免了进行复用距离分析时可能导致的内存溢出问题，同时使得复用距离的分析达到访问数据次数的线性时间复杂度。文章还通过实验说明了基于受限的复用距离进行Cache失效率分析的可行性和正确性。(2)程序Cache行为分析工具的设计与实现程序Cache行为的分析和理解能够帮助程序员寻找程序中Cache性能的瓶颈，指导程序员通过程序变换改善程序局部性，提高程序Cache性能。本文介绍一种基于复用距离的程序Cache行为分析工具的设计与实现，该工具利用一种基于中间信息栈的源代码级插桩收集程序的访存信息，然后基于受限的复用距离模型分析程序的Cache行为。同时还通过示例表明该分析工具不但能在源代码中给出Cache性能瓶颈的位置，指导进行代码变换；而且还能分析变量的Cache行为关系，指导进行数据变换。(3)基于复用距离分布的数据布局优化在利用程序Cache行为分析工具进行分析时，总结出程序中经常在一起访问的变量的复用距离在分布上具有一定的相似性。如果将这些变量进行重组，改变其布局，则能提高Cache性能。根据这个原理，本文设计并实现了一个数据布局优化框架，在框架中采用了一种基于复用距离分布的变量关系模型，用于寻找程序中经常在一起访问的变量。目前在框架中实现了一种动态数组的重组方法，用来重组利用变量关系模型发现的动态数组，以此来提高程序的数据局部性。针对SPEC CPU2000中部分测试程序的实验表明了该优化框架在优化数据局部性和提高数据Cache性能上具有一定的可行性和有效性。(4)利用结构拆分提高Cache性能结构拆分作为一种常用的通过数据变换提高Cache性能的方法，由于只需要分析结构属性域之间的相对关系，具有一定的特殊性。为了克服复用距离分析的复杂性，本文在引入一种较复用距离更为简单的距离的基础上，提出了一种属性域关系模型来度量结构中属性域之间的关系，然后寻找程序中的结构的优化布局，通过结构拆分来优化数据布局，从而提高数据Cache性能。相关的实验表明了这种基于属性域关系模型的结构拆分在提高Cache性能上有一定的有效性。

全文目录

中文摘要  5-7
英文摘要  7-9
目录  9-12
插图目录  12-14
表格目录  14-15
第一章绪论  15-33
  §1.1 研究背景  15-21
    §1.1.1 "Memory Wall"问题  15-19
    §1.1.2 Cache基础知识  19-21
  §1.2 提升Cache性能的方法  21-25
    §1.2.1 降低Cache失效率  21-23
    §1.2.2 减少失效开销  23-24
    §1.2.3 减少Cache命中时间  24-25
  §1.3 基于软件方法提高Cache性能  25-30
    §1.3.1 软件预取(Software Prefetching)  25-26
    §1.3.2 代码变换(Code Transformation)  26-28
    §1.3.3 数据变换(Data Reorganization)  28-30
  §1.4 本文概述  30-33
    §1.4.1 研究思路  30-31
    §1.4.2 研究内容  31-32
    §1.4.3 文章组织  32-33
第二章基于复用距离的Cache失效率分析  33-49
  §2.1 基本知识  33-37
    §2.1.1 定义  33-35
    §2.1.2 分析方法  35-37
  §2.2 受限的复用距离  37-40
    §2.2.1 基本思想  37-38
    §2.2.2 分析算法  38-40
    §2.2.3 性能分析  40
  §2.3 Cache失效率分析  40-41
  §2.4 实验及结果分析  41-46
    §2.4.1 试验环境  41-42
    §2.4.2 测试结果  42-43
    §2.4.3 Cache失效率比较  43-46
  §2.5 相关工作  46-47
  §2.6 本章小结  47-49
第三章一种Cache行为分析工具的设计与实现  49-69
  §3.1 概述  49-53
    §3.1.1 背景介绍  49-50
    §3.1.2 工具框架  50-51
    §3.1.3 JavaCC简介  51-53
  §3.2 源代码级插桩  53-60
    §3.2.1 插桩思想  53-54
    §3.2.2 变量信息的保存  54-56
    §3.2.3 访存变量的收集  56-58
    §3.2.4 插桩代码的生成  58-60
  §3.3 Cache行为分析  60-63
    §3.3.1 受限的复用距离分析  60-61
    §3.3.2 代码行Cache行为分析  61-62
    §3.3.3 变量的Cache行为分析  62-63
  §3.4 实验结果及分析  63-66
    §3.4.1 工具实现  63
    §3.4.2 一个例子  63-66
  §3.5 相关工作  66-67
  §3.6 本章小结  67-69
第四章基于复用距离分布的数据布局优化  69-87
  §4.1 概述  69-73
    §4.1.1 背景介绍  69-71
    §4.1.2 优化框架  71-73
  §4.2 变量关系分析  73-79
    §4.2.1 分析思想  73-75
    §4.2.2 变量关系模型  75-78
    §4.2.3 变量分组  78-79
  §4.3 动态数组重组  79-82
    §4.3.1 重组方法  79-82
    §4.3.2 关键问题  82
    §4.3.3 重组实现  82
  §4.4 实验结果及分析  82-85
    §4.4.1 实验结果  82-84
    §4.4.2 数据Cache优化分析  84-85
  §4.5 相关工作比较  85-86
  §4.6 本章小结  86-87
第五章利用结构拆分优化数据Cache性能  87-103
  §5.1 概述  87-89
    §5.1.1 背景介绍  87-88
    §5.1.2 优化框架  88-89
  §5.2 属性域关系分析  89-93
    §5.2.1 基本思想  89-90
    §5.2.2 属性域关系模型  90-92
    §5.2.3 属性域分组  92-93
  §5.3 结构拆分  93-98
    §5.3.1 拆分方法  93-97
    §5.3.2 关键问题  97-98
  §5.4 实验结果及分析  98-101
    §5.4.1 实验结果  98-99
    §5.4.2 数据Cache优化分析  99-101
  §5.5 相关工作比较  101
  §5.6 本章小结  101-103
第六章结论  103-109
  §6.1 本文主要工作  103-105
  §6.2 进一步工作  105-109
参考文献  109-121
致谢  121-123
攻读学位期间发表和投出的学术论文  123

利用程序分析和优化提高Cache性能

内容摘要

全文目录

相似论文