（计算机科学与技术专业论文）基于图着色的存储层次优化技术研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 处理器与存储器的性能差距导致了“存储墙问题的出现，使得存储系统成 为计算机系统的瓶颈。从目前工艺水平和体系结构技术的发展趋势来看，这种差 距还会继续增加，因此在未来可预测的范围内，对存储系统的优化将一直是提高 计算机系统性能的关键技术之一。 本文着重研究了如何将图着色理论应用于各级存储层次的优化问题，在c a c h e 、 以流寄存器文件为代表的片上大容量寄存器文件和主存三方面提出了创新的编译 时优化方法。本文取得的主要研究成果如下： ( 1 ) 提出了一个基于图着色的c a c h e 优化算法c a c h ec o l o r i n g 。该算法根据访存行 为将程序中的数据划分成若干数据对象，然后根据数据对象的大小将c a c h e 划分为 一个带有别名的伪寄存器文件，每个伪寄存器由若干c a c h e 行组成，可以容纳一个 数据对象；最后使用一个经过改进的图着色寄存器分配算法来决定这些对象在 c a c h e 中的位置以及发生冲突时的替换关系。数据对象的划分将c a c h e 的管理分为 两个层次，一个是编译时编译器对粗粒度的数据对象的管理，另一个是运行时硬 件对细粒度的c a c h e 行的管理，这样编译器和硬件的优势都得到发挥。我们构造了 比传统的生命周期相干图蕴涵更多相干信息的冲突矩阵，作为处理寄存器分配冲 突时的指导原则。我们基于g c c 进行了实现，并通过s i m p l e s c a l a r 构造了支持c a c h e c o l o r i n g 的硬件模拟平台。实验结果表明c a c h ec o l o r i n g 能较好的开发程序的局部 性，降低c a c h e 失效率。 ( 2 ) 提出了一个基于图着色的流寄存器文件分配算法一s r fc o l o r i n g 。该算法通过 寄存器划分将流寄存器文件转换为大小和位置固定的传统寄存器文件，从而将流 寄存器文件的分配问题归结为一个可以采用图着色寄存器分配算法解决的问题。 针对流寄存器文件的硬件机制和程序访问流寄存器文件的特点，我们对已有的图 着色算法进行了扩充，使之能够更加有效地进行流寄存器文件的分配。为了解决 因流太长而导致相干图不可着色的问题，我们提出了重用优先的双缓冲策略。我 们在s f 9 5 c o m p i l e r 编译框架中实现了s r fc o l o r i n g 。s f 9 5 c o m p i l e r 是一个为f t 6 4 及其编程语言s f 9 5 开发的编译器。实验结果表明，s r fc o l o r i n g 能够有效地管理 流寄存器文件。 ( 3 ) 提出了一个基于区间着色的主存分配算法m mc o l o r i n g 。我们以数组作为分 配主存空间的候选，将主存分配问题归结为区间着色问题。由于一般的区间着色 问题是n p 完全问题，我们利用程序所具有的一个性质，即数组生命周期的包含性 第i 页 国防科学技术大学研究生院博士学位论文 来降低区间着色的难度，将一般的区间着色问题简化为超完美图的区间着色问题， 并据此提出了实现最优区间着色的判定条件以及实现算法。当不满足最优区间着 色的条件时，可以通过分割数组的生命周期来使之得到满足。我们提出了两种分 割数组生命周期的策略。一种是自底向上的积极分割策略，它首先将数组的生命 周期分割到最小，然后在满足着色条件的前提下逐步合并生命周期；另一种是自 顶向下的被动分割策略，它在一开始将数组的生命周期保持为最长，只有在不满 足着色条件时才选择某些生命周期进行分割。我们基于g c c 进行了实现。模拟实 验结果表明，该算法是一种有效的管理主存的编译方法。 主题词：存储层次优化，c a c h e 优化，流寄存器文件分配，编译时存储分配， 图着色 第i i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t t h ep e r f o r m a n c eg a pb e t w e e np r o c e s s o ra n dm e m o r yc a u s e st h ep r o b l e mk n o w n a s “m e m o r yw a l l ”，w h i c hm a k e st h em e m o r ys y s t e mb e c o m et h eb o t t l e n e c ko ft h e c o m p u t e rs y s t e m t h ed e v e l o p i n g t r e n d so fc u r r e n ts e m i c o n d u c t o ra n dc o m p u t e r a r c h i t e c t u r et e c h n i q u e ss h o wt h a tt h i sg a pw i l lk e e pi n c r e a s i n g c o n s e q u e n t l y , t h e o p t i m i z a t i o nt ot h em e m o r ys y s t e mw i l lb eo n eo f t h ek e yt e c h n o l o g i e st oi m p r o v et h e o v e r a l lp e r f o r m a n c eo ft h ec o m p u t e rs y s t e mi nt h ev i s i b l ef u t u r e t h i st h e s i sf o c u s e so na p p l y i n gt h eg r a p hc o l o r i n gt h e o r yt ot h em a n a g e m e n t o p t i m i z i n gp r o b l e mo ft h em e m o r yh i e r a r c h i e s n o v e lm a n a g e m e n ta p p r o a c h e s i n c o m p i l e t i m eh a v eb e e np r e s e n t e di nt h ea s p e c t so fc a c h e ，l a r g eo n c h i pr e g i s t e rf i l e s r e p r e s e n t e db ys t r e a mr e g i s t e rf i l e ( s r f ) a n dt h em a i nm e m o r y p r i m a r yi n n o v a t i v e w o r k si nt h i sp a p e rc o u l db es u m m a r i z e da sf o l l o w s ： ( i ) ag r a p hc o l o r i n gb a s e dm a n a g e m e n to p t i m i z i n ga l g o r i t h mf o rc a c h e ，n a m e l y c a c h ec o l o r i n g ，h a sb e e np r o p o s e d t h i sa l g o r i t h mf i r s tp a r t i t i o n st h ed a t ai n t os e v e r a l d a t ao b j e c t sa c c o r d i n gt ot h e i rm e m o r ya c c e s s i n gb e h a v i o r s t h e ni tp a r t i t i o n st h ec a c h e i n t oap s e u d or e g i s t e rf i l e 、析t 1 1a l i a sa c c o r d i n gt ot h es i z eo ft h ed a t ao b j e c t s e a c h p s e u d or e g i s t e ri nt h i sr e g i s t e rf i l ec a nh o l do n eo ft h ed a t ao b j e c t s f i n a l l y , i tu s e sa n e x t e n d e dg r a p hc o l o r i n gr e g i s t e ra l l o c a t i o na l g o r i t h mt od e t e r m i n et h ep o s i t i o no fe a c h d a t ao b j e c ti nt h ec a c h ea n dt h e i rr e p l a c e m e n tr e l a t i o n s h i p t h ed a t ao b j e c tp a r t i t i o n i n g d i v i d e st h em a n a g e m e n to fc a c h ei n t ot w ol e v e l s ，o n ef o rt h ec o a r s e - g r a n u l a r i t y m a n a g e m e n t o ft h ed a t a o b j e c t s i nt h e c o m p i l e t i m e a n dt h eo t h e rf o r t h e f i n e - g r a n u l a r i t ym a n a g e m e n to ft h ec a c h el i n e si nt h er u n - t i m e s ot h ea d v a n t a g e so f b o t hc o m p i l e ra n dh a r d w a r ea r ee x p l o i t e d t h ec o n f l i c tm a t r i xw h i c hc o n t a i n sm o r e i n f o r m a t i o na b o u ti n t e r f e r e n c et h a nt h et r a d i t i o n a ll i v e - r a n g ei n t e r f e r e n c eg r a p hi s c o n s t r u c t e da sag u i d et od e a lw i t ht h ec o n f l i c t so fr e g i s t e ra l l o c a t i o n c a c h ec o l o r i n gi s i m p l e m e n t e di ng c c ah a r d w a r es i m u l a t i o np l a t f o r mw h i c hs u p p o r t sc a c h ec o l o r i n g i sb u i l tb a s e do ns i m p l e s c a l a r t h ep r i m a r ye x p e r i m e n t a lr e s u l t ss h o wt h a tc a c h e c o l o r i n gc a ne x p l o i tt h el o c a l i t yw e l la n dr e d u c et h ec a c h em i s sr a t e ( i i ) ag r a p hc o l o r i n gb a s e ds r fa l l o c a t i o na l g o r i t h m ，n a m e l ys r fc o l o r i n g ，i s p r o p o s e d t h i sa l g o r i t h mf o r m u l a t e st h ep r o b l e mo fs r fa l l o c a t i o ni n t o ar e g i s t e r a l l o c a t i o np r o b l e mw h i c hc a nb es o l v e db yaw e l lu n d e r s t o o dg r a p hc o l o r i n ga l g o r i t h m b yp a r t i t i o n i n gt h es r fi n t oat r a d i t i o n a lr e g i s t e rf i l e 、i t hf i x e dp o s i t i o na n dl e n g t h t h e e x i s t i n gg r a p hc o l o r i n ga l g o r i t h mi se x t e n d e da n dm o d i f i e dt oa d d r e s st h eu n i q u ea s p e c t o ft h es r fa l l o c a t i o np r o b l e m s ar e u s i n g f i r s td o u b l e - b u f f e r i n gs t r a t e g yi sp r e s e n t e dt o a d d r e s st h eu n c o l o r a l b ep r o b l e mc a u s e db yv e r yl o n gs t r e a m s t h es r fc o l o r i n g a l g o r i t h mi si m p l e m e n t e di nt h ec o m p i l e rf r a m e w o r ko fs f 9 5 c o m p i l e r , w h i c hi s 第i i i 页 国防科学技术大学研究生院博士学位论文 d e v e l o p e df o r f t 6 4s t r e a mp r o c e s s o ra n di t s p r o g r a m m i n gl a n g u a g es f 9 5 t h e e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a ts r fc o l o r i n gr e p r e s e n t sap r o m i s i n gc o m p i l e r a p p r o a c hf o rt h es r fm a n a g e m e n t ( i i i ) a ni n t e r v a lc o l o r i n gb a s e da l l o c a t i o na l g o r i t h mf o rm a i nm e m o r y , n a m e l ym m c o l o r i n g ，i sp r o p o s e d t h em a i nm e m o r ya l l o c a t i o np r o b l e mi sm a p p e d t oa ni n t e r v a l c o l o r i n gp r o b l e mb yt a k i n ga r r a y sa sc a n d i d a t e sf o rm e m o r ya l l o c a t i o n a st h eg e n e r a l i n t e r v a lc o l o r i n gp r o b l e mi sn p c o m p l e t e ，ap r o p e r t yo ft h ep r o g r a m ，n a m e l yt h e c o n t a i n m e n to fa r r a y s l i v e r a n g e s i su s e dt od e c r e a s et h eh a r d n e s so fi n t e r v a lc o l o r i n g a n ds i m p l i f yi ta sa ni n t e r v a lc o l o r i n gp r o b l e mf o rs u p e r p e r f e c tg r a p h b a s e do nt h i s ，a j u d g m e n tt h e o r e mf o ro p t i m a li n t e r v a lc o l o r i n g t o g e t h e rw i t ht h ei m p l e m e n t a t i o n a l g o r i t h mi sp r o p o s e d l i v e r a n g es p l i t t i n gc a nb eu s e dt om a k et h eg r a p hs a t i s f yt h e o p t i m a li n t e r v a lc o l o r i n gc o n d i t i o n t w os t r a t e g i e sf o rl i v e r a n g es p l i t t i n ga r ep r o p o s e d o n ei sat o p d o w na g g r e s s i v es t r a t e g yw h i c hf i r s ts p l i t st h el i v e r a n g e si n t om i n i m u m a n dt h e nm e r g e st h e mg r a d u a l l yw h e nt h ec o l o r i n gc o n d i t i o ni ss a t i s f i e d n l eo t h e ro n e i sab o t t o m - u pp a s s i v es t r a t e g yw h i c hk e e p st h el i v e r a n g e sa sl o n ga sp o s s i b l ea n d s p l i t ss o m eo ft h e mo n l yw h e nt h ec o l o r i n gc o n d i t i o ni s n o ts a t i s f i e d m mc o l o r i n g w i t hb o t ha g g r e s s i v ea n dp a s s i v es t r a t e g i e si si m p l e m e n t e di ng c c m o d e l i n gt e s t s s h o wt h a ti ti sa ne f f i c i e n ta p p r o a c hf o rc o m p i l e t i m em e m o r ya l l o c a t i o n k e yw o r d s ：m e m o r yh i e r a r c h i e so p t i m i z a t i o n ，c a c h eo p t i m i z a t i o n ，s t r e a m r e g i s t e rf i l ea l l o c a t i o n ，c o m p i l e - t i m em e m o r ya l l o c a t i o n ，g r a p hc o l o r i n g 第i v 页 国防科学技术大学研究生院博士学位论文 表目录 表2 1 对象类划分3 4 表2 2 评测c a c h ec o l o r i n g 算法的测试程序4 5 表2 3 数据对象划分结果4 6 表3 1 评测s r f 分配算法的测试程序6 7 表4 1 评测主存分配算法的测试程序9 7 第1 v 贞 国防科学技术大学研究生院博士学位论文 图目录 图1 11 9 8 0 年以来处理器和存储器的性能随时间提高的变化曲线图1 图1 21 9 8 0 年以来c p u 时钟周期、s r a m 访问时间、d r a m 访问时间和磁盘寻道 时间随时间变化的曲线图1 图1 3 层次存储系统示意图。2 图l - 4 处理器片上c a c h e 容量随时间变化示意图3 图1 5c a c h e 访问时间( 时钟周期) 随c a c h e 容量和工艺变化的曲线图3 图1 - 6c e l l 和f t 6 4 的片上存储层次4 图1 7 一个经典的c h a i t i n 风格的图着色寄存器分配算法框架1 0 图2 14 x 4 矩阵乘法代码1 9 图2 2l r u 算法下4 x 4 矩阵乘法2 1 图2 3c a c h ec o l o r i n g 的基本流程2 1 图2 4 划分c a c h e 得到的伪寄存器文件2 3 图2 5 矩阵乘法中对象的相干图2 3 图2 - 6 矩阵乘法中对象在c a c h e 中的分配结果2 4 图2 7s e q u i t u r 的压缩原理2 5 图2 8 数据对象的划分过程2 6 图2 - 9 预处理过程的算法2 7 图2 1 0 矩阵乘法中数组的数据分布和访存地址序列2 8 图2 1 1 经过预处理之后的地址序列。2 8 图2 1 2 经过s e q u i t u r 算法处理之后得到的产生式和符号序列2 9 图2 1 3 确定数据对象的算法。3 0 图2 1 4 表示对象的数据结构3 0 图2 1 5 最终得到的数据对象划分结果3 l 图2 16 数据对象分类算法一3 3 图2 1 7 寄存器文件的构造算法3 4 图2 1 8 寄存器文件示意图3 5 图2 1 9c a c h e 分配的流程3 5 图2 2 0 获取定量相干信息的示意图3 7 图2 2 1 矩阵乘法的冲突矩阵3 8 图2 2 2c a c h e 分配的主过程算法3 9 图2 2 3 构造冲突矩阵和相干图的算法4 0 第v 页 国防科学技术大学研究生院博士学位论文 图2 2 4 构造工作队列的算法4 1 图2 2 5 化简算法4 1 图2 2 6 潜在溢出算法4 2 图2 2 7 选择算法4 3 图2 2 8 在不同标量数据对象大小下f t 的c a c h e 失效率变化4 6 图2 2 9c a c h e 大小为1 6 k b 时，c a c h ec o l o r i n g 、l r u 和f f u 的失效率比较4 7 图2 3 0e p 、c g 、g e m m 和s w i m 在不同c a c h e 大小下的失效率比较4 7 图3 1 流处理模型示意图5 0 图3 2f t 6 4 体系结构示意图5 0 图3 3s f 9 5 程序及相应的流中间代码5 2 图3 4s f 9 5 c o m p i l e r 编译框架5 2 图3 5 对s r f 进行划分得到的新寄存器文件5 4 图3 - 6s r f 分配结果比较5 4 图3 7 两种分配方案下一次迭代的执行情况5 5 图3 8 改进后的s r fc o l o r i n g 各阶段相干图5 7 图3 - 9 改进后的s r fc o l o r i n g 的分配方案和一次迭代的执行情况5 7 图3 1 0s r fc o l o r i n g 算法框架5 8 图3 1 1s r fc o l o r i n g 的主过程5 9 图3 1 2s r fc o l o r i n g 的构造算法6 0 图3 1 3s r fc o l o r i n g 的构造工作队列算法6 l 图3 1 4s r fc o l o r i n g 的合并2 算法6 2 图3 15s r fc o l o r i n g 的松弛算法6 3 图3 1 6 通过双缓冲读入和写回一条流的过程6 4 图3 17 双缓冲策略算法。6 5 图3 1 8 决定缓冲大小的算法。6 6 图3 1 9 空间预留的效果6 8 图3 2 0 消除冗余的流复制语句的效果一6 9 图3 2 1 相容流共享空间的效果6 9 图3 2 2 各种优化策略的加速比7 0 图3 2 3 两种分配算法下产生的访存量与理论最小访存量之比7 0 图3 2 4l a p l a c e 在两种分配算法下、不同展开次数下的执行时间比较7 l 图3 2 5t e s t l 在改变流的数目和长度时，两种双缓冲策略产生的半缓冲切换次数 7 ：! 图3 2 6 在不同流长下，两种双缓冲策略对t e s t 2 的影响7 2 第v i 页 国防科学技术大学研究生院博士学位论文 图4 1 核外计算的编译过程7 5 图4 2 数组生命周期之间的四种关系7 7 图4 3 完美放置示意图7 9 图4 4 满足性质4 1 的相干图的最优着色算法8 1 图4 5a m mc o l o r i n g 的分配过程8 3 图4 6 用于说明分配算法的程序代码8 3 图4 7 在a - m mc o l o r i n g 分配过程中不同阶段的相干图和生命周期示意图8 4 图4 8a m mc o l o r i n g 的分配结果。8 5 图4 9a - m mc o l o r i n g 的主过程。8 6 图4 1 0 积极的生命周期分割算法8 7 图4 1 1a - m v ic o l o r i n g 的构造算法8 8 图4 1 2a m mc o l o r i n g 的合并算法8 9 图4 1 3p m mc o l o r i n g 的分配过程9 0 图4 1 4p m mc o l o r i n g 分配过程中的相干图和生命周期示意图9 0 图4 1 5p m mc o l o r i n g 的主过程9 1 图4 1 6p m mc o l o r i n g 的构造算法一9 2 图4 1 7p m mc o l o r i n g 的溢出算法9 3 图4 一l8p m mc o l o r i n g 的包含性检查和分割算法9 4 图4 1 9 为保持包含性进行的生命周期分割示意图9 4 图4 2 0 分配方案的性能评估算法一9 5 图4 - 2 1a m mc o l o r i n g 和p m mc o l o r i n g 的编译开销9 7 图4 2 2 不同分配算法产生的i o 开销比较9 8 第v i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名： 塑耋日期：加呷年，9 月尹日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名：翌牢至 作者指导教师签名：搁c 罗 7 芗 7 l v 7 ， ， 日期：枷刁年，口月7 e 1 日期：7 胡年汐月| 7 日 国防科学技术大学研究生院博士学位论文 第一章绪论 1 1 课题背景 1 1 1 处理器与存储器的性能差异 在过去的十几年中，处理器速度以每年5 0 至1 0 0 的速度平稳增长，而存储 器的速度却只以每年7 左右的速度增长1 1 1 。处理器与存储器之间的速度差距导致 了“存储墙”的出现【2 】，这使得存储访问延迟成为决定程序执行时间的决定性因素。 而且，从图1 1 【3 】和图1 - 2 1 4 1 所给出的发展趋势来看，处理器与存储器之间的速度差 距会越来越大，所以在未来可预测的范围内，存储系统仍将是影响整个计算机系 统性能的瓶颈【2 j 【5 ，6 。 10 0 0 性1 o o 台匕 日匕10 1 图1 11 9 8 0 年以来处理器和存储器的性能随时间提高的变化曲线图 ( 以1 9 8 0 年时的性能为基准) 1 0 0 。0 0 0 ，0 0 0 1 0 ，0 0 0 0 0 0 1 ，0 0 0 0 0 0 1 0 0 ，0 0 0 罂 1 0 ，0 0 0 1 0 0 0 1 1 0 1 一 ? 、 一叁x 一 套弋： 。 、心 1 9 1 9 8 51 9 9 01 9 9 52 0 图1 21 9 8 0 年以来c p u 时钟周期、s r a m 访问时间、d r a m 访问时问和磁盘寻道时间随时间 变化的曲线图 第l 页 国防科学技术大学研究生院博士学位论文 1 1 2 层次存储系统 由于处理器与存储器之间存在着越来越大的速度差异，因此近十几年来如何 解决“存储墙”问题一直是研究的热点。为了解决“存储墙”问题并出于性价比 的考虑，当前的计算机大都采用层次存储系统【_ 卜9 1 ，即把存储系统组织成层次式结 构，将速度较快、容量较小的存储器放置在离处理器较近的地方，而将速度较慢、 容量较大的存储器放置在离处理器较远的地方。典型的计算机系统的存储层次包 括寄存器、片内c a c h e 、片外c a c h e 、主存和磁盘，在多机系统中还包括分布在其 它结点的远程存储器，如图1 3 所示。 为了减少存储访问延迟，处理器运算所需要的数据要尽可能放置在离处理器 较近的存储层次中。一般应用程序的数据规模都超过c a c h e 的大小，甚至超过主存 的大小，因此数据要在各个存储层次之间不停的移动。这样，每个存储层次的管 理和优化对于减小访存延迟、缓解存储墙问题具有重要意义。 根据其不同的特点，各个存储层次上的存储器需要不同的的管理方法。寄存 器以字为操作粒度，数量最少，访问速度最快，每个寄存器都必须精心使用，一 般通过编译器对其进行管理。c a c h e 以c a c h e 行为操作粒度，一般由硬件动态管理， 以减小运行时的开销。主存( 虚存) 及以下的存储层次一般由操作系统按页面或 磁盘块进行管理。 图1 3 层次存储系统示意图 1 1 3 工艺和体系结构发展带来新的挑战 使用c a c h e 是缓解存储墙问题的传统手段。随着半导体工艺的进步，处理器片 第2 页 国防科学技术大学研究生院博士学位论文 上集成的c a c h e 容量越来越大。图1 4 给出了i n t e l 和a m d 微处理器片上c a c h e 容 量随时间变化的示意图。当前i t a n i u r n 2 1 0 1 处理器将三级c a c h e 都集成在片上，总容 量超过9 m b 。图1 5 显示了c a c h e 访问时间( 以c p u 时钟周期计算) 随c a c h e 容 量增大和工艺提高的变化曲线1 1 】。可见，随着容量的增大和工艺的提高，c a c h e 与 处理器之间的性能差异越来越大。同时大容量c a c h e 还带来功耗增大”1 等负面影 响。 5 0 0 0 岔4 0 0 0 2 皿删3 0 0 0 肄 羔2 0 0 0 u 日 u 1 0 0 0 0 - i n t e l + a m d 7 f 7 二7 1 9 8 91 9 9 31 9 9 5 1 9 9 8 2 0 0 l2 0 0 42 0 0 5 2 0 0 6 图1 4 处理器片上c a c h e 容量随时间变化示意图 1 访 存 时 黼 莳1 0 钟 周 期 1 11 01 1 0 1 0 o c a c h e 容量( 硒) 图1 - 5c a c h e 访问时间( 时钟周期) 随c a c h e 容量和工艺变化的曲线图 一些针对十亿晶体管结构( b i l l i o n t r a n s i s t o ra r c h i t e c t u r e ) 【1 4 】和高性能计算而 提出的新型体系结构，如i m a g i n e t l 5 ，16 1 、m e r r i m a c 1 7 1 、c e l l 1 引、c y c l o p s 6 4 1 9 1 、 c l e a r s p e e d l 2 0 1 以及f t 6 4 2 q 等，采用了大容量软件管理的片上存储器来解决存储墙 问题。这些新型体系结构的共同特征是采用了多个并行执行的处理单元，处理单 元与片外存储器之间存在多层由软件显式管理的存储层次。例如，c e l l 处理器由一 个p o w e r p c 处理器和8 个s p e ( s y n e r g i s t i cp r o c e s s o re l e m e n t ) 组成，每个s p e 的片 上存储器由一个寄存器文件和一个局部存储器组成，如图1 - 6 ( a ) 所示。c e l l 依靠显 第3 页 国防科学技术大学研究生院博士学位论文 式的d m a 操作来控制数据在片外存储器与s p e 局部存储器之间的移动。f t 6 4 的 运算单元由4 个a l u 计算群组成，每个计算群有独立的局部寄存器文件，并共享 一个全局的流寄存器文件( s t r e a mr e g i s t e rf i l e ，s r r ) ，如图1 - 6 ( b ) 所示。f t 6 4 通过 显式的访存指令来管理流寄存器文件。对于这些新型体系结构，提高片上存储层 次利用率的高效的编译技术是保证处理器性能的关键。 以上情况表明，无论是以c a c h e 为特征的传统体系结构还是以软件管理存储层 次为特征的新型体系结构，研究有效的存储层次优化方法都具有十分重要的意义。 s p e 运算逻辑 盟 匿 n 蕊蕊 z 、 片上互连总线 ( a ) c e l l 1 2 1 课题来源 a l u 计算群a l u 计算群 图1 - 6c e l l 和f t 6 4 的片上存储层次 1 2 课题研究内容 ( b ) f t 6 4 本课题来源于国家自然科学基金创新研究群体科学基金“千万亿次高性能计 算关键技术( 项目编号：6 0 6 2 1 0 0 3 ) 和国家自然科学基金重点项目“高效能并行 计算机体系结构研究( 项目编号：6 0 6 3 3 0 5 0 ) 。这些项目的主要研究内容是面向 高性能计算的处理器体系结构、结点互连和并行算法与编译优化技术。作为其中 的组成部分，本课题重点针对高性能计算中存储层次的管理和优化技术进行了深 入研究。 1 2 2 课题研究重点 为了减少存储访问延迟，提高程序性能，必须优化层次存储系统中各级存储 器的使用。存储层次的优化使用方法可以分为两大类，一类是数据局部性优化方 法，即通过程序变换技术来改变程序的访存行为，提高访存的局部性。这类方法 主要包括针对嵌套循环的各种循环变换和数据变换技术，前人已有广泛而深入的 研究2 2 粕i 。另一类方法是对存储器的管理优化，包括取数( 什么时候将数据从下 第4 页 一一一一一一一一一 国防科学技术大学研究生院博士学位论文 一级存储层次取进来) 、放置( 将取入的数据放置在存储器的什么位置) 和替换( 发 生冲突时如何进行替换) 等内容。这两类方法相辅相成，对于提高存储层次利用 率同样重要，本文主要考虑各存储层次的管理优化。 对存储层次的管理优化可以在程序员、编译器、操作系统以及硬件等不同层 面进行。编译器可以获取有用的全局存储访问信息，能够系统地对存储层次进行 管理，同时还可以减轻程序员的负担和减少运行时的开销。因此从编译的角度来 对存储层次进行管理是最好的选择。 作为一个经典的资源分配方法，图着色理论【2 7 ，2 8 】被广泛应用于计算机技术的 各个领域，特别是在寄存器分配方面，已经形成了许多非常高效的分配算法。将 图着色理论应用于其它存储层次的管理是一件富有意义和挑战的工作。 因此，我们将在编译时如何通过图着色理论来对各个存储层次进行有效的管 理优化作为本文的研究重点，具体内容如下： ( 1 ) c a c h e 的优化。 当前大多数计算机系统中的存储系统都包含硬件管理的c a c h e 。数据在c a c h e 中的位置由硬件实现的地址转换机制决定，发生冲突时的数据替换由硬件实现的 替换算法来完成。硬件管理的好处是速度快，运行时开销小，并且对软件透明， 这意味着任何程序，即使不经过特殊的优化，也能够通过c a c h e 获得性能的提高。 但是硬件管理也有一些缺点。首先，由于缺乏程序全局的访存信息和程序动态行 为的信息，硬件实现的算法和策略无法实现全局最优【2 9 1 。第二，采用硬件实现一 些复杂而有效的管理算法和策略的代价比较昂贵，因此硬件通常实现的都是最简 单的算法和策吲3 0 l 。第三，硬件管理的c a c h e 的性能难以预测【】，这对于那些对 程序最差执行时间有要求的实时应用来说是难以接受的。此外，随着c a c h e 容量的 增大，硬件实现还受到功耗方面的限制【1 2 ，1 3 】。因此，对于硬件管理的c a c h e ，增加 容量对缓解存储墙问题的作用受到严重限制。为了克服这些问题，我们需要研究 如何利用图着色理论在编译时进行粗粒度的管理，同时保持硬件在管理细粒度数 据方面的高效性。 ( 2 ) 以流寄存器文件为代表的大容量片上寄存器文件的分配。 f t 6 4 等面向高性能计算的新型体系结构采用了大容量的完全由软件控制的片 上寄存器文件。这些寄存器文件既可以通过编译器进行管理，也可以由程序员通 过编程接口显式地进行控制。由程序员控制会增加程序员的负担，并且不利于已 有代码的继承