（电子科学与技术专业论文）x处理器存储一致性模型的研究与实现.pdf

国防科技大学研究生院学位论文 a b s t r a c t p a r a l l e la n dd i s t r i b u t e dc o m p u t i n ga r et h ed e v e l o p i n gt r e n d so fm o d e ms c i e n t i f i c c o m p u t i n g t h em u l t i p r o c e s s o ri se x c e l l e n ti nt h ef i e l d ，t h a t ss i n g l ep r o c e s s o rb e y o n d c o m p a r e b u ti nam u l t i p r o c e s s o rs y s t e m ，t h e r em a y b es e v e r a lp r o c e s s o r sh a v er e a dt h e s a m ed a t a a n dt h e no n ep r o c e s s o rw i l lw i r t ei t a tt h a tt i m e ，t h ec o p yo ft h ed a t ai nt h e c a c h eo fo t h e rp r o c e s s o r sw i l lb eo u to fd a t e 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 d t oi n s u r et h er i g h tp 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 es i t u a t i o n h o wt ok e e pd a t a c o n s i s t e n c yi nam u l t i p r o c e s s o rs y s t e mi so n eo f t h eh o t t e s tt o p i c si nt h ew o r l d s t u d yt h em e m o r yc o n s i s t e n c ym o d e li 1 1xm u l t i p r o c e s s o r ，a n dt h e nd e s i g nt h e l o a ds t o r eu n i tw h i c hs t r o n g l yc o r r e l a t e sw i t ht h em e m o r yc o n s i s t e n c ym o d l e ，t h a ti st h e m a i nt o p i co ft h i ss u b j e c t i nt h i s p a p e r ，w em a k ep r o f o u n da n a l y s i s o ns o m ec o n v e n t i o n a lm e m o r y c o n s i s t e n c ym o d e l sa n dt h e ns u m m a r i z et h e i ra d v a n t a g ea n dd i s a d v a n t a g e ，a sw e l la s t h es c o p eo fa p p l i c a t i o n i nt h i sb a s i s ，w ec h o o s et h ea p p r o p r i a t em e m o r yc o n s i s t e n c y m o d e la c c o r d i n gt ot h ef e a t u r eo ft h exm u l t i p r o c e s s o r t s om e m o r ym o d e l t h e n w ed e s i g nt h el o a ds t o r eu n i t ，i n c l u d i n gt h ed a t ac a c h e ，d a t at l b ，s t o r eb u f 托ra n dt h e i n t e r f a c ec i r c u i t f i n a l l y ，w ev e r i f yo u rd e s i g na n ds y n t h e s i z et h eu n i tw i t ht h ed e s i g n c o m p i l e r t h er e s u l ts h o w st h a ta l lt h e12 7t e s t i n gp r o c e d u r e sa r es u c c e s s f u l l ye x e c u t e d ， a n dt h eu n i tc a l lw o r ka tt h ef r e q u e n c yb e y o n d1g h z t h ed e s i g ni sw o n d e r f u l m yw o r ki sp a r to ft h ejo bo fr e s e a r c h i n ga n di m p l e m e n t i n gt h ex m u l t i p r o c e s s o r w h i c hb e l o n g st oas i g n i f i c a n tp r o j e c tt ot h en a t i o n t h ed e s i g nh a sa l r e a d yb e e nu s e di n t h ep r o j e c t k e yw o r d s ：m e m o r yc o n s i s t e n c ym o d e l ，t s o ，l o a ds t o r eu u n i t ，m u l t i p r o c e s s o r 第j i 页 国防科技大学研究生院学位论文 表目录 表2 1 各种一致性模型的比较1 9 表4 1d c a 操作功能表3 1 表4 2d t a 操作功能表3 2 表4 3d v a 操作功能表3 3 表4 - 3 真值表3 9 表4 ，4l o a dm i s sb u f f e r 数据格式4 2 表5 1 测试激励集5 0 表5 2 综合结果5 2 第1 页 国防科技火学研究生院学位论文 图目录 图1 1 集中式共享存储器多处理器基本结构2 图1 2 分布式存储器多处理器的基本结构3 图1 3 监听协议的c a c h e 状态转换图5 图1 4 目录协议的c a c h e 状态转换图6 图2 1 数据不一致产生过程9 图2 2 顺序一致性模型10 图2 3 处理器一致性模型1 2 图2 4 松弛一致性模型13 图2 5 条件( 1 ) 和条件( 2 ) 的使用18 图3 1x 处理器存储层次结构2 1 图3 2x 处理器内核结构2 2 图3 3x 处理器t s o 弱一致性模型2 3 图3 4 弱一致性程序模型2 4 图4 1 存取部件结构示意图2 6 图4 2 路组相联并行标识比较2 8 图4 3 数据c a c h e 块2 8 图4 4 数据c a c h e 的模块划分2 9 图4 5d c a 结构简图3 0 图4 6d t a 结构简图31 图4 7d v a 结构简图3 3 图4 8d t l b 结构简图3 4 图4 1 0d t l b 内部结构图3 5 图4 1 1 多项匹配产生信号3 7 图4 1 2 替换索引生成逻辑图一3 8 图4 1 3s t b 及其相关控制电路4 0 图4 1 4l o a dm i s s 处理逻辑4 l 图4 1 5 描述了p c x i f 的主要功能4 3 图4 16c p x 结构简图4 3 图4 17a s i 快速环和慢速环4 4 图4 18a s i 发送接口4 4 图4 19a s i 接收接口4 5 图4 2 0a s i 总线数据格式4 5 第1 i 页 国防科技大学研究生院学位论文 图5 1 芯片设计流程图4 6 图5 2 模块级测试结构图4 7 图5 3 作废向量产生波形图4 9 图5 4 作废向量产生波形图4 9 图5 5 部件级测试结构图5 0 图5 6 测试报告51 第l l i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：哮矿一 日期： 2 97 年z 月3 口日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名：荸冕 日期：2 童年，2 月岁口日 作者指导教师签名：日期：动og 年，z 月岁。日 国防科技大学研究生院学位论文 第一章绪论 1 1 课题背景 当今世界科技发展日新月异，人类对计算速度和计算规模的要求不断提高。 微电子技术的发展可使单芯片上集成更多的晶体管，使得单处理器获得更为复杂 的功能及更优的性能。2 0 0 7 年，i n t e l 公司在单片上集成的晶体管数量已达8 亿个； 2 0 1 0 年，这个数字将超过1 0 亿；到2 0 1 6 年，处理器将采用l1 纳米生产工艺，处 理器晶体管数量会达到1 2 8 0 亿个；预计到2 0 1 8 年，处理器将采用8 纳米生产工 艺，届时晶体管的数量将达到2 5 6 0 亿个。然而，由于芯片中信号的传播速度不可 能超过光速，芯片的工艺精度也不可能小于原子尺寸，单芯片处理器运算性能最 终将受限于芯片的速度极限和加工工艺极限。为了进一步提高处理器性能，传统 处理器设计中大多使用超标量( s u p e r s c a l a r ) 技术，主要利用程序的指令级并行性来 提高性能。但是单个程序的有限i l p ( i n s t r u c t i o n 1 e v e lp a r a l l e l i s m ) 导致了超标量处理 器的资源利用率不高，进一步增加指令发射宽度只会加重这种情况。此外，超标 量结构的实现复杂度随着规模的增加增长很快，因此超标量结构的进一步发展已 经相当困难。为了有效的利用单个芯片上不断增加的晶体管，进一步挖掘处理器 的并行性能，计算机体系结构研究者提出了多核结构。现代科学计算正在向并行 计算、分布式运算等方向发展，而多核处理器在这些方面有着单核处理器无法比 拟的优势，这就决定了多核处理器在未来微处理器领域的主导地位。研究表明， 在执行大规模的并行程序和多道程序时，相对于超标量处理器，多核处理器在性 能上有5 0 1 0 0 的提升【5 川。 微处理器迅速发展的同时，存储技术也在不断发展。存储器的速度在不断提 高，但其提高速度远不及微处理器，它们之间存在着较大的速度差距。资料显示， 当前最主要的内存d r a m 的带宽每年增长15 2 0 ，而速度每年仅增长7 t 2 1 。 这样，存储速度就成了计算机系统的瓶颈。为了缓和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 2 国内外研究现状 1 2 1 多处理机系统的组织方式 多处理器系统有多种组织方式【3 j 。我们可以将其分为共享主存结构和非共享主 存结构。共享主存结构对系统进行全局的统一编址，在某个处理器上运行的进程 可以直接访问本地节点以及系统中其它节点主存中的数据。非共享主存结构的多 处理器虽然也可以共享主存，但对于不在本地节点的主存是不能直接访问的，需 要软件辅助才能实现，因此访问延迟开销比较大。 多处理器系统还可以分成集中式共享存储器结构和分布式存储器结构 4 j 。其 中，集中式共享存储器结构又称作一致性访存系统( u m a ) 。在u m a 结构中，所有 处理器与主存之间的距离相同，因此访存操作延迟大致相同。u m a 结构又可以分 为并行向量处理机( p v v ) 和对称多处理器系统( s m p ) 。图1 1 是集中式共享存储器多 处理器结构示意图。 图1 1 集中式共享存储器多处理器基本结构i 叫 分布式存储器多处理器包括非一致性访存结构( n u m a ) 和无远程访存结构 ( n o r m a ) 。图1 2 是分布式存储器多处理器基本结构。 分布式多处理机系统由多个节点构成，每个结点可能是一个或多个处理器及 本地存储器。非本地节点的存储器成为远端存储器。分布式多处理器系统的存储 结构可以分为n o r m a ，非c a c h e 一致性n u m a ( n c c - n u m a ) ，c a c h e 一致性 n u m a ( c c - n u m a ) 以及c o m a 。其中，n o r m a 结构的存储器逻辑编址是相互独 立的，一个节点不能直接访问远端存储器。如果节点a 想访问节点b 中的数据块 m ，那么节点b 需要执行一次发送操作，节点a 则相应的执行一次接收操作。最 终数据块m 的值拷贝到节点a 中。另外的三种结构都有专用的硬件结构将系统中 所有存储器粘合成统一的地址空间，因此任何处理器都可以访问所有存储器。 第2 页 围防科技大学研究生院学位论文 n c c n u m a 结构的处理器系统允许将远端数据送入本地节点的寄存器中，但在数 据被调入后，不会在本地存储器以及c a c h e 中留下副本，也不会自动进行数据一致 性检测。c c - n u m a 结构的多处理器系统中，指令在将远端数据调入本地处理器 寄存器的同时，还将该数据块自动拷贝到本地节点中的远端c a c h e 中。远端c a c h e 用于存放远端数据，其数据不进入本地存储器。c o m a 系统中所有的本地存储器 都被当作c a c h e ，并按照c a c h e 来组织。指令在将远端数据块调入本地处理器寄存 器的同时，还将其自动拷贝到本地存储器。 处理器、，处理器、，处理器、，处理器 + c a c h e k + c a c h e + c a c h e + c a c h e 存储器hi oii1 竽储器hi oi l 存储器hi oii 存储器hi o 互联网络 图1 2 分布式存储器多处理器的基本结构【2 】 1 2 2 存储器一致性 高速缓存一致性确保了多个处理器所看到的存储器视图是一致的，但是它并 未说明存储器视图必须是怎样的一种一致性。事实上这种一致性是指一个被处理 器修改过的值，在何时必须被其它处理器看到。既然处理器之间是通过共享变量 来通信的，那么上述问题就归结为：一个处理器应该以何种次序来查看被别的处 理器写过的数据值才能保证一致性。查看的方法无非就是读操作，所以上述问题 变为：在不同的处理器对不同的单元进行读操作和写操作时，应该加上某种属性 才能确保一致性。由此引出了一致性模型。 存储一致性的定义经历了以硬件为中心和以程序员为中心两个阶段。经过 a d v e 和g h a r a c h o r l o o t s l 的发展，存储一致性模型已经非常成熟。随后v l v e ks m k a r 6 】 等人提出了l c 模型，并给出了该模型下的一种一致性协议形式。m a t e of f i o t7 】提 出了以计算为中心的一致性定义，给出了一种最弱的一致性模型。杨学军等人【8 】 提出了一种新的存储一致性模型框架s 3 c 框架。该框架通过同步点的概念来描 述不同模型中正确的存储访问事件顺序；通过一致性维护点的概念，对同一模型 的不同实现方式也能够进行区别和比较。结合s 3 c 框架，他们提出了一种以操作系 第3 页 答 纠 蓄 纠 答 叫 蓄 国防科技大学研究生院学位论文 统为中心的线程一致性模型，并针对以顺序一致性模型为代表的存储一致性模型 的正确实现进行了论述。 1 2 3 高速缓存一致性协议 高速缓存一致性和存储器一致性是互补的：高速缓存一致性定义了对同一个 存储器地址进行的读写操作行为，而存储器一致性定义了关于访问其他存储器地 址的读写操作行为。 高速缓存的引入带来了输入输出操作的一致性问题，这是因为从高速缓存得 到的存储器视图可能会从输入输出子系统得到的存储器视图不一样。在多处理器 中存在同样的问题，因为两个不同的处理器所保存的存储器视图是通过它们各自 的高速缓存得到的。般情况下，如果在一个存储系统中读取任何一个数据项的 返回结果都是最近写入的数值，那么就可以认为该存储器是一致的。具体来说就 是如果一个存储系统满足以下条件，那么认为该存储器系统是一致的： 【1 】处理器p 对地址x 的写操作后面紧跟着处理器p 对x 的读操作，而且在 这次读操作和写操作之间没有其他处理器对x 进行写操作，这时读操作 总是返回p 写入的数值。 【2 】在其他处理器对x 写操作后处理器p 对x 执行读操作，这两个操作之间 有足够的间隔而且没有其他对x 的写操作，这时读操作返回的是写入的数 值。 【3 】对同一个地址的写操作是串行执行的，也就是说，任何处理器对同一个地 址的两个写操作在所有处理器看来都有相同的顺序。例如，如果向同一个 地址中先后写入数值1 和数值2 ，处理器绝不会从该地址先读出2 再读出 1 。 用于维护多个处理器一致性的协议成为高速缓存一致性协议。实现高速缓存 一致性协议的关键在于跟踪所有共享数据块的状态。目前广泛采用的有两种协议 监听协议和目录协议，它们采用不同的技术跟踪共享数据。 在监听协议中，每个含有物理存储器的数据块副本的高速缓存还要保留该数 据块共享状态的副本。高速缓存通常放在共享存储总线上，所有的高速缓存控制 器对总线进行监视或监听，来确定它们是否含有总线上请求的数据块的副本。图 1 3 是一个简单的监听协议c a c h e 状态变化图。 最传统的监听方式是基于总线的协议，即使用一条或多条总线来广播消息。 每个内核都与总线相连，并且必须持续监视总线的状态以决定在这个缓存上的内 存拷贝是否被访问到。如果是这种情况，处理器将根据维持一致性的基本策略改 变该缓存块的状态。最基本的两种策略是写无效和写更新。写无效是将存储在高 第4 页 国防科技大学研究生院学位论文 速缓存上的内存块标记为无效，而写吏新则是当该内1 竽块被访问到时史新该块的 内容。这些基本策略都可以用来扩展更复杂的协议模式，例如m s i 及m s e i 。总之， 监听一致性协议很容易实现，但是由于共享带宽的限制，这种协议较之其他协议 的可扩展性相对差一些。基于网络的协议使用点到点的网络连接而非广播总线来 支持监听方式。这些协议可以使用一般的技术( 如网格或环) 来创建一个可扩展的片 上互联系统。这类系统的网络延时( 请求消息穿越网络的时间) 很长，而且这种网络 不能保证所有消息都以相同的顺序投递，有可能出现对同一地址的不同操作消息 可能以不同的顺序被不同的节点接收。缺少消息排序使得基于网络监听协议的设 计和有效性验证变得困难。 求命中 图1 3 监听协议的c a c h e 状态转换图【2 】 基于目录的协议使用分布式目录结构来存储缓存块的信息。在分布式方式下， 每个内存块的状态都被保存在一个中间位置。与基于监听的协议设计不同，这种 协议使用了目录存储结构以减少监听请求占用的总线流量。这种方法使消息只会 被传送到含有内存块拷贝的缓存中去，具有很好的扩展性，但是在中型规模的系 统中仍可以引发过载，而且目录本身就是一个复杂不易实现的结构。图1 4 是一个 简单的目录协议c a c h e 状态变化图。 处理器对某个共享的数据块进行写操作时，为了保证c a c h e 一致性，根据该处 理器是向系统中其它拥有该数据块副本的处理器发送变无效信息，使那些处理器 上的过时副本作废；还是同时更新系统中其它处理器上该数据块的副本，c a c h e 一 致性协议可分为写更新和写无效。它们的区别主要有以下几点： 【1 】同一处理器对同一字的多次写入，在写更新时，要广播多次，而写无效只 需一次； 【2 】在写多个字c a c h e 块时，写更新需要广播每个字，而写无效只需在写第一 第5 页 国防科技大学研究生院学何论文 个字时进行变无效操作； 【3 】从一个处理器写与另一个处理器读出这次写操作所写的内容之间的等待 时间上看，写更新小于写无效的等待时间。 在实际设计中，为了提高协议的适用范围，可以采用一种折中方案：系统开 始时先使用写更新协议，但各个处理器对自己c a c h e 中的数据块的情况做记录。如 果某个处理器发现自己c a c h e 中的某个数据块在两次被更新之间没有被自己读取 过，那么该处理器将这个数据块变无效，并通知该数据块的主节点。这种写更新 方法可在一定程度上减少不必要的写更新。但它在处理适用于写无效协议的问题 时要先进行两次写更新并向数据块目录所在的节点送回一个表示自己c a c h e 中无 相应数据块的信息后才完成写无效协议一次写无效所做的工作，因此这种方法实 际运行起来效果并不理想。据统计【9 】，在实际工程中，写无效协议的应用多于写更 新的应用。 图1 4 目录协议的e a c h e 状态转换图【2 】 1 3 课题研究目标、内容及意义 1 3 1 课题的研究目标和内容 求命中 本课题作为国家重大科研项目“x 处理器设计 的一部分，研究的主要目标 是探讨x 处理器中存储一致性模型及存取部件的设计与实现方案。重点描述了存 取部件的设计、实现与验证。 研究的内容包括： 1 】存储一致性模型的分析，详细描述了各种常见的致性模型的工作原理； 2 】结合x 处理器需求，提出合适的一致性模型； 第6 页 国防科技大学研究生院学位论文 【3 】设计并实现与一致性相关性很大的存取部件； 【4 】通过功能测试和性能测试，确保设计的正确性。 1 3 2 课题意义 多核处理器是一种高性能处理器，相比于传统的单核处理器，其在性能上有 很大的提高。但在多机系统中，多个处理器对同一存储块进行读写操作带来的一 致性问题非常复杂。确保高速缓存的致性是j 下确设计多核处理器的关键。而合 适的存储一致性模型能减少处理器访存时间，简化编译器的工作，提高计算机系 统的整体性能。 1 4 论文结构 论文在绪论中给出了课题研究的背景、意义、主要研究的内容。 第二章详细分析研究了各种常见的存储致性模型。 第三章针对x 处理器体系结构特点提出了适用于x 处理器的存储一致性模 型。 第四章详细设计了与一致性模型相关性很大的存储部件，包括数据c a c h e 、数 据t l b 、s t o r eb u f f e r 等模块。 第五章对设计进行了详细而全面的验证与综合，确保设计的正确性。 第六章对研究设计工作进行了总结，并对未来的工作进行了展望。 第7 页 国防科技大学研究生院学f 7 = 论文 第二章存储一致性模型的研究 2 1 引言 高速缓存一致性和存储器一致性是互补的：高速缓存一致性定义了对同一个 存储器地址进行的读写操作行为，而存储器一致性定义了关于访问其他存储器地 址的读写操作行为【2 1 1 1 2 3 】【2 4 j 。为了深入讨论存储一致性模型，首先回顾一下c a c h e 的一些基本概念和数据不一致产生的过程。 在由主存和高速缓存组成的存储器层次结构中，主存是多处理机共享，而高 速缓存是每个处理机私有的。主存和高速缓存都以块为单位进行划分，以映射的 方式来检索。映射的方法有：直接映射，组关联映射，区段关联映射和全相联映 射。在主存和高速缓存之间，是以块为单位进行搬送。主存中保存有各高速缓存 的副本，高速缓存的目录中，存放相应主存的块号及一些标志。通过对目录的检 索来寻找高速缓存中的数据。 当处理机发出一个访问主存地址时，如果包含这个地址在内的模块在高速缓 存中，则称之为命中，该高速缓存可以使用。如果不在高速缓存中，则称之为未 命中( 或c a c h e 失效) ，这时，必须把这个模块从主存搬到高速缓存中，叫做块搬送。 如果高速缓存己满，则必须按一定的置换算法挑出一个模块搬出高速缓存到主存， 这叫置换。置换算法有f i f o ，l r u 等。 高速缓存的写控制有两种：写直达方式和写回方式。写直达方式是指处理机 把数据写入高速缓存的同时，也写人主存。这种方式控制简单是一优点，但如果 写命令多，访问主存次数也会很多，这样就不能充分发挥高缓的优势。影响整个 系统的性能。写回方式是当高速缓存不命中时，把所有要置换出的块都写回主存 去，这又叫简单写回方式。而如果只把修改过的块，在被替换掉时写回主存，这 时就要在高速缓存目录中设一位标志，指示该模块是否被修改过。这种方式叫做 标志写回方式。简单写回方式会产生多余的块交换，使总交换时间变长，而标志 写回方式中，必须在高缓目录中增加标志位，检索开销增加。 在共享存储器系统中，多个处理器对共享存储器的同时读写使得存储操作的 行为复杂化。如图2 1 所示。( a ) ，主存中的模块x 分别放在处理机a 和b 的高速 缓存中。而后如( b ) 所示，处理机a 向自己的高速缓存的x 块中写数据，若采用写 直达方式，则处理机a 的高速缓存中的数m 和共享主存中的数m 都变成了n 。 然后( c ) 中处理机b 要从自己的高速缓存模块x 中读数，处理机读的散数应该是n ， 但自己高速缓存中模块x 的数值却没有变成n 。这样就产生了数据不一致问题。 在共享存储的多处理器系统中，存储空间的共享必然会引起存储访问冲突和 第8 页 国防科技大学研究生院学位论文 延迟，多处理器的结构必然会引起l 叫步问题。凶此，必须采墩适当的方式米保证 并行程序的正确执行。存储一致性模型和高速缓存一致性协议就是在这种背景下 产生的。存储一致性模型可以看作是系统和程序员之间的接口。一方面他向程序 员提供了一个存储系统的行为规范，指导并约束程序员如何书写正确的程序；另 一方面，一个好的存储一致性模型应当允许充分的硬件和编译优化技术，从而提 高系统的整体性能。所以它对系统设计者也有很大的影响。在使用高速缓存的系 统中，对共享数据的缓冲导致同一个存储单元的数据可能存在多个备份，高速缓 存一致性协议则是用来保证处理器访问到的备份是最新的数据。 x 圃 l x 圃x 固 x 圃 i x 圃x 圃 x 圃 x刖xj ( a ) c a c h e 处理机 ( b ) 写直达 ( c ) 发生不致 图2 1 数据不一致产生过程【2 】 存储一致性的定义如下【lo 】：一个存储器设计方案是一致的仅当一条l o a d 指 令返回的值是由最近一条对同一地址的s t o r e 指令所写的值。这个定义包括了存 储系统行为的两个重要方面：一致性协议和访存次序。这两个方面对于在共享存 储编程模型下写出正确的程序非常关键。一致性协议规定了一个读操作应该返回 什么样的值，而访存次序则规定了一个读操作应该在什么时候返回值。一致性协 议保证多个处理及对同一个物理位置有一个一致的看法，即大家在同一时刻对同 一物理位置能够读到相同的值。而访存事件则描述了各个处理机对不同的物理位 置的读写操作之间所应有的次序。 存储一致性模型的作用是说明系统中各处理器应如何看待其中任何一个处理 器所导致的存储事件。任何高速缓存一致性协议都必须考虑它所依托的存储一致 性模型对存储访问的限制。例如，当读请求在c a c h e 中命中时，如果不等前一个对 相同数据的写操作完成就返回数据，那么可能产生错误的结果。高速缓存一致性 协议提供传播数据最新数值的机制，而存储一致性模型则限制何时数据的最新值 可以被传给某一处理器。因此，需要一个高效的存储一致性模型。存储一致性模 型除了对高速缓存一致性协议的选择、设计有较大的影响外，还影响系统的可编 程性和并行应用的可移植性等方面【1 1 1 。 存储一致性模型可以被看作是计算机软件和硬件之间的约定，它一方面说明 一个程序的主存操作执行是如何展现给程序员的；另一方面它说明了进行共享主 存操作的规则。下面详细介绍目前常见的各种存储一致性模型 第9 页 国防科技大学研究生院学位论文 2 2 顺序一致性模型 存储一致性模型最直接的模型是顺序一致性模型【1 8 1 1 9 1 。它要求程序每次执行 的结果都是一样的，看起来就像每个处理器执行的访问操作始终按顺序进行。最 先提出顺序一致性模型的是l a m p o r t 忆j 。 顺序一致性的存储器要满足以下的条件： 【1 】每个进程的内部操作顺序是确定不变的； 【2 】假如所有的c p u 上的进程都对某一个存储单元执行操作，那么，它们的 操作顺序是确定的，即任一进程都可以感知到这些进程同样的操作顺序。 上述条件的含义是指，当多个进程分别在不同的机器上并发执行的时候，只 要所有的进程都保持同样的顺序访问存储器，那么，任何有效的交叉访问执行都 是可以接受的。在顺序一致性模型中，时间不再是影响一致性的因素，它关心的 是：所有进程都必须能够感受到一直的内存访问序列。我们可以把这一致性系 统看作如图2 1 所示的系统，它由单端口存储器和开关组成。单端口存储器一次能 提供一个操作，而开关则能在每个存储操作期间把存储器与多台处理机中的一台 连接在一起。开关从一台处理机到另一台处理机的切换次序确定了存储器访问操 作的全局次序。 图2 2 顺序一致性模型1 6 】 在一个有高速缓存的系统中，写操作的原子性很难保证。为了方便讨论写操 作非原子性问题，s c h e u r i c h 给出了以下定义【1 3 】： 1 】写操作w 相对于处理器p 执行完成：w 写入的值被p 观察到，p 随后对 该存储单元的读操作将不再返回旧的数据。 【2 】读操作r 相对于处理器p 执行完成：p 随后对该存储单元的写操作不再影 响r 返回的值。 【3 】存储操作o ( 读和写) 执行完成：o 相对于所有处理器执行完成。 【4 】写操作w 全局执行完成：w 执行完成。 第l o 页 国防科技大学研究生院学位论文 【5 】读操作r 全局执行完成：r 执行完成，并且若r 返叫的是写操作w 写入 的值，则w 执行完成。 s c h e u r i c h 给出了顺序一致性模型的一个充分条件： 【1 】所有的处理机以程序顺序发射存储器访问操作； 2 】当前存储操作全局执行完成之前，处理机不能发射任何其他的存储器访问 操作。 在一个支持高速缓存的系统中，仅当高速缓存一致性被维护上面的条件才是 充分条件。 研究人员还提出了其他实现顺序一致性的方法，允许处理器在前面的存储操 作全局执行完成之前发射后续的存储操作。c o l l i e r 证吲1 4 】若一个系统中的所有写 操作按相同的顺序相对于所有的处理器执行完成，则它等价于一个写操作原子执 行的系统。他提出了一种用环形网实现一致性的方案，将处理器连成环形，其中 一个处理器p 1 用来串行化所有的写操作。系统中执行写操作的处理器p 先发送写 请求到p l ，然后p 1 产生更新( 或作废) 消息并沿环发送，当p 收到自己出发的更 新( 或作废) 消息时，即使前一个写操作可能还没有全局执行完成，p 仍然可以开 始处理下一个存储操作。 2 3 处理器一致性模型 处理器一致性( p r o c e s s o rc o h e r e n c e ，p c ) 放松了顺序一致性对时间顺序的一些 要求。它允许写操作后面的读操作旁路掉写操作。例如，可以通过写缓冲旁路技 术来消除一些r a w 相关。处理器致性比顺序一致性的条件要弱一些，所以可以 导致与顺序一致性不同的执行次序。 处理器一致性模型最初由g o o d m a n i s 】提出。处理器一致性模型要求：同一处 理器发射的所有写操作以相同的顺序相对于系统中的所有处理器执行完毕，而不 同处理器发射的写操作可以以不同的顺序相对于系统中的处理器执行完成。 c h a r a c h h o r l o o 1 6 1 将处理器一致性模型精简表述为：一个系统是处理器一致的，当 1 】 任一读操作r 相对于某一处理器执行完成之前，所有在程序顺序中先于r 的读操 作都必须执行完成；【2 】任一写操作w 相对于某一处理器执行完成之前，所有在程 序顺序中先于w 的访存操作( 包括读操作和写操作) 都必须执行完成。在 c h a r a c h h o r l o o 定义的p c 中，在写操作被系列化之前，处理器不允许返回本处理器 写回缓冲中的值。实际上处理器一致性并没有要求这一约束。 处理器一致性模型不要求写操作的执行是原子的。图2 2 描述了p c 的抽象模 型和程序顺序约束。模型将存储器建模成为多个拷贝，每个处理器拥有整个存储 器的一个拷贝。这样的模型可以方便地讨论写操作的非原子性问题。在多拷贝存 第1 1 页 国防科技大学研究生院学位论文 储器模型卜，我们需要扩展读、写操作的概念：读操作返凹发射该操作的处理器 对应的存储器拷贝中的最新值，我们把读操作r 表述为一个子操作r ( i ) ( i 是发射 r 的处理器的编号) ：写操作被分成w ( 1 ) ，w ( 2 ) w ( n ) 个子操作( n 是处理器的个数) ， 子操作w ( i ) ( i _ 1 ，n ) 更新处理器i 的存储器拷贝。为了讨论非原子性写操作，必 须引入一致性约束的概念。 存储操作0 1 和0 2 满足一致性约束当且仅当：若0 1 和0 2 是对同一存储单元 的存储操作，且有i ( i = l ，n ) 使得o l ( i ) 先于0 2 ( i ) 执行完成，则对任意0 1 0 ) 和 0 2 ( j ) ( o = l ，n ) ，0 1 0 ) 先于0 2 ( j ) 执行完成。可见，一致性约束要求对同一存储单元 的两个写操作按相同的顺序更新该存储单元的多个拷贝。 图2 3 处理器一致性模型【6 】 c o l l i e r 1 4 j 证明：若一个系统中的所有写操作按相同的顺序相对于所有处理器执 行完成，则它等价于一个写操作原子执行的系统。所以，要求写操作原子执行就 要求任意两个处理器发射的两个写操作都满足一致性约束；p c 中仅要求同一处理 器发射的写操作满足一致性约束。图2 3 描述p c 的程序顺序约束时使用了双竖线， 表示写操作的执行是非原子的，双竖线前后的两个操作的执行满足一致性约束。 在基于更新( 或作废) 的高速缓存一致性协议中，实现写操作的原子性需要 以很大的性能损失为代价。在p c 模型中，写操作可以非原子地执行，这使得p c 模型下基于更新( 或作废) 的高速缓存一致性在性能提升的同时降低了实现难度。 处理器一致性模型在顺序一致性模型的基础上放松了读操作和其前面的写操 作的程序顺序，它的值约束是t s o ( t o t a ls t o r eo r d e r ) 值约束的扩展。处理器一 致性模型是一种比顺序一致性模型弱的模型，因此，在顺序一致性模型中正确执 行的程序在处理器一致性模型中执行结果可能出乎程序员的意料。然而g o o d m a n 声称在绝大部分应用中，处理器一致性模型和顺序一致性模型能给出相同的结果。 明确地说，这些应用依赖于程序员用显式的同步机制而不是存储系统保证严格的 事件顺序。 第1 2 页 国防科技大学研究生院学位论文 2 4 弱一致性模型 并行程序中的两个存储操作只有当它们访问同一存储单元并且至少有一个是 写操作才会冲突，我们只需要保证并行程序中的所有冲突访问执行的顺序性。因 此，我们可以选择性地对程序的执行进行优化而不违背顺序一致性。 弱一致性通过在程序员和硬件设计者之间做出约定来放松对一些事件顺序的 限制。在支持弱一致性事件顺序的系统中，硬件应能区分同步访问和普通的共享 主存访问，且程序员承担通过硬件可识别的同步原语来确保对可能导致一致性问 题的访问之间互斥的责任【1 7 】【2 5 1 。 弱一致性模型对共享主存访问执行顺序增加了如下限制： 【1 同步访问相互之间是遵从顺序一致性的； 【2 】对其它所有处理器来说，在一个普通的读、写操作被允许执行之前，所有 先前的同步访问必须已经被执行，并且： 【3 】对其它所有处理器来说，在一个同步访问被允许执行之前，所有先前的普 通读、写操作必须已经被执行。 同处理器一致性模型一样，弱一致性模型也将存储器建模成多个备份，不同 的是在弱一致性模型中，读操作不能返回写缓冲中的值。 2 5 松弛一致性模型 松弛一致性模型是由g h a r a c h o r l o o 等人提出来洲1 6 1 。在松弛一致性系统中， 同步访问被进一步分为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 c q u i r e 和r e l e a s e 的那些顺序要求。 图2 4 描述了松弛一致性的访存操作。 s h a r e da c c e s s c o m p e t i n g n o n - c o m p e t i n g s y s c h r o n i z a t i o nn o n s y s c h r o n i z a t i o n 、 a c q u i r e r e l e a s e 图2 4 松弛一致性模型【1 0 】 第1 3 页 国防科技大学研究生院学位论文 【1 】在任一普通访存操作被允许执行之前，所有在同一处理机中先于这一访存 操作的获取操作a c q u i r e 都己完成； 2 】在任一释放操作r e l e a s e 被允许执行之前，所有在同一处理机中先于这一 r e l e a s e 的普通访存操作都已完成； 【3 】同步操作的执行满足处理机一致性。 2 6l c 一致性模型 19 9 3 年，g u a n g r g a o 提出了偏序关系的l c ( l o c a t i o nc o n s i s t e n c y ，l c ) 存 储一致性模型【6 】【2 0 】【2 6 1 ，它不依赖于“存储一致性假定 ，摆脱了对执行顺序的强 制性约束，是一种可伸缩且简单的存储模型。