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