（计算机系统结构专业论文）分片式处理器上非均匀一致cache的设计与优化.pdf

摘要 摘要 分片式处理器能够很好地应对纳米工艺代芯片设计中存在的功耗、线延迟和 设计复杂性问题，充分地利用日益增长的片上晶体管资源以提升应用的性能，但 对其上的c a c h e 设计提出了新的要求。一方面，需要有分片式的c a c h e 结构以满 足大量执行单元的并发访存需求；另一方面，需要有分布式内存依赖解析机制以 保证分布式的访存顺序。与传统的全局控制的c a c h e 结构相比，非均匀一致c a c h e 结构( n u c a ，n o n u n i f o r mc a c h ea r c h i t e c t u r e ) 能够满足上述要求，更好地适 应分片式处理器体系结构。本文设计了分片式处理器上的非均匀一致的二级和一 级c a c h e 结构，并根据分片式处理器中特有的访存特征对非均匀一致的一级 c a c h e 的结构进行优化，提出了l o a d 本地化执行模型，最终评估了模型的性能 和开销。该研究工作对分片式处理器上c a c h e 结构的设计具有一定的指导意义。 本文对非均匀一致二级和一级c a c h e 的设计和优化均基于实验室所研究的 分片式处理器指令级并行核( t p a p i ，t i l e dp r o c e s s o ra r c h i t e c t u r e p r o c e s s o rf o r i l p ) 。主要研究成果包括：( 1 ) 为t p a p i 设计7 - = i i ! 均匀一致二级c a c h e ，设计 包括：静态数据映射方式，片上网络互连，c a c h eb a n k 内部结构，c a c h e 事务处 理逻辑，以及c a c h e 流水线。并使用c 语言编写了面向硬件实现的t p a p i 的二 级c a c h e 模拟器。该部分亦可以作为普适的静态非均匀一致c a c h e 的设计实例。 ( 2 ) 针对t p a p i 上非均匀一致一级c a c h e 中存在的l o a d 指令的长路由延迟问 题，进行了相关的设计优化。首先剖析了结构中的访存行为特征，并根据l o a d 指令数据端和发射端不一致的情况，分析其中可能获得的性能提升潜力，据此设 计了l o a d 本地化执行的优化模型，并设计了多种拷贝策略和一致性维护策略以 控制拷贝和s t o r e 广播的开销。( 3 ) 从功能和时序模拟两个方面评估了l o a d 本 地化执行模型的性能和开销。经实验观测，基本模型可以获得平均5 7 2 的性能 提升，拷贝开销对于c a c h e 命中率的影响并不大，而s t o r e 广播开销才是更为影 响模型性能的因素。 通过在t p a - p i 上对非均匀一致c a c h e 的应用进行研究，我们得到如下认识。 ( 1 ) 非均匀一致二级c a c h e 的设计与t p a p i 处理器结构的耦合度较低，适于单 独设计；( 2 非均匀一致一级c a c h e 的设计与t p a p i 的处理器结构及执行模型 紧密相联，在分布式机制中减少路由延迟和通信开销是提高性能的关键。 关键词：线延迟分片式处理器结构非均匀一致c a c h el o a d 本地化执行模型 a b s t r a c t w h i l et i l e dp r o c e s s o r w h i c ha r ed e d i c a t e dt op r o m o t et h ep e r f o r m a n c eo ft a r g e t a p p l i c a t i o n sw i t ht h ei n c r e a s i n go n - c h i pt r a n s i s t o rr e s o u r c e s ，c o u l dc o p ew i t ht h e p r o b l e m sa r i s e s i nt h ee r ao fl l a n o - s c o p ec h i pt e c h n o l o g y , s u c hl i k ep o w e r c o n s u m p t i o n ，w i r ed e l a y , a n dd e s i g nc o m p l e x i t y , n e wc h a n l e n g e so f h o wt od e s i g nt h e c a c h eo ni tc o n f r o n tt h ec o m p u t e ra r c h i t e c t s o no n eh a n d ，d i s t r i b u t e dc a c h e a r c h i t e c t u r ei sn e e d e dt os a t i s f yp a r a l l e lm e m o r ya c c e s sr e q u e s t sf r o ml a r g ea m o u n to f p r o c e s s o rc o r e s o nt h eo t h e rh a n d ，d i s t r i b u t e dm e m o r yd e p e n d e n c ed i s a m b i g u a t i o n m e c h a n i s mi sn e e d e dt og u a r a n t e et h ec o r r e c tm e m o r ya c c e s so r d e nn o n - u n i f o i r i l l c a c h ea r c h i t e c t u r e ( n u c a ) i ss u i t a b l ef o rt h e s ed e m a n d sc o m p a r e dt ot r a d i t i o n a l c e n t r a l i z e dc o n t r o l l e dc a c h e s t h e r e f o r e ，t h i st h e s i sf o c u s e so nt h ed e s i g n o f n o n u n i f o r mc a c h ea p p l i e dt ol e v e l t w oa n dl e v e l o n ec a c h eo nt i l e dp r o c e s s o r r e s p e c t i v e l y f u r t h e r m o r e ，w em a k eo p t i m i z a t i o n st on o n u n i f o r ml e v e l o n ec a c h e a c c o r d i n gt os p e c i f i cl o a db e h a v i o r so nt i l e dp r o c e s s o r s ，w h i c hi s c a l l e dl o a d e x e c u t i o nl o c a l i z a t i o nm o d e l f i n a l l y , w ei m p l e m e n ta n de v a l u a t et h em o d e l t h i s r e s e a r c hw i l ld i r e c tf u r t h e rd e s i g na n di m p l e m e n t a t i o no fc a c h ea r c h i t e c t u r eo nt i l e d p r o c e s s o r s i nt h et h e s ， - i st h ed e s i g n a n d o p t i m i z a t i o n s t ot h el e v e lo n e a - n d l e v e l twocache a r eo nt h ep l a t f o r mo ft p ap i ( t i l e dp r o c e s s o ra r c h i t e c t u r e p r o c e s s o rf o r i l p ) ，w h i c hi san e wp r o c e s s o rp r o p o s e da n dr e s e a r c h e db ym yc o l l e g u e si nt h e l a b o r a t o r y t h e d e t a i l e dw o r ki n c l u d e sf o l l o w i n ga s p e c t s ( 1 ) w ed e s i g n a n o n u n i f o r ml e v e l t w oc a c h ef o rt p a - p i ，i n c l u d i n gs t a t i cd a t am a p p i n ga l g o d t h r n ， o nc h i pi n t e r c o n n e c t i o n i n t e m a ls t r u c t u r e so fc a c h eb a n k ，t r a n s a c t i o np r o c e s s i n gl o g i c ， a n dt h ep i p e l i n ed e s i g n al e v e l t w oc a c h es i m u l a t o rw r i t t e nb yc l a n g u a g ei s i m p l e m e n t e db a s e do nt h a t ，w h i c hi sw r i t t e ni n as i n g a l a c c u r a t ew a yt h a tc a nb e e a s i l yt r a n s f o r m e di n t oh a r d w a r ed e s i g n ( 2 ) w em a k eo p t i m i z a t i o n sw i t hr e s p e c t t o t h el o n gt r a n s f e r r i n gl o a dl a t e n c yi nn o n - u n i f o r ml e v e l o n ec a c h eo nt p a - p i t h e i o a db e h a v i o r sa r ep r o f i l e df i r s t l y , w h i c hl e a d st ot h eo b s e r v a t i o nt h a tp e r f o r m a n c e c a l lb eg a i n e df r o me l i m i n a t i n gt h el o n gl a t e n c yb e t w e e nl o a di s s u i n gs i d ea n dd a t a p l a c i n gs i d e t h e n ，a no p t i m i z e dm o d e la b o u tl o c a l i z i n gl o a de x e c u t i o ni sp r o p o s e d ， a sw e l la ss e v e r a lr e p l i c a t i o ns t r a t e g i e sa n dc o h e r e n c em a i n t a i n i n gm e t h o di no r d e rt o c o n t r o lt h eo v e r h e a di n d u c e db yc a c h ec o p ya n ds t o r em u l t i c a s t 。f i n a l l y , t h em o d e li s i i a b s t r a c t e v a l u a t e dt h r o u g hf u n c t i o na n dt i m i n gs i m u l a t i o na n dt h er e s u l t ss h o wt h a tt h eb a s i c m o d e lc a l lg a i n5 7 2 p e r f o r m a n c ei m p r o v e m e n to na v e r a g e i ti sa l s oo b s e r v e dt h a t w h i l et h ec a c h ec o p yo v e r h e a dd o e s n ti n f l u e n c et h ec a c h eh i tr a t et o om u c h ，t h es t o r e m u l t i c a s to v e r h e a di sm o r ec r i t i c a lf o rp e r f o r m a n c e w ed r a wc o n c l u s i o n sf r o mt h i sw o r ka s f o l l o w s ( 1 ) t h en o n u n i f o r m l e v e l t w oc a c h ei sl o o s e l yc o u p l e dw i t ht p a p i ，a n dt h u sc a nb ed e s i g n e ds e p a r a t e l y ( 2 ) t h en o n - u n i f o r ml e v e l o n ec a c h ei st i g h t l yc o u p l e dw i t ht p a - p ia r c h i t e c t u r e a n de x e c u t i o nm o d e l ，a n dt h ek e y p o i n tt op e r f o r m a n c ei sh o w t or e d u c et h er o u t i n g l a t e n c ya n dc o m m u n i c a t i o no v e r h c a di nt h ec a c h ea r c h i t e c u t u r e k e yw o r d s ：w i r ed e l a y , t i l e dp r o c e s s o ra r c h i t e c t u r e ，n o n u n i f o r mc a c h e a r c h i t e c t u r e ，l o c a l i z i n gl o a de x e c u t i o nm o d e l i i i 图目录 图目录 图2 1 超级块f o o $ 1 的汇编表示及数据流图：7 图2 2t - f l e x 的处理器微体系结构( k i m ，2 0 0 7 a , b ) 。9 图2 。3t - f l e x 中一个超级块的执行控制流程9 图2 4t - f l e x 中的四阶段提交协议一1o 图2 5l o a d 和s t o r e 指令的分布式执行：1 1 图2 6 计数依赖预测器( c d p ) 表及表项的状态转换图1 2 图2 7c d p 中分布式的通信协议1 3 图2 8 各种均匀一致和非均匀一致的c a c h e 结构1 4 图2 9 使用i n d e x 的低位地址索引特定b a n k 1 5 图2 1 0b a n ks e t 的两种不同映射方式1 6 图2 1 1n u r a p i d 的结构实现1 6 图2 1 2j h u l l 等人在c m p n u c a 结构上实现的共享度方案1 8 图3 1t p a p i 的片上组成结构2 0 图3 2i n t e r l e a v e d 模式下3 2 位片内地址映射方式2 l 图3 3s p l i t 模式下3 2 位片内地址映射方式2 2 图3 4t p a p i 片上互连网络结构及m t i l e 、n t i l e 的内部结构2 2 图3 5r o u t e r 的内部组成结构2 3 图3 6 地址转换寄存器的内容含义2 6 图3 7o c n 中逻辑b a n k 默认映射位置2 7 图3 8 头微片的格式2 8 图3 9m t i l e 的内部结构2 9 图3 。l ol 2c a c h eb a n k 中的t a g a r r a y 和d a t a a r r a y 物理结构3 0 图3 1 1m s h r 表项格式31 图3 1 2c a c h e 行的状态转换3 2 图3 。1 3l 2c a c h eb a n k 处理读请求的完整事务过程3 4 图3 1 4l 2c a c h eb a n k 处理写请求的完整事务过程3 5 图3 1 5c a c h e 处理的流水线3 6 图4 1l o a d 指令的传输延迟分布4 0 图4 2 实际情况和理想情况下l o a d 指令的平均路由跳数对比4 0 v i i i 图目录 图4 3 对于不同b l o c k 的l o a d 访问模式4 2 图4 4 数据块拷贝预测器：4 3 图4 5 主t i l e 上对远程t i l e 上发射的l o a d 请求的拷贝预测流程4 3 图4 6 主t i l e 、客t i l e 和目标指令t i l e 的路由关系4 4 图4 7 含有t i l et a g 的t a g 阵列结构4 6 图4 8 数据块的定位过程4 7 图4 9 推迟的l o a d 接收到n 个s t o r e 后被唤醒；5 0 图4 1 0 推迟的l o a d 被控制核的消息唤醒：5 0 图5 1 一级c a c h e 功能模拟器的运作方式5 6 图5 2l o a d 本地执行的基本模型对i p c 的提升5 8 图5 3l o a d 本地执行模型减少的路由跳数5 8 图5 4 基本模型中l o a d 在发射端本地执行的比例5 9 图5 5l o a d 本地执行基本模型对一级c a c h e 命中率的影响6 0 图5 6 基本模型中拷贝的总次数6 1 图5 7 基本模型中s t o r e 广播的总跳数6 2 图5 8 基本模型中额外提交等待时间对关键路径的影响6 2 图5 9 基本模型中l o a d 违例的总次数6 3 图5 1 0 基本模型中预测过于保守的次数6 4 图5 1 l 拷贝块的总数量随阈值的变化情况6 5 图5 1 2 传输跳数的减少量随阈值的变化情况。j 6 5 图5 1 3 缺失发生次数随阈值的变化情况6 6 图5 1 4 拷贝预测器表项平均冲突次数随预测表大小的变化情况6 7 图5 1 5 各种变量步长下平均每次拷贝所减少的路由跳数6 8 图5 1 6 通过反馈修正拷贝阈值对不被访问的拷贝比例的影响6 8 图5 1 7s t o r e 复位策略与阂值修正配合使用时对无用拷贝的影响6 9 图5 1 8 不同的一致性维护策略对于i p c 的影响6 9 图5 1 9 不同的一致性维护策略对于s t o r e 广播消息总量的影响7 0 图5 2 0 不同的一致性维护策略对拷贝块总量的影响7 0 图5 2 1g u e s td e f e r 和h o m ed e f e r 策略对于l o a d 违例次数的影响7 l 图5 2 2g u e s td e f e r 和h o m ed e f e r 策略对于预测过于保守次数的影响7 1 图5 2 3g u e s td e f e r 和h o m ed e f e r 策略对于l o a d 本地化的影响7 2 i x 表目录 表目录 表3 1 地址转换寄存器中的默认值2 6 表3 2 连续l o a dh i t 的流水过程3 6 表3 3l o a dm i s s 后接l o a dh i t 的流水过程。3 6 表3 4 连续s t o r eh i t 的流水过程3 7 表3 5s t o r em i s s 的流水过程3 7 表5 1t - f l e x 模拟器的配置 5 6 表5 2 基准测试程序描述。5 7 表5 3 基本模型参数配置5 7 表5 4 基本模型的面积开销计算5 9 x 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：篓盎硷 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 函公开口保密( 年) 作者签名：塞盎垒 签字日期： 兰旦塑：! ：! ! 导师签名： 绰犯 签字日期：2 竺誓盟 第1 章绪论 第1 章绪论 1 1 研究背景 从4 0 年代第一台计算机e n i a c ( g o l d s t i n eh 1 9 9 6 ) 诞生之日的每秒钟3 5 条指令到现在高性能计算机的每秒钟上万亿次操作( t o p5 0 0 ，2 0 0 9 ) ，过去6 0 年 内计算机的性能提升了上万亿倍。这样巨大的进步一方面来自于工艺的进步，提 供了更多更快的晶体管资源，然而更重要的另一方面，则在于各种体系结构和编 译技术的提出，从而有效地将这些晶体管资源转化成用户可见的高性能，进而反 映在应用的加速中。 因此，对于体系结构研究者们来说，所提出的体系结构方案是否有意义，取 决于是否能有效地利用工艺发展的潜力，换来等比例的应用加速。这既依赖于底 层工艺所带来的硬件资源和限制，同时也取决于应用中可以发掘的并行性的特征 和数量。 从工艺角度来说，根据摩尔定律( h a m i l t o n ，1 9 9 9 ) ，集成电路上可容纳的晶 体管数目，每隔约1 8 个月便会增加一倍。广义的摩尔定律还包括：每1 8 个月， 晶体管的特征尺寸缩小3 0 ，开关速度增加一倍，而处理器的性能则每年能提高 5 0 到6 0 。对于前面的几条规律，业界普遍认为在近十年内将仍然有效；而最 后一条却受到质疑。近几年来，随着特征尺寸的缩小，晶体管开关延迟已不再是 处理器时钟周期的决定性因素，增大的连线延迟反而占据了主导地位，因此凭借 原有的体系结构，仅靠晶体管数目的增加和开关速度的进步，已不能换来同等的 处理器性能的提升( a g a r w a l ，2 0 0 0 ，b u r g e r , 2 0 0 4 ，e d e n f e l d ，2 0 0 4 ) 。 从应用角度来说，根据并行性特征的不同，学术界普遍将其分成三大类 ( s a n k a r a l i n g a m ，2 0 0 6 ) ：指令级并行( i l p ，i n s t r u c t i o nl e v e lp a r a l l e l i s m ) ，数据 级并行( d l p ，d a t al e v e lp a r a l l e l i s m ) 和线程级并行( t l p ，t h r e a dl e v e l p a r a l l e l i s m ) 。顾名思义，指令级并行在于重叠不同指令的执行，获得较高的吞吐 量，一般以每周期能够处理的指令数目( i p c ，i n s t r u c t i o n sp e rc y c l e ) 来衡量， 并行粒度较细，如：通用桌面型应用，由于其中具有在指令层次上紧耦合的数据 依赖和控制依赖，对性能的提升主要体现在发掘指令级并行性上；数据级并行体 现为对大量数据处理的重叠，如：多媒体和科学计算等应用程序中存在对大量数 据的统一操作，因此具有大量的数据级并行性；而线程级并行则在于重叠不同指 令段的执行，可以看作是一种粗粒度的指令级并行。 本文的研究方向是探讨在目前的工艺发展趋势下，如何进一步地发掘应用中 的指令级并行性。由于分片式处理器体系结构能够较好的适应未来工艺发展中线 延迟的增长，而非均匀一致的c a c h e 也正是为了解决同样的线延迟问题而诞生， 第1 章绪论 因此本文对两者的结合加以设计和研究，分别探讨了非均匀一致c a c h e 在分片式 处理器体系结构一级和二级c a c h e 上的应用和优化。 1 1 1 片上线延迟对提高指令级并行性的影响 在过去的几十年中，发掘指令级并行度的技术主要分为两种。一种是通过提 高工艺和加深流水线来提高时钟频率；另一种则是提高指令的吞吐量，即增大每 周期能够处理的指令数目( i p c ，i n s t r u c t i o n sp e rc y c l e ) 。传统的提高i p c 的技术 分为超标量( s u p e r s c a l a r ) 和超长指令字( v l i w , v e r yl o n gi n s t r u c t i o nw o r d ) 两 种。前者依靠复杂的硬件机制发掘指令间的依赖，动态调度指令，提高指令执行 的并行度；而后者将指令调度交付编译器静态完成，虽然可以避免前者需要的复 杂的硬件结构，但由于无法精确的判断指令间的依赖情况，必须遵循保守策略， 会牺牲掉很多性能。因而在工业界中，超标量技术一直胜过超长指令字技术而处 于主导地位，并在过去的几十年里大大提升了处理器的性能。 然而，近几年来随着工艺的进步，特征尺寸的缩小，导致晶体管开关延迟已 不再是处理器时钟周期的决定性因素，增大的连线延迟反而占据了主导地位。有 研究( a g a r w a l ，2 0 0 4 ，h o ，2 0 0 1 ) 表明，在3 5 n mt 艺下，采用激进的1 3 5 g h z 主频，在4 0 0 m m 2 的芯片上，一周期内信号传输仅能覆盖1 0 的芯片面积，而 对于6 4 k b 大小的数据c a c h e 的访问将需要7 个周期。 因此，当一周期内大部分的延迟用于连线传输，而非逻辑门开关时，传统的 通过提高逻辑门开关速度而提高时钟频率的做法已不再可行，流水线的深度已经 到达极限( a g a r w a l ，2 0 0 0 ) 。与此同时，许多超标量技术( 如：动态指令调度， 多发射，以及推断执行) 多采用复杂的全局结构，当全局信号无法在周期内传 输到达时，这些全局结构同样也面临着随线延迟而扩展的挑战。 1 1 2 分片式处理器体系结构的提出 针对上- d , 节中片上线延迟对i l p 的影响，目前学术界提出了分片式处理器 体系结构( t p a ，t i l e dp r o c e s s o ra r c h i t e c t u r e ) 。该结构的核心思想在于：将传统 的复杂的全局结构分拆成许多简单的重复的单元模块( 称作t i l e ，b a n k ，u n i t ， g r i d 等) ，而相对独立的各模块分布式地完成各自的局部操作( n a g a r a j a n ，2 0 0 1 ， b u r g e r , 2 0 0 4 ) 。 在分片式体系结构的设想中，大量的通信局限在简单模块内部，使得全局通 信量减少，从而削弱线延迟的影响；同时可以通过模块的复制，充分利用片上日 益增多的晶体管资源，达到性能扩展的目的。因此，该结构的设想较好地适应了 工艺的发展。 然而，分片式结构也存在着设计上的难点，主要在于以下三个方面。 2 第1 章绪论 ( 1 ) 在分布式协作情况下如何保证功能正确，有时需要付出额外握手和同 步的开销； ( 2 ) 怎样局部化通信，尽量利用局部信息以满足模块内部操作的需要： ( 3 ) 怎样平衡各模块的负载，使各单元模块能够充分地并行运作： 同时，随着分片式结构的提出，原有的软硬件职能的划分也发生了改变。由 于上述三者的原因，在分布式结构中，由硬件完成指令粒度的依赖检测和动态调 度变得十分困难，因而一部分的指令依赖分析任务便转交给编译器静态完成，一 些新的指令集体系结构被定义出来，如：显式数据流执行模型( e d g e ，e x p l i c i t d a t ag r a p he x e c u t i o n ) ( b u r g e r , 2 0 0 4 ) 。但是它又不等同于上文中提到的v l i w 技术，在v l i w 中，指令的发射槽是由编译器静态填充的，因此编译器必须预 估每条指令的执行延迟，而在分片式体系结构对应的编译模型中，编译器只显式 指定指令间的依赖关系，并不负责指定每条指令的发射时间，这使得e d g e 既 能为分片式体系结构很好地服务，避免复杂的全局依赖判断结构，又能够避免 v l i w 过于依赖静态编译所导致的灵活性缺乏。 学术界较为著名的分片式处理器体系结构有t e x a sa u s t i n 大学研制的t r i p s ( s a n k a r a l i n g a m ，2 0 0 6 ) 及其衍生出来的t - f l e x ( k i m ，2 0 0 7 ) ，s t a n f o r d 大学研制 的s m a r tm e m o r i e s ( m a i ，2 0 0 0 ) ，以及m i t 的r a w ( w a i n g o l d ，1 9 9 7 ) 处理器等。 由于分片式处理器可以充分地利用日益增长的片上晶体管资源，较好地随片 上线延迟的增大而扩展，本人所在的实验室参考t r i p s 和t - f l e x 结构，并针对 开发指令级并行性的目标，设计了分片式处理器指令级并行核( t p a p i ) 。t p a p i 采用e d g e 指令集体系结构，以超级块为执行原子，块内实行数据流执行，块 间按照控制流执行。处理器微体系结构采用t - f l e x 的设计方案，处理器核中的 全部资源( 超级块的出口预测器、指令窗口、指令c a c h e 、数据c a c h e 、l o a d s t o r e 队列和寄存器单元) 都均匀分布在各个处理器核上( c o r e ) ，通过复制简单的处 理器核，达到计算能力的扩展。关于e d g e 指令集体系结构、块原子执行模型、 t - f l e x 的资源划分方案和分布式控制协议，详见第二章。 1 1 3 非均匀一致c a c h e 的提出 随着工艺的进步，片上c a c h e 的容量也随之增大，二级乃至三级c a c h e 都已 经做在片上。如：a l p h a2 1 3 6 4 就包含了一个1 7 5 m b 的片上二级c a c h e ( g w e n n a p ， 1 9 9 8 ) ，h pp a 8 7 0 0 包含了2 2 5 m b 的片上c a c h e ( h i l l ，2 0 0 1 ) ，i n t e li t a n i u m 2 甚 至包含了一个3 m b 的片上三级c a c h e ( h u h ，2 0 0 1 ) 。片上c a c h e 容量的增大一方 面来自于高带宽的访存需求，另一方面也得益于更多的片上晶体管资源。 然而，随着片上线延迟的增大，对于c a c h e 中不同远近数据行的访问延迟的 差距将越来越大。而传统的全局c a c h e 结构必须兼顾最长的访问延迟，并以此作 3 第1 章绪论 为统一的访问延迟，那么随着线延迟的增大，c a c h e 访问延迟也将随之成正比地 增大。这样的结构难以适应线延迟的扩展。 在这样的背景下，学术界提出了非均匀一致c a c h e 结构( n u c a ，n o n u n i f o n n c a c h ea r c h i t e c t u r e ) ( k i m ，2 0 0 2 ) 。如其名称所示，该结构中没有统一的c a c h e 访问延迟，而是以块( b a n k ) 的粒度划分不同的延迟，从而节省了较近b a n k 的 访问时间，减小了平均访问延迟，削弱了线延迟的影响。因此，n u c a 结构能够 较好地随线延迟而扩展。 1 2t p a 与n u c a 结合的研究意义 非均匀一致的c a c h e 结构的提出是为了适应日益增长的片上线延迟，其设计 不仅适用于分片式处理器，也适用于传统的超标量处理器核。本文之所以在 t p a p i 上研究非均匀一致c a c h e 结构的应用，其原因有三点： 第一、两者都是在亚微米工艺下为了解决线延迟增大的问题而提出的，因此 两者具有相同的工艺背景，其结合是自然的。 第二、分片式体系结构也对其c a c h e 设计提出了新的要求，一方面，需要有 分片式的c a c h e 结构以满足大量执行单元的并发访存需求；而另一方面，需要有 分布式内存依赖解析机制以保证分布式的访存顺序。对此，非均匀一致c a c h e 的分片式结构较好地满足了第一点；而第二点则需要额外的针对具体执行模型的 设计来保证。 第三、如何在访存指令分布式执行的条件下，减少访存指令执行的时间，是 在t p a p i 的一级c a c h e 中应用n u c a 的一个值得研究的方面。 1 3 论文主要工作 根据1 2 节所述的相关原因，本文对非均匀一致c a c h e 与分片式处理器的结 合以及结合所导致的问题进行了深入研究，分别对分片式处理器上的一级和二级 c a c h e 使用非均匀一致c a c h e 进行设计，并根据分片式处理器中特有的访存特征 对非均匀一致一级c a c h e 结构进行优化，提出了l o a d 本地化执行模型，并评估 了模型的性能和开销。 本文对非均匀一致二级和一级c a c h e 的设计和优化均基于实验室共同研究 的t p a p i 处理器。主要研究内容包括如下三个方面。 l 、为t p a p i 设计静态非均匀一致的二级c a c h e 结构，设计相应的c 程序 模拟器，以验证功能的正确性与硬件设计的可行性。 该部分设计包括静态数据映射方式，片上网络互连、c a c h eb a n k 内部结构、 c a c h e 事务，以及c a c h e 的流水化处理。最终根据所描述的方法实现t p a - p i 上 4 第1 章绪论 面向二级c a c h e 的c 程序模拟器，其模拟精确至每个时钟所产生的信号，与硬 件有较为准确的对应关系。该部分与t p a p i 的联系仅仅在于接口部分，相对较 为独立，因此可以作为一个普适的静态非均匀一致c a c h e 的设计实例。 2 、针对t p a p i 上非均匀一致一级c a c h e 结构中存在的l o a d 指令的长路由 延迟问题，进行相关的设计优化。 该部分底层的n u c a 结构设计与二级c a c h e 类似，但与分片式处理器本身 的执行模型相结合的部分则涉及到访存指令的分布式执行，访存依赖解析与顺序 维护。我们首先分析t p a p i 的访存执行模型下一级n u c a 上的访存行为特征， 并根据l o a d 指令数据端和发射端不一致的情况，考察其中可能获得的性能提升 潜力；接着，据此设计l o a d 本地化执行的优化模型，并设计多种拷贝策略和一 致性维护策略以控制拷贝和s t o r e 广播的开销。 3 、从功能和时序两个方面对模型进行实现和模拟，考察影响性能的关键因 素，并评估各种策略选择对性能和开销的影响。 在该部分中，我们首先编写一级c a c h e 的功能模拟器，输入应用程序的访存 执行序列，以获得非时钟相关的统计信息，从宏观上考察模型的不同设计选择。 接着，我们修改u ta u s t i n 大学的t - f l e x 模拟器，在其上实现l 0 a d 本地化执行 模型，并使用该模拟器对一些典型的设计选择进行评测，以获得时钟精确的统计 信息。 1 4 论文结构 本文内容按照如下结构组织： 第1 章介绍了研究背景及本文的主要研究工作。 第2 章介绍了分片式体系结构的背景模型，及非均匀一致c a c h e 的应用实例。 第3 章描述了t p a p i 上非均匀一致二级c a c h e 的组织方式，运作机制，及 内部各部件的设计。 第4 章分析了t p a p i 上非均匀一致一级c a c h e 中l o a d 发射端和数据端不一 致的情况，并详细描述了l o a d 本地化执行的优化模型。 第5 章对l o a d 本地化执行模型进行分析，并评测了减小开销的各种策略。 第6 章是全文总结和未来工作。 5 第2 章相关工作 第2 章相关工作 作为本文非均匀一致c a c h e 研究的处理器背景，在本章中我们首先介绍了 e d g e 指令集体系结构和块原子执行模型，以及作为t p a p i 设计蓝本的t - f l e x 微体系结构，重点描述了其分布式的资源分配和控制协议，以及涉及一级c a c h e 的访存依赖解析机制。接着，我们介绍了关于非均匀一致c a c h e 的一些相关研究 工作，以及其在片上多处理器和分片式一级c a c h e 上的一些已有的应用方案； 2 1 分片式处理器体系结构 t p a p i 、t r i p s 、t - f l e x 均采用e d g e 指令集体系结构。e d g e 称为显式 数据流执行的指令集体系结构( e x p l i c i td a t ag r a p he x e c u t i o n ) ，其特点在于编译 器将指令间通信显式编码表示出来，从而一条指令( 生产者指令) 计算出的结果 可以通过硬件直接传送给以该结果为操作数的指令( 消费者指令) 。 2 。l 。l 数据依赖显式编码的指令集 在传统的寄存器通信中，生产者和消费者指令间的通信是通过对共享寄存器 写后读来隐式表达的，同时，由于共享寄存器资源有限，必将出现不同的指令对 需要通过同一个寄存器进行通信，因此还会出现读后写与写后写依赖；从而在乱 序执行时，这些依赖都必须通过复杂的硬件机制分析获得。而在显式数据通信中， 不需要共享的寄存器资源，因此不存在读后写和写后写依赖，而且由于编译器已 将通信显式表达出来，在乱序执行时也无需再进行写后读的依赖判断。 例如，传统的r j s c 指令：a d dr 1 ，r 2 ，r 3 其相应的e d g e 指令为：a d dt 1 ，t 2 ( b u r g e r , 2 0 0 4 ) 在r i s c 指令中，r 1 ，i 匕，r 3 均是寄存器，从指令中我们无法得知该指令 将对哪些指令造成依赖；而在e d g e 指令中，t 1 和t 2 代表了a d d 的消费者指 令，因此a d d 与t 1 、t 2 的依赖关系是由编译器显式编码表示的。 2 1 2 静态放置动态发射方式 e d g e 是静态放置动态发射( s p d i ，s t a t i cp l a c e m e n td y n a m i ci s s u e ) 的指令 集体系结构( n a g a r a j a n ，2 0 0 4 ，s m i t h ，2 0 0 6 ) 。即：每条指令对应的执行单元和保 留站中的位置是由编译器静态确定