基于图着色的存储层次优化技术研究

发布时间：2020-10-29 21:15

　　 处理器与存储器的性能差距导致了“存储墙”问题的出现,使得存储系统成为计算机系统的瓶颈。从目前工艺水平和体系结构技术的发展趋势来看,这种差距还会继续增加,因此在未来可预测的范围内,对存储系统的优化将一直是提高计算机系统性能的关键技术之一。 本文着重研究了如何将图着色理论应用于各级存储层次的优化问题,在cache、以流寄存器文件为代表的片上大容量寄存器文件和主存三方面提出了创新的编译时优化方法。本文取得的主要研究成果如下: (1)提出了一个基于图着色的cache优化算法—Cache Coloring。该算法根据访存行为将程序中的数据划分成若干数据对象,然后根据数据对象的大小将cache划分为一个带有别名的伪寄存器文件,每个伪寄存器由若干cache行组成,可以容纳一个数据对象;最后使用一个经过改进的图着色寄存器分配算法来决定这些对象在cache中的位置以及发生冲突时的替换关系。数据对象的划分将cache的管理分为两个层次,一个是编译时编译器对粗粒度的数据对象的管理,另一个是运行时硬件对细粒度的cache行的管理,这样编译器和硬件的优势都得到发挥。我们构造了比传统的生命周期相干图蕴涵更多相干信息的冲突矩阵,作为处理寄存器分配冲突时的指导原则。我们基于GCC进行了实现,并通过simplescalar构造了支持CacheColoring的硬件模拟平台。实验结果表明Cache Coloring能较好的开发程序的局部性,降低cache失效率。 (2)提出了一个基于图着色的流寄存器文件分配算法—SRF Coloring。该算法通过寄存器划分将流寄存器文件转换为大小和位置固定的传统寄存器文件,从而将流寄存器文件的分配问题归结为一个可以采用图着色寄存器分配算法解决的问题。针对流寄存器文件的硬件机制和程序访问流寄存器文件的特点,我们对已有的图着色算法进行了扩充,使之能够更加有效地进行流寄存器文件的分配。为了解决因流太长而导致相干图不可着色的问题,我们提出了重用优先的双缓冲策略。我们在SF95Compiler编译框架中实现了SRF Coloring。SF95Compiler是一个为FT64及其编程语言SF95开发的编译器。实验结果表明,SRF Coloring能够有效地管理流寄存器文件。 (3)提出了一个基于区间着色的主存分配算法—MM Coloring。我们以数组作为分配主存空间的候选,将主存分配问题归结为区间着色问题。由于一般的区间着色问题是NP完全问题,我们利用程序所具有的一个性质,即数组生命周期的包含性来降低区间着色的难度,将一般的区间着色问题简化为超完美图的区间着色问题,并据此提出了实现最优区间着色的判定条件以及实现算法。当不满足最优区间着色的条件时,可以通过分割数组的生命周期来使之得到满足。我们提出了两种分割数组生命周期的策略。一种是自底向上的积极分割策略,它首先将数组的生命周期分割到最小,然后在满足着色条件的前提下逐步合并生命周期;另一种是自顶向下的被动分割策略,它在一开始将数组的生命周期保持为最长,只有在不满足着色条件时才选择某些生命周期进行分割。我们基于GCC进行了实现。模拟实验结果表明,该算法是一种有效的管理主存的编译方法。
【学位单位】：国防科学技术大学
【学位级别】：博士
【学位年份】：2007
【中图分类】：TP333
【部分图文】：

国防科学技术大学研究生院博士学位论文第一章绪论1.1课题背景1处理器与存储器的性能差异在过去的十几年中，处理器速度以每年50%至100%的速度平稳增长，而速度却只以每年7%左右的速度增长[’]。处理器与存储器之间的速度差距存储墙”的出现[2]，这使得存储访问延迟成为决定程序执行时间的决定性，从图1一1131和图1一214]所给出的发展趋势来看，处理器与存储器之间的速越来越大，所以在未来可预测的范围内，存储系统仍将是影响整个计算能的瓶颈[2][5，6]。尹一处理撰性能nUnUnUnUnU月11.11nU刁..

器的速度却只以每年7%左右的速度增长[’]。处理器与存储器之间的速度差距导致了“存储墙”的出现[2]，这使得存储访问延迟成为决定程序执行时间的决定性因素。而且，从图1一1131和图1一214]所给出的发展趋势来看，处理器与存储器之间的速度差距会越来越大，所以在未来可预测的范围内，存储系统仍将是影响整个计算机系统性能的瓶颈[2][5，6]。尹一CPU处理撰性能每年提高60%处理器与存储器性能差趾拣年增加5既 nUnUnUnUnU月11.11nU刁..，性匕匕八以︺目尹尸一山声M存储器性能每年提高钱000刊666尸866尸L66甲966尸的66甲啥66门尸66护入66尸尸66尸066甲686尸8目6护86L俨公匀6护的600尸呼口6尸仍06沪6N8甲尸叻6尸0口6尸图l一 11980年以来处理器和存储器的性能随时间提高的变化曲线图(以1980年时的性能为基准)100，000，00010， 000

国防科学技术大学研究生院博士学位论文上集成的。ache容量越来越大。图1一4给出了Iniel和AMD微处理器片上cache容量随时间变化的示意图。当前ItaniumZll“]处理器将三级cache都集成在片上，总容量超过gMB。图1一5显示了cache访问时间(以CPU时钟周期计算)随cache容量增大和工艺提高的变化曲线11’]。可见，随着容量的增大和工艺的提高，cache与处理器之间的性能差异越来越大。同时大容量。ache还带来功耗增大〔’2，”l等负面影响。50004000300020001000一一泣继…一一一一万声声{{{{{~Intel万 万 万~~~~~~一 一 一 /////多多二 ///奋 奋多多甲了 了︵国窝︶仲啊。上u。。 19891993199519982001200420052006图l一4处理器片上cache容量随时间变化示意图访时存fal︵时钟周期︶ 10100ca比e容凳(拙) 100010000图1一 5Cache访问时间(时钟周期)随。ache容量和工艺变化的曲线图一些针对十亿晶体管结构(Billion一肠ansisto:沁chiteeture)[’4]和高性能计算而提出的新型体系结构，如Imagine[”，’6]、Merrimac〔‘7]、eell[，81、eyelops64[’”]、clearspeedl20]以及FT6412’]等，采用了大容量软件管理的片上存储器来解决存储墙问题。这些新型体系结构的共同特征是采用了多个并行执行的处理单元
【相似文献】

相关博士学位论文 前1条

1 邓宇;基于图着色的存储层次优化技术研究[D];国防科学技术大学;2007年

相关硕士学位论文 前1条

1 陆林海;AVS_M算法优化及其在DM642上的实现[D];五邑大学;2008年

本文编号：2861461