第 7章 多处理机定义,具有两个以上的处理机，在操作系统的控制下，通过共享存储器或输入 /输出子系统或高速通信网络进行通信的系统。
7.1 多 处理机的特点及主要技术问题类别,多指令流多数据流 (MIMD)
1.与并行处理机的主要区别
结构灵活性
程序并行性
并行任务派生
1.与并行处理机的主要区别
进程同步
资源分配和任务调度
2.多处理机的主要技术问题
硬件结构的互连
发掘系统的并行性
任务和子任务的选择 — 粒度
任务进程同步问题
调度问题与死锁
容错 --系统重构
7.2 多处理机的硬件结构
7.2.1 紧耦合与松耦合方式
1,紧耦合多处理机
基本特征,共享主存实现多处理机间通信
类别,处理机不带专用 Cache和自带 Cache二种
基本组成结构
非对称 I/O子系统与冗余连接
实际举例自带 Cache的机器,IBM 3084 S-1
不带 Cache的机器,C.mmp
7.2.1 紧耦合与松耦合方式
2,松耦合多处理机
基本特征,通过通道互连或消息传输系统实现多处理机间通信
基本组成结构
通道和仲裁开关 CAS及其作用
消息传输系统 MTS的作用与分类作用,实现多处理机间的交换信息分类,单总线共享的存储器系统,存储模块和互连网络
实际举例 C*m
7.2.2 机间互连形式重要性
1,总线形式
总线系统效率的提高途径物理方法,先进的传输媒介多总线结构
公用总线访问冲突的解决方法 (仲裁算法 )
静态优先级固定时间片法动态优先级先来先服务算法
2.环形互连形式
结构
令牌 (Token)的作用
特点,
点到点通信,便于控制,适合光线通信接口会产生传输延迟
3.交叉开关形式
结构
作用
复杂性
结点开关形式
4.多端口存储器形式
结构
特点,系统复杂性在存储器模块中
场合,处理机数量较少时
应用举例
5.开关枢纽结构形式
结构形式
理想的拓扑结构
X-TREE
结点开关形式
7.2.3存储器组织简介
1,并行主存储器的构成
访问主存储器特点
高位交叉编址方式
低位交叉编址方式
并行主存储器的无冲突访问
7.2.3存储器组织简介
2,多 Cache与主存的信息一致性
不一致的产生原因
处理方法硬件,写作废法 /写更新 (播写法 )
软件,公用的写数据不进入 Cache
7.3 程序并行性
7.3.1 并行算法
1,算术表达式的并行运算
Horner法的问题
树形流程图运算级数 /树高 Tp 加速比 Sp 效率 Ep
Sp=T1/Tp
Ep=Sp / P
算术的运算规律与树高的降低
2,递归程序的并行性
7.3 程序并行性
7.3.2 程序并行性的分析
1,数据相关 类似流水线的“先写后读”
Pi A=B+D
Pj C=A*E
2,数据反相关 类似流水线的“先读后写”
Pi C=A+E
Pj A=B+D
3,数据输出相关
Pi A=B+D
Pj A=C+E
7.3 程序并行性
7.3.3 并行程序设计语言
1,并行程序分类
扩充的顺序型程序设计语言
并行语言
2,并行任务的派生与汇合
FORK 语句作用,派生并行任务形式,FORK m,m为 一新进程开始的标号具体功能,准备信息 ; 访存准备 ; 处理机分配 ; 执行原进程
2,并行任务的派生与汇合
JOIN 语句功能,汇合并发任务形式,JOIN n,n为已派生出的并发进程个数具体操作,通过计数器比较的方法确定汇合
举例计算表达式 Z=E+A*B*C/D+F
编译后得到并行程序,
S1 G=A*B
S2 H=C/D
S3 I=G*H
S4 J=E+F
S5 Z=I+J
利用 FORK 和 JOIN语句实现派生和汇合
FORK 20
10 G=A*B (进程 S1)
JOIN 2
GOTO 30
20 H=C/D (进程 S2)
JOIN 2
30 FORK 40
I=G*H (进程 S3)
JOIN 2
GOTO 50
40 J=E+F (进程 S4)
JOIN 2
50 Z=I+J (进程 S5)
E,W,Dijkstra对 FORK 和 JOIN语句的发展块结构式语言
cobegin-coend (或 parbegin-parend)的作用嵌套方法
7.5 多处理机的操作系统
7.5.1 多处理机操作系统的难度和特点
1.多处理机的操作系统的难度
多处理机的分配和进程调度不仅进行处理机的分配还要合理使用系统资源,使负荷均衡任务的并行性发掘
进程间的同步同步机制和算法
1.多处理机操作系统的难度
进程间的通信消息包存储转发的间接方式通信
存储器的管理访存地址的映象变换访存冲突的仲裁数据的一致性
文件系统的管理集中式 分散式 分布式
系统重组
2.多处理机操作系统的特点
程序执行的并行性
分布性任务上的分布资源上的分布控制上的分布
机间通信与同步性集中式 分散式 分布式
系统的容错动态切换和重新组合系统降级处理磁盘的容错 — 软件硬件来组建镜象盘
7.5.2,多处理机操作系统的类型
1,主从型 (Master-Slave Configuration)
实现方法
特点
实现场合
2,各自独立型 (Separate Supervisor)
实现方法及要求每个处理机均运行管理程序具有可再入性
特点
7.5.2,多处理机操作系统的类型
3,浮动型 (Floating Supervisor)
实现方法及要求每个处理机均可运行管理程序主控制程序可以从一台处理机转移到另一台处理机多台处理机执行管理程序
特点管理程序的可再入性表格和数据集的互斥
适用场合 紧耦合多处理机系统 同构型多处理机
7.1 多 处理机的特点及主要技术问题类别,多指令流多数据流 (MIMD)
1.与并行处理机的主要区别
结构灵活性
程序并行性
并行任务派生
1.与并行处理机的主要区别
进程同步
资源分配和任务调度
2.多处理机的主要技术问题
硬件结构的互连
发掘系统的并行性
任务和子任务的选择 — 粒度
任务进程同步问题
调度问题与死锁
容错 --系统重构
7.2 多处理机的硬件结构
7.2.1 紧耦合与松耦合方式
1,紧耦合多处理机
基本特征,共享主存实现多处理机间通信
类别,处理机不带专用 Cache和自带 Cache二种
基本组成结构
非对称 I/O子系统与冗余连接
实际举例自带 Cache的机器,IBM 3084 S-1
不带 Cache的机器,C.mmp
7.2.1 紧耦合与松耦合方式
2,松耦合多处理机
基本特征,通过通道互连或消息传输系统实现多处理机间通信
基本组成结构
通道和仲裁开关 CAS及其作用
消息传输系统 MTS的作用与分类作用,实现多处理机间的交换信息分类,单总线共享的存储器系统,存储模块和互连网络
实际举例 C*m
7.2.2 机间互连形式重要性
1,总线形式
总线系统效率的提高途径物理方法,先进的传输媒介多总线结构
公用总线访问冲突的解决方法 (仲裁算法 )
静态优先级固定时间片法动态优先级先来先服务算法
2.环形互连形式
结构
令牌 (Token)的作用
特点,
点到点通信,便于控制,适合光线通信接口会产生传输延迟
3.交叉开关形式
结构
作用
复杂性
结点开关形式
4.多端口存储器形式
结构
特点,系统复杂性在存储器模块中
场合,处理机数量较少时
应用举例
5.开关枢纽结构形式
结构形式
理想的拓扑结构
X-TREE
结点开关形式
7.2.3存储器组织简介
1,并行主存储器的构成
访问主存储器特点
高位交叉编址方式
低位交叉编址方式
并行主存储器的无冲突访问
7.2.3存储器组织简介
2,多 Cache与主存的信息一致性
不一致的产生原因
处理方法硬件,写作废法 /写更新 (播写法 )
软件,公用的写数据不进入 Cache
7.3 程序并行性
7.3.1 并行算法
1,算术表达式的并行运算
Horner法的问题
树形流程图运算级数 /树高 Tp 加速比 Sp 效率 Ep
Sp=T1/Tp
Ep=Sp / P
算术的运算规律与树高的降低
2,递归程序的并行性
7.3 程序并行性
7.3.2 程序并行性的分析
1,数据相关 类似流水线的“先写后读”
Pi A=B+D
Pj C=A*E
2,数据反相关 类似流水线的“先读后写”
Pi C=A+E
Pj A=B+D
3,数据输出相关
Pi A=B+D
Pj A=C+E
7.3 程序并行性
7.3.3 并行程序设计语言
1,并行程序分类
扩充的顺序型程序设计语言
并行语言
2,并行任务的派生与汇合
FORK 语句作用,派生并行任务形式,FORK m,m为 一新进程开始的标号具体功能,准备信息 ; 访存准备 ; 处理机分配 ; 执行原进程
2,并行任务的派生与汇合
JOIN 语句功能,汇合并发任务形式,JOIN n,n为已派生出的并发进程个数具体操作,通过计数器比较的方法确定汇合
举例计算表达式 Z=E+A*B*C/D+F
编译后得到并行程序,
S1 G=A*B
S2 H=C/D
S3 I=G*H
S4 J=E+F
S5 Z=I+J
利用 FORK 和 JOIN语句实现派生和汇合
FORK 20
10 G=A*B (进程 S1)
JOIN 2
GOTO 30
20 H=C/D (进程 S2)
JOIN 2
30 FORK 40
I=G*H (进程 S3)
JOIN 2
GOTO 50
40 J=E+F (进程 S4)
JOIN 2
50 Z=I+J (进程 S5)
E,W,Dijkstra对 FORK 和 JOIN语句的发展块结构式语言
cobegin-coend (或 parbegin-parend)的作用嵌套方法
7.5 多处理机的操作系统
7.5.1 多处理机操作系统的难度和特点
1.多处理机的操作系统的难度
多处理机的分配和进程调度不仅进行处理机的分配还要合理使用系统资源,使负荷均衡任务的并行性发掘
进程间的同步同步机制和算法
1.多处理机操作系统的难度
进程间的通信消息包存储转发的间接方式通信
存储器的管理访存地址的映象变换访存冲突的仲裁数据的一致性
文件系统的管理集中式 分散式 分布式
系统重组
2.多处理机操作系统的特点
程序执行的并行性
分布性任务上的分布资源上的分布控制上的分布
机间通信与同步性集中式 分散式 分布式
系统的容错动态切换和重新组合系统降级处理磁盘的容错 — 软件硬件来组建镜象盘
7.5.2,多处理机操作系统的类型
1,主从型 (Master-Slave Configuration)
实现方法
特点
实现场合
2,各自独立型 (Separate Supervisor)
实现方法及要求每个处理机均运行管理程序具有可再入性
特点
7.5.2,多处理机操作系统的类型
3,浮动型 (Floating Supervisor)
实现方法及要求每个处理机均可运行管理程序主控制程序可以从一台处理机转移到另一台处理机多台处理机执行管理程序
特点管理程序的可再入性表格和数据集的互斥
适用场合 紧耦合多处理机系统 同构型多处理机
