16
总线仲裁算法
计 算
机
系
❖ 静态优先级算法：为每一个连到总线的部件分配一
统 结
固定的优先级，例如：串行链接、独立请求结构 构
❖ 固定时间片算法：把总线按固定大小时间片，轮流 提供给部件使用
适合同步总线，时钟同步
❖ 动态优先级算法：让总线上各部件优先级可根据情 况按一定规则动态地改变
近期最少使用法，循环串行链法
存中同一个信息块在多个Cache中都有时，会出
现信息块内容不一致情况；
❖写直达法---保证一个；
进程迁移----将一个尚未执行完而被挂起的进程 调度到另一个空闲的处理机上去执行；
通过输入/输出操作改变内存
32
多Cache的一致性问题的解决办法
计 算
机
系
❖ 1 解决进程迁移引起的多Cache不一致性
22
计 算 机 系 统 结 构
四端口存储器形式的结构
23
蠕虫穿洞寻径网络
计 算
机
系
❖ 机间采用小容量缓冲存储器，实现消息分组
统 结
寻径存储转发之用
构
❖ 曙光1000多处理机
24
开关枢纽结构形式
计 算
机
系
❖ 把互连结构的开关设置在各个处理机或其接
统 结
口内部，组成分布式结构。
构
❖ 美国加州大学伯克利分校设计的树形多处理 机X-TREE
结 构
全映象目录表法
❖ 表中每项有N个标志位对应于多处理机中全部N台处理机的Cache。 系统中全部Cache均可同时存有同一个信息块的副本。
有限目录表法
❖ 表中每项的标志位少于N个。因此，限制了一个数据块在各 Cache中能存放的副本数目。
链式目录表法
❖ 它把目录分散存放在各个Cache中，主存只存有一个指针，指向 一台处理机。要查找所有放有同一个信息块的Cache时，先找到 一台处理机的Cache，然后顺链逐台查找，直到找到目录表中的 指针为空时为止。
❖ 高位交叉：按物理地址顺序从模块0到模块 m-1依次连续分布。
连续
多处理机中采用高位交叉；
27
模块0 0 m
im
模块1 1
m+1
im+1
计
模块m-1
算 机
m-1
系 统
2m-1
结 构
(i+1)m-1
(n-1)*m
(n-1)*m+1
模块内部单元号 模块号
log2n
log2m
m个模块的低位交叉编址
n*m-1
❖ 使用场合：使用于在处理机机数很多的分布 式多处理机场合
25
3 存储器的组织
计 算
机
系
❖ 并行存储器的构成
统 结
❖ 多Cache的一致性问题
构
26
并行存储器的构成
计 算
机
系
❖ 有高位交叉和低位交叉
统 结
❖低位交叉：按物理地址顺序轮流地分布在 构
各个存储模块中。
不连续，步距为m
向量、流水或阵列处理机中采用低位交叉
统 结
不同处理机间或者通过通道互连实现通信， 构
以共享某些外部设备；或者通过消息传送系
统（MTS）连接来交换信息。
❖ 可看成分布系统；
12
计 算 机 系 统 结 构
通过消息传送系统连接的松耦合多处理机结构
13
计
算
机
❖ 处理机之间的连接频带比较低
系
统
通过输入输出接口连接,处理机间互为外围设备进行连接
❖ 当通信速度要求更高时，可以通过一个通道和仲裁 开关CAS（Channel and Arbiter Switch）直接载存储 器总线之间建立连接。CAS中有一个高速的通信缓 冲存储器。
14
2 机间互联形式
计 算
机
系
❖ 总线ቤተ መጻሕፍቲ ባይዱ式
统 结
❖ 环形互连形式
构
❖ 交叉开关形式
❖ 多端口存储器形式
❖ 蠕虫穿洞寻径网络
36
3 以软件为基础解决Cache一致性
计 算
机
系
❖ 利用软件限制,不把一些公用的可写数据存入
统 结
Cache中
构
❖ 例编译时,把信息分为能存入Cache和不能存 入Cache的两部分
37
小结
计 算
机
系
❖ 硬件方法------通讯量大，处理机数多时复杂；统 结
❖ 软件方法------减少复杂，降低通讯量，性能 构
❖ 使用场合：处理机机数较多的场合
20
计 算 机 系 统 结 构
交叉开关形式
21
多端口存储器形式
计 算
机
系
❖ 如果每个存储器模块有多个访问端口，且将
统 结
分布在交叉开关矩阵中的控制、转换和优先 构
级仲裁逻辑分别移到相应存储器模块的接口
中，就构成多端口存储器形式。
❖ 使用场合：机数少的多处理机场合
算 机
系
❖ 监视Cache协议（Snoopy Protocol）法:
统 结
各个处理机中的Cache控制器随时都在监视着其 构
它Cache的行动。对于采用总线互连共享主存的
多处理机， 可利用总线的播送来实现。
写作废法、写更新法
35
计
算
机
❖ 目录表法:
系 统
建立目录表,有选择的通知其它Cache该信息块作废或更新
2
§7.1多处理机的概念、问题和硬件结构
计 算
机
系
❖ 定义：多处理机具有两个以上的处理机，在
统 结
操作系统控制下，通过共享的主存或输入/ 构
输出子系统或高速通信网络进行通信。
多任务处理，协同求解，提高速度；
利用冗余，提高可靠性、适应性、可用性。
❖ 组成分类：同构型、异构型、分布型
❖ 属于多指令流、多数据流系统（MIMD)
28
模块0 0 1
i
模块1 n
n+1
n+i
计
模块m-1
算 机
(m-1)*n
系
统
(m-1)*n+1 结 构
(m-1)n+i
n-1
2n-1
模块号 模块内部单元号
log2m
log2n
m个模块的高位交叉编址
M*n-1
29
计
算
机
系
❖ 本地存储器（HomeMemory）：放置处理机
统 结
执行进程要用到的绝大多数页面的那个存储 构
3
计 算 机 系 统 结 构
计 算 机 系 统 结 构
多处理机存在的技术问题
计 算
机
系
❖ 硬件结构上如何解决处理机、存储器模块及I/O子 统
系统之间的互连
结 构
❖ 如何最大限度地开发系统的并行性，实现多处理机 各级的全面并行；
❖ 如何分割任务的大小，任务的粒度大小；
❖ 如何协调好处理机中各并行执行的任务和进程间的 同步问题；
结
例如，IBM公司的机器，都可以通过通道到通道的连接器CTC把两个 构
不同计算机系统的IOP连接起来。
❖ 通过并口或串口把多台计算机连接起来
例如，用串口加一个MODEL拨号上网，也可以直接连接；多台计算 机之间的连接需要有多个接口。
❖ 通过Ethernet网络接口连接多台计算机 速度达10Mb、 100Mb、1Gb，Mynet已经达到1.28Gb和2.56Gb。
统 结
❖ 2 以硬件为基础实现多Cache的一致性
构
❖ 3 以软件为基础实现多Cache的一致性
33
计
1 解决进程迁移引起的多Cache不一致性
算 机
系
❖ 对于进程迁移的Cache不一致性----禁止进程
统 结
迁移, 或者进程挂起时，用硬件强行把Cache 构
块写回主存；
34
计
2 以硬件为基础实现多Cache的一致性
❖ 如何将各个任务分配到一个或多个处理机上，解决 好处理机调度、任务调度和资源分配问题，防止死 锁；
❖ 系统发生故障，系统如何重新组织，正常工作
6
多处理机的硬件结构
计 算
机
系
❖ 紧耦合和松耦合
统 结
❖ 机间互联形式----性能的重要因素
构
❖ 存储器组织
7
1 紧耦合多处理机
计 算
机
系
❖ 是通过共享主存来实现处理机间通讯，通信
❖ 开关枢纽结构形式
15
总线形式
计 算
机
系
❖ 多个处理机、存储器模块和外围设备通过接口与公
统 结
用总线相连，采用分时或多路转接技术传送。 构
❖ 结构简单，成本低，增减模块方便，但对总线的 失效敏感。
❖ 提高总线的系统效率方法：
采用优质高频同轴电缆，使用光纤； 采用多总线方式减少冲突概率；
❖ 使用场合：只使用处理机数较少的场合
❖ 先来先服务算法：按接受到访问总线请求先后顺序 来响应
17
环形互连形式
计 算
机
系
❖ 总线形成环形互连。
统 结
❖ 令牌（Token）
构
❖ 点点连接，物理参数容易控制
❖ 使用场合：高通信带宽的光纤通信；
❖ 总线形式必须在原来的信息不在总线上时， 才可以发送新的信息。环形不需要如此。
18
计 算 机 系 统 结 构
通过映象部件MM把处理机访问逻辑地址变换 成局部物理地址、主存地址、Cache
通过互连网络寻找合适的路径，并分解访问存 储器的冲突