（计算机科学与技术专业论文）多核处理器中cache一致性协议研究和实现.pdf

国防科学技术大学研究生院学位论文 摘要 集成电路材料和工艺的发展使得在单芯片上集成多个处理器核成为可能。随着芯片上 晶体管密度和线延迟的增加，设计者需要寻求一种新的方式来有效利用芯片上数量巨大的 晶体管。这就产生了单片多处理器。 单片多处理器芯片中，各个处理器核对共享数据的访问必然引起存储访问冲突。存储 一致性模型是用户和硬件之间的一个协议，规定了程序中访存操作的执行约束，影响程序 设计模式和系统的性能。单片多处理器中，各个处理器核有自己私有的高速缓存。在一个 有高速缓存的系统中，高速缓存一致性是系统正确性的先决条件，是支持整个存储一致性 模型实现的重要部分。为了提高性能，当前的高速缓存一致性协议允许将事务分成多个阶 段，支持多个请求同时并存。这就引入了一些临时状态，使得一致性协议的实现和描述变 复杂。 本文分析了存储一致性模型对高速缓存一致性模型实现的约束，给出了侦听协议的一 种满足顺序一致性模型的实现方案。介绍了m s i 协议和m e s i 协议的实现。提出了侦听代 理不同时处理同事务情况下m e s l 协议读失效的一种“半完全区分方法”并证明了它的 可行性。设计了一个c 语言高速缓存模拟器，针对数字信号处理应用对本文的一致性方案 进行评测。对程序运行的统计信息进行分析提出有效地优化单片多处理器系统设计的几个 方向和原则。 【关键字】单片多处理器， 存储一致性，高速缓存一致性， 侦听协议，模拟器 国防科学技术大学研究生院学位论文 a b s t r a c t a d v a n c e si ni cp r o c e s s i ga l l o wf o rm o r e l i c m p r o c e s s o rd e s i g n 叩t i o n s t h em c r e a s i n g g a t ed e l l s i t ya n dc o s to f w i r e si f ia d v a n c e di n t e g r a t e dc i r c u i tt e c l l l l o l o g i e sr e q u i r ct 1 1 a t 、v e1 0 0 kf o r n e ww a y st ou s et l l e i rc a p a b i l i t i e se 腩c t i v e ly s oc o m e sc m p _ i nac h j pm u l t i p r o c e s s o rs y s t c m ，m u l t i p l ec p u sm a ys j m u l t 觚e o u s l yr c a da 1 1 dw r i t et h e s a m em e m o r yl o c a t i o n s am 锄o r ym o d e lf o ras h 盯e d _ m e m o r ys y s t e mi sa i l 盯c l l i t e c t u r a j 印e c i n c a t i o no f h o wm 啪o r y 叩e r a 时o n so fap r o g r a m 、i l la p p e 甜t oe x e c u t et o 血ep r o g r a l l l i i l c r - t h em e m o r ym o d e l 赶r e c t sn l ee 船eo fp r o g m m m i n ga 1 1 d 廿l ep e r f o m l a n c eo ft 1 1 es y s t e ma sw e l l i nac h i pm u l t i p r o c e s s o rs y s t e m ，e a c hc p uc o r eh a si t so w nc a c h e c a c h ec o h e r e n c ei sa p r e r e q u i s i t ef o ra c h j e v i n gc o r r e c tm e m o r yb e ha _ v i o rms y s t e m st l l a ta l l o wt l l ec a c l l i n go fs h a r e d d a t a ni sa l li m p o r t 趴tp a r to ft l l eo v e r a l ls c h e m ef o rs u p p o r t i n gam e m o 珂m o d e l t be n a b l e h i g h e rp e o n a n c e ，c u r r e n tc a c h ec o h e r e n c ep r o t o c o l sa l l o wt r a n s a c t i o n st ob es p l i ta n da l l o w m l l l t i p l eo u t s t a l l d i n gr e q u e s t s t l l i sc o m p l i c a t e sm ei m p l 啪e n t a t i o no fc o h 凹e n c ep r o t o c o lb y i n t r c d u c i n gt r a i l s i e l l ts t a t e s ，嬲t h es p e c i f i c a t i o no f 廿l ep r o t o c 0 1 i i lt l l i s p r o j e c t ，w ea d d r e s st h ec o n s 删n t st 0t l l ei n l p l e m e n t a t i o no fc a c h ec o h e r e n c e i m p o s e db yam e m o r ym o d e l as c h e m ew h i c hs a t i s f i e sas e q u e n t i a l l yc o i l s i s t e n c ym e m o r y m o d e li sg i v e nf - o rs n o o p i n gp m t o c o l s t h ei m p l e m e n t a t i o n so fm s i 锄dm e s ia r ei i l 仃o d u c e d 趾da i l o n 一向l ld i “s i o n ”t 0p a r t i t i o nt 1 1 er e a dm i s s 证t l l ec 嬲et h a tm e s s a g ei s1 1 0 ts e r v e db ya l l c p u ss i m l l l t a n e o u s l yi sp r o p o da i l dp r o v e dt ob ef e 船i b l e ac a c h es i m u l a t o rw r i t t e ni l lc l a n g l l ei sp r e p a r e d ，a n ds o m ed s pp r o 舯m sw e r ee x e c u t e dt oe s t i m a t e 伽ei l i l p l e m e 雠m 蚰o f t l l e p m t o c 0 1 b 舔e do nm ea n a l y s i so f t l l es 诅t i s t i c so b t a i n e dt l l r o u 曲也er u n so f t l l ep r o 龋衄s ，s o m e d i r e c t i o n so ri n s 仇l c t i o n sw l l i c hm a y o 砸m i z e t 1 1 ed e s i 印o f c m ps y s t e ma r e 西v e l l 【k e y w o r d s 】c h - pm u l t i p h 坶髂s o bm e m o r y n s i s 钯n c y ， c a c h ec o h e 件n c e ， 、 s o o p i n gp r o t o c o i ， s i m u l a t o r 国防科学技术大学研究生院学位论文 图目录 图1 顺序一致性模型中的程序5 图2 顺序一致性v s 高速缓存一致性6 图3 顺序一致性模型和程序约束8 图4p c 模型及其程序约束9 图5w o 模型及其程序约束。lo 图6r c 模型及其程序约束1 1 图7d r f ov sw o 1 2 图8 几种存储一致性模型的性质一1 6 图9 目录结构18 图1 0m s i 协议状态转化图2 0 图1 lm e s i 协议状态转化图2 1 图1 2l c 模型中的高速缓存一致性协议2 3 图1 3l c 模型v sr c 模型2 4 图1 4l c 模型与边界不确定性2 5 图1 5 有限缓冲死锁问题2 6 图1 6 基本监听一致性系统中节点结构2 9 图1 7 状态扩展后的m e s i 协议3 l 图1 8 优化高速缓存一致性协议实现方案系统结构3 2 图1 9m e s i 协议状态转化图3 6 图2 0 模拟器中单个节点结构图4 5 图2 1 存储操作执行流程4 7 图2 2 测试程序一矩阵乘法4 9 图2 3 测试程序分解后的矩阵乘法4 9 图2 41 2 3 和1 2 & 3 方式下取指导致的存储器访问的间隔5 3 图2 5 访存密集度模式5 3 图2 61 2 3 和1 2 3 方式下存储器访问的间隔5 4 图2 7 增加的存储操作产生的频度5 4 图2 8 不同模时下串行程序执行时间比较5 6 图2 9 不同模时下矩阵乘法执行时间比较5 7 图3 0 串行程序执行是网络使用状况统计5 7 图3 1 矩阵乘法程序执行时网络使用状况的统计5 7 国防科学技术大学研究生院学位论文 表目录 表1 使用到一些符号及其意义一13 表2m s i 协议的状态及其描述3 3 表3m s i 协议中高速缓存控制器的动作及其描述3 3 表4m s i 协议的状态转化3 4 表5 目录的动作及其描述3 5 表6 存储器块的状态转化3 5 表7m e s i 协议的状态转化3 7 表8m e s i 协议中存储器块的状态转化3 7 表9 状态推算表3 9 表1 0 数据不共享程序中高速缓存行的状态转化3 9 表1 1 串行程序在多核处理器上的执行统计5 0 袁1 2 矩阵乘法在多和处理器上的执行统计51 表1 3 一致性导致的读写操作统计5 2 表1 4 存储延时为1 0 时串行程序在不同方式下的执行时间5 5 表1 5 存储延时为1 0 时矩阵乘法在不同方式下的执行时间5 5 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：垒趑丛理墨主鲤= 塾性选邀盈塞狸塞理 学位论文作者签名：盘至望日期：。l 。f 年t 2 月8 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 垒挂赴堡墨主叁婴垦二熬性垃达珏堑狸塞理 学位论文作者签名： 酲垒盟 作者指导教师签名：三茎主丘 日期：如0 5 年f 2 月8 日 日期：j _ 年，二月，日 国防科学技术大学研究生院学位论文 第一章绪论 1 1 课题背景和意义 微电子工艺的发展使得单芯片可以集成更多的晶体管。预计2 0 l o 年前后，单片能够 集成1 0 亿个晶体管，可以在芯片中集成更为复杂的功能。随着芯片上晶体管密度和线延 迟的增加，设计者需要寻求一种新的方式来有效利用芯片上数量巨大的晶体管。多发射超 标量处理器中，动态发射机制实现复杂，寄存器文件大小随发射带宽的平方正比增长，这 必将使得处理器的时钟频率受到很大限制。相比之下，一个由几个结构简单的处理器核构 成的，可以在面积大致相同的芯片上实现的单片多处理器会容易实现，并且由于部件的局 部性较好，它可以有更高的时钟频率。k u 出e0 1 u k o t i l n 等人【l h 研究表明：执行串行程序时， 多发射超标量处理器的性能比单片多处理器性能高3 0 ；执行细粒度线程级并行程序时， 单片多处理器能够利用程序的并行性，即使在相同的时钟频率下，单片多处理器性能也比 多发射超标量处理器性能高1 0 。预计在单片多处理器条件下，加入由于功能单元局部性 带来的钟频率提高的因素，执行大规模的并行程序和多道程序时，单片多处理器的性能将 会比多发射超标量处理器性能高5 0 一1 0 0 。在数字信号处理领域，应用程序的特征决 定了单片多处理器技术具有广阔的前景。 单片多处理器应用前景广阔。在许多高性能嵌入式的应用场合，微处理器实际上用作 专门用途的后台高性能计算装置，如t i l e 结构的算法加速部件、多核结构的数字信号处理 器。作为3 g 基础的多模软件无线电，对信号处理的能力需求达到1 0 0 g 口s 以上，短期内 单核数字信号处理器难于胜任，非常需要开发出多核高性能微处理器来解决这些应用。随 着我国集成电路实现水平的不断提升，加上我国在计算机体系结构和多处理机技术方面多 年积累，融合多处理器体系结构技术和超大规模集成电路实现技术的s o c 芯片将为我们赶 超世界先进水平带来契机。 单片多处理器芯片中各个处理器核通过共享某一级缓存进行通讯，需要什么样的存储 模型提供合理高效的编程模式，需要什么样的一致性维护机制保证程序执行的正确性，如 何高效地实现一致性都成为设计过程中的重要问题。本文将研究单片多处理器中高速缓存 一致性协议及其实现，通过模拟的方法对高速缓存一致性实现方案进行性能评测。 1 。2 1 高性能处理器发展概述 1 2 相关研究综述 高性能微处理器在经历了c i s c 、r j s c 的发展过程之后，已过渡到优化超标量和新型 v l l w 结构。通过提高软硬件复杂度，解决了单线程应用指令级并行性问题。下一步则是 向加速单线程应用和加速多线程应用两个方向发展。加速单线程应用沿袭传统的指令级并 行方法，通过进一步提高复杂度来提高性能。其目标在于进一步挖掘单个应用内在的指令 级并行性。目前正在开发的这类处理器有可同时发射1 6 3 2 条指令的先进超标量处理器、 采用激进推测策略的超级推测处理器、增强取指和转移预测效果的踪迹高速缓存处理器和 多标量处理器等。它们的共同之处包括：增加可以同时执行的指令数，芯片内集成多级大 第1 页 国防科学技术大学研究生院学位论文 容量缓存，显著提高内存带宽，强化转移预测功能，提高对乱序执行( o u t o f - o r d e r ) 的支 持，增加多媒体指令和专用电路，等等。但由于超标量技术越来越向复杂化方向发展，多 功能部件的控制复杂度成平方关系增长，这大大限制了更高指令级并行性和资源利用率的 开发，所以提高性能的潜力很快就会达到极限。加速多线程应用是通过开发线程进程级 并行性来提高性能的方法。这类处理器的典型代表是同时多线程( s i i t i u l t a l l e o u s m u l t i 蛆m a d i n g ，简称s m t ) 处理器和单芯片多处理器( c h i pm u l t i p m c e s s o r ，简称c m p ) 。 s m t 可通过复制处理器上的结构状态，让同一个处理器上的多个线程同步执行并共享处理 器的执行资源，可最大限度地实现宽发射、乱序执行的超标量处理，提高处理器运算部件 的利用率，缓和由于数据相关或高速缓存未命中带来的访问内存延时。当没有多个线程可 用时，s m t 处理器几乎和传统的宽发射超标量处理器一样。s m t 最具吸引力的是只需小 规模改变处理器核心的设计，几乎不用增加额外的成本就可以显著地提升效能。这对于桌 面低端系统来说无疑十分具有吸引力。i n t e l 从3 0 6 g h zp e n t i l l i n4 开始，所有处理器都将 支持s m t 技术。c m p 是由美国斯坦福大学提出的，其思想是将大规模并行处理器中的s m p ( 对称多处理器) 集成到同一芯片内，各个处理器并行执行不同的进程。与c m p 比较，s m t 处理器结构的灵活性比较突出。但是，当半导体工艺进入0 1 8 微米以后，线延时已经超过 了门延迟，要求微处理器的设计通过划分许多规模更小、局部性更好的基本单元结构来进 行。相比之下，由于c m p 结构已经被划分成多个处理器核来设计，每个核都比较简单， 有利于优化设计，因此更有发展前途。目前，i b m 的p o w e r4 芯片和s u n 的m a j c 5 2 0 0 芯片都采用了c m p 结构，并且i n t e l 和a m d 的新型处理器也将融入c m p 结构。多核处理 器可以在处理器内部共享缓存，提高缓存利用率，同时简化多处理器系统设计的复杂度。 多线程技术则可以为高速的运算核心准备更多的待处理数据，减少运算核心的闲置时问。 多核多线程设计的处理器在运算性能和性能价格比方面都非常出色。从各大芯片制造商的 开发计划看，这两种技术走向融合是处理器发展的一种趋势。 从7 0 年代x k o n g 的s y s t o l i c 阵列v l s i 单元，到9 0 年代中商用并行多核d s p t 1 3 2 0 c 8 0 ，单片多微处理器技术有了一定的发展。1 9 9 7 年s 诅n f o r d 大学研究的h y d m ，在 单芯片上集成了4 个m 口s 微处理器，每个拥有独立的一级数据和指令高速缓存，所有处 理器共享二级高速缓存。采用了线程级前瞻技术，更好的利用芯片资源。m r rr a w 片上集 成了1 6 片简单的m s c “瓦片”( t i l e ) ，瓦片之间通过二维的动态可重构m e s h 网络互连， 并且该互连结构为编译器可见，编译器可以控制数据在t i l e 之间的传递。因此，r a w 处理 器可以高效支持多种类型的应用程序：s e v c r 、科学计算、流等。美国t i 公司推出两款基 于o m a p 2 架构的器件o m a p 2 4 1 0 与o m a p 2 4 2 0 处理器，集成了a r m l l 核、t i 可编程 d s p 、2 d 3 d 图像加速器、最先进的d m a 控制器等。 1 2 2 存储一致性模型相关研究 要让程序产生期望的结果，程序员需要对程序中的存储操作的语义有一个概念性的模 型。由此引出了存储一致性模型，它定义了允许的存取访问顺序的集合，是用户和硬件之 间的一个合同或协议。即硬件提供给用户一个界面告诉他什么是允许的，什么是不允许的， 而将底层的具体实现对用户屏蔽起来。存储一致性的问题是伴随着多处理器时代的来临而 出现的，它对系统的正确性、性能以及程序的复杂性都有重要的影响。 存储一致性模型的发展经历了从硬件或系统为中心( h a r d w a r c c e n 廿i c ) 的一致性定义、程 序员为中心( p r o g r 锄m e r - c e n t r i c ) 的一致性定义两个阶段。以g h a r a c h o r l o o 及a d v e 的博 第2 页 国防科学技术大学研究生院学位论文 士论文【8 】为标志，存储器一致性模型已经非常成熟。随后g u a n gr g a o l l 埘提出的一种不 依赖于一致性假定( s c d e t i v e d ) 存储一致性模型一l c 模型，并给出了该模型下的一种一 致性协议形式，为存储一致性的研究提供了开阔的思路。m a t t e of r i g o 【j 刮的硕士论文中提出 了计算为中心( c o m p u 扭t i o n - c e n c r i c 舶m e 、v o r k ) 一致性定义，这中定义很容易抽象出一致 性模型的主要特征，m a t t e of r i g o 给出一种最弱的、合理的存储一致性模型。胡伟武p j 等人 提出存储一致性的一种新的框架，这种框架下，我们可以方便地讨论了程序正确性和存储 一致性实现正确性等问题。戴华东【10 】等人将系统同步事件抽象成虚拟的同步访存操作，提 出了基于同步点和一致性维护点的存储模型框架一s c 框架，并提出了线程一致性模型。 1 2 3 高速缓存一致性协议相关研究 在一个允许缓冲共享数据的系统中，同一主存单元的数据可能在多个高速缓存中有备 份。高速缓存一致性研究的就是同一主存单元的多个备份的一致性问题。即如何让多个备 份保持最新的数据。 常见的高速缓存一致性协议分为监听和目录协议两种。监听协议要求系统中所有处理 机都能观察到存储器正在进行的事务活动。如果总线事务破坏了本地高速缓存中数据的一 致性状态，那么高速缓存的控制器就应采取相应的动作使本地拷贝无效。总线是一种廉价 而有效的广播工具，常用于实现监听协议。但总线是一种独占性资源，可伸缩性有限。总 线延迟受仲裁、总线长度和总线阻抗等因素的影响，随处理机数目的增加而增加。可扩展 的多处理机系统用点对点的短线直接地实现处理机互连或用多级网络实现处理机互连。与 采用总线连接的情况不同，这些网络的频宽随系统中处理机数目的增加而增加。然而这些 网络没有方便的监听机制，而且也不提供有效的广播功能。这类系统常采用目录协议。 在侦听协议设计中，主要有两种设计选择：是写直达高速缓存，还是写回高速缓存： 是写无效w i ( 、h t e i n v a i i d a t e ) ，还是写更新w u ( w r i t e u p d a t e ) 协议。广泛使用的 写无效协议有m s i 、m e s i 等；广泛使用的写更新有d r a g o n 等。描述一致性协议的抽象状 态转化图是简单的，但在实现的层次上会出现很多微妙的问题。抽象层的一致性协议被描 述为一个有限状态机，本地高速缓存行的状态在本地事件以及监听事件的控制下进行状态 转化。状态这转化过程中可能伴随一个或多个原子事务，状态更新发生在事务处理结束之 后。每个事务的处理常常由多个系统部件的多个动作构成。这些部件包括高速缓存控制器、 目录控制器、处理器间的互联网络，它们可能跨越多个处理器。这些事务的原子性很难保 证。允许多个未完成的操作同时执行，而不是等待一个操作完成之后才开始一个新的操作， 从而提高了效率。但是这样做，也使得事件间会发生许多复杂的交互，实现复杂度提升， 正确性可能被破坏。高速缓存一致性协议在实现层可能使用不同于抽象层的协议描述形式 以提供充分的实现和验证细节。 1 3 课题工作与研究内容 课题结合单片多处理器自身的特点，研究单片多处理器片内高速缓存一致性问题。本 文首先从多个角度探讨了存储一致性模型，研究不同存储一致性模型下的高速缓存一致性 协议。课题重点讨论了高速缓存一致性协议的优化实现，给出了侦听协议的一种满足顺序 一致性模型的实现方案，介绍该方案下m s i 协议和m e s i 协议的实现，对该实现方案的正 确性、硬件支持、性能作了详细的分析和评价。为了提高性能，方案中各个侦听代理并不 第3 页 国防科学技术大学研究生院学位论文 同时处理同一个一致性事件。课题详细讨论了这种情况下m e s i 协议中读失效的区分问题。 给出了一种半完全区分方法”并证明了它的可行性。课题设计实现了一个多核环境下的 高速缓存c 语言模拟器，模拟器与课题组里的s m t 多核d s p 模拟器相结合，模拟运行1 1 c 6 2 的测试程序，评价优化实现的m s i 和m e s i 协议的性能。 1 4 本文结构 本文组织如下： 第一章，首先说明了课题的研究背景及意义，然后介绍国内外一些相关研究的基础， 概括本课题工作和研究内容，最后给出了论文的组织结构。 第二章，高速缓存一致性协议和存储器一致性模型是密切相关的。一致性协议的充分 条件是顺序存储器一致性模型充分条件的子集。研究人员希望找到一种更松弛的，合理的 存储一致性模型，放松对存储操作顺序的要求，并居于它发现新的高速缓存一致性协议， 适应可扩展和高性能的要求。本章阐述存储一致性的概念及其与高速缓存的密切关系，分 析不同一致性模型对高速缓存一致性的约束。从多个角度介绍几种有研究价值的存储一致 性模型。 第三章，首先介绍高速缓存致性的相关概念和广泛使用的几种高速缓存一致性协议 及其分类，在此基础上重点介绍探讨居于侦听的高速缓存一致性协议的实现，给出了侦听 协议的一种满足顺序一致性模型的实现方案，介绍该方案下m s i 协议和m e s i 协议的实现， 对该实现方案的正确性、硬件支持、性能作了详细的分析和评价。 第四章，为评测前面m s i 和m e s i 协议优化实现方法的性能本课题设计实现了一个高 速缓存模拟器，本章首先简单介绍模拟器的相关知识，在此基础上介绍本课题设计实现的 高速缓存模拟器的体系结构及实现要点。通过模拟执行t i 的一组测试程序，对按前面章节 介绍的高速缓存一致性协议实现方案实现的m s i 协议和m e s i 协议进行性能评测，给出对 测试结果的分析，得出结论。 第五章，概括全文，总结课题所做的工作及研究成果，并展望未来。 第4 页 国防科学技术大学研究生院学位论文 第二章存储一致性模型 2 1 存储一致性模型与高速缓存一致性 在共享存储器系统中，多个处理器对共享存储器的同时读写使得存储操作的行为复杂 化。在图l 中，代码( a ) 展示了处理器p 1 和p 2 的一种生产者一消费者关系：处理器p 1 对 x 和y 进行写操作并在操作结束后设置标志n a g ，而处理器p 2 等n a g 被设置后对x 和y 进行读操作，希望能够读取x 和y 的新值。代码基于这样的假设：在p 2 对n a g 的读操作 返回f l a g 被p l 设置的新值之后，p 2 对x 和y 的读操作也将返回x 和y 的新值；代码( b ) 是d e k k e r 用于实现临界区的代码，代码基于这样的假设：如果p 1 对y 的读操作发生在 p 2 对y 的写操作之前( 即p 1 对y 的读操作返回0 ) ，那么p 1 对x 的写操作也发生在p 2 对y 的读操作之前( p 2 对x 的读操作返回1 ) 。同样，如果p 2 对x 的读操作返回0 ，p 1 对y 的读操作将返回1 。也就是说p 1 和p 2 的读操作不可能都返回o 。一些在单处理器中 正常不过的优化可能使得这些假设被破坏。例如，对指令顺序的动态或者静态调度、使用 写回缓冲旁路写后读、为对存储单元分配寄存器等都将导致代码中的两个读操作可能同 时返回0 ；即使在不对指令进行调度，不使用写缓冲的系统中，如果系统有多个存储模块， 重叠执行写操作导致写操作的原子性很难保证。代码( a ) 在这样的系统中执行时，有可能 出现p 2 观察到n a g 的新值的时候还没有观察到x 和y 的新值。 1 n n i a l l y x 龠y 孤n a g 置0 p 1 x = 1 4 w h i i e ( a a g ! = 1 ) ： y = 2 6r i 嚣x n a g l 2 = y i a ) i n 谐a l l y x = y 盅o ，l j p 2 x 堵ly 罩l r i yr 2 = x 图1 顺序一致性模型中的程序 事实上，无论是物理上共享还是逻辑上共享，在共享存储的多处理器系统中，存储空 间的共享必然会引起存储访问冲突和延迟，多处理器的结构必然会引起同步问题。因此， 必须采取适当的方式来保证并行程序的正确执行。存储一致性模型和高速缓存一致性协议 就是在这种背景下产生的。存储一致性模型( m 锄o r yc o n s i s t e n c ym o d e l ) 可以看作是系统和 程序员之间的接口。一方面，它向程序员提供了一个存储系统的行为规范，从而指导和约 束程序员如何书写正确的程序：另一方面，一个好的存储一致性模型应当允许充分的硬件 和编译优化技术，从而提高系统的整体性能。因此，它对系统设计者也有很大的影响。在 使用高速缓存的系统中，对共享数据的缓冲导致同一存储单元的数据可能存在多个备份， 高速缓存一致性协议则是用来保证处理器访问到的备份含有最新的数据。 c e n s i e r 和f e a u 讯e 一”给出了存储器一致性方案的原始定义( 所谓严格一致性模型或瞬 间a t o m i c 一致性模型) ：一个存储器方案是一致的仅当任一条l o a d 指令所返回的值是 由最近的一条对同一地址的s t o r e 指令所写的值决定的。实际上，这个定义包括了存储 第5 页 国防科学技术大学研究生院学位论文 器系统行为的两个重要方面：一致性协议( c o h e r e n c e ) 和访存次序( e v e n to r d e r i n g ) 。这两个 方面对于在共享存储编程模型下写出正确的程序非常关键。一致性协议规定了一个读操作 应该返回什么样的值。而访存次序则规定了一个读操作应该在什么时候返回值。一致性协 议保证多个处理机对同一物理位置有一个一致的看法，即大家在同一时刻对同一物理位置 能够读到相同的值。而访存事件则描述了各个处理机对不同的物理位置的读写操作之间所 应有的次序。 下面，让我们先从h e n n e s s y 和p a n 螂o n 给出的一致性协议的充分条件出发，来仔细 地研究存储器一致性模型和高速缓存一致性协议以及处理机内的访存事件的次序之间的 关系。 h e n n e s s y 和p a n e r s o n 给出的关于c o h e r c n c e 的充分条件如下： 1 在处理机p 上对地址x 的读操作，跟随在它对同一地址的一次写操作之后，如果 在这期间没有别的处理机对地址x 有写操作，那么处理机p 对地址x 的读操作应 该返回它自己所写的值； 2 一个处理机p 1 对地址x 的读操作跟随在另一个处理机p 2 对地址x 的写操作之后， 如果这两次访存操作相隔得足够远，并且在它们之间没有其他对地址x 的写操作， 那么处理机p 1 应该返回处理机p 2 所写的值： 3 对同一地址的写操作应该是顺序的，即两个处理机对同一地址的写操作的顺序对 所有其他处理机来说是相同的。例如，如果值1 和2 先后被写入某个地址x ，那么 处理机就不能先读到值2 再读到值1 。 上面的三个条件保证所有的处理机对同一物理位置x 有一个一致的看法，但是并没有 告诉我们在同一处理机内的访存事件的次序是怎样的，因此就不能明确在什么时候会返回 一个已经取得一致看法的值。这样，为了更加准确的描述存储系统的行为，就有必要对上 面两者都进行限制，这就是存储器一致性模型。 下面的例子显示了高速缓存一致性和顺序一致性的不同。在图2 中，高速缓存一致性 不允许出现( a ) 的结果，而顺序一致性既不允许出现( a ) 的结果，也不允许出现( b ) 的 结果。可以说，在允许缓冲共享数据的系统中，高速缓存一致性是存储操作功能正确的先 决条件，但它并不是充分条件。事实上，存储一致性模型蕴涵的对访存次序的约束大部分 都不依赖于系统是否支持高速缓存。 l n i a 时x y o p lp lp lp 4p 1p：plp i x 麓lx 盅2r l 鬲x3 盖xx = i y = 2r i 黑xr 3 兰y r 2 = x1 4 = xr 2 = y4 ；x r e s h n ：r l = i ，r 2 = 2 r 3 = 2 r 4 = i r e s u 硅：r i = i 。r 2 蕾0 ir 3 霉2 ，r 4 罱o ( a )( b ) 图2 顺序一致性v s 高速缓存一致性 第6 页 国防科学技术大学研究生院学位论文 2 2 以硬件为中心的存储一致性模型 存储一致性的发展经历了多个阶段：“单处理器”阶段、“正确性”阶段、“正确性 + 性能”阶段、“正确性+ 性能+ 易编程性”阶段。在“单处理器”阶段，顺序程序在单 处理器系统下执行，存储操作的语义很简单： ( 1 ) 按照程序规定的顺序一次执行一个存 储操作； ( 2 ) 一个读操作总是返回同一存储位置最后一个写操作写入的值。对于程序员 来说，这种模型相当直观。实现的时候，在不背离该模型的前提下，可以通过多种优化技 术，如写缓冲、动态调度、寄存器分配等，允许不同存储位置的操作无序完成，从而提高 系统的性能。在“正确性”阶段，多进程程序在多处理器系统中执行，设计者对共享存储 访问操作的顺序加以严格限制以保证程序的正确执行。1 9 7 9 年l 锄p o n 提出了顺序一致性 模型1 2 j 。s c 模型相对比较直观，符合程序员的直觉，即一旦一个存储访问流出，就立即为 系统中的所有处理器可见。因此直到现在它仍是使用最为广泛的一种共享存储多处理器一 致性模型。很多一致性模型都以顺序一致性为正确性标准，即允许性能优化的同时保证没 有数据竞争( d a t a r a c e 舶e ) 的程序的执行符合顺序一致性模型。在“正确性+ 性能”阶段， 由于s c 模型对共享存储访问操作顺序的限制过于严格，使得许多单处理器系统中高效的 硬件和编译优化技术无法实旌。为了充分利用这些技术，提高系统的性能，一些存储一致 性模型对s c 的严格顺序要求和写原子性要求进行了不同程度的放松，允许数据在整个系 统中的i 临时不一致现象，从而在保证程序正确执行的前提下，允许一定的优化。这些模型 通常基于硬件支持，具有很明显的硬件约束性和访问顺序针对性如处理机一致性模型 ( p r o c e s rc o l l s i s t e n c ym o d e l ，p c ) 和s p u 汇v 8t 0 t a ls t o m0 r d e r i n g ( 简称t s 0 ) 模型对w r i t e 到m a d 操作之间的顺序要求进行了放松，s p a r c v 8p a n i a ls t o r c0 r d 耐n g ( 简称p s o ) 模型对 、砌t e 到r e a d 操作和w r i t e 到w r i t e 操作之间的顺序要求进行了放松，而p r m 模型和高速 缓存c o n s i s t e n c y 模型则仅对同一存储位置或同一处理器流出的写操作之间的顺序做出了 限制。在“正确性+ 性能+ 易编程性”阶段，程序员一般都主观地认为，一旦一个存储访 问流出之后，它应该立即可见于所有的处理器。因此，存储一致性模型的任务应强调存储 行为的规范而不是将存储访问事件的顺序限制展现在程序员面前，即不应将大量的一致性 维护工作交给程序员来处理。这一阶段的模型的目的就是在保证程序正确执行的前提下， 通过对存储访问进行适当的分类，进行相应的顺序约束，既提高系统的性能，又减轻程序 员的负担。通常，程序员只要按照s c 模型进行编程，根据存储访问分类情况提供少量有 关访问的信息，就可以获得遵循s c 模型的正确执行结果，而不用考虑底层硬件的顺序限 制。这一阶段比较有代表性的模型包括弱一致性模型( w e a k o r d e r i n g ，w o ) 和释放一致性模 犁。 2 2 1 顺序一致性模型 最先被提出的共享存储器模型是l a m p o n 【2 】提出的顺序一致性模型( s e q u e n t i a l l y c o n s i s t c n t ， s c ) ，它是对单处理器一致性模型的自然扩展。 l a m p o n 定义某一多处理机系统为顺序一致的，若：对于满足顺序一致性的多处理机 中的任一次执行，总可以找到同一程序在单机多进程环境下的一次执行与之对应，并且两 者的结果相等。 可见，顺序一致性模型要求：所有的访存操作应该好像是以某种全序执行，并且这 第7 页 国防科学技术大学研究生院学位论文 些执行都是不可分割的( a t o m i c ) ；每个处理机内的所有访存操作好像是以程序指定的次序 来执行，所有的读操作总是返回对同一单元所做的最后一个存操作写入的值。按照l 锄p o r t 定义，我们可以把满足顺序一致性的系统看作如图3 所示的系统，它由单端口存储器和开 关组成。单端口存储器恰好能一次提供一个操作；而开关则能在每个存储操作期间把存储 器与多台处理机中的一台连接在一起。开关从一台处理机到另一台处理机的切换次序确定 了存储器访问操作的全局次序。 p r o g m mo r d e r rrww llil rwrw 图3 顺序一致性模型和程序约束 在一个有高速缓存的系统中，写操作的原子性很难保证。为了方便讨论写操作非原子 性问题，s c h e u 血h 和d u b o i s i 川给出以下定义： 写操作w 相对于处理器p 执行完成( p e 】晌皿e d 诵t l lr e s p e c t 硒) ：w 写入的值被p 观察到，p 随后对该存储单元的读操作将不再返回旧的数据。 读操作r 相对于处理器p 执行完成( p 舭e d 诵n lr e s p e c tt o ) ：p 随后对该存储单 元的写操作不再影响r 返回的值。 存储操作o ( 读和写) 执行完成( p e 响肌e d ) ：o 相对于所有处理器执行完成。 写操作w 全局执行完成( g l o b a l l yp e r f o m e d ) ：w 执行完成。 读操作r 全局执行完成( g l o b a l l yp e r f o 瑚e d ) ：r 执行完成，并且若r 返回的是写 操作w 写入的值，则w 执行完成。 s c h 吼l r i c h 和d 咖i s 【3 j 给出了顺序一致性模型的一个充分条件： 1 所有的处理机以程序顺序发射存储器访问操作； 2 当前存储操作全局执行完成之前，处理机不能发射任何其他的存储器访问操作。 显然，在一个支持高速缓存的系统中，仅当高速缓存一致性被维护上面的条件才是充 分条件。 研究人员提出一些实现顺序一致性的方法，允许处理器在前面的存储操作全局执行完 成之前发射后续的存储操作。c o l l i e r 【6 l 证明了：若一个系统中的所有写操作按相同的顺序 相对于所有处理器执行完成，则它( i nm o s tc a s e s ) 等价于一个写操作原子执行的系统。他 提出一种用环形网实现顺序一致性的方案。他将处理器连成环形，其中一个处理器p a 用 来串行化所有的写操作。系统中执行写操作的处理器p 先发送写请求到p a ，然后p a 产生 更新( 或作废) 消息并沿环发送，当p 收到自己触发的更新( 或作废) 消息时，即使前一 写操作可能还没有全局执行完成，p 仍然可以开始处理下一个存储操作。 为了后面讨论的方便，在此将一致性模型对存储顺序的约束分成两类：程序顺序约束 和值约束。程序顺序约束用于描述一致性模型需要维护的程序顺序；值约束描述一致性模 型对读操作返回值的要求。如在单处理器中，程序顺序约束要求存在数据相关的存储操作 第8 页 国防科学技术大学研究生院学位论文 的程序顺序被维护，值约束要求对存储单元m 的读操作返回处理器最后一次对m 的写操 作写入的值；在顺序一致性模型中，程序顺序约束如图1 所示，要求所有存储操作的程序 顺序被维护，值约束要求对存储单元m 的读操作返回该读操作之前的最后一个对m 的写 操作写入的值。 2 2 2 处理器一致性模型 处理器一致性模型( p f o c e s s o rc o n s i