（计算机科学与技术专业论文）多处理器系统中高效cache协议的实现方案设计与模拟.pdf

国防科学技术大学研究生院学位论文 摘要 f 随着社会不断向前发展，人类对计算速度和计算规模的需求不断提高。而单处理器 计算机系统由于处理器运算性能受限于芯片速度极限和加工工艺极限，不可能无限提高。 于是超大规模并行处理系统应运而生。但这也引入了一些在单处理器系统中没有出现的 问题。在系统中出现的多机存储信息的一致性问题便是当今国际上研究的热门问题之一。 现在，计算机处理器性能提高的速度远高于存储器件性能的提高，而较长的存储访问 延时大大限制了计算机性能的提高。为了缓和c p u 与存储器之间的速度差距，在计算机系 统的c p u 与主存之间引入了c a c h e 。但在多处理器系统中，由于多个处理器可能对同一 数据块进行读操作，当某个处理器对共享的数据块进行写操作时，其它处理器的c a c h e 中该数据块的副本将成为过时的数据。如果不及时地通知相应的处理器，将导致错误的 运行结果。存储一致性协议就是用来在这种情况下保证程序运行正确性的。但一致性协 议的使用也将占用系统资源，影响程序的运行速度。因此，个高效的存储一致性协议 必不可少。 在多处理器计算机系统中，c a c h e 一致性一直是一个重要的问题。虽然已有许多研究 成果，但仍在远程访问延时、系统的通讯量、数据的假共享等问题的解决方面不尽人意。，j 本文首先对常用的c a c h e 一致性协议进行了分析，提出了一种在多处理器系统中减 少远程访问延时的方式一在路由部件中加入存储部件一路由器c a c h e 。f 路由器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 一致性协 议。 ， e 为了对采用路由器c a c h e 的多处理器系统的性能进行模拟，我们选择以美国r i c e 大 学的r s i m 共享主存多处理器系统模拟器为基础，对其进行适当修改，建立了用于模拟含 路由器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 的组织做了一些改进， 既保持了性能，又减少了硬件开销。 总的来说，采用路由器c a c h e 是一种值得进一步深入研究的在多处理器系统中减少 远程访问延时、提高系统性能的方式。二r w ， 国防科学技术大学研究生院学位论文 关键字：c a c h e 一致性 、一 路由器c a c h e 国防科学技术大学研究生院学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fo u rs o c i e t y m a n sd e m a n d sf o rh i g hc o m p u t i n gs p e e d a n dw i d e c o m p u t i n g s c a l ea r e r a i s i n g b e c a u s e t h e p e r f o r m a n c eo fs i n g l e m i c r o p r o c e s s o rc a n tb ei m p r o v e di n d e f i n i t e l yd u et ot h e1 i m i t a t i o no fs p e e d a n dm a c h i n i n gt e c h n o l o g yo fc h i p s ，s oc a m et h em a s s i v ep a r a l l e lp r o c e s s o r ss y s t e m b u tt h i sl e dt os o m en e wp r o b l e m s h o wt ok e e pd a t ac o n s i s t e n c yi n m u l t i p r o c e s s o r s s y s t e m s i so n eo ft h eh o tp r o b l e m si nt h ew o r l d t o d a y ，t h ep e r f o r m a n c eo fp r o c e s s o r si si n c r e a s i n ga taf a s t e rs t e pt h a nt h a t o fm e m o r y t h el o n gd e l a yo fm e m o r ya c c e s st i m eh a s1 i m i t e dt h ed e v e l o p m e n to f c o m p u t e rp e r f o r m a n c e i no r d e rt oe a s eu pt h eg a pb e t w e e nc p ua n dm e m o r y ，c a c h e isin t r o d u c e db e t w e e nt h e m b u ti nam u l t i p r o c e s s o r ss y s t e m ，t h e r em a yb es e v e r a l p r o c e s s o r sh a v er e a dt h es s m ed a t a ，a n dt h e no n ep r o c e s s o rw i l lw r i t ei t t h i s t i m e ，t h ec o p yo ft h ed a t ai nt h ec a c h e so fo t h e rp r o c e s s o r sw i l lb eo u to fd a t e i ft h ep r o c e s s o rw h o s ec a c h eh a st h e0 1 dd a t ac a n tb ei n f o r m e di nt i m e itm a y l e a dt ow r o n gr e s u l t s t h em e m o r yc o n s i s t e n c yp r o t o c o li su s e dt oi n s u r et h er i g h t p r o c e s s i n go r d e ro fp r o g r a mu n d e rt h i s s i t u a t i o n b u tt h em e m o r yc o n s i s t e n c y p r o t o c o lw i l lu s es y s t e mr e s o u r c e s ，h a se f f e c to ns y s t e mp e r f o r m a n c e t h u s i t isn e c e s s a r yt oh a v ea ne f f i c i e n tm e m o r yc o n s i s t e n c yp r o t o c 0 1 i nm u l t i p r o c e s s o r ss y s t e m s ，c a c h ec o h e r e n c ei sa l w a y sa ni m p o r t a n ti s s u e a 1 t h o u g hm a n yr e s e a r c hr e s u l t sh a v eb e e np r o v i d e d ，t h e r es t i l la r em a n yf i e l d s n e e df u r t h e rr e s e a r c h ，s u c ha sr e m o t ea c c e s sd e l a y ，s y s t e mc o m m u n i c a t i o n ，f a l s e s h a r i n go fd a t a i nt h i s p a p e r ，w e m a d es o m e a n a l y s i s o nc o n v e n t i o n a lc a c h ec o h e r e n c e p r o t o c o l s w ep r o v i d e o n e w a y t or e d u c er e m o t ea c c e s s d e l a y a d d i n g a r o u t e r c a c h ei nr o u t i n gc o m p o n e n t s w h e nt h em e s s a g et h a tc o n t a i n i n gd a t ap a s s e s b y ，r o u t e r c a c h ek e e p so n ec o p yo ft h ed a t aa c c o r d i n gt ot h es i t u a t i o n w h e nn e w r e q u e s tt h a ta s k i n gf o rt h es a m ed a t ac o m e s ，r o u t e r c a c h ec a np r o v i d et h ed a t a i nt h i sw a y ，r o u t e r c a c h ec a nr e d u c et h er e s p o n s et i m eo fr e m o t ea c c e s sa n dt h e c o s t so fm e m o r yd i r e c t o r y a d d i n gc a c h ei nr o u t i n gc o m p o n e n t sw i l li n c r e a s et h e c o m p l e x i t yo f r o u t e ra n di t sc o s t b u tw i t ht h ea d v a n c ei nl a r g e s c a l ei n t e g r a t i o n t e c h n o l o g y ，i ti sp o s s i b l et od e s i g na n dp r o d u c er e u t e r sw i t hh i g hc o m p l e x i t y t h u sw ec a ni m p r o v et h ep e r f o r m a n c eo fm u l t i p r o c e s s o r ss y s t e mb yi n c r e a s i n gt h e c o m p l e x i t yo fh a r d w a r e t h e n ，w eg i v es o m ed e s c r i p t i o na b o u tt h ew o r k i n gp r i n c i p l e 、o r g a n i z a t i o n 、 f u n c t i o no fr o u t e r c a c h ea n dw h e r ei ts h o u l db e w ea l s o g a v eo u tac a c h ec o h e r e n c e p r o t o c o l f o rm u l t i p r o c e s s o r ss y s t e m sw i t hr o u t e r c a c h e s 国防科学技术人学研究生院学位论文 i no r d e rt o g i v e s i m u l a t i o na b o u tt h ep e r f o r m a n c eo f s y s t e m w i t h r o u t e r c a c h e s ， w es e tu pan e ws i m u l a t o ra f t e rg i v i n gn e c e s s a r yr e v i s i o no nt h e r s i ms i m u l a t o r ( as i m u l a t o rf o rs h a r e dm e m o r ym u l t i p r o c e s s o r ss y s t e m ) d e s i g n e d b y r i c eo n i v e r s i t y a tl a s t w er u ns e v e ns t a n d a r da p p l i c a t i o n so nt h es i m u l a t o rt oe v a l u a t et h e e f f e c to fr o u t e r c a c h eo ns y s t e mp e r f o r m a n c e w ea l s os i m u l a t eu n d e rd i f f e r e n t e n v i r o n m e n t s t h er e s u l t so fs i m u l a t i o ns h o wt h a t ：i ns y s t e m st h a th a v eal o t o f0 fp r o c r e s s o r s ，u s i n gr o u t e r c a c h ec a ni m p r o v et h e s p e e do fm u l t i p r o c e s s o r s s y s t e m su n d e rm o s tc o n d i t i o n s t os o m ea p p i i c a t i o n st h a th a v el o wh i t t i n gr a t e o fr o u t e r - c a c h e ，u s i n gr o u t e r c a c h ew o u l dn o ta f f e c ts y s t e mp e r f o r m a n c eh e a v i i f r o u t e r c a c h ec a na l s or e d u c et h ew o r k l o a do fn o d eb u sa n dm e m o r y ，s oi ti su s e f u l i ns y s t e m sw h o s ep e r f o r m a n c ea r e li m i t e db yn o d eb u so rm e m o r y b a s e do nt h e r e s u l t so fs i m u l a t i o n w ea l s om a d es o m er e v i s i o n sa b o u tt h eo r g a n i z a t i o no f r o u t e r c a c h e t h er e v i s i o nc a nr e d u c et h eh a r d w a r ec o s t so fs y s t e mw h i l ek e e p s y s t e mp e r f o r m a n c e i ns u m m e r y ，u s i n gr o u t e r c a c h ei sam e t h o dw o r t hf u r t h e rr e s e a r c ht or e d u c e r e m o t ea c c e s sd e l a ya n di m p r o v es y s t e mp e r f o r m a n c e k e y w o r d s ：c a c h ec o h e r e n c e r o u t e r c a c h er e m o t ea c c e s sd e ia y 国防科学技术大学研究生院学位论文 第一章前言 随着社会不断向前发展，人类对计算速度和计算规模的需求不断提高。而单处理器 计算机系统由于处理器运算性能受限于芯片的速度极限和加工工艺极限( 即芯片中信号 的传播速度不可能超过光速，芯片的加工工艺精度不可能高于原子) ，无法满足这些需求。 于是基于大型超结点的超大规模并行处理系统应运而生。在这种系统中，成千上万个处 理器协同工作，协作完成交给系统的在一般单处理器系统上难以有效处理的任务。但这 也引入了一些在单处理器系统中没有的新问题，当今国际上研究的热门问题一多处理器 系统中的多机存储信息一致性问题便是其中之一。 现在，计算机处理器性能提高的速度远高于存储器件性能的提高，而较长的存储器访 问延时大大限制了计算机性能的提高。为了缓和c p u 与存储器之间的速度差距，在计算机 系统的c p u 与主存之间引入了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 中该数据块的副本将成为过时数据。如果不及时地通知相 应的处理器，将会导致错误的运行结果。存储一致性协议就是用来在这种情况下保证程 序运行正确性的。但一致性消息的处理也将占用系统资源，影响程序的运行速度。因此， 设计一个高效的存储一致性协议对于保证大型并行系统的应用效率是必不可少的。 1 1 组织多处理器系统的方式 组织多处理器系统的方式很多【ij 。如果一个系统全局统一进行逻辑编址，在某个处 理器上的进程可以直接访问本地结点和系统中其它结点主存中的数据，那么这个系统是 共享主存结构；否则，是非共享主存结构。在共享主存结构中，一条指令( 例如l o a d ， s t o r e ) 可以直接访问多处理器系统中任何主存。在非共享主存结构中，虽然也可以共享 主存，但对不在本地结点的主存的访问不是直接的，需要提供软件层或用户可调用的库 来实现，访问延时较大。 多处理器系统也可以分成集中主存结构和分布主存结构。分布主存结构包括非一致 性访存结构( n u m a ：n o n u n i f o r m m e m o r ya c c e s s ) 和无远程访存结构( n o r v i a ：n o - r e m o t e m e m o r ya c c e s s ) 。也可以将n o r m a 结构归入n u m a 结构，因为在n o r m 【a 结构中，对存储器 的访问操作也是不一致的。 集中主存系统又称作一致性访存系统( u m a ：u n i f o r mm e m o r ya c c e s s ) 。在u k a 结构中， 所有主存和任何处理器之间的距离相同，所以所有存储访问操作所用的时间大致相等。 主要有两种u m a 结构：并行向量处理机( p v p ：p a r a l l e l v e c t o r p r o c e s s o r ) 和对称多处理器 系统( s m p ：s y m m e t r i cm u l t i p r o c e s s o r ) 。 分布主存系统中含有多个结点，每个结点中有一个或多个处理器以及本地主存。在 国防科学技术人学研究生院学位论文 非本地结点上的主存称作远端主存。当前主要有以下几种分稚主存结构：n o r m a ，非c a c h e 一致性n u m a ( n c c - - n u m a ：n o n c a c h ec o h e r e n tn u m a ) ，c a c h e 一致性n u m a ( c c n u m a ： c a c h ec o h e r e n tn u m a ) ，c o m a ( c a c h e o n l ym e m o r y a r c h i t e c t u r e ) 。 n o r m a 结构还可以进一步分成松耦合的簇( c l u s t e r ) 结构和紧耦合的传统大规模并 行结构( 现在不少大规模并行系统已经改采用c c n u m a 结构了) 。在n o r m a 结构中，结 点主存的逻辑编址是相互独立的，一个结点不能直接访问远端主存。如果结点p 想访问 结点q ( p 、q 不相同) 中的数据a ，需要结点a 执行一个发送操作，结点p 相应地执行一 个接收操作，最终，a 的值被拷贝到结点p 的主存中。 其它三种分布主存结构都有专用的硬件结构将系统中所有主存粘合成一个单一的地 址空间，以使任何处理器都可以访问所有主存。例如，它们都可以使用l o a d 指令取远程 数据。一个典型的n c c n u m a 系统为c r a y - - t 3 e 。除了本地主存外，c r a y - - t 3 e 的每个结 点都有一组称作扩展寄存器的结点级寄存器。有专门的指令将远端数据放入扩展寄存器 中。可以将扩展寄存器中的内容调入处理器的寄存器或本地主存。其它n c c n u m a 系统 也允许将远端数据送入处理器的寄存器。应注意的是：在n c c n u 凇结构中，远端数据 被调入到处理器寄存器或扩展寄存器后，不在本地的主存和c a c h e 中留下副本，也不自 动进行数据一致性检测。 在c c n u m a 结构中。指令在将远端数据a 调入本地处理器的寄存器的同时，还将a 自动拷贝到本地结点中的另一个特殊存储设备一远端c a c h e ( r c ：r e m o t ec a c h e ) q b 。顾名 思义，远端c a c h e 用于存放远端数据，其存放的数据不拷贝到本地主存中。在一些c c n u m a 系统中( 例如s g i 公司的o r i g i n2 0 0 0 系统) ，结点中没有远端c a c h e ，远端发送来 的数据直接拷贝到结点的二级c a t h e 中。 在c o m a 系统中，所有的本地主存都被当作c a c h e ( 称作c o m ac a c h e ) ，并按c a c h e 组织。 这样，结点c a c h e 的容量大于二级c a c h e 和远端c a c h e 的容量。指令在将远端数据a 调入 本地处理器的寄存器的同时，还将a 自动拷贝到本地主存( 即c o m ac a c h e ) 中。c o m a 结 构可由硬件支持在多个结点的主存中复制同一数据块。 下面对c c n u m a 和c o m a 这两种n u m a 结构进行一下比较旧，3 1 ： 在c c n u m a 结构中，主存包括所有结点上的本地主存。在c o m a 结构中，主存包括 所有c o 姒c a c h e 。c o m r 结构需要更多的硬件来维护c o m ac a c h e 的状态信息及标识。此外， c 0 姒结构的硬件还要支持c o m ac a c h e 管理和虚存管理二者的结合( 例如：如何从硬盘中 将一页数据调入c o m ac a c h e ) 。这些硬件方面的开销使得c o m a 系统要比c c n u m a 系统昂 贵。 c c n u m a 结构的操作系统在将程序调入运行时为每个数据块( c a c h e 块大小) 分配一 个h o m e ( 宿主) 结点。h o m e 结点的本地主存成为数据块的永久驻留地。当结点p 访问 数据块a 时，p 将a 临时存放在自己的本地c a c h e 中。当写回时，a 的内容必须被传回h o m e 的本地主存中。为了减轻写回导致的消息流量，c c - - n u m a 结构的操作系统可以以页为单 位进行数据复制或将数据迁移到对它们访问最频繁的结点的本地主存中。 在处理数据复制和数据迁移方面，c o m a 结构的效率比c c n u m a 高。首先，c o m a 结 构用硬件实现数据复制和数据迁移。在c o m a 系统中，数据可存放在任何地方，c a c h e 块 在运行时可以迁移到需要它的地方( 称作a t t r a c t i v em e m o r y ) 。其次，在c o m a 结构中，数 国防科学技术大学研究生院学位论文 掘复制和数据迁移的粒度是c a c h e 块，而在c c - - n u m a 结构中是页。所以，在c o m a 结构 中出现假共享情况的概率要低于在c c - - n u m a 结构中。 定义1 1 假共享是指两个处理器访问同一一致性粒度单位( 例如c a c h e 块，页) 中 的不同数据。 c c n u m a 结构和c o 姒结构的性能主要依赖应用程序的工作集大小和通讯计算比这 两个因素。当应用程序的工作集较小且通讯计算比低时，c c n u m a 和c o m a 的性能都比 较好。因为这种情况下，大部分数据访问都在本地的c a c h e 中被满足。当应用程序的工 作集比较大且通讯计算比高时，两种结构的性能都比较差。因为工作集大时，数据访问 在本地c a c h e 中被满足的比例降低，高的通讯计算比意味着网络流量的增加。 当应用程序的工作集较小且通讯计算比高时，c c - - n u m a 结构的性能一般优于c o m a 结构。因为访问在本地不命中时，c o m a 结构的操作开销较大。当应用程序工作集较大而 通讯计算比低时，c o m a 结构由于c a c h e 容量大，可以存储较多的远端数据而体现出较好 的性能。 表1 1 列出了四种分布共享主存结构的一些属性【l 4 ，5 】。 表1 1四种分布共享主存结构的部分属性 属性n o r m an c c n u m ac c n u m ac o 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 块 1 2c a c h e 一致性协议概述 如果对一个存储系统中任何一个c a c h e 块x 访问的返回结果满足以下三个条件【2 】： 条件1 1 ：对于处理器p 对x 进行写操作之后的读请求，如果在p 的写操作之后没有 其它处理器对x 进行写操作，那么返回的是处理器p 写的值。 条件1 2 ：另一个处理器q 对x 进行写操作后，处理器p 对x 进行读请求，如果这两个 操作分离足够长，且两者之间没有其它写操作，那么返回给p 的是q 所写的值。 条件1 3 ：写操作要顺序化，即对系统中任何处理器来说，所有对x 的写操作的次序 是相同的。 那么，这个存储系统就是一致的。 主要有三个因素导致c a c h e 中数据出现不一致： 1 不同的处理器的c a c h e 中有同一数据的副本，而这些处理器又不同步地对自己 c a c h e 中该数据的副本进行写操作。 国防科学技术人学研究生院学位论文 2 进程在多个处理器之间迁移，而迁移时没有互相通知。 3 i o 操作旁路了c a c h e 副本的所有者( o w n e r ) 。 1 2 1c a c h e 一致性协议中的写回法与写直达法 根据c a c h e 中数据被修改时，主存中相应的数据是否被同时更新，c a c h e 一致性协议 可分为写回法和写直达法( 写穿过法) 。如果c p u 更新c a c h e 中的某个数据的同时还更新 主存中的相应数据，那么，这种方式叫写直达法。而写回法在c p u 更新c a c h e 中的某个 数据时并不马上更新主存中的相应数据，而是等到一定条件被满足时( 例如该数据块从 c a c h e 中被替换出来时、该数据块被更新了一段时间后) 再更新主存中的相应数据。 这两种方法各有其优缺点。写直达法较好地保证了c a c h e 与主存中相同数据的内容 始终一致，但增加了c a c h e 与主存之间的通讯量。写回法则恰恰相反，它在c p u 对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 与主存数据不一致问题带来的影响。 1 2 2c a c h e 一致性协议中的写更新法与写无效法 目前，关于在多处理器系统中保持c a c h e 一致性的协议很多，根据当一个处理器对某 个共享的数据块进行写操作时，为了保证系统的c a c h e 一致性，该处理器是向系统中其它 拥有该数据块副本的处理器发送变无效信息，使那些处理器上的过时副本作废：还是同时 更新系统中其它处理器上该数据块的副本，c a c h e 一致性协议可分为写更新法和写无效 法。二者的区别如下嘶，7 ，8 】： 1 ) 同一处理器对同一字的多次写入，在写更新时，要广播多次，而写无效只需一次。 2 ) 在写多字c a c h e 块时，写更新法需广播每个字，而写无效法只在写第一个字时进行 变无效操作。 3 ) 从一个处理器的写与另一个处理器读出这次写操作所写的内容之间的等待时间上 看，写更新小于写无效。 可以看出，写无效法通过增加相关失效来减少写的代价和信息流量；写更新法通过 增加执行写操作时的信息流量来消除相关。 这两种方式，到底哪个好，与具体的应用的类型有关。在实际工作中，适用于写无效协 议的应用和适用于写更新协议的应用都要碰到。为了提高协议的适用范围，可以采用一 种折中方案：系统开始时先使用写更新协议，但各处理器对自己c a c h e 中的数据块的情况 作记录。如果某个处理器发现自己c a c h e 中的某个数据块在两次被更新之间没有被自己 国防科学技术大学研究生院学位论文 读过，那么该处理器将这个数据块变无效，并告诉该数据块的h o m e 结点。这样，这种写更 新方法可在一定程度上减少不必要的写更新。但它在处理适用于写无效协议的问题时要 先进行两次写更新并向数据块目录所在的结点回送一个表示自己c a c h e 中无相应数据块 的信息后( 即相当于三次广播的通讯量) ，才完成写无效协议一次写无效所做的工作，所以 这种方法实际运行起来效果并不理想，与纯写无效协议和纯写更新协议相比，其性能的提 高并不大。另外，使用这种方法，要有相应的跟踪、记录设备，增加了系统的硬件复杂 度。根据统计【2 ”，在实际应用中，适用于写无效协议的应用比适用于写更新协议的应用 多一些。 1 2 3 基于总线结构的监听协议和基于非总线结构的目录协议 按所基于的硬件来分，c a c h e 一致性可分为基于总线结构的监听协议和基于非总线结 构的目录协议。用总线结构来支持c a c h e 一致性协议有以下几个优点【7 】： i ) 总线的结构比较简单，易于实现。 2 ) 总线技术使用的时间较长，技术比较成熟。 3 ) 总线技术对一些方面的问题，如写无效c a c h e 协议中的无效信息的广播、写更新协 议中的共享信息的更新，解决得比较好。 但是，使用总线技术来互连多个微处理器也有不尽人意之处。其中最突出的问题就是 总线技术的可扩展性( s c a l a b i l i t y ) 较差，当通讯量变大时，总线成为系统的瓶颈。如图 1 1 所示，群a 和群b 是同一多处理器系统计算机中的共享不同主存信息的两组处理器( 同 一群中的处理器共享某一主存信息) ，当某一时刻，群a 内的s l 处理器和群b 内的s 2 处理 器都要利用总线向各自群内的其它处理器发消息时，由于总线一次只能响应一个请求，所 以必然有一个处理器的请求被推迟响应，从而降低了系统效率。 目前，微处理器的发展日新月异，在用高性能微处理器组成的计算机系统中，各微处 理器之间的通讯量将大大增加，总线带宽将是阻碍系统充分发挥其性能的主要因素之 一。当计算机系统中的微处理器个数增加时，总线带宽无法相应提高，使多个微处理器的 优势发挥不出来，降低了性能价格比。目前，人们虽然提出了总线分段、复用等技术，但 都是治标不治本，无法避免使总线成为系统的瓶颈。 为了提高处理器之间的通讯带宽，还有人提出使用多条总线的方案。在多总线方案中， 信息一般被分为几类，不同的信息使用不同的总线，从而减少每条总线的负载，提高通讯 速度。但是，总线的价格一般比较昂贵，且总线的带宽是固定的，当系统结点的数目较少时， 总线带宽被浪费，性能价格比不高；而当系统结点增多时，总线带宽又无法提高，仍有可 能成为系统的瓶颈。所以，多总线方案的效果也不十分理想。因此，在处理器数目较多的 大规模并行系统中都不采用总线来互连各结点。 里堕型兰垫查尘兰婴壅尘堕堂垡笙苎 图1 1 用总线互连各处理器 c p u 读请求命中 图1 2 监听协议的c a c h e 状态转化 c p b 读请求不命中 将读缺失放到总线 图1 _ 2 为一个简单的监听协议的c a c h e 状态变化图。在图中所示的协议中，c a c h e 块 有无效( i n v a l i d ) 、共享( s h a r e d ) 、修改( m o d i f y ) 三种状态。“无效”为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 口u 浓请求命叶1 图1 3目录协议的c a c h e 状态转化 c d u 读请求不命叶1 发读缺失消息 在非总线的微处理器互连技术中，c r o s s b a r 占有比较重要的地位。c r o s s b a r 的主要 思路就是在多微处理器系统中，每一对结点之间都有直接通路。这样，多对结点可同时进 行通讯，而无需象在总线结构中那样排队等待，依次通讯，从而大大减少了通讯的等待时 间，使通讯不再成为制约系统性能的瓶颈。当然，c r o s s b a r 也有缺点，主要是： 1 ) c r o s s b a r 的广播功能不太好，它虽可保证系统中每一对结点之间都有直接通路，但一 个结点一次只能和一个结点通讯，无法让一个结点同时与多个结点通讯。 2 ) 由于c r o s s b a r 为系统中的每对结点间都提供了通路，所以其结构相对复杂。另外，因 为每个结点都可向其它结点发送信息以及接收从其它结点来的信息，其控制结构也相对 复杂。 在不使用总线互连各处理器的系统中，无法象总线那样同时通知所有c a c h e 中有某 一数据块副本的处理器作废相应的c a c h e 块，所以需要一个专门记录数据块被共享情况 的结构一目录。图1 3 描述一个简单的目录协议中c a c h e 状态的变化，协议中关于c a c h e 块状态的定义与图1 2 中相同。 国防科学技术大学研究生院学位论文 1 3 存储一致性模型 存储一致性模型的作用是说明系统中各处理器应如何看待其中任何一个处理器所导 致的存储事件。任何c a c h e 一致性协议都必须考虑它所依托的存储一致性模型对存储访 问的限制。例如，当读请求在c a c h e 中命中时，如果不等前一个对相同数据的写操作完 成就返回数据，那么可能产生错误的结果。c a c h e 一致性协议提供传播数据最新值的机制， 而存储一致性模型则限制何时数据的最新值可以被传给某一处理器。因此，需要个高 效的存储一致性模型。存储一致性模型除了对c a c h e 一致性协议的选择、设计有较大的 影响外，还影响系统的可编程性和并行应用的可移植性等方面 1 , 9 - 1 4 1 。 存储一致性模型可以被看作是计算机软件和硬件之间的约定，它一方面说明一个程序 的主存操作执行是如何展现给程序员的；另一方面它说明了进行共享主存操作的规则。 目前主要有以下几种一致性模型【9 _ “l ： 1 3 1 顺序一致性模型( s e q u e n t i a lc o n s i s t e n c y ) 顺序一致性是最受程序员欢迎的编程模式，它定义一个正确的执行次序，按这个次序 执行的结果与所有处理器上的操作都按某种顺序的序列执行，且每个处理器的操作在该 序列中按程序说明的次序出现的情况下的执行结果相同。在顺序一致性中，正确性通过 要求一个进程只有等到它前面的对共享主存的操作已经“全局地完成”时才可以发送另 一个对共享主存的访问来保证。 顺序一致性对存储操作有严格的限制，许多在单处理器系统中可使用的技术，例如预 取、流水线、多发射、写缓冲都不能在顺序一致性中使用。 1 3 2 处理器一致性( p r o c e s s o rc o n s i s t e n c y ) 处理器一致性放松了顺序一致性对事件顺序的一些要求。它允许存操作后面的取操 作旁路掉存操作。例如，可以通过写缓冲旁路技术来消除一些r a w ( r e a da f t e rw r i t e ) 相关。处理器一致性比顺序一致性的条件要弱一些，所以可能导致与顺序一致性不同的 执行次序。 1 3 3 部分( 偏序) 存储一致性( p a r t i a ls t o r ec o n s i s t e n c y ) 部分存储一致性允许不相关的写操作乱序执行，从而放松了对写操作次序的一些限 制。从实现的观点来看，部分存储一致性允许流水线技术和写重叠技术，它不再限制必 须在一个写操作完成之后才能进行下一个写操作。只有导致写栅栏( f e n c e ) 的同步操作 才会导致停顿。 1 3 4 弱一致性( w e a kc o n s i s t e n c y ) 弱一致性通过在程序员和硬件设计者之间做出约定来放松对一些事件顺序的限制。 在支持弱一致性事件顺序的系统中，硬件应能区分同步访问和普通的共享主存的访问， 且程序员承担通过硬件可识别的同步原语来确保对可能导致一致性问题的访问之间互斥 的责任。弱一致性增加了以下对共享主存访问执行顺序的限制： 国防科学技术大学研究生院学位论文 a ：同步访问相互之间是遵从顺序一致性的。 b ：对其它所有处理器来说，在一个普通的存、取访问被允许执行之前，所有先前的 同步访问必须已经被执行，并且： c ：对其它所有处理器来说，在一个同步访问被允许执行之前，所有先前的普通存、 取访问必须已经被执行。 上面的条件允许个特定的处理器发出的主存访问在其它处理器看来是乱序的，从 而允许多个普通的访问被流水线化。 1 3 5 松弛一致性( r e l e a s ec o n s i s t e n c y ) 在松弛一致性系统中，同步访问被进一步分为a c q u i r e ( 获取) ，r e l e a s e ( 释放) 两个 操作。a c q u i r e 用来获取对一组共享空间的访问许可权；r e l e a s e 用来释放这个权力。松 弛一致性对存储器访问事件的顺序增加了下列限制： a ：同步访问之间遵从顺序一致性。 b ：对其它处理器而言，在一个普通存、取访问被允许执行之前，所有先前的a c q u i r e 访问必须完成，并且： c ：对其它处理器而言，在一个r e l e a s e 操作被允许执行之前，所有先前的普通存、 取操作必须完成。 在d a s h 这样的硬件分布共享主存系统中就采用了松弛一致性。 1 3 6 积极松弛一致性( e a g e r r e l e a s e c o n s i s t e n c y ) 在软件分布共享主存系统中，减少信息的数量是十分重要的。因此，在积极松弛一 致性中，对共享主存的写操作被缓存起来，直至r e l e a s e 操作。在r e l e a s e 操作时，所 有对同一目的地的写操作被合并成一个单独的信息。通过将写操作合并，而不是将它们 流水线化，消息的交换量被减少了很多们。 1 3 。7 惰性松弛一致性( l a z yr e l e a s ec o n s i s t e n c y ) 在惰性松弛一致性中，系统在r e l e a s e 操作时并不传播对共享数据的修改，而是直 到a c q u i r e 时才将缓存起来的修改传给申请被释放的锁的处理器。这样，惰性松弛一致