高等教育并行计算多媒体课件并行体系结构lec15DSM

《高等教育并行计算多媒体课件并行体系结构lec15DSM》由会员分享，可在线阅读，更多相关《高等教育并行计算多媒体课件并行体系结构lec15DSM（49页珍藏版）》请在装配图网上搜索。

1、 高等教育高等教育 并行计算并行计算-多媒多媒体课件体课件-并行体系结构并行体系结构-lec15-DSMlec15-DSMPCA L16 Chp7.2Wu Spring 04 USTC概要概要复习第复习第14讲讲基于目录高速缓存一致性协议基于目录高速缓存一致性协议放松的存储一致性模型放松的存储一致性模型PCA L16 Chp7.3Wu Spring 04 USTC并行文件系统并行文件系统工作站机群上的文件系统工作站机群上的文件系统并行应用一般要处理很大的数据集并行应用一般要处理很大的数据集I/O系统应该能允许并行应用中协作化的操作。系统应该能允许并行应用中协作化的操作。因此需要设计一个高性能的

2、文件系统来简化进程间的协作，高效地利因此需要设计一个高性能的文件系统来简化进程间的协作，高效地利用所有资源，并且对用户是透明的。用所有资源，并且对用户是透明的。考虑机群系统最基本的两个特点：考虑机群系统最基本的两个特点：大量资源：如磁盘、内存等。大量资源：如磁盘、内存等。-并行存取多个磁盘来提高传输带宽；并行存取多个磁盘来提高传输带宽；-利用机群系统中的内存，建立大的文件系统缓冲区来提高性能；利用机群系统中的内存，建立大的文件系统缓冲区来提高性能；高速互连网络高速互连网络-允许系统依赖远地节点完成某些任务。例如，现在的一些系统允许系统依赖远地节点完成某些任务。例如，现在的一些系统依赖远地节点的

3、内存来保存本地节点中放不下的高速缓存块。依赖远地节点的内存来保存本地节点中放不下的高速缓存块。PCA L16 Chp7.4Wu Spring 04 USTC软件软件RAID软件（逻辑）软件（逻辑）RAID：将将RAID的思想用在机群中，将数据分布在机群系统的多个磁盘中。的思想用在机群中，将数据分布在机群系统的多个磁盘中。软件软件RAID表现就象表现就象RAID 5，并且与，并且与RAID具有相同的优缺点具有相同的优缺点 与与RAID的区别，就是文件系统需要负责分布数据和维护容错级别。的区别，就是文件系统需要负责分布数据和维护容错级别。条块组（条块组（Stripe Group）：）：将机群系统所

4、有的磁盘组成一个逻辑将机群系统所有的磁盘组成一个逻辑RAID-向所有磁盘写的大的写操作非常困难，导致很多小写操作。但在向所有磁盘写的大的写操作非常困难，导致很多小写操作。但在RAID 5，小的写操作效率差。因此，系统就不能充分利用所有磁盘的写带宽。，小的写操作效率差。因此，系统就不能充分利用所有磁盘的写带宽。-节点的网络连接的带宽有限，不能够同时读节点的网络连接的带宽有限，不能够同时读/写所有磁盘，只能利用部分写所有磁盘，只能利用部分磁盘性能。磁盘性能。-发生故障的可能性大。奇偶校验机制不够，可能同时多个磁盘故障。发生故障的可能性大。奇偶校验机制不够，可能同时多个磁盘故障。解决方法是将数据条块

5、化分布到磁盘的一个子集上（条块组）。解决方法是将数据条块化分布到磁盘的一个子集上（条块组）。-系统需要执行的小的写操作数目大量减少。系统需要执行的小的写操作数目大量减少。-网络连接的带宽与条块组中磁盘的集合带宽相匹配，充分利用资源。网络连接的带宽与条块组中磁盘的集合带宽相匹配，充分利用资源。-系统中允许多个磁盘失效，只不过不能是属于同一条块组的多个磁盘。系统中允许多个磁盘失效，只不过不能是属于同一条块组的多个磁盘。代价：减少了磁盘存储容量和有效带宽，因为每个条块组都必须有一个存放奇代价：减少了磁盘存储容量和有效带宽，因为每个条块组都必须有一个存放奇偶校验块磁盘，而在原来的方法中整个系统只要一个

6、存放奇偶校验块的磁盘。偶校验块磁盘，而在原来的方法中整个系统只要一个存放奇偶校验块的磁盘。PCA L16 Chp7.5Wu Spring 04 USTC日志结构的文件系统（日志结构的文件系统（Log-structure Filesystem）日志结构的文件系统提高磁盘速度。日志结构的文件系统提高磁盘速度。基本假设：高速缓存满足读操作的比例是很高的，因此磁盘的通信量基本假设：高速缓存满足读操作的比例是很高的，因此磁盘的通信量主要是由写操作决定。如果能够改善写操作的执行，顺序执行所有写主要是由写操作决定。如果能够改善写操作的执行，顺序执行所有写操作，就可避免寻道和查找时间，能极大提高磁盘性能。操作

7、，就可避免寻道和查找时间，能极大提高磁盘性能。日志结构文件系统的基本思想：使大部分写操作是按顺序执行。日志结构文件系统的基本思想：使大部分写操作是按顺序执行。日志结构文件系统中，将整个文件系统作为一个日志来日志结构文件系统中，将整个文件系统作为一个日志来实现。日志结构的文件系统在每次块被写到一个文件时实现。日志结构的文件系统在每次块被写到一个文件时都将数据块加到日志的末尾，同时将以前写的块置为无都将数据块加到日志的末尾，同时将以前写的块置为无效。这种方法允许每个文件被顺序写入；不管写的块顺效。这种方法允许每个文件被顺序写入；不管写的块顺序，因此提供了更快的写速度。序，因此提供了更快的写速度。降

8、低读性能的代价换来很高的写性能，增加了复杂性。降低读性能的代价换来很高的写性能，增加了复杂性。块按照写时的顺序分配使文件以随机顺序在磁盘中分散放置。块按照写时的顺序分配使文件以随机顺序在磁盘中分散放置。增加一个单独的垃圾清除程序来扫描文件系统、移除无效块。增加一个单独的垃圾清除程序来扫描文件系统、移除无效块。需要一个复杂的缓存需要一个复杂的缓存/查询机制来支持高效的查询，并且每个文件的块查询机制来支持高效的查询，并且每个文件的块位置信息必须保存起来。位置信息必须保存起来。PCA L16 Chp7.6Wu Spring 04 USTC缓存缓存 利用局部性原理利用局部性原理多级缓存：能够在不同的层

9、次利用缓存机制。（服务器多级缓存：能够在不同的层次利用缓存机制。（服务器或客户端磁盘控制器、操作系统、或客户端磁盘控制器、操作系统、I/O库、用户程序）库、用户程序）缓存一致性问题缓存一致性问题：放松的文件共享语义：对话语义，增加了程序员负担放松的文件共享语义：对话语义，增加了程序员负担一致性算法：实现一致性算法：实现Unix语义。不缓存写操作，语义。不缓存写操作，令牌：写之前必须获得令牌。令牌的回收，租约。令牌：写之前必须获得令牌。令牌的回收，租约。粒度：文件，文件块，自定义粒度：文件，文件块，自定义协同缓存：协同缓存：如不同的缓存间没有协作，如不同的缓存间没有协作，不能充分利用所有的缓存空

10、间；不能充分利用所有的缓存空间；一个一个节点需要的文件块，已经缓存在另一个节点的缓存中了，从该缓存读节点需要的文件块，已经缓存在另一个节点的缓存中了，从该缓存读提高系统的性能。提高系统的性能。第一个实现协同文件缓存的系统是第一个实现协同文件缓存的系统是xFS。基本思想：机群中每个节点分配一部分主存作为文件缓存。协同缓存基本思想：机群中每个节点分配一部分主存作为文件缓存。协同缓存算法利用所有这些主存来创建一个大型的、机群范围的文件缓存。当算法利用所有这些主存来创建一个大型的、机群范围的文件缓存。当客户不命中局部文件缓存时，转向远地客户的存储器去取数据。客户不命中局部文件缓存时，转向远地客户的存储

11、器去取数据。PCA L16 Chp7.7Wu Spring 04 USTC数据预取数据预取 预取：真正存取数据块之前就将其读入内存。预取：真正存取数据块之前就将其读入内存。并行预取：每个节点独立的预取数据并行预取：每个节点独立的预取数据。One-block-ahead 或或 Stride 透明通知预取透明通知预取：用户向：用户向I/O系统提供一些存取文件情况的提示信息，系统提供一些存取文件情况的提示信息，系统利用这些信息，能够更好进行预取系统利用这些信息，能够更好进行预取。积极预取：一旦当磁盘准备好后，就进行预取，将内存中最远的将积极预取：一旦当磁盘准备好后，就进行预取，将内存中最远的将来才用

12、到的数据块替换出去。来才用到的数据块替换出去。表6.6 采用积极预取算法得到的预取调度序列一览表时间T1T2T3T4T5T6T7T8T9T10T11T12服务块F1A1B2C1D2E1F1块1F1F1F1D2D2D2D2D2D2F1F1F1块2B2B2B2B2B2B2B2E1E1E1E1E1块3A1A1A1C1C1C1C1C1C1C1PCA L16 Chp7.8Wu Spring 04 USTC I/O接口接口 传统的传统的I/O接口不能表达数据并行、协同化操作等概念，接口不能表达数据并行、协同化操作等概念，开发一种新的开发一种新的I/O接口来表达这些新的语义信息接口来表达这些新的语义信息.共

13、享文件指针共享文件指针:全局共享文件指针全局共享文件指针分布共享文件指针分布共享文件指针跨步存取模式：跨步存取模式：简单的跨步存取操作简单的跨步存取操作嵌套的跨步操作嵌套的跨步操作 PCA L16 Chp7.9Wu Spring 04 USTCBerkeley NOW 主动消息（主动消息（Active Message）：实现低开销通信的一种）：实现低开销通信的一种异步通信机制。异步通信机制。在消息头部控制信息中携带一个用户级子例程（称作消息处理程序）的在消息头部控制信息中携带一个用户级子例程（称作消息处理程序）的地址。当信息头到达目的节点时，调用消息处理程序从网络上抽取剩下地址。当信息头到达目

14、的节点时，调用消息处理程序从网络上抽取剩下的数据，并把它集成到正在进行的计算中。的数据，并把它集成到正在进行的计算中。GLUnix：全局层（：全局层（Global Layer）Unix运行在工作站标准运行在工作站标准Unix之上的一个软件层，支持可用性和单一系统映像之上的一个软件层，支持可用性和单一系统映像易于实现、可移植性、有效性、鲁棒性。易于实现、可移植性、有效性、鲁棒性。xFS：无服务器文件系统：无服务器文件系统文件服务的功能分布到机群的所有节点上文件服务的功能分布到机群的所有节点上 软件软件RAID协同式文件缓存协同式文件缓存分布管理分布管理PCA L16 Chp7.10Wu Spri

15、ng 04 USTCIBM SP2系统系统 机群体系结构机群体系结构 标准环境标准环境 标准编程模型标准编程模型 系统可用性系统可用性 精选的单一系统映像精选的单一系统映像 高性能开关高性能开关 HPS 多级多级网络网络 宽节点、窄节点和窄节点宽节点、窄节点和窄节点2 网络接口网络接口 系统软件系统软件PCA L16 Chp7.11Wu Spring 04 USTC分布式共享存储系统分布式共享存储系统 共享存储器分布于各节点之中，节点之间通过可扩放性共享存储器分布于各节点之中，节点之间通过可扩放性好的互连网络相连。好的互连网络相连。在物理上分布存储的系统上逻辑地实现共享存储模型在物理上分布存储

16、的系统上逻辑地实现共享存储模型对于程序设计者隐藏了远程通信机制，保持了方便性和可移植性。对于程序设计者隐藏了远程通信机制，保持了方便性和可移植性。DSM系统底层分布式存储具有可扩放性和代价有效性系统底层分布式存储具有可扩放性和代价有效性分布式的存储器和可扩放的互连网络增加了访存带宽，但却导致了不分布式的存储器和可扩放的互连网络增加了访存带宽，但却导致了不一致的访存结构一致的访存结构PCA L16 Chp7.12Wu Spring 04 USTC共享存储系统的体系结构共享存储系统的体系结构 无高速缓存结构无高速缓存结构：Cray-XMP，YMP-C90 向量机，大向量机，大型机，早期分布式共享存

17、储机器型机，早期分布式共享存储机器共享总线结构共享总线结构：SMP UMA 小型商用服务器小型商用服务器CC-NUMA结构结构:COMA结构结构：NCC-NUMA结构：结构：共享虚拟存储共享虚拟存储SVM结构结构：PCA L16 Chp7.13Wu Spring 04 USTCCC-NUMA结构结构高速缓存一致的非均匀存储访问系统：高速缓存一致的非均匀存储访问系统：共享存储器分布于各节点之中。共享存储器分布于各节点之中。节点之间通过可扩放性好的互连网络相连，每个处理器都能缓存共享节点之间通过可扩放性好的互连网络相连，每个处理器都能缓存共享单元，单元，通常采用基于目录的方法来维持处理器之间的高速

18、缓存一致性。高速通常采用基于目录的方法来维持处理器之间的高速缓存一致性。高速缓存一致性的维护是这类系统的关键，决定着系统的可扩放性。缓存一致性的维护是这类系统的关键，决定着系统的可扩放性。Stanford大学的大学的DASH和和FLASH，MIT的的Alewife，以及，以及SGI的的Origin 2000等。等。PCA L16 Chp7.14Wu Spring 04 USTCCOMA结构结构 唯高速缓存存储结构唯高速缓存存储结构:共享存储器的地址是活动的，存储单元与物理地址分离，数据可以根共享存储器的地址是活动的，存储单元与物理地址分离，数据可以根据访存模式动态地在各节点的存储器间移动和复制

19、。据访存模式动态地在各节点的存储器间移动和复制。每个节点的存储器相当于一个大容量高速缓存，数据一致性也在这一每个节点的存储器相当于一个大容量高速缓存，数据一致性也在这一级维护。级维护。优点是在本地共享存储器命中的概率较高。其缺点是当处理器的访问优点是在本地共享存储器命中的概率较高。其缺点是当处理器的访问不在本节点命中时，由于存储器的地址是活动的，需要一种机制来查不在本节点命中时，由于存储器的地址是活动的，需要一种机制来查找被访问单元的当前位置，因此延迟很大。找被访问单元的当前位置，因此延迟很大。目前采用唯高速缓存结构的系统有目前采用唯高速缓存结构的系统有Kendall Square Resea

20、rch的的KSR1和瑞典计算机研究院的和瑞典计算机研究院的DDM。此外，。此外，COMA结构常用于共享虚结构常用于共享虚拟存储拟存储SVM(Shared Virtual Memory)系统中系统中 PCA L16 Chp7.15Wu Spring 04 USTC共享虚拟存储共享虚拟存储SVM结构结构 SVM(Shared Virtual Memory)系系统统，又又称称为为软软件件DSM系统，系统，SVM系系统统在在基基于于消消息息传传递递的的MPP或或机机群群系系统统中中，用用软软件件把把分分布布于于各各节节点的多个独立编址的存储器组织成一个统一编址的共享存储空间。点的多个独立编址的存储器组

21、织成一个统一编址的共享存储空间。优优点点是是在在消消息息传传递递的的系系统统上上实实现现共共享享存存储储的的编编程程界界面面，但但主主要要问问题题是是难以获得满意的性能难以获得满意的性能-与与硬硬件件共共享享存存储储系系统统相相比比，SVM系系统统中中较较大大的的通通信信和和共共享享粒粒度度(通常是存储页通常是存储页)会导致假共享及额外的通信；会导致假共享及额外的通信；-在在基基于于机机群群的的SVM系系统统中中，通通信信开开销销很很大大。基基于于SVM系系统统的的并并行程序通信量通常比基于消息传递的并行程序的通信量大。行程序通信量通常比基于消息传递的并行程序的通信量大。SVM系统的实现系统的

22、实现在操作系统上改进，如在操作系统上改进，如Ivy、Mermaid、Mirage和和Clouds等；等；由由 运运 行行 系系 统统 来来 支支 撑撑，如如 CMU Midway、Rice Munin、Rice TreadMarks、Utah Quarks、DIKU CarlOS、Maryland CVM和和JIAJIA等；等；从语言级来实现，如从语言级来实现，如MIT CRL、Linda和和Orca等。等。混混合合实实现现的的分分布布式式共共享享存存储储系系统统，其其基基本本思思想想是是结结合合软软硬硬件件实实现现的的分分布式共享存储系统的优点。布式共享存储系统的优点。PCA L16 Chp

23、7.16Wu Spring 04 USTCOverview关于论文答辩与考试关于论文答辩与考试Review of Lec14基于目录高速缓存一致性协议基于目录高速缓存一致性协议放松的存储一致性模型放松的存储一致性模型PCA L16 Chp7.17Wu Spring 04 USTC高速缓存一致性问题的解决高速缓存一致性问题的解决 硬件不支持高速缓存一致性硬件不支持高速缓存一致性(NCC-NUMA结构结构)为了避免一致性问题，共享数据被标识为不可高速缓存的，只有私有为了避免一致性问题，共享数据被标识为不可高速缓存的，只有私有数据才能被高速缓存数据才能被高速缓存 好处在于仅需要很少的硬件支持就足够好

24、处在于仅需要很少的硬件支持就足够缺点在于：缺点在于：-支持透明的软件高速缓存一致性的编译机制非常有限，基支持透明的软件高速缓存一致性的编译机制非常有限，基于编译支持的软件高速缓存一致性是不太现实的。于编译支持的软件高速缓存一致性是不太现实的。-如果没有高速缓存一致性，那么在与访问远地单字所需的同如果没有高速缓存一致性，那么在与访问远地单字所需的同等开销下系统将失去获取并使用一个高速缓存行中多个字的优点。等开销下系统将失去获取并使用一个高速缓存行中多个字的优点。当每次访问远地主存只能获得一个单字时，共享存储所具有的空当每次访问远地主存只能获得一个单字时，共享存储所具有的空间局部性的优点就荡然无存

25、了。间局部性的优点就荡然无存了。-如果可以同时处理多个字（如一个高速缓存行）时，则诸如如果可以同时处理多个字（如一个高速缓存行）时，则诸如预取等延迟容忍技术效果才能更好。预取等延迟容忍技术效果才能更好。PCA L16 Chp7.18Wu Spring 04 USTCContext for Scalable Cache CoherenceRealizing Pgm Modelsthrough net transactionprotocols -efficient node-to-net interface -interprets transactionsCaches naturally repl

26、icatedata -coherence through bussnooping protocols -consistencyScalable Networks -many simultaneoustransactionsScalabledistributedmemoryNeed cache coherence protocols that scale!-no broadcast or single point of orderPCA L16 Chp7.19Wu Spring 04 USTC解决方法解决方法:目录协目录协议议显式地包含状态向量显式地包含状态向量 与存储块状态相联系与存储块状态相

27、联系记录每个存储块的状态记录每个存储块的状态未命中，与目录通信未命中，与目录通信决定高速缓存拷贝的地址决定高速缓存拷贝的地址决定将要进行的操作决定将要进行的操作确定协议以保持同步确定协议以保持同步PCA L16 Chp7.20Wu Spring 04 USTC一个高速缓存一致性系统必须一个高速缓存一致性系统必须:提供状态集提供状态集,状态转移图状态转移图,以及动作以及动作管理一致性协议管理一致性协议(0)决定何时调用一致性协议决定何时调用一致性协议(a)找出其他高速缓存上的存储模块的信息以决定将要进行的操作找出其他高速缓存上的存储模块的信息以决定将要进行的操作-是否需要同其他高速缓存拷贝进行通

28、信是否需要同其他高速缓存拷贝进行通信(b)确定其他拷贝的地址确定其他拷贝的地址(c)与这些拷贝通信与这些拷贝通信 (使无效使无效/更新更新)在所有的系统中都使用同样的方法进行在所有的系统中都使用同样的方法进行(0)存储块的状态保存在高速缓存中存储块的状态保存在高速缓存中若未命中则调用协议若未命中则调用协议不同的方法通过不同的方法通过(a)到到(c)区分开来区分开来PCA L16 Chp7.21Wu Spring 04 USTC基于总线的一致性基于总线的一致性(a),(b),(c)都是通总线广播实现都是通总线广播实现访存失败的处理器发出一个访存失败的处理器发出一个“寻找寻找”信号信号 其他的对该

29、信号做出响应并采取必要的动作其他的对该信号做出响应并采取必要的动作在规模不同的网络上都可实现在规模不同的网络上都可实现向所有处理器广播向所有处理器广播,并使它们做出响应并使它们做出响应Conceptually simple,but broadcast doesnt scale with pon bus,bus bandwidth doesnt scaleon scalable network,every fault leads to at least p network transactionsScalable coherence:can have same cache states and

30、state transition diagramdifferent mechanisms to manage protocolPCA L16 Chp7.22Wu Spring 04 USTCOne Approach:Hierarchical SnoopingExtend snooping approach:hierarchy of broadcast mediatree of buses or rings(KSR-1)processors are in the bus-or ring-based multiprocessors at the leavesparents and children

31、 connected by two-way snoopy interfaces-snoop both buses and propagate relevant transactionsmain memory may be centralized at root or distributed among leavesIssues(a)-(c)handled similarly to bus,but not full broadcast faulting processor sends out“search”bus transaction on its buspropagates up and d

32、own hiearchy based on snoop resultsProblems:high latency:multiple levels,and snoop/lookup at every levelbandwidth bottleneck at rootNot popular todayPCA L16 Chp7.23Wu Spring 04 USTCScalable Approach:DirectoriesEvery memory block has associated directory informationkeeps track of copies of cached blo

33、cks and their stateson a miss,find directory entry,look it up,and communicate only with the nodes that have copies if necessaryin scalable networks,communication with directory and copies is through network transactionsMany alternatives for organizing directory informationPCA L16 Chp7.24Wu Spring 04

34、 USTCBasic Directory TransactionsPCA L16 Chp7.25Wu Spring 04 USTCBasic Operation of Directory k processors.With each cache-block in memory:k presence-bits,1 dirty-bit With each cache-block in cache:1 valid bit,and 1 dirty(owner)bit Read from main memory by processor i:If dirty-bit OFF then read from

35、 main memory;turn pi ON;if dirty-bit ON then recall line from dirty proc(cache state to shared);update memory;turn dirty-bit OFF;turn pi ON;supply recalled data to i;Write to main memory by processor i:If dirty-bit OFF then supply data to i;send invalidations to all caches that have the block;clear

36、directory entries;turn dirty-bit ON;turn pi ON;.PCA L16 Chp7.26Wu Spring 04 USTCA Popular Middle GroundTwo-level“hierarchy”Individual nodes are multiprocessors,connected non-hiearchicallye.g.mesh of SMPsCoherence across nodes is directory-baseddirectory keeps track of nodes,not individual processors

37、Coherence within nodes is snooping or directoryorthogonal,but needs a good interface of functionalityExamples:Convex Exemplar:directory-directorySequent,Data General,HAL:directory-snoopySMP on a chip?PCA L16 Chp7.27Wu Spring 04 USTCExample Two-level HierarchiesPCA L16 Chp7.28Wu Spring 04 USTCAdvanta

38、ges of Multiprocessor NodesPotential for cost and performance advantagesamortization of node fixed costs over multiple processors-applies even if processors simply packaged together but not coherentcan use commodity SMPsless nodes for directory to keep track ofmuch communication may be contained wit

39、hin node(cheaper)nodes prefetch data for each other(fewer“remote”misses)combining of requests(like hierarchical,only two-level)can even share caches(overlapping of working sets)benefits depend on sharing pattern(and mapping)-good for widely read-shared:e.g.tree data in Barnes-Hut-good for nearest-ne

40、ighbor,if properly mapped-not so good for all-to-all communicationPCA L16 Chp7.29Wu Spring 04 USTCSharing Patterns SummaryGenerally,few sharers at a write,scales slowly with PImplies directories very useful in containing trafficif organized properly,traffic and latency shouldnt scale too badlySugges

41、ts techniques to reduce storage overheadPCA L16 Chp7.30Wu Spring 04 USTCOrganizing DirectoriesCentralizedDistributedHierarchicalFlatMemory-basedCache-basedDirectory SchemesHow to find source ofdirectory informationHow to locate copiesPCA L16 Chp7.31Wu Spring 04 USTCHow to Find Directory Informationc

42、entralized memory and directory-easy:go to itbut not scalabledistributed memory and directoryflat schemes-directory distributed with memory:at the home-location based on address(hashing):network xaction sent directly to homehierarchical schemes-Hierarchical of caches that guarantee the inclusion pro

43、perty;each parent keeps track of exactly which of its immediate children has a copy of the block.-Latency and network transaction-Not so popularPCA L16 Chp7.32Wu Spring 04 USTCHow Hierarchical Directories WorkDirectory is a hierarchical data structureleaves are processing nodes,internal nodes just d

44、irectorylogical hierarchy,not necessarily phyiscal-(can be embedded in general network)PCA L16 Chp7.33Wu Spring 04 USTCFind Directory Info(cont)distributed memory and directoryflat schemes-hashhierarchical schemes-nodes directory entry for a block says whether each subtree caches the block-to find d

45、irectory info,send“search”message up to parentroutes itself through directory lookups-like hiearchical snooping,but point-to-point messages between children and parentsPCA L16 Chp7.34Wu Spring 04 USTCHow Is Location of Copies Stored?Hierarchical Schemesthrough the hierarchyeach directory has presenc

46、e bits child subtrees and dirty bitFlat Schemesvary a lotdifferent storage overheads and performance characteristicsMemory-based schemes-info about copies stored all at the home with the memory block-Dash,Alewife,SGI Origin,FlashCache-based schemes-info about copies distributed among copies themselv

47、eseach copy points to next-Scalable Coherent Interface(SCI:IEEE standard)PCA L16 Chp7.35Wu Spring 04 USTCFlat,Memory-based Schemesinfo about copies colocated with block at the homejust like centralized scheme,except distributedPerformance Scalingtraffic on a write:proportional to number of sharersla

48、tency on write:can issue invalidations to sharers in parallelStorage overheadsimplest representation:full bit vector,i.e.one presence bit per nodestorage overhead doesnt scale well with P;64-byte line implies-64 nodes:12.7%ovhd.-256 nodes:50%ovhd.;1024 nodes:200%ovhd.for M memory blocks in memory,st

49、orage overhead is proportional to P*MPMPCA L16 Chp7.36Wu Spring 04 USTCPMReducing Storage OverheadOptimizations for full bit vector schemesincrease cache block size(reduces storage overhead proportionally)use multiprocessor nodes(bit per mp node,not per processor)still scales as P*M,but reasonable f

50、or all but very large machines-256-procs,4 per cluster,128B line:6.25%ovhd.Reducing“width”addressing the P term?Reducing“height”addressing the M term?PCA L16 Chp7.37Wu Spring 04 USTCStorage ReductionsWidth observation:most blocks cached by only few nodesdont have a bit per node,but entry contains a

51、few pointers to sharing nodesP=1024=10 bit ptrs,can use 100 pointers and still save spacesharing patterns indicate a few pointers should suffice(five or so)need an overflow strategy when there are more sharersHeight observation:number of memory blocks number of cache blocksmost directory entries are

52、 useless at any given timeorganize directory as a cache,rather than having one entry per memory blockPCA L16 Chp7.38Wu Spring 04 USTCFlat,Cache-based SchemesHow they work:home only holds pointer to rest of directory infodistributed linked list of copies,weaves through caches-cache tag has pointer,po

53、ints to next cache with a copyon read,add yourself to head of the list(comm.needed)on write,propagate chain of invals down the listScalable Coherent Interface(SCI)IEEE Standarddoubly linked listPCA L16 Chp7.39Wu Spring 04 USTCScaling Properties(Cache-based)Traffic on write:proportional to number of

54、sharersLatency on write:proportional to number of sharers!dont know identity of next sharer until reach current onealso assist processing at each node along the way(even reads involve more than one other assist:home and first sharer on list)Storage overhead:quite good scaling along both axesOnly one

55、 head ptr per memory block-rest is all prop to cache sizeVery complex!PCA L16 Chp7.40Wu Spring 04 USTCSummary of Directory OrganizationsFlat Schemes:Issue(a):finding source of directory datago to home,based on addressIssue(b):finding out where the copies arememory-based:all info is in directory at h

56、omecache-based:home has pointer to first element of distributed linked listIssue(c):communicating with those copiesmemory-based:point-to-point messages(perhaps coarser on overflow)-can be multicast or overlappedcache-based:part of point-to-point linked list traversal to find them-serializedHierarchi

57、cal Schemes:all three issues through sending messages up and down treeno single explicit list of sharersonly direct communication is between parents and childrenPCA L16 Chp7.41Wu Spring 04 USTCSummary of Directory ApproachesDirectories offer scalable coherence on general networksno need for broadcas

58、t mediaMany possibilities for organizing directory and managing protocolsHierarchical directories not used muchhigh latency,many network transactions,and bandwidth bottleneck at rootBoth memory-based and cache-based flat schemes are alivefor memory-based,full bit vector suffices for moderate scale-m

59、easured in nodes visible to directory protocol,not processorsPCA L16 Chp7.42Wu Spring 04 USTC放松的存储一致性模型放松的存储一致性模型 顺序一致性模型非常严格顺序一致性模型非常严格程序序的要求程序序的要求存储执行的原子性存储执行的原子性-写操作的全局执行后才能执行下一个存储操作写操作的全局执行后才能执行下一个存储操作-读操作的执行完成必须等待产生值的写操作完成读操作的执行完成必须等待产生值的写操作完成并非所有的存储操作的重叠进行都会引起错误，因此可并非所有的存储操作的重叠进行都会引起错误，因此可以对某些

60、执行次序要求放松。以对某些执行次序要求放松。处理器一致性模型：处理器一致性模型：wr弱一致性模型弱一致性模型:同步操作与普通操作同步操作与普通操作释放一致性模型释放一致性模型急切释放一致性模型急切释放一致性模型懒惰释放一致性模型懒惰释放一致性模型域一致性模型域一致性模型单项一致性模型单项一致性模型PCA L16 Chp7.43Wu Spring 04 USTC释放一致性模型释放一致性模型Release Consistency硬件和程序员之间建立某种约定，由程序员来负担一些硬件和程序员之间建立某种约定，由程序员来负担一些维护数据一致性的责任，从而放松硬件对访存事件发生维护数据一致性的责任，从而放

61、松硬件对访存事件发生次序的限制。次序的限制。操作分为操作分为同步操作和普通访存操作；同步操作和普通访存操作；同步操作进一步划分为获取操作同步操作进一步划分为获取操作acquire和释放操作和释放操作release。acquire用于获取对某些共享存储单元的独占性访问权，而用于获取对某些共享存储单元的独占性访问权，而release则则用于释放这种访问权。用于释放这种访问权。释放一致性模型对访存事件发生次序作如下限制：释放一致性模型对访存事件发生次序作如下限制：-在任一普通访存操作允许被执行之前，所有在同一处理器中在任一普通访存操作允许被执行之前，所有在同一处理器中先于这一访存操作的获取操作先于这

62、一访存操作的获取操作acquire都已完成；都已完成；-在任一释放操作在任一释放操作release允许被执行之前，所有在同一处理器允许被执行之前，所有在同一处理器中先于这一中先于这一release的普通访存操作都已完成；的普通访存操作都已完成；-同步操作的执行满足顺序一致性条件。同步操作的执行满足顺序一致性条件。PCA L16 Chp7.44Wu Spring 04 USTC急切释放一致性模型急切释放一致性模型SVM系统中，由于通信和数据交换的开销很大，所以有必要减少通信系统中，由于通信和数据交换的开销很大，所以有必要减少通信和数据交换的次数。和数据交换的次数。急切释放一致性模型中，临界区内的

63、多个存数操作不是及时进行的，急切释放一致性模型中，临界区内的多个存数操作不是及时进行的，而是在执行而是在执行release操作之前操作之前(即退出临界区之前即退出临界区之前)集中进行。把多个存集中进行。把多个存数操作合并在一起统一执行，就减少了数据通信次数，这对于由软件数操作合并在一起统一执行，就减少了数据通信次数，这对于由软件实现的共享存储系统是十分必要的。实现的共享存储系统是十分必要的。懒惰释放一致性模型懒惰释放一致性模型在此模型中，由一个处理器对某单元的存数操作并不是由此处理器主在此模型中，由一个处理器对某单元的存数操作并不是由此处理器主动地传播到所有共享该单元的其它处理器，而是在其它处

64、理器要用到动地传播到所有共享该单元的其它处理器，而是在其它处理器要用到此处理器所写的数据时此处理器所写的数据时(即其它处理器执行即其它处理器执行acquire操作时操作时)再向此处理再向此处理器索取该单元的最新备份。这样可以进一步减少通信量。器索取该单元的最新备份。这样可以进一步减少通信量。PCA L16 Chp7.45Wu Spring 04 USTC高速缓存一致性协议和存储一致性模型高速缓存一致性协议和存储一致性模型解决高速缓存一致性问题，即如何保持数据在多个高速解决高速缓存一致性问题，即如何保持数据在多个高速缓存和主存中的多个备份的一致性。缓存和主存中的多个备份的一致性。高速缓存一致性协

65、议都是为实现某种存储一致性模型而高速缓存一致性协议都是为实现某种存储一致性模型而设计的。设计的。存储一致性模型对高速缓存一致性协议提出一致性要求，存储一致性模型对高速缓存一致性协议提出一致性要求，即高速缓存一致性协议应该实现什么样的即高速缓存一致性协议应该实现什么样的“一致性一致性”。例如在释放一致性例如在释放一致性RC中，一个处理器对共享变量写的新值，其它处理中，一个处理器对共享变量写的新值，其它处理器只有等到该处理器释放锁后才能看到；而在顺序一致性器只有等到该处理器释放锁后才能看到；而在顺序一致性SC中，一个中，一个处理器写的值会立刻传播给所有的处理器。因此处理器写的值会立刻传播给所有的处

66、理器。因此SC和和RC所描述的所描述的“一一致性致性”观点不同，实现观点不同，实现SC的高速缓存一致性协议与实现的高速缓存一致性协议与实现RC的高速缓存的高速缓存一致性协议也就不一样。一致性协议也就不一样。高速缓存一致性协议通常需要考虑以下几方面：高速缓存一致性协议通常需要考虑以下几方面：如何传新值：是写无效还是写更新；如何传新值：是写无效还是写更新；谁产生新值：是单写协议还是多写协议；谁产生新值：是单写协议还是多写协议；何时传新值：是及时传播还是延迟传播；何时传新值：是及时传播还是延迟传播；新值传向谁：是侦听协议还是目录协议。新值传向谁：是侦听协议还是目录协议。PCA L16 Chp7.46Wu Spring 04 USTC Stanford DASH多计算机多计算机 Dash(Directory Architecture for Shared Memory)John Hennessy领导下由领导下由Stanford大学研制的大学研制的CC-NUMA多处理器系多处理器系统统使用分布式一致性高速缓存和分布式存储器层次结构，这使建立具有使用分布式一致性高速缓存和分布式存储器层次结构，这使