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

面向软件管理片上存储器的编译优化技术研究

作　者: 汪黎
导　师: 杨学军
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 软件管理片上存储器存储器管理便笺存储器流寄存器文件图着色区间着色置换图可比图
分类号: TP333
类　型: 博士论文
年　份: 2009年
下　载: 127次
引　用: 1次
阅　读: 论文下载

内容摘要

由于处理器性能和存储器性能的巨大差异,导致了“存储墙”问题的出现,使得存储系统成为系统的瓶颈。传统计算机体系结构均采用硬件管理的cache来解决存储墙问题。然而,随着应用和工艺的发展,Cache逐渐暴露出一些问题。相比之下,软件管理的片上存储器以其面积、功耗和访问时间等方面的优势,被认为是解决存储墙问题的一个有效途径。目前,软件管理的片上存储器已被普遍运用于嵌入式系统、流处理器和图形处理器中,并被逐渐运用到新型高性能计算机体系结构中。与硬件管理的cache不同,软件管理的片上存储器需要由软件通过数据传输语句显式地管理所有片上与片外存储器之间的数据传输,决定数据进入存储器的时机和位置。软件管理的片上存储器给编译提出了重要的挑战。如何在保证程序正确性的基础上,尽可能提高有限的片上存储器空间的利用率,尽量避免存储器碎片;充分捕获数据复用,优化存储层次间的通信,从而最小化存储器带宽需求;开发计算与访存并行,有效隐藏存储器访问延迟,是提高基于软件管理片上存储器的系统上程序性能的关键。本文重点研究了面向软件管理片上存储器的编译优化问题。本文的主要工作和创新概述如下:(1)提出了基于置换图着色的便笺存储器分配算法。现代嵌入式系统中,广泛地将片上存储器组织为软件管理的便笺存储器(Scratchpad Memory, SPM)。本文深入研究了面向嵌入式应用的SPM分配问题,首次发现了大部分嵌入式应用的相干图(Interference Graph)为置换图(Permutation Graph),从而能在线性时间内获得最优的SPM分配。本文首次提出了一个基于置换图着色的SPM分配算法。理论分析和实验表明,基于置换图着色的SPM分配算法与国际上最新的基于超完美图(Superperfect Graph)的SPM分配算法相比,流程更简洁,复杂度更低,性能更优。(2)提出了基于存储器着色的流寄存器文件分配框架。流体系结构是一种新兴的面向流应用的高性能计算机体系结构。流体系结构采用软件管理的片上存储器,称为流寄存器文件(Stream Register File, SRF),作为数据的核心存储部件。SRF是不可旁路的存储层次,软件必须保证计算需要的输入流提前加载到SRF中,并为输出流分配足够的SRF空间。优良的SRF分配方案还应能在避免引入额外的片外存储器传输的前提下,有效地捕获流应用中广泛存在的生产者消费者局部性,并尽可能地开发计算与访存并行。本文提出了一套基于存储器着色(即存储器划分加上图着色寄存器分配)技术的SRF分配框架。本文研究的新颖之处在于将开发重用和并行巧妙地整合到传统的图着色寄存器分配框架中。此外,针对应用的特点,本文对传统的图着色寄存器分配技术做出了一些改进,如提出了渐增的联合技术,寄存器排序技术。实验表明基于存储器着色的SRF分配框架能够在不引入溢出的前提下,有效地开发复用和并行。(3)提出了基于最佳有向路径寻找的流寄存器文件分配算法。基于存储器着色的SRF分配框架能够有效地开发复用和并行。但是,存储器着色技术在划分SRF以及对相干图进行着色时有一定的缺陷,容易引入SRF空间浪费。本文的另一个研究重点是在相干图确定的情况下(即操作流相干图开发复用和并行后),如何最小化需要的SRF空间,避免引入存储碎片。本文首次发现了大部分的流应用的相干图为可比图(Comparability Graph),或可以降解为多个可比子图,从而能够获得多项式时间的最优SRF分配。本文首次将SRF分配问题建模为最佳有向路径寻找问题,提出了一个新颖的SRF分配算法。严格的理论分析和大量的实验表明,我们的算法能获得最优或近似最优的SRF分配。相对目前普遍采用的基于First-Fit的启发式算法,我们的算法具有更好的性能。(4)提出了基于层次图着色的软件管理多级存储层次分配算法。现代的高性能计算机体系结构中,为了更有效地实现计算与访存的平衡,优化访存带宽和延迟,越来越多地采用软件管理的多级存储层次来替代硬件管理的多级cache存储层次。传统的编译优化研究大都面向单一存储层次,缺乏对存储层次全局的综合考虑,对存储层次间通信等的优化不足。而最小化存储层次间的通信,能大大减少存储器带宽需求,是影响性能的一个重要因素。本文扩展了图着色寄存器分配算法,首次将其运用到多级存储层次分配上。通过将存储层次建模为一个带权图,我们的方法可以运用到任何多级软件管理存储层次组织上。我们对传统数据相干图进行扩展,提出路径合并和路径消解技术,有效地减少存储层次间通信。通过数据生存期扩展技术,还能有效地进行计算与访存并行的开发,从而隐藏存储访问延迟。以上的优化都跟扩展后的图着色寄存器分配框架巧妙地整合在一起。实验表明,我们的算法有良好的性能。

全文目录

摘要  12-14
ABSTRACT  14-17
第一章绪论  17-35
  1.1 课题研究背景  17-23
    1.1.1 存储墙问题  17-18
    1.1.2 Cache 存在的问题  18-19
    1.1.3 软件管理片上存储器  19-23
  1.2 课题研究内容  23-26
    1.2.1 课题来源  23-24
    1.2.2 课题研究重点  24-25
    1.2.3 课题研究难点  25-26
  1.3 相关研究工作  26-31
    1.3.1 便笺存储器分配的相关工作  26-28
    1.3.2 流寄存器文件分配的相关工作  28-29
    1.3.3 其它片上软件管理存储器分配的相关工作  29-30
    1.3.4 多级软件管理存储层次分配的相关工作  30-31
  1.4 本文的主要工作和创新  31-32
  1.5 论文结构  32-35
第二章基于置换图着色的便笺存储器分配算法  35-53
  2.1 算法背景  35-39
    2.1.1 带权图的区间着色  35-37
    2.1.2 置换图及其性质  37-39
  2.2 问题提出及建模  39-43
    2.2.1 问题建模  39-42
    2.2.2 嵌入式应用特点  42-43
  2.3 置换图判定  43-47
  2.4 便笺存储器分配算法  47-48
  2.5 评测  48-50
  2.6 本章小结  50-53
第三章基于存储器着色的流寄存器文件分配框架  53-83
  3.1 算法背景  54-61
    3.1.1 流体系结构和编程模型  54-56
    3.1.2 图着色寄存器分配技术  56-60
    3.1.3 存储器着色技术  60-61
  3.2 问题提出及建模  61-66
  3.3 算法框架  66-77
    3.3.1 预处理  67
    3.3.2 生存期分割  67-70
    3.3.3 生存期联合  70-73
    3.3.4 生存期延长  73-77
    3.3.5 最佳分配方案选择  77
  3.4 评测  77-81
  3.5 本章小结  81-83
第四章基于最佳有向路径寻找的流寄存器文件分配算法  83-115
  4.1 算法背景  83-88
    4.1.1 无环定向与区间着色  83-86
    4.1.2 极小可比图完成  86-88
  4.2 问题提出及建模  88-90
    4.2.1 问题建模  88-89
    4.2.2 流应用特点  89-90
  4.3 最优或近似最优的流寄存器文件分配算法  90-102
    4.3.1 最优性判定  90-94
    4.3.2 算法框架  94-99
    4.3.3 算法性能分析  99-102
  4.4 一般化的流寄存器文件分配算法  102-103
  4.5 评测  103-112
  4.6 本章小结  112-115
第五章基于层次图着色的多级软件管理存储层次分配算法  115-139
  5.1 基本分配算法  115-123
    5.1.1 存储层次建模  116-117
    5.1.2 程序划分  117
    5.1.3 数据对应最佳存储层次求解  117-120
    5.1.4 相干图构建  120-121
    5.1.5 存储层次分配  121-123
  5.2 优化  123-131
    5.2.1 访存优化  123-128
    5.2.2 并行开发  128-131
  5.3 评测  131-135
  5.4 存储层次组织和管理方案决策  135-138
    5.4.1 Cache 与SPM 的比较  135-137
    5.4.2 SPM: 软件cache 与编译分配的比较  137-138
    5.4.3 SPM: 规整划分与连续划分的比较  138
  5.5 本章小结  138-139
第六章结论与展望  139-143
  6.1 工作总结  139-141
  6.2 研究展望  141-143
致谢  143-145
参考文献  145-159
作者在学期间取得的学术成果  159-161
攻读博士学位期间参加的主要科研工作  161

面向软件管理片上存储器的编译优化技术研究

内容摘要

全文目录

相似论文