- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
用来实现计算机系统内部多个处理机或 多个功能部件之间的相互连接。 互连网络已成为并行处理系统的核心组 成部分。 互连网络对整个计算机系统的性能价格 比有着决定性的影响。 如图7.2具有本地存储器、私有高速缓存、 共享存储器和共享外围设备的一般处 理机系统的互连结构
3
多处理机系统框图
P1
P2
P3
Pn
（7）超立方体网（也称 n 维立方体）
超立方体网由N＝2n 个结点组成, 分布在n维上, 每维有两个结点
超立方体网结点度为n，直径也为n，每个结点 由n个二进制数实行编号，相邻结点只能有一个 1010 数字不同，
Y 10 11 010 110 011
1110 1000 1100
1011
1111
111
σk(xn-1,xn-2,...,xk,...x1,x0)= xn-1,xn-2,... ,xk+1, xk-1,...x1,x0 ,xk
σk(xn-1,xn-2,... ,xn-k,xn-k-1, xn-k-2,...x1,x0)= xn-2,... ,xn-k,xn-k-1, xn-1, xn-k-2,...x1,x0
17
7.1.3互连网络特性和传输的性能参数
1.互连网络的特性
互连网络通常是用有向边或无向边连接 有限个结点的组成。 互连网络的主要特性有： (1) 网络规模：网络中结点的个数 (2) 结点度：与结点相连接的边数称为结 点度。包括入度和出度。进入结点的边 数叫入度，从结点出来的边数则叫出度 (3) 距离：两个结点之间相连的最少边数
18
(4) 网络直径：网络中任意两个结点间距 离的最大值。用结点间的连接边数表示 (5)等分宽度:当某一网络被切成相等的两 半时,沿切口的最小边数
(6) 结点间的线长：两个结点间连线的 长度。用米等表示 (7) 对称性：从任何结点看到拓扑结构 都是一样的网络称为对称网络。对称网 络比较易实现，编程也较容易。
22
例7.1：
假设一个网络的频宽为10Mbps，发送 方开销为230μs，接收方开销为270μs。 如果两台机器相距100m，现在要发送 一个1000Byte的消息给另一台机器，试 计算总时延。如果两台机器相距1000公 里，那么总时延为多大？
解：
光的速度为299792.5KM/S，信号在导 体中传递速度大约是光速的50％，相距 100米时总时延为：
19
2.互连网络传输的性能参数
发送方数据发送的步骤如下：
机器间通信示意图
(1) 用户程序把要发送的数据拷贝到操作系统的缓冲区。 (2) 操作系统把缓冲区中的数据打包(计算检查和)，启动超时 计数器,并发送到网络接口部件。 (3) 网络接口硬件开始发送消息。
接受方数据包的接收步骤如下：
(1) 把数据包从网络接口部件拷贝到操作系统缓冲区。 (2) 检查收到的数据包，如果检查和匹配则正确，给接收方发 回答信号。若不正确,删除此消息. (3) 把接收到的数据拷贝到用户地址空间。并启动应用程序继 续执行,发送方接收到回答信号后，释放系统缓冲区.若超时则 20 重发.
（5）二叉胖树的结点度从叶子结点往根结点 逐渐增加。胖树缓解了一般二叉树根结 点通信速度高的矛盾。
星形网 二叉胖树网
32
（6）二维网格
是一种比较流行的网络结构，有各种变体形 式。在Illiac IV、MPP、DAP、CM-2和 Intel Paragon等。
一般的二维网格，N＝n1×n2 个结点组成，直径是 D=（n1 –1）+（n2 –1） 实际上经常是n1=n2 =n。 1 2 3 结点的编号就是结点在网络 4 5 6 中地址，十分重要。 路由算法与此有关。
N1 N2 N3 N4 N5 Nn-1 Nn 28
（2）环形网
单向环行网：右环网，直径是D=N-1 双向环行网：又称为一维邻居网，直径 D=N/2 ，它们的结点度都是常数d=2 将结点度由2提高至3，可得到弦环网。增加的 弦愈多，则结点度愈高，网络直径愈小。还有 全连网（D=1）和循环移数网络等 循环移数网络将环上每个结点与其距离为2的整 数幂的结点之间连接构成。循环移数网的网络 规模是2n ，结点度为2n-1，直径为D=n/2。 （例如：结点数64，n=6，d=11，D=3）
相距1000公里时的总时延为：
1000 10 6 1000 8 T 230 s s s 270 s 0.5 299792 .5 10 = 230 s 6671 s 800 s 270 s = 7971 s
24
7.1.4 互连网络的种类
1 、静态互连网络
等于飞行时间与传输时间之和。
21
(5) 发送方开销(Sender overhead)：
处理器把消息放到互连网络的时间。
(6) 接收方开销(Receiver overhead)：
处理器把消息从网络取出来的时间。
(7) 一个消息的总时延用下面公式表示： 总时延＝ 发送方开销＋ 飞行时间＋ 消息长度/频宽＋ 接收方开销
000 001 101 X
0010 0110 0000 0100
1001 1101
0011
0111
00
互连网络在传输方面的 主要性能参数：
(1) 频带宽度(Bandwidth)：
互连网络传输信息的最大速率。
(2) 传输时间(Transmission time)：
等于消息长度除以频宽。
(3) 飞行时间(Time of flight)：
第一位信息到达接收方所花费的时间。
(4) 传输时延(Transport latency)：
0 0
1 2 3 4 5 6 7
1 2 3 4 5 6 7
8
2、交换置换
E(xn-1,xn-2,......x1,x0)= xn-1,xn-2,......x1,x0 n=8 的交换置换
0 0
1 2 3 4 5 6 7
1 2 3 4 5 6 7
9
3、方体置换
Ck(xn-1,xn-2,...,xk,...x1,x0)= xn-1,xn-2,... ,xk,...x1,x0 C0(x2,x1,x0)= x2, x1,x0 C1(x2,x1,x0)= x2, x1,x0
23
相距100m时的总时延为：
消息长度 T 发送方开销 飞行时间 接收方开销 频宽 0.1Km 1000 8位 230 s 270 s 0.5 299792 .5Km / s 10兆位/秒 230 s 0.67 s 800 s 270 s 1301 s
第七章 互连网络
本章主要内容：并行处理机和 多处理机系统中的互连网络
7.1 互连网络的基本概念 7.2 消息传递机制 7.3 互连网络实例
1
7.1 互连网络的基本概念
7.1.1 互连网络的作用 7.1.2 互连函数 7.1.3 互连网络特性和传输的性能参数 7.1.4 互连网络的种类
2
7.1.1 互连网络的作用
1 、静态互连网络
在各结点之间有固定的连接通路，在运行 过程中不能改变的网络结构。一维的有 线性阵列结构；二维的有环形、星形、 树形、网格形等；三维的有立方体等； 三维以上的有超立方体等。
27
（1）线性阵列
•结点度等于2 •n个结点，直径为n-1。 •线性阵列结构最简单，但网络的延迟 比较大，N1有信息发送到Nn必需通过所 有其他结点。
2、 动态互连网络
3 、其他分类
25
互连网络的种类很多，分类方法也很多，总 的来说可以分为静态互连网络和动态互连 网络两大类 1、静态互连网络：连接通路是固定的，在运 行的过程中不能改变连接通路结构。按拓 朴结构又可分为一维、二维、三维等。 2、动态互连网络：连接通路是可变的，结点 之间的连接可以重新配置。一般由开关和 连线组成，通过控制开关来建立不同的连 接。 26
29
0 7 6 5 环形网
1 2 7 3 6 4
0
1
0
1 2 3
2
3
7 6 5 4 循环移数网
5 4 度为3的弦环网
0 7 6 5 全连通 4 1 2 3
30
（3）树形和星形网
一棵k层二叉树有N＝2k－1个结点，结点 度是3，直径是2(k-1)。
二叉树网
31
（4）星形是一种特殊的2层树，结点度很高， 为d=N-1，直径是2。
12
(实际k=1)
用于构造Ω网络
13
用于构造Ω-1网络 σ-1(xn-1,xn-2,....x1,x0)= x0xn-1xn-2...x1
14
5、蝶式置换
β(xn-1,xn-2,...,xk,...x1,x0)= x0 , xn-2,... ,xk,...x1, xn-1
βk(xn-1,xn-2,...,xk,...x1,x0)= xn-1,xn-2,... ,xk+1, x0 , xk-1,...x1, xk βk(xn-1,xn-2,... ,xn-k,xn-k-1, xn-k-2,...x1,x0)= xn-k-1, xn-2,... ,xn-k, xn-1, xn-k-2,...x1,x0
环形二维网格
Illiac网格
34
Illiac网络的结点连接 按一定的算法进行: Illiac+1(j)=(j+1)mod(N) Illiac-1(j)=(j-1)mod(N) Illiac+n(j)=(j+n)mod(N) Illiac-n(j)=(j-n)mod(N)
例如： Illiac+1(4)=(4+1)mod(16)=5 Illiac+n(4)=(4+4)mod(16)=8 Illiac-1(4)=(4-1)mod(16)=3 Illiac-n(4)=(4-4)mod(16)=0 35
