计算机系统机构 ppt 第7章

7.1.2互连函数
0 1 2 ... N-1 f(0) f(1) f(2)...f(N-1)

循环表示法: 把互连函数f(x)表示为： (x0，x1，...，xj) (xk，xk+1，...，xl) ... 表示对应关系为: f(x0)=x1，f(x1)=x2，...，f(xj)=x0 j+1称为该循环的长度
计算机系统结构
第一章 第二章 第三章 第四章 第五章 第六章 第七章 第八章 第九章

基本概念 指令系统 存储系统 输入输出系统 标量处理机 向量处理机 互连网络 并行处理机 多处理机
1
第七章 互连网络 互连网络是一种由开关元件按照一定的拓扑结构和控制方式 构成的网络

用于实现计算机系统内部多个处理机或多个功能部件之间的 相互连接
2
11
4、均匀洗牌置换Perfect shuffle
S ( x n 1 x n 2 ... x 1 x 0 ) x n 2 x n 3 ... x 1 x 0 x n 1
把二进制结点循环左移一位。 子混洗(subshuffle)S(k) 最低k位循环左移一位 超混洗牌(supershuffle) S(k) 最高k位循环左移一位
5

具有本地存储器、私有高速缓存、共享存储器和共享外围设 备的一般处理机系统的互连结构
SM1 SM2 …… SMm (共享存储器) (共享I/O与外设) Cn LM C1 LM P1 …… IPCN Pn PION …… 磁盘 磁带 打印机 终端 网络 … IPMN ……
IPMN(处理机-存储器网络) PION(处理机-I/O网络) IPCN (处理机之间通信网络) P(处理机) C(高速缓冲存储器) SM(共享存储器) LM(本地存储器)
0 1 2 3 4 5 6 7
A
8、加减2i置换 通常采用移数函数可以构成环型网(包括单向环网、双向环网、 弦环网)、方格网、移数网等。 例如，Illiac函数是构成Illiac IV阵列的基础，它包含PM20和 PM2n/2等四个互连函数。 采用全部移数函数构成网络称为移数网，移数网的结点度 d=2n-1，网络直径D=n/2

其他互连函数还有：方体置换、均匀洗牌置换、蝶式置换、 位序颠倒置换、移数置换、加减2i置换
9
3、方体置换Cube
C k ( x n 1 ... x k 1 x k x k 1 ... x 1 x 0 ) x n 1 ... x k 1 x k x k 1 ... x 1 x 0
i i
其中：0 x N-1，0 i n-1，n = log2 N。
0 1 2 3 4 5 6 7 ｉ＝0 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 i＝ + 1 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 i＝ + 2
18
0 1 2 3 4 5 6 7
19
7.1.3互连网络的特性和传输的性能参数 1 互连网络的特性 互连网络通常是用有向边或无向边连接有限个结点的组成。 互连网络的主要特性有 (1) 网络规模：网络中结点的个数 (2) 结点度：与结点相连接的边数称为结点度。包括入度和 出度。 进入结点的边数叫入度，从结点出来的边数则叫出度 (3) 距离：两个结点之间相连的最少边数 (4) 网络直径：网络中任意两个结点间距离的最大值。 用结点间的连接边数表示

6
互连函数 将互连网的N个输入和N个输出端分别用整数(0, 1, 2, ..., N-1)来表示，则表示相互连接的输出端号和输入端号之间 的一一对应关系 表示方法： 互连函数法，图形表示法, 输入输出对应表示法 函数表示法： x表示输入端号，常用n位二进制形式表示 xn-1xn-2...x1x0 f(x)表示互连函数，为：f(xn-1xn-2...x1x0 ) 图形表示法: 用图形表示输入和输出端之间的连接 输入输出对应(矩阵)表示法：

(k )
( x n 1 x n 2 ... x n k x n k 1 ... x 1 x 0 ) = x n k x n k 1 ... x n 2 x n 1 x n k 1 ... x 1 x 0
对于n=3的情况，正好有 R=B，R(2)=B(2)，R(2)=B(2)。
12
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
4、均匀洗牌置换Perfect shuffle
0 1 2 3 4 5 6 7 子 洗 牌 置 换 S (2) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 超洗牌置换S
(2)
0 1 2
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
(x
n 1
显然成立：
S S
(n)
( x ) S (n) ( x ) S ( x ) ( x ) S (1 ) ( x ) x
(1 )
逆混洗函数：
S
1
( x n 1 x n 2 ... x 1 x 0 ) x 0 x n 1 x n 2 ... x 1
教材P397L2,3,6错
7
常用的互连函数如下：

1 恒等置换： I( xn-1xn-2 ... x1x0 )= xn-1xn-2 ...x1x0
8
2 交换置换Exchange

实现二进制地址编号中第0位位值不同的输入和输出端之间 的连接。 E(xn-1xn-2 ... x1x0 )= xn-1xn-2 ... x1x0
16
7、移数置换

将输入端数组循环移动一定的位置向输出端传输。
A ( x ) ( x k ) mod N , 0 x N

也可以将整个输入数组分成若干个子数组，在子数组内进行 循环移数置换，这种段内循环移数的表达式可写成为两个式 A ( x ) ( n 1 ):r ( x ) ( n 1 ):r 子如下：

10
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
ቤተ መጻሕፍቲ ባይዱ
CE 0 交 换 函 数 0
CE 1 交 换 函 数 1
E C 2交换函数
变化发生在 0，1，2位 分别是高 2，1，0位相同的为一个组 组内加/减 1，2，4

当n=3时，共有3种函数，每种函数能够表示8个结点之间的 连接关系。
C 0 ( x 2 x1 x 0 ) x 2 x1 x 0 C 1 ( x 2 x1 x 0 ) x 2 x1 x 0 C 2 ( x 2 x1 x 0 ) x 2 x1 x 0
由于交换函数主要用于超立方体互连网中，因此也称为超立 方体函数，用Cube表示，如：Cube0、Cube1、Cube2等。 用交换函数构成的互连网络的结点度为n，网络直径也为n。
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 B
(2 ) (2 )
0 1 2 3 4 5 6 7 =R 函数
B (2 )= R (2 )函 数
与全混洗函数类似，只用蝶式函数也不能实现任意结点之间 的互连。
15
6、位序颠倒置换Bit Reversal 将输入端二进制地址的位序反过来就得相应输出的地址。
B B
(n)
显然成立
( x ) B(n) ( x ) B ( x ) ( x ) B (1 ) ( x ) x
(1 )

教材P398L1,2错
14
5、蝶式置换Butterfly
0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7 B＝ R函 数
0 1 2 3 4 5 6 7

S (k) (x S
(k)
n 1
x n 2 ... x k x k -1 x k - 2 ... x 1 x 0 ) = x n 1 x n 2 ... x k x k 2 ... x 1 x 0 x k -1 x n 2 ... x n k x n k 1 ... x 1 x 0 ) = x n 2 ... x n k x n 1 x n k 1 ... x 1 x 0
-1
3 4 5 6 7
均匀洗牌置换
逆均匀洗牌置换S
子洗牌是将整组数据分成若干个子组，对每个子组完成均匀 洗牌变换。S(2) 分两组0，1，2，3；4，5，6，7 只用均匀洗牌函数不能实现任意结点之间的互连 通常用均匀洗牌函数与其他函数，如交换函数一起构成互 连网络。 均匀洗牌与逆均匀洗牌是两种十分有用的互连函数 以它们代表的链路与以交换置换代表的开关多级组合起来 可构成Omega(Ω)网络与逆Omega(Ω^-1)网络。 逆均匀洗牌是均匀洗牌的逆函数，两者的输入端和输出端 13 正好互换
2
第七章 互连网络
互连网络的基本概念 消息传递机制

3
7.1 互连网络的基本概念
互连网络的作用 互连函数 互连网络的特性和传输的性能参数 互连网络的种类

4
7.1.1互连网络的作用 用来实现计算机系统内部多个处理机或多个功能部件之间的 相互连接。 为并行处理系统的核心组成部分。 对整个计算机系统的性能价格比有着决定性的影响。

5、蝶式置换Butterfly

蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样。
B ( x n 1 x n 2 ... x 1 x 0 ) x 0 x n 2 ... x 1 x n 1