第 12章 互连网络与多处理机本章主要内容：
本章介绍多个处理机与多个计算机系统的互连网络基本概念,特性,种类,基本互连网络和多处理机互连网络,对于计算技术和通信技术结合的远程网也作了简单的介绍 。 最后讲述多处理机的结构和特点,机群系统以及多处理机的性能分析等内容 。 学习时主要掌握互连网络的连接方式及其特点和结构,掌握典型的寻径算法,并对典型实例有一定的了解 。
12.1 互连网络的基本概念
12.2 静态互连网络
12.3 动态互连网络
12.4 互连网络的消息传递机制
12.5 多处理机系统特点与分类
12.6 典型的多处理机系统
12.7 机 群 系 统
12.1 互连网络的基本概念
12.1.1 互连网络在计算机系统中的作用图 12-1 互连网络的连接结构结点 结点 结点 结点链路 链路 链路 链路软件接口硬件接口软件接口硬件接口软件接口硬件接口软件接口硬件接口互连网络
12.1.2 主要特性和性能参数
1,互连网络的特性
（ 1）网络规模
（ 2）结点度
（ 3）结点距离
（ 4）网络直径
（ 5）等分宽度
（ 6）结点间线长
（ 7）网络对称性
（ 8）可扩展性
2,传输性能参数
（ 1）频宽
（ 2）传输时间
（ 3）,飞行,时间
（ 4）发送方开销
（ 5）接收方开销
（ 6）总时延图 12-3 互连网络的传输性能参数发送开始接收结束传输时间发送方开销 传输时间 在
“飞行”时间 传输时间 接收方开销总时延发送第 1 位 发送最后 1 位最后 1 位到达接收方第 1 位到达接收方
12.1.3 互连函数
1,恒等置换
I(xn?1 xn?2 xn?3…… x1 x0)= xn?1 xn?2
xn?3…… x1 x0
2,交换置换 （ Exchange Permutation）
E(xn?1 xn?2 xn?3…… x1 x0)= xn?1 xn?2
xn?3…… x1
3,方体置换 （ Cube Permutation）
Ck(xn?1 xn?2… xk+1 xk xk?1… x1 x0)= xn?1
xn?2 … xk+1xk?1… x1 x0
4,均匀洗牌置换 （ Perfect Shuffle
Permutation）
σ(xn?1 xn?2…… x1 x0)= xn?2 xn?3…… x1 x0 xn?1
5,蝶式置换 （ Butterfly Permutation）
β(xn?1 xn?2…… x1 x0)= x0xn?1 xn?2 …… x1
xn?1
6,位 序 颠 倒 置 换 （ Bit Reversal
Permutation）
ρ(xn?1 xn?2…… x1 x0)= x0x1 x2…… xn?2 xn?1
7,移数置换 （ Shift Permutation）
αx= (X+k) modN,0≤ x≤ N
8,加减 2i置换
PM2+i(X)=(X+2i)modN
PM2?i(X)=(X?2i)mod N
12.1.4 互连网络的种类
1,共享介质的网络
2,非阻塞网络
3,直接网络
4,间接网络
5,混合网络图 12-11 互连网络的分类混合网络单总线双总线令 牌环总线争用总线底板总线总线环共享介质的网络非阻塞网络二维网络交换开关共享存储网络空分总线
Clos e 网间接网络
( 基于开关的网络 )
规则拓扑非规则拓扑单向 M IN
双向 M IN
单向环互连网络直接网络
（基于寻径器的网络）
超立方体网络二维网络三维网络网格网络环形网络双向环形网单向环形网二维环形网三维环形网一维环形网
12.2 静态互连网络
12.2.1 静态互连网络结构
1,一维线性阵列
2,环和带弦环
3,循环移数网络
4,树形和胖树形
5,网格形与环形网格
6,超立方体和带环立方体
7,k元 n立方体
12.2.2 静态互连网络特性表 12-1 静态网络的性能一览表网络类型结点度 d
网络直径 D
链路数 l
等分带宽 B
对称性网络规格评注线性阵列
2 N?1 N?1 1 非 N个结点环形 2 N /2 N 2 是 N个结点全连接 N?1 1 N(N?
1)/2
(N/2)2 是 N个结点二叉树 3 2(h?1) N?1 1 非 树高 h=log2 N
星形 N?1 2 N?1 (N/2) 非 N个结点
2D网络 4 2(r?1) 2N?2
r
r 非 r× r网络,N=
r2
Illiac网 4 r?1 2N 2r 非 与 N= r2的带弦环等效
2D环网 4 2(r/2) 2N 2r 是 r× r环网,N=
r2
超立方体
n n nN/2 N/2 是 N 个结点,
n=log2 N(维数 )
带环立方体
3 2k?1+k/2 3N/2 N/(2k) 是 N= k× 2k个结点,环长 ≥ 3
k 元 n 立方体
2n n( k/2) nN 2kn-1 是 N=kn个结点
12.3 动态互连网络
12.3.1 动态互连网络的互连形式
1,基于公共介质的互连
2,交叉开关
3,多级互连
（ 1） 开关模块
（ 2） 级间连接模式
（ 3） 控制方式
12.3.2 多级互连网络
1,?网络 （ Omega网络 ）
2,STARAN网络
3,基准网络
4,间接二进制 n方体网络
5,Benes二进制置换网络
6,多级 Close网络
Benes网络的置换函数表达式为：
σ σ
EEEE nn 1)1(1 )2(1 )1( -- -- - E?)1(
En )1( -
12.4 互连网络的消息传递机制
12.4.1 消息寻径
1,消息的格式图 12-34 消息的组织方式包 i +1 包 i 包 i - 1
数据片 数据片? 数据片 顺序号 寻径片 包消息
2,寻径方式
（ 1） 线路交换 （ Circuit Switch）
（ 2） 存储转发 （ Store and Forward）
（ 3） 虚拟直通 （ Virtual Cut Through）
（ 4） 虫蚀寻径 （ Wormhole）
12.4.2 死锁和虚拟通道
1,虚拟通道
2,死锁的产生
3,死锁的避免
12.4.3 单播方式的寻径
1．包阻塞及其应对措施
2．固定寻径方式
3．自适应寻径
12.4.4 广播方式下的寻径
（ 1）单播模式
（ 2）选播模式
（ 3）广播模式
（ 4）会议模式
12.5 多处理机系统特点与分类
12.5.1 基本结构图 12-43 多处理机系统的两种基本结构互连网络
I /O
I /O
存储器存储器存储器处理机 1
处理机 2
处理机 n
互连网络
I /O
存储器处理机 1
I /O
存储器处理机 2
I /O
存储器处理机 n
（ b ） （ a ）共享存储器的多处理机结构 （ b ）分布式存储器的多处理机结构
12.5.2 多处理机系统特点
（ 1）结构灵活性和功能通用性
（ 2）主要开发高层次作业及任务级（粗粒度）
并行性
（ 3）并行任务的派生需要用显式的专用语句或指令加以表示
（ 4）并发执行的进程间的同步需要采取特殊的措施
（ 5）对资源和任务分配如果要进行良好的调度
（ 6） MIMD计算机系统在执行条件语句时
（ 7） MIMD系统的异步特性使得它在执行完成时间可变的指令时,比 SIMD具有更高的效率 。
12.5.3 多处理机系统的 Cache一致性问题
1,产生 Cache一致性问题的原因
（ 1） 共享可写数据引起的不一致性
（ 2） 进程迁移引起的不一致性
2,解决 Cache一致性问题的方法
（ 1） 以硬件为基础的方法
（ 2） 以软件为基础的方法
12.6 典型的多处理机系统
12.6.1 MPP大规模并行多处理机系统
12.6.2 CM-5系统
1,CM-5的系统结构
2,CM-5的网络结构
（ 1）数据网络
（ 2） 控制网络
（ 3） 诊断网络
3,控制处理机和处理结点
12.6.3 SGI Origin 2000系列服务器互连网络（ In t er co nn ec t i on Net work ）
处理器 1
Cache
主存
Mai n Mem or y
处理器 2
Cache
主存
Mai n Mem or y
处理器 n
Cache
主存
Mai n Mem or y
图 12-53 S2MP系统的体系结构
1,SGI Origin 2000系列服务器性能
2,SGI Origin 2000服务器结构
3,存储组织
12.7 机 群 系 统
12.7.1 机群系统的结构特点
（ 1）系统开发周期短
（ 2）系统价格低
（ 3）用户投资风险小
（ 4）节约系统资源
（ 5）系统的可扩展性好
（ 6）用户编程方便
12.7.2 机群系统的关键技术
1,高效的通信系统
2,并行程序开发环境
3,多种语言支持
4,全局资源的管理与应用
5,机群负载平衡技术
12.7.3 几种典型的机群系统
本章介绍多个处理机与多个计算机系统的互连网络基本概念,特性,种类,基本互连网络和多处理机互连网络,对于计算技术和通信技术结合的远程网也作了简单的介绍 。 最后讲述多处理机的结构和特点,机群系统以及多处理机的性能分析等内容 。 学习时主要掌握互连网络的连接方式及其特点和结构,掌握典型的寻径算法,并对典型实例有一定的了解 。
12.1 互连网络的基本概念
12.2 静态互连网络
12.3 动态互连网络
12.4 互连网络的消息传递机制
12.5 多处理机系统特点与分类
12.6 典型的多处理机系统
12.7 机 群 系 统
12.1 互连网络的基本概念
12.1.1 互连网络在计算机系统中的作用图 12-1 互连网络的连接结构结点 结点 结点 结点链路 链路 链路 链路软件接口硬件接口软件接口硬件接口软件接口硬件接口软件接口硬件接口互连网络
12.1.2 主要特性和性能参数
1,互连网络的特性
（ 1）网络规模
（ 2）结点度
（ 3）结点距离
（ 4）网络直径
（ 5）等分宽度
（ 6）结点间线长
（ 7）网络对称性
（ 8）可扩展性
2,传输性能参数
（ 1）频宽
（ 2）传输时间
（ 3）,飞行,时间
（ 4）发送方开销
（ 5）接收方开销
（ 6）总时延图 12-3 互连网络的传输性能参数发送开始接收结束传输时间发送方开销 传输时间 在
“飞行”时间 传输时间 接收方开销总时延发送第 1 位 发送最后 1 位最后 1 位到达接收方第 1 位到达接收方
12.1.3 互连函数
1,恒等置换
I(xn?1 xn?2 xn?3…… x1 x0)= xn?1 xn?2
xn?3…… x1 x0
2,交换置换 （ Exchange Permutation）
E(xn?1 xn?2 xn?3…… x1 x0)= xn?1 xn?2
xn?3…… x1
3,方体置换 （ Cube Permutation）
Ck(xn?1 xn?2… xk+1 xk xk?1… x1 x0)= xn?1
xn?2 … xk+1xk?1… x1 x0
4,均匀洗牌置换 （ Perfect Shuffle
Permutation）
σ(xn?1 xn?2…… x1 x0)= xn?2 xn?3…… x1 x0 xn?1
5,蝶式置换 （ Butterfly Permutation）
β(xn?1 xn?2…… x1 x0)= x0xn?1 xn?2 …… x1
xn?1
6,位 序 颠 倒 置 换 （ Bit Reversal
Permutation）
ρ(xn?1 xn?2…… x1 x0)= x0x1 x2…… xn?2 xn?1
7,移数置换 （ Shift Permutation）
αx= (X+k) modN,0≤ x≤ N
8,加减 2i置换
PM2+i(X)=(X+2i)modN
PM2?i(X)=(X?2i)mod N
12.1.4 互连网络的种类
1,共享介质的网络
2,非阻塞网络
3,直接网络
4,间接网络
5,混合网络图 12-11 互连网络的分类混合网络单总线双总线令 牌环总线争用总线底板总线总线环共享介质的网络非阻塞网络二维网络交换开关共享存储网络空分总线
Clos e 网间接网络
( 基于开关的网络 )
规则拓扑非规则拓扑单向 M IN
双向 M IN
单向环互连网络直接网络
（基于寻径器的网络）
超立方体网络二维网络三维网络网格网络环形网络双向环形网单向环形网二维环形网三维环形网一维环形网
12.2 静态互连网络
12.2.1 静态互连网络结构
1,一维线性阵列
2,环和带弦环
3,循环移数网络
4,树形和胖树形
5,网格形与环形网格
6,超立方体和带环立方体
7,k元 n立方体
12.2.2 静态互连网络特性表 12-1 静态网络的性能一览表网络类型结点度 d
网络直径 D
链路数 l
等分带宽 B
对称性网络规格评注线性阵列
2 N?1 N?1 1 非 N个结点环形 2 N /2 N 2 是 N个结点全连接 N?1 1 N(N?
1)/2
(N/2)2 是 N个结点二叉树 3 2(h?1) N?1 1 非 树高 h=log2 N
星形 N?1 2 N?1 (N/2) 非 N个结点
2D网络 4 2(r?1) 2N?2
r
r 非 r× r网络,N=
r2
Illiac网 4 r?1 2N 2r 非 与 N= r2的带弦环等效
2D环网 4 2(r/2) 2N 2r 是 r× r环网,N=
r2
超立方体
n n nN/2 N/2 是 N 个结点,
n=log2 N(维数 )
带环立方体
3 2k?1+k/2 3N/2 N/(2k) 是 N= k× 2k个结点,环长 ≥ 3
k 元 n 立方体
2n n( k/2) nN 2kn-1 是 N=kn个结点
12.3 动态互连网络
12.3.1 动态互连网络的互连形式
1,基于公共介质的互连
2,交叉开关
3,多级互连
（ 1） 开关模块
（ 2） 级间连接模式
（ 3） 控制方式
12.3.2 多级互连网络
1,?网络 （ Omega网络 ）
2,STARAN网络
3,基准网络
4,间接二进制 n方体网络
5,Benes二进制置换网络
6,多级 Close网络
Benes网络的置换函数表达式为：
σ σ
EEEE nn 1)1(1 )2(1 )1( -- -- - E?)1(
En )1( -
12.4 互连网络的消息传递机制
12.4.1 消息寻径
1,消息的格式图 12-34 消息的组织方式包 i +1 包 i 包 i - 1
数据片 数据片? 数据片 顺序号 寻径片 包消息
2,寻径方式
（ 1） 线路交换 （ Circuit Switch）
（ 2） 存储转发 （ Store and Forward）
（ 3） 虚拟直通 （ Virtual Cut Through）
（ 4） 虫蚀寻径 （ Wormhole）
12.4.2 死锁和虚拟通道
1,虚拟通道
2,死锁的产生
3,死锁的避免
12.4.3 单播方式的寻径
1．包阻塞及其应对措施
2．固定寻径方式
3．自适应寻径
12.4.4 广播方式下的寻径
（ 1）单播模式
（ 2）选播模式
（ 3）广播模式
（ 4）会议模式
12.5 多处理机系统特点与分类
12.5.1 基本结构图 12-43 多处理机系统的两种基本结构互连网络
I /O
I /O
存储器存储器存储器处理机 1
处理机 2
处理机 n
互连网络
I /O
存储器处理机 1
I /O
存储器处理机 2
I /O
存储器处理机 n
（ b ） （ a ）共享存储器的多处理机结构 （ b ）分布式存储器的多处理机结构
12.5.2 多处理机系统特点
（ 1）结构灵活性和功能通用性
（ 2）主要开发高层次作业及任务级（粗粒度）
并行性
（ 3）并行任务的派生需要用显式的专用语句或指令加以表示
（ 4）并发执行的进程间的同步需要采取特殊的措施
（ 5）对资源和任务分配如果要进行良好的调度
（ 6） MIMD计算机系统在执行条件语句时
（ 7） MIMD系统的异步特性使得它在执行完成时间可变的指令时,比 SIMD具有更高的效率 。
12.5.3 多处理机系统的 Cache一致性问题
1,产生 Cache一致性问题的原因
（ 1） 共享可写数据引起的不一致性
（ 2） 进程迁移引起的不一致性
2,解决 Cache一致性问题的方法
（ 1） 以硬件为基础的方法
（ 2） 以软件为基础的方法
12.6 典型的多处理机系统
12.6.1 MPP大规模并行多处理机系统
12.6.2 CM-5系统
1,CM-5的系统结构
2,CM-5的网络结构
（ 1）数据网络
（ 2） 控制网络
（ 3） 诊断网络
3,控制处理机和处理结点
12.6.3 SGI Origin 2000系列服务器互连网络（ In t er co nn ec t i on Net work ）
处理器 1
Cache
主存
Mai n Mem or y
处理器 2
Cache
主存
Mai n Mem or y
处理器 n
Cache
主存
Mai n Mem or y
图 12-53 S2MP系统的体系结构
1,SGI Origin 2000系列服务器性能
2,SGI Origin 2000服务器结构
3,存储组织
12.7 机 群 系 统
12.7.1 机群系统的结构特点
（ 1）系统开发周期短
（ 2）系统价格低
（ 3）用户投资风险小
（ 4）节约系统资源
（ 5）系统的可扩展性好
（ 6）用户编程方便
12.7.2 机群系统的关键技术
1,高效的通信系统
2,并行程序开发环境
3,多种语言支持
4,全局资源的管理与应用
5,机群负载平衡技术
12.7.3 几种典型的机群系统
