[高等教育]并行计算-多媒体课件-并行体系结构-lec15-DSM.ppt

1、PCA L16 Chp7.1Wu Spring 04 USTCParallel Computer Architecture并行计算机体系结构并行计算机体系结构Lecture 16PCA 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的区别，就是文件系统需要负责分布数据和维护容错级别。的区别，就是文件系统需要负责分布数据和维护容错级别。

4、条块组（条块组（Stripe Group）：）：将机群系统所有的磁盘组成一个逻辑将机群系统所有的磁盘组成一个逻辑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

13、/O接口来表达这些新的语义信息接口来表达这些新的语义信息.共享文件指针共享文件指针:全局共享文件指针全局共享文件指针 分布共享文件指针分布共享文件指针跨步存取模式：跨步存取模式：简单的跨步存取操作简单的跨步存取操作 嵌套的跨步操作嵌套的跨步操作 M=2KBP=5KBN=3存取块（块大小1Kbyte）PCA L16 Chp7.9Wu Spring 04 USTCBerkeley NOW 主动消息（主动消息（Active Message）：实现低开销通信的一种）：实现低开销通信的一种异步通信机制。异步通信机制。在消息头部控制信息中携带一个用户级子例程（称作消息处理程序）的在消息头部控制信息中携带一

14、个用户级子例程（称作消息处理程序）的地址。当信息头到达目的节点时，调用消息处理程序从网络上抽取剩下地址。当信息头到达目的节点时，调用消息处理程序从网络上抽取剩下的数据，并把它集成到正在进行的计算中。的数据，并把它集成到正在进行的计算中。GLUnix：全局层（：全局层（Global Layer）Unix 运行在工作站标准运行在工作站标准Unix之上的一个软件层，支持可用性和单一系统映像之上的一个软件层，支持可用性和单一系统映像 易于实现、可移植性、有效性、鲁棒性。易于实现、可移植性、有效性、鲁棒性。xFS：无服务器文件系统：无服务器文件系统 文件服务的功能分布到机群的所有节点上文件服务的功能分布

15、到机群的所有节点上 软件软件RAID 协同式文件缓存协同式文件缓存 分布管理分布管理PCA L16 Chp7.10Wu Spring 04 USTCIBM SP2系统系统 机群体系结构机群体系结构 标准环境标准环境 标准编程模型标准编程模型 系统可用性系统可用性 精选的单一系统映像精选的单一系统映像 高性能开关高性能开关 HPS 多级多级网络网络 宽节点、窄节点和窄节点宽节点、窄节点和窄节点2 网络接口网络接口 系统软件系统软件PCA L16 Chp7.11Wu Spring 04 USTC分布式共享存储系统分布式共享存储系统 共享存储器分布于各节点之中，节点之间通过可扩放性共享存储器分布于各

16、节点之中，节点之间通过可扩放性好的互连网络相连。好的互连网络相连。在物理上分布存储的系统上逻辑地实现共享存储模型在物理上分布存储的系统上逻辑地实现共享存储模型 对于程序设计者隐藏了远程通信机制，保持了方便性和可移植性。对于程序设计者隐藏了远程通信机制，保持了方便性和可移植性。DSM系统底层分布式存储具有可扩放性和代价有效性系统底层分布式存储具有可扩放性和代价有效性 分布式的存储器和可扩放的互连网络增加了访存带宽，但却导致了不分布式的存储器和可扩放的互连网络增加了访存带宽，但却导致了不一致的访存结构一致的访存结构网络控制器存储器处理器高速缓存网络控制器存储器处理器高速缓存网络控制器存储器处理器高

17、速缓存DSM共享地址空间互连网络PCA L16 Chp7.12Wu Spring 04 USTC共享存储系统的体系结构共享存储系统的体系结构 无高速缓存结构无高速缓存结构：Cray-XMP，YMP-C90 向量机，大向量机，大型机，早期分布式共享存储机器型机，早期分布式共享存储机器共享总线结构共享总线结构：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等。等。P1P2Pnx互联网络 宿主拷贝拷贝

19、拷贝xx0m-1m2m-1(n-1)mnm-1处理器保证一致性的高速缓存高速缓存控制器分布式共享内存PCA L16 Chp7.14Wu Spring 04 USTCCOMA结构结构 唯高速缓存存储结构唯高速缓存存储结构:共享存储器的地址是活动的，存储单元与物理地址分离，数据可以根共享存储器的地址是活动的，存储单元与物理地址分离，数据可以根据访存模式动态地在各节点的存储器间移动和复制。据访存模式动态地在各节点的存储器间移动和复制。每个节点的存储器相当于一个大容量高速缓存，数据一致性也在这一每个节点的存储器相当于一个大容量高速缓存，数据一致性也在这一级维护。级维护。优点是在本地共享存储器命中的概率

20、较高。其缺点是当处理器的访问优点是在本地共享存储器命中的概率较高。其缺点是当处理器的访问不在本节点命中时，由于存储器的地址是活动的，需要一种机制来查不在本节点命中时，由于存储器的地址是活动的，需要一种机制来查找被访问单元的当前位置，因此延迟很大。找被访问单元的当前位置，因此延迟很大。目前采用唯高速缓存结构的系统有目前采用唯高速缓存结构的系统有Kendall Square Research的的KSR1和瑞典计算机研究院的和瑞典计算机研究院的DDM。此外，。此外，COMA结构常用于共享虚结构常用于共享虚拟存储拟存储SVM(Shared Virtual Memory)系统中系统中 P1P2Pnxxx

21、互联网络拷贝属主拷贝处理器高速缓存保证一致性的共享内存高速缓存控制器PCA L16 Chp7.15Wu Spring 04 USTC共享虚拟存储共享虚拟存储SVM结构结构 SVM(Shared Virtual Memory)系统，又称为软件系统，又称为软件DSM系统，系统，SVM系统在基于消息传递的系统在基于消息传递的MPP或机群系统中，用软件把分布于各节或机群系统中，用软件把分布于各节点的多个独立编址的存储器组织成一个统一编址的共享存储空间。点的多个独立编址的存储器组织成一个统一编址的共享存储空间。优点是在消息传递的系统上实现共享存储的编程界面，但主要问题是优点是在消息传递的系统上实现共享存

22、储的编程界面，但主要问题是难以获得满意的性能难以获得满意的性能-与硬件共享存储系统相比与硬件共享存储系统相比，SVM系统中较大的通信和共享粒度系统中较大的通信和共享粒度(通常是存储页通常是存储页)会导致假共享及额外的通信；会导致假共享及额外的通信；-在基于机群的在基于机群的SVM系统中，通信开销很大。基于系统中，通信开销很大。基于SVM系统的并系统的并行程序通信量通常比基于消息传递的并行程序的通信量大。行程序通信量通常比基于消息传递的并行程序的通信量大。SVM系统的实现系统的实现 在操作系统上改进，如在操作系统上改进，如Ivy、Mermaid、Mirage和和Clouds等；等；由运行系统来支

23、撑由运行系统来支撑，如，如CMU Midway、Rice Munin、Rice TreadMarks、Utah Quarks、DIKU CarlOS、Maryland CVM和和JIAJIA等；等；从语言级来实现从语言级来实现，如，如MIT CRL、Linda和和Orca等。等。混合实现的分布式共享存储系统，其基本思想是结合软硬件实现的分混合实现的分布式共享存储系统，其基本思想是结合软硬件实现的分布式共享存储系统的优点布式共享存储系统的优点。PCA L16 Chp7.16Wu Spring 04 USTCOverview关于论文答辩与考试关于论文答辩与考试Review of Lec14基于目录

24、高速缓存一致性协议基于目录高速缓存一致性协议放松的存储一致性模型放松的存储一致性模型PCA L16 Chp7.17Wu Spring 04 USTC高速缓存一致性问题的解决高速缓存一致性问题的解决 硬件不支持高速缓存一致硬件不支持高速缓存一致性性(NCC-NUMA结构结构)为了避免一致性问题，共享数据被标识为不可高速缓存的，只有私有为了避免一致性问题，共享数据被标识为不可高速缓存的，只有私有数据才能被高速缓存数据才能被高速缓存 好处在于仅需要很少的硬件支持就足够好处在于仅需要很少的硬件支持就足够 缺点在于：缺点在于：-支持透明的软件高速缓存一致性的编译机制非常有限，基于支持透明的软件高速缓存一

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

26、时，则诸如预取等延迟容忍技术效果才能更好。取等延迟容忍技术效果才能更好。PCA L16 Chp7.18Wu Spring 04 USTCContext for Scalable Cache CoherenceScalable networkCAP$SwitchMSwitchSwitchRealizing Pgm Modelsthrough net transactionprotocols -efficient node-to-net interface -interprets transactionsCaches naturally replicatedata -coherence throu

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

28、，与目录通信未命中，与目录通信 决定高速缓存拷贝的地址决定高速缓存拷贝的地址 决定将要进行的操作决定将要进行的操作 确定协议以保持同步确定协议以保持同步P1CacheMemoryScalable Interconnection NetworkComm.AssistP1CacheCommAssistDirectoryMemoryDirectoryPCA L16 Chp7.20Wu Spring 04 USTC一个高速缓存一致性系统必须一个高速缓存一致性系统必须:提供状态集提供状态集,状态转移图状态转移图,以及动作以及动作管理一致性协议管理一致性协议(0)决定何时调用一致性协议决定何时调用一致性协

29、议(a)找出其他高速缓存上的存储模块的信息以决定将要进行的操作找出其他高速缓存上的存储模块的信息以决定将要进行的操作-是否需要同其他高速缓存拷贝进行通信是否需要同其他高速缓存拷贝进行通信(b)确定其他拷贝的地址确定其他拷贝的地址(c)与这些拷贝通信与这些拷贝通信 (使无效使无效/更新更新)在所有的系统中都使用同样的方法进行在所有的系统中都使用同样的方法进行(0)存储块的状态保存在高速缓存中存储块的状态保存在高速缓存中 若未命中则调用协议若未命中则调用协议不同的方法通过不同的方法通过(a)到到(c)区分开来区分开来PCA L16 Chp7.21Wu Spring 04 USTC基于总线的一致性基

30、于总线的一致性(a),(b),(c)都是通总线广播实现都是通总线广播实现 访存失败的处理器发出一个访存失败的处理器发出一个“寻找寻找”信号信号 其他的对该信号做出响应并采取必要的动作其他的对该信号做出响应并采取必要的动作在规模不同的网络上都可实现在规模不同的网络上都可实现 向所有处理器广播向所有处理器广播,并使它们做出响应并使它们做出响应Conceptually simple,but broadcast doesnt scale with p on bus,bus bandwidth doesnt scale on scalable network,every fault leads to a

31、t least p network transactionsScalable coherence:can have same cache states and state transition diagram different mechanisms to manage protocolPCA L16 Chp7.22Wu Spring 04 USTCOne Approach:Hierarchical SnoopingExtend snooping approach:hierarchy of broadcast media tree of buses or rings(KSR-1)process

32、ors are in the bus-or ring-based multiprocessors at the leaves parents and children connected by two-way snoopy interfaces-snoop both buses and propagate relevant transactions main memory may be centralized at root or distributed among leavesIssues(a)-(c)handled similarly to bus,but not full broadca

33、st faulting processor sends out“search”bus transaction on its bus propagates up and down hiearchy based on snoop resultsProblems:high latency:multiple levels,and snoop/lookup at every level bandwidth bottleneck at rootNot popular todayPCA L16 Chp7.23Wu Spring 04 USTCScalable Approach:DirectoriesEver

34、y memory block has associated directory information keeps track of copies of cached blocks and their states on a miss,find directory entry,look it up,and communicate only with the nodes that have copies if necessary in scalable networks,communication with directory and copies is through network tran

35、sactionsMany alternatives for organizing directory informationPCA L16 Chp7.24Wu Spring 04 USTCBasic Directory TransactionsPAM/DCPAM/DCPAM/DCRead requestto directoryReply withowner identityRead req.to o wnerDataReplyRe vision messageto directory1.2.3.4a.4b.PAM/DCPAM/DCPAM/DCRdEx requestto directoryRe

36、ply withsharers identityIn val.req.to sharer1.2.PAM/DCIn v al.req.to sharerIn v al.ack In v al.ack 3a.3b.4a.4b.RequestorNode withdirty cop yDir ectory nodefor blockRequestorDir ectory nodeShar erShar er(a)Read miss to a block in dirty state(b)Write miss to a block with two sharersPCA L16 Chp7.25Wu S

37、pring 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)bitPPCacheCacheMemoryDirectorypresence bitsdirty bitInterconnection Network Read from main memory by processor i:If dirty-bi

38、t OFF then read from 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 h

39、ave the block;clear 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-hiearchically e.g.mesh of SMPsCoherence across nodes is directory-based directory keeps track of nodes,not

40、 individual processorsCoherence within nodes is snooping or directory orthogonal,but needs a good interface of functionalityExamples:Convex Exemplar:directory-directory Sequent,Data General,HAL:directory-snoopySMP on a chip?PCA L16 Chp7.27Wu Spring 04 USTCExample Two-level HierarchiesPCSnooping B1B2

41、PCPCB1PCMainMemMainMemAdapterSnoopingAdapterPCB1Bus(or Ring)PCPCB1PCMainMemMainMemNetworkAssistAssistNetwork2PCAM/DNetwork1PCAM/DDirectory adapterPCAM/DNetwork1PCAM/DDirectory adapterPCAM/DNetwork1PCAM/DDir/Snoop y adapterPCAM/DNetwork1PCAM/DDir/Snoop y adapter(a)Snooping-snooping(b)Snooping-directo

42、ryDir.Dir.(c)Directory-directory(d)Directory-snoopingPCA L16 Chp7.28Wu Spring 04 USTCAdvantages of Multiprocessor NodesPotential for cost and performance advantages amortization of node fixed costs over multiple processors-applies even if processors simply packaged together but not coherent can use

43、commodity SMPs less nodes for directory to keep track of much communication may be contained within 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

44、pattern(and mapping)-good for widely read-shared:e.g.tree data in Barnes-Hut-good for nearest-neighbor,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 usef

45、ul in containing traffic if organized properly,traffic and latency shouldnt scale too badlySuggests techniques to reduce storage overheadPCA L16 Chp7.30Wu Spring 04 USTCOrganizing DirectoriesCentralizedDistributedHierarchicalFlatMemory-basedCache-basedDirectory SchemesHow to find source ofdirectory

46、informationHow to locate copiesPCA L16 Chp7.31Wu Spring 04 USTCHow to Find Directory Informationcentralized memory and directory-easy:go to it but not scalabledistributed memory and directory flat schemes-directory distributed with memory:at the home-location based on address(hashing):network xactio

47、n sent directly to home hierarchical schemes-Hierarchical of caches that guarantee the inclusion property;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 Directo

48、ries WorkDirectory is a hierarchical data structure leaves are processing nodes,internal nodes just directory logical hierarchy,not necessarily phyiscal-(can be embedded in general network)processing nodeslevel-1 directorylevel-2 directory(Tracks which of its childrenprocessing nodes have a copyof t

49、he memory block.Also trackswhich local memory blocks arecached outside this subtree.Inclusion is maintained betweenprocessor caches and directory.)(Tracks which of its childrenlevel-1 directories have a copyof the memory block.Also trackswhich local memory blocks arecached outside this subtree.Inclu

50、sion is maintained betweenlevel-1 directories and level-2 directory.)PCA L16 Chp7.33Wu Spring 04 USTCFind Directory Info(cont)distributed memory and directory flat schemes-hash hierarchical schemes-nodes directory entry for a block says whether each subtree caches the block-to find directory info,se