（计算机科学与技术专业论文）ccnuma系统存储体系结构关键技术研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 分布共享存储( d s m ) 系统支持全系统统一地址编程空间，有效地将传统的 共享主存多处理器系统和分布主存系统的优点结合起来，兼具可编程性好和可扩 展性高的优势，成为大规模并行高性能计算机研究领域首选的硬件平台。采用 c c - n u m a 机制是实现d s m 系统的有效技术途径，但如何高效维护c a c h e 一致性 是实现c c - n u m a 系统的难点之一，它不仅决定着系统的正确性，而且对系统的 性能有着极其重要的影响。目前国内外对c a c h e 一致性的研究主要集中在目录结 构的可扩展性和协议的高效实现两方面。 由于c c n u m a 系统中各处理器通过共享存储器进行通信，因此，处理器访 问存储器的时延，特别是当处理器数目非常大的时候，处理器访问远程存储器的 时延将极大地影响计算机系统的性能。这样，如何尽可能地提高访存带宽、降低 访存延迟、减小远程访存与本地访存时延的差距就成为c c n u m a 系统是否好用、 实用的关键。 针对这些问题，本文围绕如何实现高效的c c n u m a 系统存储体系结构，着 重对基于目录的c a c h e 一致性协议的可扩展性、目录协议的优化技术、提高访存 带宽、降低访存延迟，以及大规模c c - n u m a 系统模拟验证环境等关键技术展开 研究探索。本文的主要工作和创新点是： 1 提出了一种基于s m p 结点的可扩展c c - n u m a 体系结构模型一s c d s m ， 并在此系统上实现了一种高效、无死锁、基于目录的c a c h e 一致性协议。在协议 实现中，针对共享读总线脏命中时c a c h e 状态和目录状态不一致的问题，提出了 一种强制写回( f w b ) 方法，解决了目录协议和监听协议兼容的难题；提出了本 地访存请求直接转发( l m r d f ) 技术，解决了基于s m p 结构的c c n u m a 系统 由于等待总线监听结果造成的请求延迟问题，s c d s m 系统性能由此可以提高 1 0 1 5 。 2 为多处理器系统中共享数据的分布建立了马尔科夫模型，并对共享数据的 分布模式进行了分析，得出结论：c c - n u m a 系统中共享数据的平均c a c h e 副本 数一般比较小。该理论分析结果对我们提出更有效的目录组织方案有很好的指导 】：一， 思义o 3 针对目录存储开销影响c a c h e 一致性协议的可扩展性问题，本文提出了基 于目录c a c h e 的两级目录组织方案，有效地降低了目录信息所需要的存储空间， 使协议实现具有较好的可扩展性。对基于目录c a c h e 的两级目录模型进行了模拟 和性能验证，结果表明，并行测试程序的运行时间都有不同程度的减少。 4 存储墙问题是影响系统性能进一步提升的瓶颈，如何降低访存延迟是存储 第i 页 国防科学技术大学研究生院博士学位论文 系统设计面临的巨大挑战。本文提出了四种不同约束强度的访存调度算法，并对 四种调度算法进行了性能分析，分析结果表明，带体地址冲突消解和防饿死机制 的贪婪启发式访存调度算法具有最佳性价比。具体实现了采用带体地址冲突消解 和防饿死机制的贪婪启发式访存调度算法的d d r 2 访存控制器。 5 为了更有效地模拟验证复杂系统和大规模系统的正确性，本文提出了分布 环境下的多结点模拟验证平台c o s i m ：为了配合模拟测试任务的进行以及c a c h e 一致性协议的功能验证，本文提出了c m c v 模型。在c o s i m 平台上，对v e r i l o g 代码编写的s c d s m 系统进行了全面的功能验证。另外还使用v e r i l o g 语言构造了 类似s t r e a mc o p y 程序行为的q s c v 模型，对s c d s m 系统的l m r d f 技术和访存 带宽进行了评测和分析。 以上关键技术和相应解决方案均已在工程项目中得到实际应用，对推进高效 的c c n u m a 系统存储体系结构的进一步研究具有一定的理论意义和重要参考价 值。 主题词：c c n u m a ，访存延迟，c a c h e 一致性协议，目录结构，存储开销， 可扩展性，访存调度算法，模拟验证 第i i 页 鏊防懿学技拳大学磅囊生藏壤学位论文 a 8 s t r a e t d i s t r i b u t e ds h a r e dm e m o r y ( d s m ) s y s t e mp r o v i d e sag l o b a ls h a r e da d d r e s ss p a c e ， w h i c ht r a d e so f fs h a r e dm e m o r ym u l t i - p r o c e s s o ra n dd i s t r i b u t em e m o r ys y s t e m 。镢斑 t h ea d v a n t a g e so fp r o g r a n m m b i l i 移a n ds c a l a b i l i t y ，d s mh a sb e c o m et h ep r e f e r r e d h a r d w a r e p l a t f o r m f o rm a s s i v e p a r a l l e lh i g hp e r f o r m a n c ec o m p u t e rs y s t e m s e c 冷诞 涎蠢i sa ne f f e c t i v em e c h a n i s mt oi m p r o v et h ep e r f o m m n c eo fd s m s y s t e m s t l 憾m a i n t e n a n c eo fc a c h ec o h e r e n c e ，w h i c hn o to n l yd e t e r m i n e ss y s t e mc o r r e c t n e s s ， b u ta l s og r e a t l yi m p a c t ss y s t e mp e r f o r m a n c e ，h a sb e e nt h ep r i m a r yd i f f i c u l t yt o i m p l e m e n tc c 凝戮as y s t e m s 。c u r r e n t l yr e s e a r c h e sf o c u so nt h es e a l a b l ea n dh i g h p e r f o r m a n c ei m p l e m e n t a t i o no fd i r e c t o 鼬a s e dc a c h ec o h e r e n c es y s t e m p r o c e s s o r s 遗c c - n u m as y s t e m sc o m m u n i c a t ew i t he a c ho t h e rt h r o u g hs h a r e d m e m o r y ，s ol a t e n c yo fr e m o t em e m o r ya c c e s s ，e s p e c i a l l yw i 也g r e a tn u m b e ro f p r o c e s s o r s w i l ld r a m a t i c a l l yi m p a c tt h es y s t e mp e r f o r m a n c e 硼把k e yo fe f f e c t i v e i m p l e m e n t a t i o no fc c 撼艇as y s t e m sl i e so ni m p r o v i n gt h em e m o r yb a n d w i d t h , s h o r t e n i n gm e m o r ya c c e s sl a t e n c ya n dr e d u c i n gt h eg a pb e t w e e nl o c a la n dr e m o t e m e m o r ya c c e s sl a t e n c y 聪sd i s s e r t a t i o ni sd e v o t e dt ot h ei m p l e m e n t a t i o no fe f f e c t i v e 淡棚颡as y s t e m s m e m o r ya r c h i t e c t u r e i tr e s e a r c h e st h es c a l a b i l i t yo fd i r e c t o r y b a s e dc a c h ec o h e r e n c e ， t h eo p t i m i z a t i o no fd i r e c t o r yp r o t o c o l s , t h es i m u l a t i o na n dv e r i f i c a t i o np l a t f o r mf o r c c - n u m a s y s t e m s ，a n dt h et e c h n o l o g yo fi m p r o v i n gm e m o r yb a n d w i d t ha n dr e d u c i n g a c c e s sl a t e n c y 。t i l em a i n w o r ka n dc o n t r i b u t i o n so ft h ed i s s e r t a t i o na r ea sf o l l o w s ： 差。轰n e ws c a l a b m e 专蛙默蠡a r c h i t e c t u r eb a s e do ns 攀n o d e s 。c a l l e ds c d s m , i s p r o p o s e d al o c k f r e e ，h i g hp e r f o r m a n c ed i r e c t o r y b a s e dc a c h ec o h e r e n c ep r o t o c o li s i m p l e m e n t e db a s e do ns c d s m af w bs t r a t e g yi sp r o p o s e dt oa d d r e s st h ei n c o n s i s t e n t p r o b l e mb e t w e e nc a c h es t a t ea n dd i r e c t o r ys t a t ew h e nr e a dr e q u e s th i t sd i r t yc a c h e b l o c ko nt h eb u so fs m pn o d e n es t r a t e g ys o l v e st h ed i f f i c u l t p r o b l e mo f c o m p a t i b i l i t yo fd i r e c t o r yp r o t o c o l sa n ds n o o p i n gp r o t o c o l s al m r d fs t r a t e g yi s p r o p o s e dt od e c r e a s er e q u e s ts e n d i n gd e l a yc a u s e db yw a i t i n gt h eh i tr e s n ro nb u si n c c * n u m a s y s t e mb a s e do ns m pn o d e t h i st e c h n i q u ei m p r o v e st h ep e r f o r m a n c eo f s c d s m s y s t e m 舞l 番缸| 5 ， 2 am a r k o vc h a i n sm o d e li sb u i l tf o r t h ed i s t r i b u t i o no fs h a r e dd a t ai n c c n u m as y s t e m s w ea n a l y z et h ed i s t r i b u t i n gp a t t e mo fs h a r e dd a t ab a s e do nt h i s m o d e l 。i ti sp r o v e dt h a t ，t h ea v e r a g en u m b e ro fc a c h ec o p i e so fs h a r e dd a t ai ss m a l li n c c - n u m as y s t e m s t h i st h e o r e t i c a la n a l y s i so fd i s t r i b u t i n gp a t t e mf o rs h a r e dd a t ai n c c - n u m as y s t e m sc a r lb eh e 肇f u li np r o p o s i n gm o r ee f f e c t i v ed i r e c t o r yo 鹅a 魏i 2 躐i 建 m e t h o d s 3 at w o w l e v e ld i r e c t o r yo r g a n i z a t i o ns c h e m eb a s e do nd i r e c t o r yc a c h ei sp r o p o s e d 繁i i i 餮 国防科学技术大学研究生院博士学位论文 t oa d d r e s st h ep r o b l e mo fd i r e c t o r ym e m o 巧o v e r h e a dp r o h i b i t i n gt h es c a l a b i l i t yo f c a c h ec o h e r e n c ep r o t o c 0 1 t h i ss c h e m ec a nr e d u c et h em e m o r yo v e r h e a do fd i r e c t o r y i n f o r m a t i o na n di m p r o v et h es c a l a b i l i t yo ft h ep r o t o c 0 1 s i m u l a t i o na n da n a l y s i ss h o w e d t h a tt h ee x e c u t i o nt i m e so fan u m b e ro fp a r a l l e lb e n c h m a r k sw e r es h o r t e n e dt ov a r i o u s d e g r e e s 4 m e m o r yw a l li st h eb o t t l e n e c ko fs y s t e mp e r f o r m a n c e t or e d u c em e m o r y a c c e s sl a t e n c yi st h ec h a l l e n g ew eh a v et of a c e f o u rm e m o r ys c h e d u l i n ga l g o r i t h m s 、析t hd i f f e r e n tc o n s t r a i n td e g r e e sa r ep r e s e m e d ，t h es i m u l a t i o na n da n a l y s i ss h o w e dt h a t t h eg r e e d ym e m o 巧s c h e d u l i n ga l g o r i t h mw i t hc o n f l i c te l i m i n a t i o no fb a n ka d d r e s sa n d s t a r v a t i o na v o i d a n c es t r a t e g yi se f f e c t i v e t h ed d i 匕b a s e dm e m o 巧c o n t r o l l e ri s i m p l e m e n t e d o i lh a r d w a r e 5 ad i s t r i b u t e dm u l t i n o d es i m u l a t i o na n dv e r i f yp l a t f o r mn a m e dc o s i mi s p r o p o s e dt oe f f e c t i v e l yv e r i f yt h ec o r r e c t n e s so fc o m p l e xo rl a r g es y s t e m s t oa s s i s t s i m u l a t i o nt e s t sa n dv e r i f i c a t i o no fc a c h ec o h e r e n c ep r o t o c o l ，t h ec m c vm o d e l i s p r o p o s e d aq s c v m o d e ls i m i l a rt os t r e a mc o p yw i t hv e r i l o gh a r d w a r ed e s c r i p t i o n l a n g u a g ei sb u i l tt o e v a l u a t et h el m i 江t e c h n i c a la n dt h em e m o r yb a n d w i d t ho f s c d s m s y g e m i ns 1 】m m a r v ，t h ed i s s e r t a t i o np r o v i d e saf e a s i b l es o l u t i o nf o ran u m b e ro f c h a l l e n g i n gp r o b l e m s o fc c - n u m as y s t e m s a n dt h e s es o l u t i o n sh a v eb e e n i m p l e m e m e di ne n g n e e r i n g i ti sb e l i e v e dt h a tt h er e s e a r c hw i l lm a k ea n i c eg r o u n d w o r k f o rt h ef u r t h e rr e s e a r c ha n de n g i n e e r i n go nc c n u m ab a s e dm e m o r ya r c h i t e c t u r e k e yw o r d s ：c c n u m a ，m e m o r ya c c e s sl a t e n c y ，c a c h ec o h e r e n c ep r o t o c o l ， d i r e c t o r yo r g a n i z a t i o n ，m e m o r yo v e r h e a d ，s c a l a b i l i t y ，m e m o r ys c h e d u l i n g a l g o r i t h m ，s i m u l a t i o na n dv e r i f i c a t i o n 第i v 页 国防科学技术大学研究生院博士学位论文 表目录 表2 1 互联结构比较2 2 表2 2 各系统实现的c a c h e - - 致性协议比较2 2 表3 1s c d s m 系统支持的c a c h e a b l em e m o r y 事务及其对应请求的名称3 7 表3 2 一致性消息的划分3 8 表3 3s c d s m 系统中处理器接口逻辑冲突情况列表4 8 表4 1 模拟器参数设置7 9 表4 2 测试程序规模设置7 9 表5 1d d r 2 主要功能改进8 6 表5 2 当前请求与下一请求之间的关系8 8 表5 3q 一。与纠之间的延迟约束关系1 0 5 表5 4q 一：与纠之间的延迟约束关系1 0 5 表5 5q ，3 与斜之间的延迟约束关系1 0 6 表6 1 测试程序集说明。l l8 表6 2 关键逻辑功能测试程序集118 表6 3 不同预取距离、不同频率下的系统测试带宽：1 2 0 第v 页 国防科学技术大学研究生院博士学位论文 图目录 图1 1c c n u m a 结构的d s m 系统及存储层次2 图1 2 一种c c n u m a 超结点结构3 图1 3o r i g i n2 0 0 0 系统结构框图4 图1 4c c - n u m a 结构的访问层次顺序5 图1 5 论文组织结构11 图2 1d a s h 系统结构示意图一17 图2 2a l e w i f e 结构示意图l8 图2 3f l a s h 结构示意图19 图2 4n u m a c h i n e 结构示意图1 9 图2 5s u p e r d o m e 结点内部结构和互连示意图一2 0 图2 6n o v a s c a l e51 6 0 系统结构示意图。2l 图2 7d a s h 协议目录状态转换示意图2 4 图2 8o r i g i n2 0 0 0 协议目录状态转换示意图2 5 图2 9a l p h a s e r v e rg s 3 2 0 协议基本流程2 8 图3 1s c d s m 系统结构示意图3 3 图3 2s m i c 结构框图3 4 图3 3c a c h e 状态转换示意图3 6 图3 4 目录项为未缓存态时，共享读的处理流程3 9 图3 5 目录项为独占态时，共享读的处理流程4 0 图3 6 目录项为临时状态时，共享读的处理流程4 0 图3 7 目录项为未缓存状态时，独占读的处理流程4 1 图3 8 目录项为独占态时，独占读的处理流程4 l 图3 9 目录项为共享态时，独占读的处理流程4 2 图3 1 0 目录项为临时态时，独占读的处理流程。4 2 图3 1 1 共享读总线脏命中时导致c a c h e 状态的变化4 3 图3 1 2 目录状态置为独占态时导致的错误处理。4 4 图3 1 3 目录状态置为共享态时导致的错误处理4 4 图3 1 4f w b 的一般处理流程4 5 图3 1 5c a c h e 块状态为m 态时f w b 的处理流程4 6 图3 1 6 冲突请求的串行化处理4 8 图3 1 7 写回请求和i r d s h 请求的冲突处理4 9 图3 18 写回请求和i r d e x 请求的冲突处理4 9 第v i i 页 国防科学技术大学研究生院博士学位论文 图3 1 9 写回请求和i r d e x 请求由于网络延迟带来的冲突处理5 0 图3 2 0 目录状态为独占时的超发请求5 l 图3 2 l 目录状态为忙共享时的超发请求5 l 图3 2 2 目录状态为忙独占，且独占者为本地结点时的超发请求5 2 图3 2 3 目录状态为忙独占，且独占者为其它结点时的超发请求5 2 图4 1 位向量目录5 7 图4 2 有限指针目录5 8 图4 3 有限指针目录项溢出的处理5 8 图4 4 动态指针分配目录5 9 图4 5 链式目录6 0 图4 60 3 k 标准目录格式6 1 图4 70 3 k 高级目录格式6 l 图4 8 状态转移图6 3 图4 9 读请求占2 5 情况下的共享数据c a c h e s i j 本数的分布6 7 图4 1 0 读请求占5 0 情况下的共享数据c a c h e 昌l j 本数的分布6 8 图4 1 l 读请求占7 5 情况下的共享数据c a c h e n 本数的分布6 8 图4 1 2 读请求占9 0 情况下的共享数据c a c h e n 本数的分布6 8 图4 1 3 共享读比例对共享数据平均c a c h e 哥i j 本数的影响6 9 图4 1 4 降低目录存储开销的两个方面7 0 图4 1 5 两级目录组织方案7 l 图4 1 6 目录c a c h e 组织示意图7 4 图4 17 目录c a c h e 访问示意图。7 5 图4 18 比较法逻辑电路一7 6 图4 1 9r s i m 多处理器系统7 7 图4 2 0 基于目录c a c h e 的两级目录对应用程序运行结果的影响8 0 图4 2 11 6 个结点时目录c a c h e 大小对系统性能的影响8 1 图4 2 23 2 个结点时目录c a c h e 大小对系统性能的影响8 l 图4 2 36 4 个结点时目录c a c h e 大小对系统性能的影响8 1 图4 2 41 6 个结点时目录c a c h e 组相联度对系统性能的影响8 2 图4 2 53 2 个结点时目录c a c h e 组相联度对系统性能的影响8 3 图4 2 63 2 个结点时目录c a c h e 组相联度对系统性能的影响8 3 图5 1d d r 2s d r a m 三维结构示意图8 7 图5 2 同体刁 结 构，s g io r i g i n2 0 0 0 、a l t i x3 0 0 0 ，h ps u p e r d o m e 都属于这种结构。由于硬件实现 比软件实现效率高，性筢好，因此，我们通常所说的d s m 都是指硬件实现的d s m 。 由于c c - n u m a 系统中各处理器通过共享存储器进行通信，因此，处理器访 问存储器的时延，特别是当处理器数目非常大的时候，处理器访问远程存储器的 时延将极大地影响计算枫系统的性能。如何尽可能地提高访存带宽、降低访存延 迟，减小远程访存与本地访存时延的差距就成为c c n u m a 系统是否好用、实用 第1 页 国防科学技术大学研究生院博上学位论文 的关键，成为人们研究的热点。 目前国内外就降低远程存储访问延迟的问题进行了大量研究，其中包括高带 宽低延迟的互连网络技术 1 4 1 7 、处理器与局部存储器之间的大数据块传输( b l t ) 技术 1 8 1 、页迁移技术 1 9 2 4 等，此外还提出了许多改进的缓冲策略 2 5 2 7 。 另一方面，由于c c n u m a 系统引入了c a c h e 访问层次，可能带来数据不一 致性的问题。如何高效维护c a c h e 一致性( c a c h ec o h e r e n c e ) 是实现d s m 系统的 难点之一，它不仅决定着系统的正确性，而且对系统的性能也有着极其重要的影 响。目前国内外对c a c h e 一致性的研究主要集中在目录结构的可扩展性和协议的 高效实现两方面。 本文的工作正是针对上述这一具有深刻技术背景和广泛应用前景的热点研究 问题展开，围绕如何实现高效的c c - n u m a 系统存储体系结构，对c c n u m a 系 统中存储体系结构的关键技术进行深入研究和探讨。 1 2c c n u m a 系统概述 c c - n u m a 是具有c a c h e 一致性的非一致存储访问结构，c a c h e 一致性必须保 证处理器每次读到的都是系统中数据的最新值。c c - n u m a 实现了d s m 结构，对 分布式的物理内存保持单一的逻辑地址空间。由于系统存储器物理上的分布，处 理器访问远程和本地存储器的时间不再统一。远程存储访问延迟对系统的性能有 着较大的影响，在c c - n u m a 系统中，本地和远程访存延迟比可达到1 ：2 到1 ： 5 1 2 1 ，2 8 ，2 9 】，甚至更高。 图1 1c c n u m a 结构的d s m 系统及存储层次 第2 页 藿防秘学技术大学研究生院博学位论文 图1 1 给出了c c n u m a 系统结构示意。结点y 的处理器流出的读写请求如果命中 l l 或者l 2c a c h e ，则只需花费数个时钟周麓。如果不会中，则需要访闯存储器， 访问本地存储器一般需要近百个时钟周期。如果数据不在本地存储器，则需要访 问远程存储器( 比如结点x 的本地存储器) ，一般需要花费数百个时钟周期。尽管 通过使用弱一致性存储模型 3 0 1 ，可以隐藏存储器写操作的延迟，但对存储器的读 操作带来的延迟将极大地影响系统的性能。 为了实现超高性麓计算，大援模并行处理系统处理器数譬越来越多，基于超 结点的大规模并行处理系统已成为一种发展趋势。在超结点结构中，每个超结点 拥有多个处理器，它们既可以是传统的对称多处理器( s y m m e t r i cm u l t i p r o e e s s o r ， s m p ) 系统，也可以是采用c c - n u m a 结构的d s m 多处理器系统。利用数据局部 性原理，个应用的大多数存储访问可以在超结点内得到满足。这样，一方面减 小了超结点之间互连网络的规模，有利于降低远程存储访闻延迟，同时减少了超 结点间的访存流量，有利于降低互连网络的负载。 图1 2 给出了一个基于超结点簏大规模并行处理系统结构示意图。 图1 2 种c c ，n u m a 超结点结枣每 e x e m p l a r 3 1 】是h p c o n v e x 公司于1 9 9 6 年推感的一个基予超结点酌 c c - n u m a 类型的可扩展并行处理机。一个e x e m p l a rx 系统包含若干个超结点， 超结点之闻通过一致性环形至连网络( c o h e r e n tt o r o i d a li n t e r c o n n e c t ，c t i ) 互连。 系统通过硬件和软件提供全局共享存储器，允许任何处理器和i o 设备控制器访问 第3 页 国防科学技术大学研究生院博士学位论文 整个系统中所有超结点的本地存储器。同样，任何处理器可以访问连接在任一超 结点上的i o 设备，系统通过硬件维护系统范围内的c a c h e 一致性。 大部分时间，处理器只需访问自己的c a c h e ；在c a c h e 失效的情况下，处理器 通过交叉开关访问同一超结点内的本地共享存储器；如果在本地存储器中仍无法 找到该数据，处理器通过c t i 网络访问另一个超结点的本地存储器以获得数据。 为了减少远程存储器访问，每个超结点设有一个c t ic a c h e ，用于缓存访问远程结 点而取得的读数据，c t ic a c h e 通过全局物理地址进行索引和标记。 s e q u e n t 公司于1 9 9 6 年安装成功n u m a q2 0 0 0 1 2 8 系统。n u m a q 的基本组 成部件是一个4 处理器的s m p 电路板，称为q u a d 。系统最多可拥有6 3 个q u a d 或者说有2 5 2 个处理器，所有q u a d 中的局部存储器通过基于s c i ( s c a l a b l e c o h e r e n c ei n t e r f a c e ) 的互连网络( i q 1 i n k 和i q p l u s ) 粘合成一个全局存储器。通 过一个硬件的基于目录的协议实现高速缓存的一致性。因为一个q u a d 本身就有很 大的局部存储器( 4 g b ) 和一个大容量的远程高速缓存( 3 2 m b ) ，大部分数据存 取在一个q u a d 内就可完成。 s g i 公司o r i g i n2 0 0 0 1 2 1 】的设计目标是最小化远程访存和本地访存的时延比， 通过硬件和软件的支持来确保尽可能多的存储访问是本地的。为了达到远程和本 地访存时延比尽可能小的目标，o r i g i n 主要采取了两个措施：一是在软硬件方面有 效地支持页迁移和复制，系统为每页提供了一个硬件存储访问计数器和一个块拷 贝引擎，能以接近访存峰值的速度来拷贝数据，还提供了减少t l b 更新代价的机 制；二是提供高性能的本地和全局互连以及大量的同步原语。 存曹篓和+ + i l u a 芯j 牛r 了 月习c l 一j 一一? 二 - 路由芯片 图1 3o r i g i n2 0 0 0 系统结构框图 第4 页 司! 一 擎 c 一 一 一 一 国防科学技术大学研究生院博士学位论文 o r i g i n2 0 0 0 结点内由h u b , t 片实现四路全交叉开关( 处理器、本地存储器、i o 和网络接口) 互连。全局互连基于六端口的路由芯片，实现一个多级的胖立方体 拓扑结构。图1 3 给出t o f i g i n 2 0 0 0 的结构框图。 上面介绍的三种系统都是长期以来极具代表性的c c n u m a 机器，这些 c c - n u m a 系统的存储访问可分为四个层次，如图1 4 所示。 h o m e 结点层 与给定地址相关 的目录和主存 远程结点层 远程结点所有处理器c a c h e 图1 4c c - n u m a 结构的访司层次顺序 本地结点层，是指支持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 传到c a c h e 失效的处理器。发生c a c h e 失效时，如果宿主( h o m e ) 结点 和拥有者( o w n e r ) 结点不同，则必须访问远程结点层才能得到所需的数据，这时 访问存储器时延最长。因此，虽然c c - n u m a 机器实现了本地和远程访问的透明 性，可以缓存远程数据，但c a c h e 失效时远程访问延迟很大，数据的局部性对 c c - n u m a 机器的性能有着很大的影响。基于这方面的考虑，o r i g i n2 0 0 0 采用自 动页迁移技术动态开发数据局部性。 1 3 降低存储访问延迟的技术 前文已提到c c - n u m a 系统的性能很大程度上依赖于存储访问延迟。本节中 我们将回顾各种降低存储访问延迟技术，包括预取、多线程、远程访问c a c h e 、网 络c a c h e 、s c o m a 等。 1 3 - 1 预取 预取( p r e f e c h i n g ) 是指在实际使用之前，将数据取入c a c h e 或者本地存储器， 并期望在不远的将来用到它 3 2 3 6 】。正确的预取操作可以避免从远程存储器读取 第5 页 国防科学技术大学研究生院博士学位论文 数据造成的停顿。软件预取机制最大的问题是预取时机而不是预测准确性，如果 预取时间过于接近请求数据的时间，预取就会太晚；如果预取过早，则会造成资 源浪费。通过编译器的指导，使用静态分析在代码序列中插入显式的非阻塞预取 指令，在取数据前的一个恰当的时间预取数据，可以保证数据在需要时已经存在 c a c h e 中，同时减少c a c h e 污染。而简单的硬件预取机制就是根据访存地址顺序地 取相邻的下一个c a c h e 块。更为复杂的硬件实现机制试图检测访问地址模式，比 如恒定的步进量，并相应地进行预取。但由于硬件预取需要猜测哪些数据将被使 用，同时增加了远程通信，这也是一个需要关注的问题。 1 3 2 多线程 多线程( m u l t i t h r e a d i n g ) 机铜j 3 7 3 9 通过活跃在每个处理器上的多个硬件线 程间的切换，来隐藏存储访问延迟。存储访问延迟隐藏是否成功主要决定于两个 重要因素：第一，底层硬件必须支持带快速内容切换的低延迟、多线程能力；第 二，工作负载在共享同一c a c h e 的线程中必须有有利的数据访问模式，使得内容 切换不会破坏每个结点上的c a c h e 内容。如果有足够的线程等待，多线程可以很 好地隐藏延迟，并产生高吞吐量。但多线程并不能降低每个单独线程的延迟，也 不能减少远程通信量。 1 3 3 远程c a c h e 和网络c a c h e 在每个结点上使用一大块r a m 作为本地的远程c a c h e ( n u m a r c ) 4 0 4 2 。 某个请求者访问c a c h e 块失效，该块的h o m e 是远程结点，则该数据应答返回后， 不但被存入请求者的处理器c a c h e ，同时也会放入该请求者的远程c a c h e 。远程 c a c h e 中的所有c a c h e 块与主存保持数据的一致性。 1 3 4c o m a 类似于n u m a r c ，c o m a ( c a c h e o n l ym e m o 巧a r c h i t e c t u r e ) 4 3 4 5 也使用 本地存储器为本地进程保存工作集。c o m a 与n u m a r c 的主要不同在于，在 c o m a 中，某个数据块没有被保存在h o m e 结点，而是存放在使用最多最经常的 结点上。由于数据块可以驻留在任何结点，与n u m a r c 相比，定位任一个数据 块的处理变得相当复杂。 1 4c a c h e 一致性协议 在摩尔定律的推动下，处理器和存储器的速度差距越拉越大，从而造成c p u 第6 页 国防科学技术大学研究生院博士学位论文 等待访问存储器数据的时间占c p u 运行时间的比例越来越大，使得平衡体系结构 的设计越来越困难。由通信带宽和延迟构成的“存储墙( m e m o r yw a l l ) 成为提 高系统性能的最大障碍。 根据存储局部性原理和小型存储器可以做得比较快这一事实，层次结构存储 器系统 4 6 成为人们追求“无限、快速存储器”、解决c p u 和主存之间速度不匹 配的最有效、最经济的手段 4 7 】。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 一 致性协议( c a c h ec o h e r e n c ep r o