《讲义年月日》由会员分享,可在线阅读,更多相关《讲义年月日(52页珍藏版)》请在金锄头文库上搜索。
1、哈尔滨工业大学计算机科学与技术学院,1,并行处理与体系结构,哈尔滨工业大学计算机科学与技术学院,2,第5章 分布式存储器及其时延容忍,1 层次存储器技术2 高缓一致性协议3 共享存储器的一致性4 分布式高速缓存/主存体系结构5 时延容忍技术,哈尔滨工业大学计算机科学与技术学院,3,4 分布式高缓/主存体系结构,一、几种分布式存储结构1.前言物理上分布的存储器可被逻辑共享、不共享或部分共享共享存储器体系结构(多处理器)同时支持共享存储器和消息传递编程模型SMP具有共享存储器体系结构,而传统的MPP不是还有许多分布式存储器结构介于两者之间,哈尔滨工业大学计算机科学与技术学院,4,2.共享存储器体系
2、结构的定义 某个系统称为具有共享存储器体系结构(多处理器),如果该系统内任何处理器上的进程都能直接访问整个系统内的任何本地和远程存储器。非共享存储器体系结构(多计算机)。,哈尔滨工业大学计算机科学与技术学院,5,哈尔滨工业大学计算机科学与技术学院,6,3.UMA,NUMA,NORMA,COMA,CC-NUMA,NCCNUMANORMA:No-remote memory access结构 CC-NUMA:cachecoherent NUMA NCCNUMA:non cache coherent NUMA,哈尔滨工业大学计算机科学与技术学院,7,(1)数据访问方式的不同设LM:本地存储器,A和B:
3、存储器地址RC:远程高速缓存E:寄存器R:通用寄存器,哈尔滨工业大学计算机科学与技术学院,8,哈尔滨工业大学计算机科学与技术学院,9,(2)NORMA机器:各结点的存储器有不同的地址空间,结点不能直接访问远程存 而必须通过消息传递方式。结点P需要结点Q上变量A中的数据这可在结点Q上的发送例程和结点P上对应的接收例程完成,最后,A的值被拷贝P到结点P本地存储器中的变量B。,哈尔滨工业大学计算机科学与技术学院,10,其他3种体系结构都有特殊的硬件结构将所有的本地存储器合并为单一的地址空间,使所有的处理器都能访问任意的存储器单元。它们都可以通过load指令获得远程数据A。但是,它们的获取机制还是不同
4、的。典型的NCC-NUMA机器是Cray T3E。T3E中的每个结点除了具有本地存储器外,还有一组结点级的寄存器称为E寄存器(E-registers),哈尔滨工业大学计算机科学与技术学院,11,(3)CC-NUMA系统关于CC-NUMA机器的说明:CC-NUMA机器是SMP系统的扩展,它将几个SMP结点连接起来构成一个更大的系统。缓解了传统SMP系统规模不可扩展的问题。大多数商用的CC-NUMA多处理机系统采用了基于目录的高速缓存一致性协议。CC-NUMA机器既保持了SMP结构的优点,缓解了争用和带宽问题。,哈尔滨工业大学计算机科学与技术学院,12,CCNUMA机器显著优点:程序员不需要显式指
5、定数据结构应分配到哪一个结点上,系统的硬件和软件会在开始时自动将数据分配到各个结点处。在应用程序运行期间,高速缓存一致性硬件会自动将数据移至需要使用该数据的结点上。这个优点实现起来并不总是有效的,,哈尔滨工业大学计算机科学与技术学院,13,例如:CCNUMA系统中远程高速缓存(remote caching)的问题假设程序有两个进程P和Q执行以下代码,这两个进程都必须访问数据数组A和B P Q阶段1 使用(A) 使用(B)阶段2 使用(B) 使用(A),哈尔滨工业大学计算机科学与技术学院,14,哈尔滨工业大学计算机科学与技术学院,15,阶段1两个结点之间不需要通信,所以远程高速缓存为空。阶段2系
6、统硬件设备自动将数组B移到结点1的远程高速缓存,将数组A移到结点2的远程高速缓存,程序员不需要进行数据重分配。缺点:,哈尔滨工业大学计算机科学与技术学院,16,上图中:可通过某指令将A的值载入本地处理器的寄存器R1中,同时A所在的高速缓存块被自动拷贝到一个结点级的高速缓存中,称为远程高速缓存(remotecache,RC)。该高速缓存块并不被拷贝至本地存储器中。某些CCNUMA系统没有远程高速缓存,所以A所在的高速缓存块被拷贝至结点的2级高速缓存中。,哈尔滨工业大学计算机科学与技术学院,17,(4)COMA机器所有的本地存储器都采取高速缓存的结构(称为COMA高速缓存)。这样的高速缓存有比2级
7、高速缓存和远程高速缓存大得多的容量。可通过指令将A的值载入本地处理器寄存器中,同时A所在的高速缓存块被自动拷贝至本地存储器(也就是COMA高速缓存)中。COMA是唯一对在多个本地存储器中复制同一高速缓存块提供硬件支持的结构。,哈尔滨工业大学计算机科学与技术学院,18,(5)COMA与CC-NUMA的主要区别:COMA中的复制和迁移更为有效。在COMA中复制和迁移的颗粒度是高速缓存行,而在CCNUMA中是页;这使COMA中的假共享现象比CC-NUMA少。,哈尔滨工业大学计算机科学与技术学院,19,(6)NCC_NUMA和CC-NUMACOMA NCCNUMA系统比CCNUMA和COMA系统具有更
8、好的可扩展性NCC-NUMA系统没有对高速缓存一致性提供硬件支持CC-NUMA和COMA结构都提供了硬件支持。最有名的NCC-NUMA例子是Cray T3DT3E系统,它完全通过软件来保持地址空间的一致性,这既是机遇也同样是挑战。,哈尔滨工业大学计算机科学与技术学院,20,哈尔滨工业大学计算机科学与技术学院,21,二、基于目录的一致性协议高速缓存目录法的定义1.集中式目录;这种集中式目录只是适于集中式共享存储器的小规模SMP的高速缓存一致性控制。,哈尔滨工业大学计算机科学与技术学院,22,2.分布式目录 每个存储器模块维护了一个单独的目录来记录所有的高速缓存行的状态和当前信息。 目录项包含了高
9、速缓存行的状态和具有该行拷贝的所有远程高速缓存的位置信息。,哈尔滨工业大学计算机科学与技术学院,23,例题 用于高速缓存一致性控制的分布式目录 在下图中,共享存储器由多个存储器模块组成。每个存储器模块Mi,i=1,2,m,维护了一个高速缓存目录Di;该例表明了高速缓存C1和C2对相同高速缓存行的共享情况。,哈尔滨工业大学计算机科学与技术学院,24,哈尔滨工业大学计算机科学与技术学院,25,3.高速缓存目录结构全映射目录有限目录链式目录。,哈尔滨工业大学计算机科学与技术学院,26,4.全映射目录 该目录包含了在全局范围内共享的所有高速缓存行的信息。只有小规模的多处理机和多计算机系统可以使用这个办
10、法。,哈尔滨工业大学计算机科学与技术学院,27,哈尔滨工业大学计算机科学与技术学院,28,5.有限目录 如果任意一个数据块在高速缓存中同时存在的拷贝数目有一定限制,那么目录大小的增加不会超过一个常数。有限目录协议可以解决目录过大的问题。,哈尔滨工业大学计算机科学与技术学院,29,哈尔滨工业大学计算机科学与技术学院,30,6.链式目录 用指针链管理高速缓存目录。这种高速缓存一致性方法称为链式方法,它是通过维护一个目录指针链来跟踪共享数据拷贝的。 链式目录实现方法较简单的一种是单链法。,哈尔滨工业大学计算机科学与技术学院,31,哈尔滨工业大学计算机科学与技术学院,32,三、斯坦福Dash多处理机这
11、是在John Hennessy领导下由Stanford大学研制的CC-NUMA多处理器系统。Dash共享存储器的目录结构(directory architecturer shared memory)Dash的主要贡献在于它使用分布式一致性高速缓存和分布式存储器层次结构;建立L了具有单一地址空间的可扩展并行计算机成为可能。Dash在首先使用这种技术建立CCNUMA结构的同时保持了消息传递多处理机所具有的可扩展性。,哈尔滨工业大学计算机科学与技术学院,33,哈尔滨工业大学计算机科学与技术学院,34,Dash原型机 CPU:它在16个SGI SMP结点,每个SGI结点上有4个MIPS R3000R3
12、010处理器。共有64个微处理器,这种结点结构对Silicon Graphics的4D340 Power station作了少量修改。 在每个Power station结点上插入了两块特殊的子板,上面装有网络接口电路和连接到同一监听总线上,为4个处理器共享的高速缓存目录,哈尔滨工业大学计算机科学与技术学院,35,16个SGI结点中的互联网络是一对采用虫蚀路由方式的二维4x4网格型(Mesh)网络,由扁平线和虫蚀路由器组成,网格的通道带宽为16位,通过时间为50ns,而周期时间为35ns。请求网络用于向远程存储器发请求,而另一个则为应答网格。网格交点处的小方块表示由Charles Seitz主持
13、的Caltech大学研究组研制的虫蚀路由器。,哈尔滨工业大学计算机科学与技术学院,36,特殊硬件 Stanford大学的研究组对现有的系统板进行了微小的修改:设计了一对新板用于支持目录存储器和结点间消息传递。对现存CPU板的主要修改是增加了总线重试信号,用于某个请求需要获得远程结点服务。,哈尔滨工业大学计算机科学与技术学院,37,中央总线仲裁器也被修改为接受来自目录的屏蔽码,有效地为远程服务请求创建了分离事务(split-transaction)的总线协议,新的目录控制板包含了目录存储器,机群间一致性状态控制和状态缓存区,以及全局互联网络的本地部分。用于机群间事务的输出和输入部份而分割为两块逻
14、辑板。,哈尔滨工业大学计算机科学与技术学院,38,哈尔滨工业大学计算机科学与技术学院,39,哈尔滨工业大学计算机科学与技术学院,40,Dash的存储器层次结构 Dash系统的存储器共享在高速缓存行级完成。Dash通过分布式高速缓存目录机制实现了写无效一致性协议。,哈尔滨工业大学计算机科学与技术学院,41,在存储器中的高速缓存行或本地高速缓存中缓存的拷贝为以下3种状态之一:未缓存的不在任何结点机群的高速缓存中共享的在一个或多个结点机群的高速缓存中的未修改状态污染的仅在某个唯一结点机群的高速缓存中,并已被修改。,哈尔滨工业大学计算机科学与技术学院,42,目录保持了每一高速缓存行的概要信息,说明它的
15、状态和所有缓存它的结点机群,Dash存储器系统在逻辑上分为4个层次,如上图所示。,哈尔滨工业大学计算机科学与技术学院,43,四、Dash中基于目录的协议目录存储器使得处理器高速缓存不用再监听存储器请求。在宿主结点上,为每一高速缓存行帧都设有一个目录项,其中对每个处理器高速缓存都有一个存在标志位。有一个状态标志位指示该行是否为未缓存,或者由多个高速缓存共享的,还是由某个高速缓存独占(即该行是否是已污染的)。,哈尔滨工业大学计算机科学与技术学院,44,例:Dash多处理器的高速缓存目录协议 在下图中,描述了在目录项为污染(写无效)状态时,读请求如何传至远程存储器。读请求被转发至污染数据所在的结点,
16、后者发送两个消息作为应答:一个包含数据的消息被直接发送至提出请求的结点机群;而一个共享回写请求被发送至宿主机群,该请求将高速缓存行的内容回写至存储器并更新目录信息。,哈尔滨工业大学计算机科学与技术学院,45,哈尔滨工业大学计算机科学与技术学院,46,对某一需要远程服务的写操作的反应过程,哈尔滨工业大学计算机科学与技术学院,47,第5章 分布式存储器及其时延容忍,1 层次存储器技术2 高缓一致性协议3 共享存储器的一致性4 分布式高速缓存/主存体系结构5 时延容忍技术,哈尔滨工业大学计算机科学与技术学院,48,5 时延容忍技术,一.前言可扩展的多处理机和大规模多计算机机群必须使用各种机制以减少、避免和隐藏时延。将来的可扩展系统最有可能使用分布式共享存储器体系结构,从而对远程存储器的访问可能产生很长的时延,