五、加速比的概念
加速比的常规定义
加速比概念的延伸
六、非线性流水线的概念
非线性流水线的预约表
延迟禁止表
初始冲突向量
状态转移图：调度方案, 平均延迟
七, 指令级高级并行超级处理机
超标量处理机
超长指令字处理机
超流水线处理机
处理机并行的度
第六章 多机系统
§1概述
一, 并行性概念
并行性是指在执行任务过程中可同时进行的运算或操作 。
1,开发并行性的目的
提高计算机的运行效率
2,并行性的含义
具有双重含义：同时性与并发性
同时性是指两个或两个以上的事件在同一时刻发生 。
并发性是指两个或两个以上的事件在同一时间间隔内
发生 。
3.并行性的意义
1） 并行意味着有多个事件在并行执行, 当这
多个事件都在完成同一性质的处理时, 意味着
单位时间完成的结果数增加了, 从而可提高对
数据处理速度 。
2） 并行同样意味着多个事件中并行处理, 当
这些处理都在为一个目的工作时, 从提高可靠
性出发, 按多数表决法, 对多数得出的相同结
果具有高的可靠性 。
3） 并行也可能意味着要增加硬件成本, 因而
需根据性能价格比来评价这种开销是否合理 。
二, 从单机向多机发展的三条途径
2? ?÷á ÷? ? ??
μ¤ oú ?μ í3
?· á? á÷? ? ??
1ê á÷? ? ??
ò? ? Dí μ?
?- oú ?μ í3
?- ′￥ àì 2? ?t ?? ?
í? ? Dí ?- oú ?μ í3
￡¨? ü à¨2 ￠ D ê? ?￠
?ó áD ê? ?- oú ?μ í3
ó? ?￠ D? Dí oú ′ú ì? Dé
?a oú
?? 2? ê? ?- oú ?μ í3
′? ′￠ ?÷? - ì? ?? ?
?- ó? o§? ? êa? μ í3
Dé ?a oú 2o í? ·? ?? ??
? μ? ?? ?? oú ?μ í3
êa? ? ?× μt
?ê ?′ ?2 ?ì
?ê ?′ ?× ·′
o? a- ?? ? ￡?
C ?? ? ?? ??
oú ?μ í3
?并行处理的四个等级,
? 单机流水处理中一条指令内多个操作的并行处理 ;
? 并行处理机多条相同指令的并行处理（指令间） ;
? 多处理机多个任务的并行处理 ;
? 多计算机系统多程序（作业）的并行处理。
三, 多机系统的耦合度
1.何谓耦合度
多机之间相互的通信控制能力或相互依赖程
度, 称为多机之间的耦合度 。
2.三种耦合度
1） 最低耦合：多机之间几乎没有共享设备, 如仅用二,
三条线连接起来的计算机 。 （ 如 RS232C通信 ） 。
2） 松散耦合：多机之间有一定的共享设备, 如大型的
主机与外围机, 它们之间共享受主存, I/O通道 。 但它
们之间也可相对独立工作, 又如连接在网络上的计算机,
连接在局域网上的计算机共享硬盘 。 处理机间一般通过
消息传递系统交换信息, 也有通过通道互联实现处理机
间的通讯 。
3） 紧密耦合：耦合度最高, 相互依赖很强, 如阵列式
多处理机的 CU（ 控制部件 ） 和 PU（ 处理部件 ） 之间 。 通
过共享主存实现处理机间的通讯, 通讯速率受限于主存
频宽 。
四, 多机系统的分类及特点
多机系统指的是多处理机系统和多计算机系统 。
1.多处理机系统
1） 各处理机共享 I/O通道 。
2） 属于紧耦合 。
3） 表现形式有,
并行 (阵列 )式多处理机系统；
分布式多处理机系统 。
2.多计算机系统
1）各处理机具有自己的 I/O通道和主存
2）属于最低耦合或松耦合
3） 典型表现为计算机网络。
§2 多处理机系统
一,伊（ ILLIAC） IV阵列式
多处理机系统
1,总体结构：最初设计具有
四个象限的阵列式多处理机
系统，其中,CU为阵列控制
部件,A为阵列处理部件。
CU1
A1
CU2
A2
CU4
A4
CU3
A3
I/O CH2,CU的主要功能
1） 对指令进行译码。
2） 向阵列处理部件 A发出公共地址、公共数据。
3）向 A发出各种控制命令。
CU应当具备高性能的标量处理能力，否则将制约整个
阵列处理机的性能。
3 阵列处理部件 A
1） 由 64个 PU组成, 且排列成 8*8的阵列结构 。
PU0 PU1 PU7
PU56
PU57 PU63
PU8
PU63
PU8 PU9 PU15 PU16
PU7
PU56 PU57 PU63 PU0
PU55
PU0 PU1
PU7
2 ） 各 PU在水平方向上按 a1进行连接, 且以 64为模,
称为水平螺旋连接 。
3） 各 PU在竖直方向上按 a8进行连接, 也以 64为模,
称为竖直圆柱连接 。
（ 在本节的互连网络中, 这种连接采用何种互连函
数, 将会介绍 ）
3 阵列存储器
1） 每个 PU除它们共享的主存外, 各 PU还有自己的局
部存储器 。 （ 其总容量是 2K?64个局部存储器 （ PEM0
?PEM63） 共有 2K?64=128K）
2） 由于局部存储器随阵列分布, 因此又称为阵列分
布存储器 。
二, 阵列式多处理机适应的算法
1,二维调和函数的求解
二维调和函数的求解 U(x,y):满足二维拉普拉斯方程的函
数, 即
其中,h是网格点的间距, (x,y)为网格点坐标 。
利用此法计算, 又称为平滑或滤波, 目的是消除偶然干扰 。
4
hyxuyhxuhyxuyhxu
yxu
h
hyxuyxu2hyxu
y
u
h
yhxuyxu2yhxu
x
u
0
y
u
x
u
22
2
22
2
2
2
2
2
),(),(),(),(
),(
),(),(),(
),(),(),(
???????
?
?????
?
?
?
?????
?
?
?
?
?
?
?
?
?
所以
2 矩阵加
1） 有如下两个矩阵
63 57 56
15 9 8
7 1 0
a a a
a a a
a a a
A
…
… … … …
…
…
?
63 57 56
15 9 8
7 1 0
b b b
b b b
b b b
B
…
… … … …
…
…
?
63 57 56
15 9 8
7 1 0
c c c
c c c
c c c
C
…
… … … …
…
…
?
计算 C=A+B
则,c0=a0+b0 c1=a1+b1
… c63=a63+b63
2） 阵列存储器分配
每个局部存储器占用三个单元
c0
b0
a0
|?
|?
PEM0
k+0
k+1
k+2
c1
b1
a1
|?
|?
PEM1
c63
b63
a63
|?
|?
PEM63
k+0
k+1
k+2
k+0
k+1
k+2
|
3）完成矩阵的加运算
CU向各 PU发出有关命令,
①公共地址 K+0和（取操
作数）读命令。
因此各 PU从 K+0单元中分
别取出 A阵列数据 a0~a63。
② 第二个公共地址 K+1和
取操作数，各 PU又将 K+1单
元中的 b0~b63取出。
③ CU向各 PU发出求和命令，各 PU将取出的 ai及 bi求和，即 ci=ai+ bi。
④ CU第三次向各 PU 发出公共地址 K+2和写命令，各 PU将 ci存入
K+2单元
3 矩阵乘
用阵列式多处理机完成矩阵乘法，不如阵列流水线处
理机，因为用矩阵乘法运算比矩阵加法复杂，对阵列多
处理机各部件的利用率不如矩阵加。
4 可加速累加和的形式（与单机比较）
1）计算
?
?
?
7
0i
iaS
① S1=a0+a1 ② S2=a2+a3
③ S3=a4+a5 ④ S4=a6+a7
⑤ S5=S1+S2 ⑥ S6=S3+S4
⑦ S=S5+S6
2）参数存放
3） 计算过程
① PU0,PU1,PU2,PU3分别取出 a0,a2,a4,a6；
② PU0,PU1,PU2,PU3再分别取出 a1,a3,a5,a7；
③ 四个 PU分别求和计算得 S1,S2 S3,S4；
④ PU1→PU0 由 PU0计算 S1+S2,PU3→PU2, 由 PU2计算
S3+S4；
⑤ PU2→PU0 由 PU0计算 S。
a1
a0
PEM0
k+0
k+1
k+2
a3
a2
k+0
k+1
k+2
a5
a4
PEM2
k+0
k+1
k+2
PEM3
a7
a6
k+0
k+1
k+2
PEM1
三, SIMD互连网络
1,概述
1） 互连：实现处理机之间相互连接, 称互连 。
2） 互连网络：实现处理机之间相互连接的某种拓扑
结构的逻辑电路, 称互连网络 。
3） 互连函数：实现处理机之间相互连接的某种拓扑
结构的逻辑函数, 称互连函数 。
4） 对互连网络的评价
① 要有利于实现；
② 要有一定的通信频带；
③ 要有一定的灵活性, 可实现多种连接通信 。
5） 互连网络的主要类型
① 从性质上分
Ⅰ ） 立方体 （ cube） 互连网络
Ⅱ ） PM2I互连网络
Ⅲ ） 混洗交换 互连网络
② 从级数多少来分
Ⅰ ） 单级 互连网络
Ⅱ ） 循环 互连网络 （ 物理一级但可实现多级 ）
Ⅲ ） 多级 互连网络
6） 互连函数中, 部件 （ 或处理机 ） 的编码 。
设用 n 位二进制来表示部件编码, 即有,Pn-1Pn-
2… P2P1P0
当用 3位二进制数表示时 （ 即 n=3） 则有：
P2P1P0
2,单级立方体 （ Cube） 互连网络
1） 立方体互连函数 （ 设 n=3）
① Cube0:仅在第 0位上的代码取反, 其余各
位不变 。
Cube0（ P2P1P0） = P2P1P0
② Cube1,仅在第 1位上的代码取反, 其余各
位不变 。
Cube1（ P2P1P0） = P2P1 P0
③ Cube2,仅在第 2位上的代码取反，其余各
位不变。
Cube2（ P2P1P0） = P2P1 P0
2） 实现的连接关系
Cube0 Cube1 Cube2
P2P1P0 P2P1P0 P2P1 P0 P 2P1 P0
0 0 0 0 0 1 0 1 0 1 0 0
0 0 1 0 0 0 0 1 1 1 0 1
0 1 0 0 1 1 0 0 0 1 1 0
0 1 1 0 1 0 0 0 1 1 1 1
1 0 0 1 0 1 1 1 0 0 0 0
1 0 1 1 0 0 1 1 1 0 0 1
1 1 0 1 1 1 1 0 0 0 1 0
1 1 1 1 1 0 1 0 1 0 1 1
① Cube0可实现 8个部件 （ 处理单元 ）, 在 x方向连接 。
② Cube1可实现 8个部件 （ 处理单元 ）, 在 y方向连接 。
③ Cube2可实现 8个部件 （ 处理单元 ）, 在 z方向连接 。
0
x
54
6
7
3
1
2
11
98
12
10
14
z
y
15
13
3）当 n=4时，有 P3P2P1P0, 则
Cube3（ P3P2P1P0 ） =P3 P2P1 P0
用 Cube3可将两个立方体连接起来，构成一个立方
体组（四维空间）。
当 n=5时，有 P4P3P2P1P0, 则
Cube4（ P4P3P2P1P0） = P4 P3 P2P1 P0
用 Cube4可将两个立方体组连接起来，构成一个立
方体群（五维空间）。
4）互连网络的链接关系图
3,单级 PM2I互连网络 （ Plus-Minus2i）
1） PM2I互连函数
① PM2+i( j )=j+2i
② PM2-i( j )=j-2i
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
Cube1Cube0 Cube2
2） 实现的连接关系 （ 设 j分别为 0～ 7,以 8为模 。 ）
j j+20 j-20
0 1 7
1 2 0
2 3 1
3 4 2
4 5 3
5 6 4
6 7 5
7 0 6
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
PM2+0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
PM2-0
伊 Ⅳ 机在水平连接采用 PM2+0,PM2-0（ 双向）且以
64为模。
3） PM2a1
① PM2+1( j )=j+21=j+2
② PM2-1( j )=j-21=j-2
4） 当 I=3时, 有
① PM2+3( j )=j+8
② PM2-3 ( j )=j-8
伊 Ⅳ 阵列式多处理机, 在竖直方向上的连接采用
PM2a3以 64为模 。
所以, 伊 Ⅳ 共采用了 PM2a0和 PM2a3实现相互连接
（ 以 64为模 ） 。
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
PM2+1
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
PM2-1
§1概述
并行性概念
并行性的意义
从单机向多机发展的三条途径
多机系统的耦合度
§2 多处理机系统
伊（ ILLIAC） IV阵列式多处理机系统
阵列式多处理机适应的算法
SIMD互连网络
互连, 互连网络, 互连函数
互连网络的主要类型
立方体 （ Cube） 互连网络
PM2I互连网络
4,单级混洗交换互连网络
1） 立方体和 PM2I互连函数太规整, 为了实现具有随意性
连接, 采用混洗 。
2） 混洗互连函数,Sh(Pn-1Pn-2┅ P1P0)=Pn-2Pn-3┅ P1P0Pn-1即
循环左移一位, n=3时
Sh(P2P1P0) = P1P0P2
0 0 0 0 0 0
0 0 1 0 1 0
0 1 0 1 0 0
0 1 1 1 1 0
1 0 0 0 0 1
1 0 1 0 1 1
1 1 0 1 0 1
1 1 1 1 1 1
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
3） 利用混洗互连网函数将 8个部件分为互不相联的四组,
如下图,0； 1,2,4； 3,5,6； 7
1 2 30 5 6 74
4）在混洗基础上加入 Cube0的交换，即构成混洗交换互
连函数。
0?1 2?3 4?5 6?7
可将 8个部件实现相互通信。
Cube0(Shuffle(bn-1…b 0))=Cube0(bn-2…b 0bn-1)= bn-2…b 0bn-1
5,循环互连网络
1） 构成：由单级互连
网络多路开关
（ MUX） 和输入寄存
器 （ IR） 组成 。
2） 目的：利用对单级
互连网的重复使用,
在一定程度上模拟互
连网络的功能 。
3） 特点,
单
级
互
连
网
络
IR0
IR1
IR2
IR3
MUX
MUX
PU0
PU0
PU1
PU1
输出0
输出1
C1
C2
①结构简单，易于实现。
② 对单级互连网络的重复使用，往往是机械重复，灵
活性差。
③重复加入时，重复频率受到限制。
6,描述多级互连网络的参数
1） 交换单元的功能
交换单元：是一个具有两个输入, 两个输出和一个
控制端的五端开关 。
I1
I2
O 1
O 2
G
① 双功能交换单元：具有直通和交换两种功能 。
I1
I2
O 1
O 2
G=00
I1
I2
O 1
O 2
G=01
② 四功能交换单元 （ G为两位 ）,除上述的直通,
交换外, 还有上播, 下播两种 。
2） 拓扑结构
拓扑结构 是 各级间出端与入端互连的模式。前述各种
单级互连网络的连接模式均可用来组合构成不同的多级互
连网络。
解决在级与级之间采用何种规则连接，通常采用级间
对号连接，如三级 立方体互联网络,
I1
I2
O 1
O 2
G=10
I1
I2
O 1
O 2
G=11
0
1
0
1
G C u b e 0
2
3
2
3
G
4
5
4
5
G
6
7
6
7
G
一级
0
2
0
2
1
3
1
3
G
4
6
4
6
G
5
7
5
7
G
二级
0
4
0
4
1
5
1
5
G
2
6
2
6
G
3
7
3
7
G
三级
G C u b e 1 G C u b e 2
3） 控制方式
① 级控制方式：同一级的所
有交换单元只用一个控制
信号控制 。
② 单元控制方式：同一级的
每个交换单元各有各的独
立控制信号 。
③ 部分级控制方式：介于 ①
② 两种控制方式之间, 对
同一级交换单元来讲, 控
制信号的数目 ≥ 2个, 但小
于交换单元数 。
G
G0
G1
G2
G3
7,采用双功能交换单元级控制方式的三级立方体互连网络
1） 网络构成：由 Cube0,Cube1,Cube2三级构成 （ 要求画出 3*4=12
个交换单元的三级立方体互连网络图 ） 。
0
1
0
1
G0
2
3
2
3
G0
4
5
4
5
G0
6
7
6
7
G0
一级
0
2
0
2
G1
1
3
1
3
G1
4
6
4
6
G1
5
7
5
7
G1
二级
0
4
0
4
G2
1
5
1
5
G2
2
6
2
6
G2
3
7
3
7
G2
三级
C u b e 0 C u b e 1 C u b e 2
2） 写出控制信号 G2G1G0实现的连接关系表 。
3） 画出控制信号 G2G1G0实现的连接关系图 。
4） 写出控制信号 G2G1G0实现的连接名称 。
入端号
G 2 G 1 G 0
0 1 2 3 4 5 6 7
连接关系名称
0 0 0 0 1 2 3 4 5 6 7
直通或恒等
0 0 1 1 0 3 2 5 4 7 6
四组二元交换
0 1 0 2 3 0 1 6 7 4 5 二组四元加四组二元交换
0 1 1 3 2 1 0 7 6 5 4 二组四元
1 0 0 4 5 6 7 0 1 2 3 一组八元加二组四元交换
1 0 1 5 4 7 6 1 0 3 2 4, 2 & 2.4 & 1.8
1 1 0 6 7 4 5 2 3 0 1 四组二元加一组八元交换
1 1 1 7 6 5 4 3 2 1 0 一组八元交换
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
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
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
G 2 G 1 G 0 = 0 0 0 G 2 G 1 G 0 = 0 1 1G 2 G 1 G 0 = 0 1 0G 2 G 1 G 0 = 0 0 1
G 2 G 1 G 0 = 1 0 0 G 2 G 1 G 0 = 1 1 1G 2 G 1 G 0 = 1 1 0G 2 G 1 G 0 = 1 0 1
8,采用级控和部分级控相结合的三级立方体
互连网络 —— 移数网络
1） 网络构成：也由 Cube0,Cube1,Cube2三级
构成 。
2） 控制方式
① 第一级采用级控制方式 （ G0） 。
② 第二级采用部分级控制方式 （ G1G2） 。
③ 第三级采用部分级控制方式 （ G3G4G5） 。
2
3
G0
1
3
G2
4
5
G0
4
6
G1
0
1
G0
0
2
G1
6
7
G0
5
7
G2
1
5
G4
2
6
G5
0
4
G3
3
7
G5
2
3
4
5
0
1
6
7
1
5
2
6
0
4
3
7
1
3
4
6
0
2
5
7
3） 控制信号 （ G5~G0） 与连接关系表, 连接关系图和
移数名称 。
入端号
G 5 G 4 G 3 G 2 G 1 G 0
0 1 2 3 4 5 6 7
移数名称
0 0 0 0 0 0 0 1 2 3 4 5 6 7 直通
0 0 0 0 0 1 1 0 3 2 5 4 7 6 移 1 模 2
0 0 0 0 1 1 1 2 3 0 5 6 7 4
移 1 模 4
0 0 0 1 1 0 2 3 0 1 6 7 4 5 移 2 模 4
0 0 1 0 1 1 1 2 3 4 5 6 7 0 移 1 模 8
0 1 1 1 1 0 2 3 4 5 6 7 0 1 移 2 模 8
1 1 1 0 0 0 4 5 6 7 0 1 2 3 移 4 模 8
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
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
000011 000110000001 111000011110001011
9,采用四功能交换单元, 级控制方式的三级立方体实
现广播式通信
1） 网络构成：也由 Cube0,Cube1,Cube2三级构成 。
2） 实现某个部件向所有部件进行广播式通信 （ 如 4#部
件 ） 。
① 写出有关交换单元的功能 。
② 画出完成广播式通信的通信线路图 。
③ 写出控制信号 G2G1G0。
例：实现 4#部件向 0～ 7部件 完成广播式通信 。
第一级交换单元 C上播,G0=10
第二级交换单元 GH上播,G1=10
第三级交换单元 IJKL下播,G2=11
0
1
0
1
G0
B
2
3
2
3
4
5
4
5
D
6
7
6
7
E
0
2
0
2
G1
F
1
3
1
3
G
4
6
4
6
5
7
5
7
0
4
0
4
G2
J
1
5
1
5
2
6
2
6
3
7
3
7
Cube0
Cube1 Cube2
H
I
A
K
L
C
10.三级立方体互连网络对以下两组部件同时通信
能力分析
1） 第一组部件,0→ 5与 1→ 7同时通信 。
0→ 5号部件通信,A交换 F直通 J交换
1→ 7号部件通信,A直通 F交换 J交换
同时对 A,F两个交换单元有矛盾要求, 所以不能
同时实现 0→ 5,1→ 7同时通信 。
2） 第二组部件,5→ 0,7→ 1
5→ 0号部件通信,C交换 G直通 I交换
7→ 1号部件通信,D直通 H交换 J交换
没有对交换单元矛盾要求, 但第一, 二级要采用
部分控 制方式或单元控制方式才可同时通信 。
0
1
0
1
G0
B
2
3
2
3
C
4
5
4
5
D
6
7
6
7
E
0
2
0
2
G1
F
1
3
1
3
G
4
6
4
6
H
5
7
5
7
I
0
4
0
4
G2
J
1
5
1
5
K
2
6
2
6
L
3
7
3
7
C u b e 0
C u b e 1 C u b e 2
A
4,单级混洗交换互连网络
5,循环互连网络
6,描述多级互连网络的参量
1）交换单元的功能
2）拓扑结构
3）控制方式
7.采用双功能交换单元级控制方式的三级立方体互连网络
8,采用级控和部分级控相结合的三级立方体互连网络 ——
移数网络
9,采用四功能交换单元, 级控制方式的三级立方体实现广
播式通信
10.三级立方体互连网络对以下两组部件同时通信能力分
析
11,四级立方体互连网络
1） 网络构成：由 Cube0～ cube3四级构成 （ 共 4*8=32
个交换单元 ） 。
2）四功能交换单元，广播式通信。例,5号对 0～ 15
号广播式通信,
① 第一级 A下播,G0=11
② 第二级 B,C上播,G1=10
③ 第三级 D～ G下播,G2=11
④ 第四级 H～ O上播,G3=10 即
G3G2G1G0=10111011B
3） 控制信号 G3G2G1G0与连接关系表, 连接关系图及
连接关系名称 。
0
1
0
1
G0
2
3
2
3
4
5
4
5
6
7
6
7
0
2
0
2
G1
1
3
1
3
4
6
4
6
5
7
5
7
0
4
0
4
G2
1
5
1
5
2
6
2
6
3
7
3
7
8
9
8
9
10
11
10
11
12
13
12
13
14
15
14
15
8
10
8
10
9
11
9
11
12
14
12
14
13
15
13
15
8
12
8
12
9
13
9
13
10
14
10
14
11
15
11
15
0
8
0
8
G3
1
9
1
9
2
10
2
10
3
11
3
11
4
12
4
12
5
13
5
13
6
14
6
14
7
15
7
15
Cube0
Cube1 Cube2 Cube3
B
C
H
I
J
K
L
M
N
O
A
D
E
F
G
入端号 G 3 G 2 G 1 G 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 5
连接关系名称
0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 5 直通或恒等
0 0 0 1 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 八组二元交换
0 0 1 0 2 3 0 1 6 7 4 5 10 11 8 9 14 1 5 1 2 13 8.2 ⊕ 4.4
0 0 1 1 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 四组四元
0 1 1 1 7 6 5 4 3 2 1 0 15 14 1 3 1 2 1 1 1 0 9 8 二组八元
1 0 0 0 8 9 10 11 12 1 3 1 4 1 5 0 1 2 3 4 5 6 7 2.8 ⊕ 1.16
1 1 1 1 1 5 1 4 1 3 1 2 1 1 10 9 8 7 6 5 4 3 2 1 0 一组十六元
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
0011G3G2G1G0=0010 0001
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0111
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
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
1000 1111
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
12,三级混洗交换互连网络
1） 网络构成：也由 Cube2,Cube1,Cube0三级构
成, 但与三级立方体互连网络有以下两点区别：
① Cube0与 Cube2的位置互换 （ 第一级是 Cube2，
第三级是 Cube0）
② Cube1中间两个交换单元位置互换 。
其目的是使级间连接形式与混洗连接一致 。
（ 混洗循环左移一位 ）
I
0
1
0
1
G0
J
2
3
2
3
G0
K
4
5
4
5
G0
L
6
7
6
7
G0
A
0
4
0
4
G2
B
1
5
1
5
G2
C
2
6
2
6
G2
D
3
7
3
7
G2
E
0
2
0
2
G1
F
4
6
4
6
G1
G
1
3
1
3
G1
H
5
7
5
7
G1
μù òo ?? μù ?t ?? μù èy ??
Cube2
Cube1 Cube0
2） 对以下两组部件同时通信能力分析 。
① 0→ 5, 1→ 7
0→ 5,A交换 F直通 K交换
1→ 7,B交换 H交换 L直通
对交换单元无矛盾要求, 但第二, 三级需采用部分级控
制或单元控制 。
② 5→ 0, 7→ 1
5→ 0,B交换 G直通 I交换
7→ 1,D交换 G交换 I直通
对 G,I交换单元有矛盾要求, 因此不能同时通信 。 （ 与
三级立方体正好相反 —— 逆网络 ）
3） 三级混洗交换互连网络的控制信号 G2G1G0与连接关系
表, 关系图, 连接名称与三级立方体相似 。 （ 略 ）
13,全排列互连网络
1） 网络构成：由三级立方体与三级混洗交换互连网络构
成 。
I
0
1
0
1
G
J
2
3
2
3
G
K
4
5
4
5
G
L
6
7
6
7
G
M
0
2
0
2
G
N
1
3
1
3
G
P
4
6
4
6
G
Q
5
7
5
7
G
R
0
4
0
4
G
S
1
5
1
5
G
T
2
6
2
6
G
U
3
7
3
7
G
A
0
4
0
4
G
B
1
5
1
5
G
C
2
6
2
6
G
D
3
7
3
7
G
E
0
2
0
2
G
F
4
6
4
6
G
G
1
3
1
3
G
H
5
7
5
7
G
èy ?? o? ?′ ?o o í? ?? èy ?? á￠ ?? ì? o¤ á? í? ??
2） 对 0→ 5,1→ 7同时通信能力分析 。
0→ 5,A交换 F直通 K交换 Q直通 S直通
1→ 7,B直通 G直通 I直通 N交换 U交换
无对交换单元矛盾要求, 但级控不行, 单元控, 部分
级控可以 。
（ 可以有两条以上通路,
B交换 H直通 K直通 Q交换 U直通
B交换 H交换 L直通 Q直通 U直通 ）
3） 对 5→ 0,7→ 1同时通信能力分析 。
5→ 0,B交换 G直通 I交换 M直通 R直通
7→ 1,D交换 G直通 J直通 N交换 S直通
（ D直通 H交换 K直通 Q直通 S交换 ）
无对交换单元功能的矛盾要求, 但级控不行 （ 第一,
二, 五级可以 ）, 部分, 单元控制可以 。
14,三级 PM2I互连网络
1） 网络构成：由 PM2a2,PM2a1,PM2a0三级构成 。
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
0
1
0
1
2
3
6
7
4
5
6
7
P
M
2
-
2
P
M
2
+
2
第 一 级 第 二 级 第 三 级
入端
出端
P M 2 a 2
G2
P M 2 a 1
G1
P M 2 a 0
G0
7
0
.
.
.
.
.
.
.
.
.
2） 控制信号与功能关系 。
① Gi=00 直通 （ 或平控 ）
② Gi=01 上控 （ 按 PM2+I,如第一级 I=2）
③ Gi=10 下控 （ 按 PM2-I）
3） 利用三级 PM2I互连网络实现点到点通信所需各
级控制信号和路径 （ 可有多条路径 ） 。
如：实现 0→ 5通信
① 方案一：上控 （ 0→ 4） 平控 （ 4→ 4）
上控 （ 4→ 5） G2G1G0=010001
② 方案二：上控 （ 0→ 4） 上控 （ 4→ 6）
下控 （ 6→ 5） G2G1G0=010110
1 在具有编号为 0～ 31的共 32个部件 SIMD互
连 网络中
（ 1） 画出四个立方体之间采用 Cube 3,Cube
4连接的拓扑结构图；
（ 2） 画出前 16个部件的四级立方体互 连 网络
结构图 （ Cube 0,Cube1,Cube 2,Cube 3级
间对号连接 ） ；
（ 3） 设交换单元为双功能交换单元
1） 0# 与 14# 部件,7# 与 10# 部件能同时实
现通信吗？ 为什么？
2） 10# 与 1# 部件,15# 与 9# 部件能同时实
现通信吗？为什么？
1,解 （ 1）
0
54
6 7
3
1
2
11
98
12
10
14 15
13
C u b e 3
C u b e 1
C u b e 0
C u b e 2
16
22 23
19
17
18
27
25
24
28
26
30 31
29
2120
C u b e 4
（ 2）
A
0
1
0
1
G 0 一 级
2
3
2
3
4
5
4
5
6
7
6
7
B
0
2
0
2
G 1 二 级
1
3
1
3
4
6
4
6
5
7
5
7
0
4
0
4
G 2 三 级
1
5
1
5
C
2
6
2
6
3
7
3
7
E
8
9
8
9
H
10
11
10
11
12
13
12
13
L
14
15
14
15
8
10
8
10
I
9
11
9
11
12
14
12
14
M
13
15
13
15
8
12
8
12
J
9
13
9
13
10
14
10
14
11
15
11
15
0
8
0
8
G 3 四 级
K
1
9
1
9
2
10
2
10
3
11
3
11
4
12
4
12
5
13
5
13
D
6
14
6
14
7
15
7
15
C u b e 0
C u b e 1 C u b e 2 C u b e 3
（ 3） 1） 0# → 14#,A直通 B交换 C交换 D交换
7# → 10#,E交换 F直通 C交换 G交换
对每个交换单元的功能无矛盾要求, 但第一, 二级不可以
用级控, 可采用单元控制或部分级控 。
2） 10# → 1#,H交换 I交换 J直通 K交换
15# → 9#,L直通 M交换 J交换 K直通
对 J,K交换单元的功能有矛盾要求, 因此不能直接通信 。
2,解 （ 1） 三级立方体互联网络图, 三级 PM2I互联网络图
及三级混洗互联网络图分别绘图如下,
（ 2） 2# → 5#通信分析
立方体,B交换 F交换 J交换
PM2I,上控 （ 2 → 6） 平控 （ 6 → 6） 下控 （ 6 → 5）
混洗,C交换 F交换 K交换
0
1
0
1
G0
B
2
3
2
3
C
4
5
4
5
D
6
7
6
7
E
0
2
0
2
G1
F
1
3
1
3
G
4
6
4
6
H
5
7
5
7
I
0
4
0
4
G2
J
1
5
1
5
K
2
6
2
6
L
3
7
3
7
C u b e 0
C u b e 1 C u b e 2
A
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
0
1
0
1
2
3
6
7
4
5
6
7
P
M
2
-
2
P
M
2
+
2
第 一 级 第 二 级 第 三 级
入端
出端
P M 2 a 2
G2
P M 2 a 1
G1
P M 2 a 0
G0
7
0
.
.
.
.
.
.
.
.
.
I
0
1
0
1
G0
J
2
3
2
3
G0
K
4
5
4
5
G0
L
6
7
6
7
G0
A
0
4
0
4
G2
B
1
5
1
5
G2
C
2
6
2
6
G2
D
3
7
3
7
G2
E
0
2
0
2
G1
F
4
6
4
6
G1
G
1
3
1
3
G1
H
5
7
5
7
G1
第 一 级 第 二 级 第 三 级
C u b e 2
C u b e 1 C u b e 0
3,解 （ 1） 三级混洗互联网络图绘图如下,
（ 2） 4# 号部件广播式通信
第一级,A上播 （ 10）
第二级,E,F下播 （ 11）
第三级,I,J,K,L下播 （ 11）
（ 3） G2G1G0 = 10 11 11
I
0
1
0
1
G0
J
2
3
2
3
G0
K
4
5
4
5
G0
L
6
7
6
7
G0
A
0
4
0
4
G2
B
1
5
1
5
G2
C
2
6
2
6
G2
D
3
7
3
7
G2
E
0
2
0
2
G1
F
4
6
4
6
G1
G
1
3
1
3
G1
H
5
7
5
7
G1
第 一 级 第 二 级 第 三 级
C u b e 2
C u b e 1 C u b e 0
0
x
54
6
7
3
1
2
11
98
12
10
14
z
y
15
13
4,解
1）
2）
3） G2G1G0 = 11 10 10
0
1
0
1
G 0 C u b e 0
2
3
2
3
G0
4
5
4
5
G0
6
7
6
7
G0
一级
0
2
0
2
1
3
1
3
G1
4
6
4
6
G1
5
7
5
7
G1
二级
0
4
0
4
1
5
1
5
G2
2
6
2
6
G2
3
7
3
7
G2
三级
G 1 C u b e 1 G 2 C u b e 2
第六章
1.描述多级互连网络的三要素 （ 参量 ） 是 交换单元, 拓扑
结构, 控制方式 。
2,单级互连网络的三种类型是 立方体, PM2I,混洗交换
互连网络 。
3,在多级互连网络中, 交换开关的三种控制方式是 级控制,
单元控制, 部分级控制 。
4,从单机向多机发展的三条途径是 时间重叠, 资源重复,
资源共享 。
5,两大类多机系统是指 多处理机系统 和 多计算机系统 。
6,在互连网络中所用的四功能交换单元的四功能是 直通,
交换, 下播, 上播 。
7,多机系统的两类耦合是 松耦合 和 紧耦合 。
8,SIMD互连网络是 （ B） 网络 。
A,连接多个计算机的 B,连接多个处理机的
C,混洗互连 D,多级互连
9,多机系统 （ C ） 。
A,即多计算机系统 B,即多处理机系统
C,包括多处理机系统 D,多用户系统
10.利用 SIMD互连网络, 可实现广播式通信, 因此 （ B ） 。
A,可用双功能交换单元实现
B,必须用四功能交换单元实现
C,必须用单级互连网络实现
D,要用移数网络实现
11,立方体互连网络 （ D ） 。
A,多个部件排成立方体
B,0#可和 5#部件直接通信
C,1#不能和 3#部件直接通信
D,应具有 cube0,cube1,cube2
12,阵列式多处理机系统 （ B ） 。
A,具有多个相同的排成阵列结构的 CPU
B,具有多个相同的排成阵列结构的处理机
C,具有多个不同的排成阵列结构的处理机
D,最适合完成对累加和求解
13,并行式多处理机系统 （ C ） 。
A,具有多个相同的 CPU B,具有多个不同的 CPU
C,具有多个相同的处理机 D,具有多个不同的处理机
14,多级混洗交换互连网络 （ B ） 。
A,是 PM2I的逆网络 B,是多级立方体的逆网络
C,完全与多级立方体相同 D,完全与 PM2I相同
15,利用 SIMD互连网络, 实现 8个部件之间点对点通信,
可用 （ C ） 。
A,单级 B,两级 C,三级 D,四功能交换单元
16,并行处理机与流水线处理机相比，通用性 ( )，灵活性
( )。 D
A．好 差 B．差 好 C．好 好 D．差 差
17,有 16个处理器组成的交换网络，其输入与输出之间的
一种对应关系如下,
0123456789ABCDEF
32107654BA98FEDC
它是实现的 ( A )交换。
A,4组 4元交换 B,2组 8元交换
C,1组 16元交换 D,8组 2元交换
18,并行处理机获得并行性的方式采用的是 ( B )。
A,时间重叠 B．资源重复 C,资源共享 D,都不是
19,有 8个处理单元互连成的并行处理机，要求按
(0,5),(1,4),(2,7),(3,6)配对通信。
实现此功能的互连函数的一般表达式。
A,f(x2 x1 x0)= x2 x0 x1 B,f(x2 x1 x0)= x2 x1 x0
C,f(x2 x1 x0)= x1 x0 x2 D,f(x2 x1 x0)= x2 x1 x0
20,紧耦合多处理机系统是指处理机之间通过 ( )
相互通讯。
A,共享主存 B．消息传递系统
C,I／ 0通道 D．脱机 I／ O设备
加速比的常规定义
加速比概念的延伸
六、非线性流水线的概念
非线性流水线的预约表
延迟禁止表
初始冲突向量
状态转移图：调度方案, 平均延迟
七, 指令级高级并行超级处理机
超标量处理机
超长指令字处理机
超流水线处理机
处理机并行的度
第六章 多机系统
§1概述
一, 并行性概念
并行性是指在执行任务过程中可同时进行的运算或操作 。
1,开发并行性的目的
提高计算机的运行效率
2,并行性的含义
具有双重含义：同时性与并发性
同时性是指两个或两个以上的事件在同一时刻发生 。
并发性是指两个或两个以上的事件在同一时间间隔内
发生 。
3.并行性的意义
1） 并行意味着有多个事件在并行执行, 当这
多个事件都在完成同一性质的处理时, 意味着
单位时间完成的结果数增加了, 从而可提高对
数据处理速度 。
2） 并行同样意味着多个事件中并行处理, 当
这些处理都在为一个目的工作时, 从提高可靠
性出发, 按多数表决法, 对多数得出的相同结
果具有高的可靠性 。
3） 并行也可能意味着要增加硬件成本, 因而
需根据性能价格比来评价这种开销是否合理 。
二, 从单机向多机发展的三条途径
2? ?÷á ÷? ? ??
μ¤ oú ?μ í3
?· á? á÷? ? ??
1ê á÷? ? ??
ò? ? Dí μ?
?- oú ?μ í3
?- ′￥ àì 2? ?t ?? ?
í? ? Dí ?- oú ?μ í3
￡¨? ü à¨2 ￠ D ê? ?￠
?ó áD ê? ?- oú ?μ í3
ó? ?￠ D? Dí oú ′ú ì? Dé
?a oú
?? 2? ê? ?- oú ?μ í3
′? ′￠ ?÷? - ì? ?? ?
?- ó? o§? ? êa? μ í3
Dé ?a oú 2o í? ·? ?? ??
? μ? ?? ?? oú ?μ í3
êa? ? ?× μt
?ê ?′ ?2 ?ì
?ê ?′ ?× ·′
o? a- ?? ? ￡?
C ?? ? ?? ??
oú ?μ í3
?并行处理的四个等级,
? 单机流水处理中一条指令内多个操作的并行处理 ;
? 并行处理机多条相同指令的并行处理（指令间） ;
? 多处理机多个任务的并行处理 ;
? 多计算机系统多程序（作业）的并行处理。
三, 多机系统的耦合度
1.何谓耦合度
多机之间相互的通信控制能力或相互依赖程
度, 称为多机之间的耦合度 。
2.三种耦合度
1） 最低耦合：多机之间几乎没有共享设备, 如仅用二,
三条线连接起来的计算机 。 （ 如 RS232C通信 ） 。
2） 松散耦合：多机之间有一定的共享设备, 如大型的
主机与外围机, 它们之间共享受主存, I/O通道 。 但它
们之间也可相对独立工作, 又如连接在网络上的计算机,
连接在局域网上的计算机共享硬盘 。 处理机间一般通过
消息传递系统交换信息, 也有通过通道互联实现处理机
间的通讯 。
3） 紧密耦合：耦合度最高, 相互依赖很强, 如阵列式
多处理机的 CU（ 控制部件 ） 和 PU（ 处理部件 ） 之间 。 通
过共享主存实现处理机间的通讯, 通讯速率受限于主存
频宽 。
四, 多机系统的分类及特点
多机系统指的是多处理机系统和多计算机系统 。
1.多处理机系统
1） 各处理机共享 I/O通道 。
2） 属于紧耦合 。
3） 表现形式有,
并行 (阵列 )式多处理机系统；
分布式多处理机系统 。
2.多计算机系统
1）各处理机具有自己的 I/O通道和主存
2）属于最低耦合或松耦合
3） 典型表现为计算机网络。
§2 多处理机系统
一,伊（ ILLIAC） IV阵列式
多处理机系统
1,总体结构：最初设计具有
四个象限的阵列式多处理机
系统，其中,CU为阵列控制
部件,A为阵列处理部件。
CU1
A1
CU2
A2
CU4
A4
CU3
A3
I/O CH2,CU的主要功能
1） 对指令进行译码。
2） 向阵列处理部件 A发出公共地址、公共数据。
3）向 A发出各种控制命令。
CU应当具备高性能的标量处理能力，否则将制约整个
阵列处理机的性能。
3 阵列处理部件 A
1） 由 64个 PU组成, 且排列成 8*8的阵列结构 。
PU0 PU1 PU7
PU56
PU57 PU63
PU8
PU63
PU8 PU9 PU15 PU16
PU7
PU56 PU57 PU63 PU0
PU55
PU0 PU1
PU7
2 ） 各 PU在水平方向上按 a1进行连接, 且以 64为模,
称为水平螺旋连接 。
3） 各 PU在竖直方向上按 a8进行连接, 也以 64为模,
称为竖直圆柱连接 。
（ 在本节的互连网络中, 这种连接采用何种互连函
数, 将会介绍 ）
3 阵列存储器
1） 每个 PU除它们共享的主存外, 各 PU还有自己的局
部存储器 。 （ 其总容量是 2K?64个局部存储器 （ PEM0
?PEM63） 共有 2K?64=128K）
2） 由于局部存储器随阵列分布, 因此又称为阵列分
布存储器 。
二, 阵列式多处理机适应的算法
1,二维调和函数的求解
二维调和函数的求解 U(x,y):满足二维拉普拉斯方程的函
数, 即
其中,h是网格点的间距, (x,y)为网格点坐标 。
利用此法计算, 又称为平滑或滤波, 目的是消除偶然干扰 。
4
hyxuyhxuhyxuyhxu
yxu
h
hyxuyxu2hyxu
y
u
h
yhxuyxu2yhxu
x
u
0
y
u
x
u
22
2
22
2
2
2
2
2
),(),(),(),(
),(
),(),(),(
),(),(),(
???????
?
?????
?
?
?
?????
?
?
?
?
?
?
?
?
?
所以
2 矩阵加
1） 有如下两个矩阵
63 57 56
15 9 8
7 1 0
a a a
a a a
a a a
A
…
… … … …
…
…
?
63 57 56
15 9 8
7 1 0
b b b
b b b
b b b
B
…
… … … …
…
…
?
63 57 56
15 9 8
7 1 0
c c c
c c c
c c c
C
…
… … … …
…
…
?
计算 C=A+B
则,c0=a0+b0 c1=a1+b1
… c63=a63+b63
2） 阵列存储器分配
每个局部存储器占用三个单元
c0
b0
a0
|?
|?
PEM0
k+0
k+1
k+2
c1
b1
a1
|?
|?
PEM1
c63
b63
a63
|?
|?
PEM63
k+0
k+1
k+2
k+0
k+1
k+2
|
3）完成矩阵的加运算
CU向各 PU发出有关命令,
①公共地址 K+0和（取操
作数）读命令。
因此各 PU从 K+0单元中分
别取出 A阵列数据 a0~a63。
② 第二个公共地址 K+1和
取操作数，各 PU又将 K+1单
元中的 b0~b63取出。
③ CU向各 PU发出求和命令，各 PU将取出的 ai及 bi求和，即 ci=ai+ bi。
④ CU第三次向各 PU 发出公共地址 K+2和写命令，各 PU将 ci存入
K+2单元
3 矩阵乘
用阵列式多处理机完成矩阵乘法，不如阵列流水线处
理机，因为用矩阵乘法运算比矩阵加法复杂，对阵列多
处理机各部件的利用率不如矩阵加。
4 可加速累加和的形式（与单机比较）
1）计算
?
?
?
7
0i
iaS
① S1=a0+a1 ② S2=a2+a3
③ S3=a4+a5 ④ S4=a6+a7
⑤ S5=S1+S2 ⑥ S6=S3+S4
⑦ S=S5+S6
2）参数存放
3） 计算过程
① PU0,PU1,PU2,PU3分别取出 a0,a2,a4,a6；
② PU0,PU1,PU2,PU3再分别取出 a1,a3,a5,a7；
③ 四个 PU分别求和计算得 S1,S2 S3,S4；
④ PU1→PU0 由 PU0计算 S1+S2,PU3→PU2, 由 PU2计算
S3+S4；
⑤ PU2→PU0 由 PU0计算 S。
a1
a0
PEM0
k+0
k+1
k+2
a3
a2
k+0
k+1
k+2
a5
a4
PEM2
k+0
k+1
k+2
PEM3
a7
a6
k+0
k+1
k+2
PEM1
三, SIMD互连网络
1,概述
1） 互连：实现处理机之间相互连接, 称互连 。
2） 互连网络：实现处理机之间相互连接的某种拓扑
结构的逻辑电路, 称互连网络 。
3） 互连函数：实现处理机之间相互连接的某种拓扑
结构的逻辑函数, 称互连函数 。
4） 对互连网络的评价
① 要有利于实现；
② 要有一定的通信频带；
③ 要有一定的灵活性, 可实现多种连接通信 。
5） 互连网络的主要类型
① 从性质上分
Ⅰ ） 立方体 （ cube） 互连网络
Ⅱ ） PM2I互连网络
Ⅲ ） 混洗交换 互连网络
② 从级数多少来分
Ⅰ ） 单级 互连网络
Ⅱ ） 循环 互连网络 （ 物理一级但可实现多级 ）
Ⅲ ） 多级 互连网络
6） 互连函数中, 部件 （ 或处理机 ） 的编码 。
设用 n 位二进制来表示部件编码, 即有,Pn-1Pn-
2… P2P1P0
当用 3位二进制数表示时 （ 即 n=3） 则有：
P2P1P0
2,单级立方体 （ Cube） 互连网络
1） 立方体互连函数 （ 设 n=3）
① Cube0:仅在第 0位上的代码取反, 其余各
位不变 。
Cube0（ P2P1P0） = P2P1P0
② Cube1,仅在第 1位上的代码取反, 其余各
位不变 。
Cube1（ P2P1P0） = P2P1 P0
③ Cube2,仅在第 2位上的代码取反，其余各
位不变。
Cube2（ P2P1P0） = P2P1 P0
2） 实现的连接关系
Cube0 Cube1 Cube2
P2P1P0 P2P1P0 P2P1 P0 P 2P1 P0
0 0 0 0 0 1 0 1 0 1 0 0
0 0 1 0 0 0 0 1 1 1 0 1
0 1 0 0 1 1 0 0 0 1 1 0
0 1 1 0 1 0 0 0 1 1 1 1
1 0 0 1 0 1 1 1 0 0 0 0
1 0 1 1 0 0 1 1 1 0 0 1
1 1 0 1 1 1 1 0 0 0 1 0
1 1 1 1 1 0 1 0 1 0 1 1
① Cube0可实现 8个部件 （ 处理单元 ）, 在 x方向连接 。
② Cube1可实现 8个部件 （ 处理单元 ）, 在 y方向连接 。
③ Cube2可实现 8个部件 （ 处理单元 ）, 在 z方向连接 。
0
x
54
6
7
3
1
2
11
98
12
10
14
z
y
15
13
3）当 n=4时，有 P3P2P1P0, 则
Cube3（ P3P2P1P0 ） =P3 P2P1 P0
用 Cube3可将两个立方体连接起来，构成一个立方
体组（四维空间）。
当 n=5时，有 P4P3P2P1P0, 则
Cube4（ P4P3P2P1P0） = P4 P3 P2P1 P0
用 Cube4可将两个立方体组连接起来，构成一个立
方体群（五维空间）。
4）互连网络的链接关系图
3,单级 PM2I互连网络 （ Plus-Minus2i）
1） PM2I互连函数
① PM2+i( j )=j+2i
② PM2-i( j )=j-2i
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
Cube1Cube0 Cube2
2） 实现的连接关系 （ 设 j分别为 0～ 7,以 8为模 。 ）
j j+20 j-20
0 1 7
1 2 0
2 3 1
3 4 2
4 5 3
5 6 4
6 7 5
7 0 6
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
PM2+0
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
PM2-0
伊 Ⅳ 机在水平连接采用 PM2+0,PM2-0（ 双向）且以
64为模。
3） PM2a1
① PM2+1( j )=j+21=j+2
② PM2-1( j )=j-21=j-2
4） 当 I=3时, 有
① PM2+3( j )=j+8
② PM2-3 ( j )=j-8
伊 Ⅳ 阵列式多处理机, 在竖直方向上的连接采用
PM2a3以 64为模 。
所以, 伊 Ⅳ 共采用了 PM2a0和 PM2a3实现相互连接
（ 以 64为模 ） 。
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
PM2+1
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
PM2-1
§1概述
并行性概念
并行性的意义
从单机向多机发展的三条途径
多机系统的耦合度
§2 多处理机系统
伊（ ILLIAC） IV阵列式多处理机系统
阵列式多处理机适应的算法
SIMD互连网络
互连, 互连网络, 互连函数
互连网络的主要类型
立方体 （ Cube） 互连网络
PM2I互连网络
4,单级混洗交换互连网络
1） 立方体和 PM2I互连函数太规整, 为了实现具有随意性
连接, 采用混洗 。
2） 混洗互连函数,Sh(Pn-1Pn-2┅ P1P0)=Pn-2Pn-3┅ P1P0Pn-1即
循环左移一位, n=3时
Sh(P2P1P0) = P1P0P2
0 0 0 0 0 0
0 0 1 0 1 0
0 1 0 1 0 0
0 1 1 1 1 0
1 0 0 0 0 1
1 0 1 0 1 1
1 1 0 1 0 1
1 1 1 1 1 1
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
3） 利用混洗互连网函数将 8个部件分为互不相联的四组,
如下图,0； 1,2,4； 3,5,6； 7
1 2 30 5 6 74
4）在混洗基础上加入 Cube0的交换，即构成混洗交换互
连函数。
0?1 2?3 4?5 6?7
可将 8个部件实现相互通信。
Cube0(Shuffle(bn-1…b 0))=Cube0(bn-2…b 0bn-1)= bn-2…b 0bn-1
5,循环互连网络
1） 构成：由单级互连
网络多路开关
（ MUX） 和输入寄存
器 （ IR） 组成 。
2） 目的：利用对单级
互连网的重复使用,
在一定程度上模拟互
连网络的功能 。
3） 特点,
单
级
互
连
网
络
IR0
IR1
IR2
IR3
MUX
MUX
PU0
PU0
PU1
PU1
输出0
输出1
C1
C2
①结构简单，易于实现。
② 对单级互连网络的重复使用，往往是机械重复，灵
活性差。
③重复加入时，重复频率受到限制。
6,描述多级互连网络的参数
1） 交换单元的功能
交换单元：是一个具有两个输入, 两个输出和一个
控制端的五端开关 。
I1
I2
O 1
O 2
G
① 双功能交换单元：具有直通和交换两种功能 。
I1
I2
O 1
O 2
G=00
I1
I2
O 1
O 2
G=01
② 四功能交换单元 （ G为两位 ）,除上述的直通,
交换外, 还有上播, 下播两种 。
2） 拓扑结构
拓扑结构 是 各级间出端与入端互连的模式。前述各种
单级互连网络的连接模式均可用来组合构成不同的多级互
连网络。
解决在级与级之间采用何种规则连接，通常采用级间
对号连接，如三级 立方体互联网络,
I1
I2
O 1
O 2
G=10
I1
I2
O 1
O 2
G=11
0
1
0
1
G C u b e 0
2
3
2
3
G
4
5
4
5
G
6
7
6
7
G
一级
0
2
0
2
1
3
1
3
G
4
6
4
6
G
5
7
5
7
G
二级
0
4
0
4
1
5
1
5
G
2
6
2
6
G
3
7
3
7
G
三级
G C u b e 1 G C u b e 2
3） 控制方式
① 级控制方式：同一级的所
有交换单元只用一个控制
信号控制 。
② 单元控制方式：同一级的
每个交换单元各有各的独
立控制信号 。
③ 部分级控制方式：介于 ①
② 两种控制方式之间, 对
同一级交换单元来讲, 控
制信号的数目 ≥ 2个, 但小
于交换单元数 。
G
G0
G1
G2
G3
7,采用双功能交换单元级控制方式的三级立方体互连网络
1） 网络构成：由 Cube0,Cube1,Cube2三级构成 （ 要求画出 3*4=12
个交换单元的三级立方体互连网络图 ） 。
0
1
0
1
G0
2
3
2
3
G0
4
5
4
5
G0
6
7
6
7
G0
一级
0
2
0
2
G1
1
3
1
3
G1
4
6
4
6
G1
5
7
5
7
G1
二级
0
4
0
4
G2
1
5
1
5
G2
2
6
2
6
G2
3
7
3
7
G2
三级
C u b e 0 C u b e 1 C u b e 2
2） 写出控制信号 G2G1G0实现的连接关系表 。
3） 画出控制信号 G2G1G0实现的连接关系图 。
4） 写出控制信号 G2G1G0实现的连接名称 。
入端号
G 2 G 1 G 0
0 1 2 3 4 5 6 7
连接关系名称
0 0 0 0 1 2 3 4 5 6 7
直通或恒等
0 0 1 1 0 3 2 5 4 7 6
四组二元交换
0 1 0 2 3 0 1 6 7 4 5 二组四元加四组二元交换
0 1 1 3 2 1 0 7 6 5 4 二组四元
1 0 0 4 5 6 7 0 1 2 3 一组八元加二组四元交换
1 0 1 5 4 7 6 1 0 3 2 4, 2 & 2.4 & 1.8
1 1 0 6 7 4 5 2 3 0 1 四组二元加一组八元交换
1 1 1 7 6 5 4 3 2 1 0 一组八元交换
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
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
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
G 2 G 1 G 0 = 0 0 0 G 2 G 1 G 0 = 0 1 1G 2 G 1 G 0 = 0 1 0G 2 G 1 G 0 = 0 0 1
G 2 G 1 G 0 = 1 0 0 G 2 G 1 G 0 = 1 1 1G 2 G 1 G 0 = 1 1 0G 2 G 1 G 0 = 1 0 1
8,采用级控和部分级控相结合的三级立方体
互连网络 —— 移数网络
1） 网络构成：也由 Cube0,Cube1,Cube2三级
构成 。
2） 控制方式
① 第一级采用级控制方式 （ G0） 。
② 第二级采用部分级控制方式 （ G1G2） 。
③ 第三级采用部分级控制方式 （ G3G4G5） 。
2
3
G0
1
3
G2
4
5
G0
4
6
G1
0
1
G0
0
2
G1
6
7
G0
5
7
G2
1
5
G4
2
6
G5
0
4
G3
3
7
G5
2
3
4
5
0
1
6
7
1
5
2
6
0
4
3
7
1
3
4
6
0
2
5
7
3） 控制信号 （ G5~G0） 与连接关系表, 连接关系图和
移数名称 。
入端号
G 5 G 4 G 3 G 2 G 1 G 0
0 1 2 3 4 5 6 7
移数名称
0 0 0 0 0 0 0 1 2 3 4 5 6 7 直通
0 0 0 0 0 1 1 0 3 2 5 4 7 6 移 1 模 2
0 0 0 0 1 1 1 2 3 0 5 6 7 4
移 1 模 4
0 0 0 1 1 0 2 3 0 1 6 7 4 5 移 2 模 4
0 0 1 0 1 1 1 2 3 4 5 6 7 0 移 1 模 8
0 1 1 1 1 0 2 3 4 5 6 7 0 1 移 2 模 8
1 1 1 0 0 0 4 5 6 7 0 1 2 3 移 4 模 8
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
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
000011 000110000001 111000011110001011
9,采用四功能交换单元, 级控制方式的三级立方体实
现广播式通信
1） 网络构成：也由 Cube0,Cube1,Cube2三级构成 。
2） 实现某个部件向所有部件进行广播式通信 （ 如 4#部
件 ） 。
① 写出有关交换单元的功能 。
② 画出完成广播式通信的通信线路图 。
③ 写出控制信号 G2G1G0。
例：实现 4#部件向 0～ 7部件 完成广播式通信 。
第一级交换单元 C上播,G0=10
第二级交换单元 GH上播,G1=10
第三级交换单元 IJKL下播,G2=11
0
1
0
1
G0
B
2
3
2
3
4
5
4
5
D
6
7
6
7
E
0
2
0
2
G1
F
1
3
1
3
G
4
6
4
6
5
7
5
7
0
4
0
4
G2
J
1
5
1
5
2
6
2
6
3
7
3
7
Cube0
Cube1 Cube2
H
I
A
K
L
C
10.三级立方体互连网络对以下两组部件同时通信
能力分析
1） 第一组部件,0→ 5与 1→ 7同时通信 。
0→ 5号部件通信,A交换 F直通 J交换
1→ 7号部件通信,A直通 F交换 J交换
同时对 A,F两个交换单元有矛盾要求, 所以不能
同时实现 0→ 5,1→ 7同时通信 。
2） 第二组部件,5→ 0,7→ 1
5→ 0号部件通信,C交换 G直通 I交换
7→ 1号部件通信,D直通 H交换 J交换
没有对交换单元矛盾要求, 但第一, 二级要采用
部分控 制方式或单元控制方式才可同时通信 。
0
1
0
1
G0
B
2
3
2
3
C
4
5
4
5
D
6
7
6
7
E
0
2
0
2
G1
F
1
3
1
3
G
4
6
4
6
H
5
7
5
7
I
0
4
0
4
G2
J
1
5
1
5
K
2
6
2
6
L
3
7
3
7
C u b e 0
C u b e 1 C u b e 2
A
4,单级混洗交换互连网络
5,循环互连网络
6,描述多级互连网络的参量
1）交换单元的功能
2）拓扑结构
3）控制方式
7.采用双功能交换单元级控制方式的三级立方体互连网络
8,采用级控和部分级控相结合的三级立方体互连网络 ——
移数网络
9,采用四功能交换单元, 级控制方式的三级立方体实现广
播式通信
10.三级立方体互连网络对以下两组部件同时通信能力分
析
11,四级立方体互连网络
1） 网络构成：由 Cube0～ cube3四级构成 （ 共 4*8=32
个交换单元 ） 。
2）四功能交换单元，广播式通信。例,5号对 0～ 15
号广播式通信,
① 第一级 A下播,G0=11
② 第二级 B,C上播,G1=10
③ 第三级 D～ G下播,G2=11
④ 第四级 H～ O上播,G3=10 即
G3G2G1G0=10111011B
3） 控制信号 G3G2G1G0与连接关系表, 连接关系图及
连接关系名称 。
0
1
0
1
G0
2
3
2
3
4
5
4
5
6
7
6
7
0
2
0
2
G1
1
3
1
3
4
6
4
6
5
7
5
7
0
4
0
4
G2
1
5
1
5
2
6
2
6
3
7
3
7
8
9
8
9
10
11
10
11
12
13
12
13
14
15
14
15
8
10
8
10
9
11
9
11
12
14
12
14
13
15
13
15
8
12
8
12
9
13
9
13
10
14
10
14
11
15
11
15
0
8
0
8
G3
1
9
1
9
2
10
2
10
3
11
3
11
4
12
4
12
5
13
5
13
6
14
6
14
7
15
7
15
Cube0
Cube1 Cube2 Cube3
B
C
H
I
J
K
L
M
N
O
A
D
E
F
G
入端号 G 3 G 2 G 1 G 0
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 5
连接关系名称
0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 5 直通或恒等
0 0 0 1 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 八组二元交换
0 0 1 0 2 3 0 1 6 7 4 5 10 11 8 9 14 1 5 1 2 13 8.2 ⊕ 4.4
0 0 1 1 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 四组四元
0 1 1 1 7 6 5 4 3 2 1 0 15 14 1 3 1 2 1 1 1 0 9 8 二组八元
1 0 0 0 8 9 10 11 12 1 3 1 4 1 5 0 1 2 3 4 5 6 7 2.8 ⊕ 1.16
1 1 1 1 1 5 1 4 1 3 1 2 1 1 10 9 8 7 6 5 4 3 2 1 0 一组十六元
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
0011G3G2G1G0=0010 0001
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0111
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
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
1000 1111
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
8
9
10
11
12
13
14
15
12,三级混洗交换互连网络
1） 网络构成：也由 Cube2,Cube1,Cube0三级构
成, 但与三级立方体互连网络有以下两点区别：
① Cube0与 Cube2的位置互换 （ 第一级是 Cube2，
第三级是 Cube0）
② Cube1中间两个交换单元位置互换 。
其目的是使级间连接形式与混洗连接一致 。
（ 混洗循环左移一位 ）
I
0
1
0
1
G0
J
2
3
2
3
G0
K
4
5
4
5
G0
L
6
7
6
7
G0
A
0
4
0
4
G2
B
1
5
1
5
G2
C
2
6
2
6
G2
D
3
7
3
7
G2
E
0
2
0
2
G1
F
4
6
4
6
G1
G
1
3
1
3
G1
H
5
7
5
7
G1
μù òo ?? μù ?t ?? μù èy ??
Cube2
Cube1 Cube0
2） 对以下两组部件同时通信能力分析 。
① 0→ 5, 1→ 7
0→ 5,A交换 F直通 K交换
1→ 7,B交换 H交换 L直通
对交换单元无矛盾要求, 但第二, 三级需采用部分级控
制或单元控制 。
② 5→ 0, 7→ 1
5→ 0,B交换 G直通 I交换
7→ 1,D交换 G交换 I直通
对 G,I交换单元有矛盾要求, 因此不能同时通信 。 （ 与
三级立方体正好相反 —— 逆网络 ）
3） 三级混洗交换互连网络的控制信号 G2G1G0与连接关系
表, 关系图, 连接名称与三级立方体相似 。 （ 略 ）
13,全排列互连网络
1） 网络构成：由三级立方体与三级混洗交换互连网络构
成 。
I
0
1
0
1
G
J
2
3
2
3
G
K
4
5
4
5
G
L
6
7
6
7
G
M
0
2
0
2
G
N
1
3
1
3
G
P
4
6
4
6
G
Q
5
7
5
7
G
R
0
4
0
4
G
S
1
5
1
5
G
T
2
6
2
6
G
U
3
7
3
7
G
A
0
4
0
4
G
B
1
5
1
5
G
C
2
6
2
6
G
D
3
7
3
7
G
E
0
2
0
2
G
F
4
6
4
6
G
G
1
3
1
3
G
H
5
7
5
7
G
èy ?? o? ?′ ?o o í? ?? èy ?? á￠ ?? ì? o¤ á? í? ??
2） 对 0→ 5,1→ 7同时通信能力分析 。
0→ 5,A交换 F直通 K交换 Q直通 S直通
1→ 7,B直通 G直通 I直通 N交换 U交换
无对交换单元矛盾要求, 但级控不行, 单元控, 部分
级控可以 。
（ 可以有两条以上通路,
B交换 H直通 K直通 Q交换 U直通
B交换 H交换 L直通 Q直通 U直通 ）
3） 对 5→ 0,7→ 1同时通信能力分析 。
5→ 0,B交换 G直通 I交换 M直通 R直通
7→ 1,D交换 G直通 J直通 N交换 S直通
（ D直通 H交换 K直通 Q直通 S交换 ）
无对交换单元功能的矛盾要求, 但级控不行 （ 第一,
二, 五级可以 ）, 部分, 单元控制可以 。
14,三级 PM2I互连网络
1） 网络构成：由 PM2a2,PM2a1,PM2a0三级构成 。
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
0
1
0
1
2
3
6
7
4
5
6
7
P
M
2
-
2
P
M
2
+
2
第 一 级 第 二 级 第 三 级
入端
出端
P M 2 a 2
G2
P M 2 a 1
G1
P M 2 a 0
G0
7
0
.
.
.
.
.
.
.
.
.
2） 控制信号与功能关系 。
① Gi=00 直通 （ 或平控 ）
② Gi=01 上控 （ 按 PM2+I,如第一级 I=2）
③ Gi=10 下控 （ 按 PM2-I）
3） 利用三级 PM2I互连网络实现点到点通信所需各
级控制信号和路径 （ 可有多条路径 ） 。
如：实现 0→ 5通信
① 方案一：上控 （ 0→ 4） 平控 （ 4→ 4）
上控 （ 4→ 5） G2G1G0=010001
② 方案二：上控 （ 0→ 4） 上控 （ 4→ 6）
下控 （ 6→ 5） G2G1G0=010110
1 在具有编号为 0～ 31的共 32个部件 SIMD互
连 网络中
（ 1） 画出四个立方体之间采用 Cube 3,Cube
4连接的拓扑结构图；
（ 2） 画出前 16个部件的四级立方体互 连 网络
结构图 （ Cube 0,Cube1,Cube 2,Cube 3级
间对号连接 ） ；
（ 3） 设交换单元为双功能交换单元
1） 0# 与 14# 部件,7# 与 10# 部件能同时实
现通信吗？ 为什么？
2） 10# 与 1# 部件,15# 与 9# 部件能同时实
现通信吗？为什么？
1,解 （ 1）
0
54
6 7
3
1
2
11
98
12
10
14 15
13
C u b e 3
C u b e 1
C u b e 0
C u b e 2
16
22 23
19
17
18
27
25
24
28
26
30 31
29
2120
C u b e 4
（ 2）
A
0
1
0
1
G 0 一 级
2
3
2
3
4
5
4
5
6
7
6
7
B
0
2
0
2
G 1 二 级
1
3
1
3
4
6
4
6
5
7
5
7
0
4
0
4
G 2 三 级
1
5
1
5
C
2
6
2
6
3
7
3
7
E
8
9
8
9
H
10
11
10
11
12
13
12
13
L
14
15
14
15
8
10
8
10
I
9
11
9
11
12
14
12
14
M
13
15
13
15
8
12
8
12
J
9
13
9
13
10
14
10
14
11
15
11
15
0
8
0
8
G 3 四 级
K
1
9
1
9
2
10
2
10
3
11
3
11
4
12
4
12
5
13
5
13
D
6
14
6
14
7
15
7
15
C u b e 0
C u b e 1 C u b e 2 C u b e 3
（ 3） 1） 0# → 14#,A直通 B交换 C交换 D交换
7# → 10#,E交换 F直通 C交换 G交换
对每个交换单元的功能无矛盾要求, 但第一, 二级不可以
用级控, 可采用单元控制或部分级控 。
2） 10# → 1#,H交换 I交换 J直通 K交换
15# → 9#,L直通 M交换 J交换 K直通
对 J,K交换单元的功能有矛盾要求, 因此不能直接通信 。
2,解 （ 1） 三级立方体互联网络图, 三级 PM2I互联网络图
及三级混洗互联网络图分别绘图如下,
（ 2） 2# → 5#通信分析
立方体,B交换 F交换 J交换
PM2I,上控 （ 2 → 6） 平控 （ 6 → 6） 下控 （ 6 → 5）
混洗,C交换 F交换 K交换
0
1
0
1
G0
B
2
3
2
3
C
4
5
4
5
D
6
7
6
7
E
0
2
0
2
G1
F
1
3
1
3
G
4
6
4
6
H
5
7
5
7
I
0
4
0
4
G2
J
1
5
1
5
K
2
6
2
6
L
3
7
3
7
C u b e 0
C u b e 1 C u b e 2
A
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
0
1
0
1
2
3
6
7
4
5
6
7
P
M
2
-
2
P
M
2
+
2
第 一 级 第 二 级 第 三 级
入端
出端
P M 2 a 2
G2
P M 2 a 1
G1
P M 2 a 0
G0
7
0
.
.
.
.
.
.
.
.
.
I
0
1
0
1
G0
J
2
3
2
3
G0
K
4
5
4
5
G0
L
6
7
6
7
G0
A
0
4
0
4
G2
B
1
5
1
5
G2
C
2
6
2
6
G2
D
3
7
3
7
G2
E
0
2
0
2
G1
F
4
6
4
6
G1
G
1
3
1
3
G1
H
5
7
5
7
G1
第 一 级 第 二 级 第 三 级
C u b e 2
C u b e 1 C u b e 0
3,解 （ 1） 三级混洗互联网络图绘图如下,
（ 2） 4# 号部件广播式通信
第一级,A上播 （ 10）
第二级,E,F下播 （ 11）
第三级,I,J,K,L下播 （ 11）
（ 3） G2G1G0 = 10 11 11
I
0
1
0
1
G0
J
2
3
2
3
G0
K
4
5
4
5
G0
L
6
7
6
7
G0
A
0
4
0
4
G2
B
1
5
1
5
G2
C
2
6
2
6
G2
D
3
7
3
7
G2
E
0
2
0
2
G1
F
4
6
4
6
G1
G
1
3
1
3
G1
H
5
7
5
7
G1
第 一 级 第 二 级 第 三 级
C u b e 2
C u b e 1 C u b e 0
0
x
54
6
7
3
1
2
11
98
12
10
14
z
y
15
13
4,解
1）
2）
3） G2G1G0 = 11 10 10
0
1
0
1
G 0 C u b e 0
2
3
2
3
G0
4
5
4
5
G0
6
7
6
7
G0
一级
0
2
0
2
1
3
1
3
G1
4
6
4
6
G1
5
7
5
7
G1
二级
0
4
0
4
1
5
1
5
G2
2
6
2
6
G2
3
7
3
7
G2
三级
G 1 C u b e 1 G 2 C u b e 2
第六章
1.描述多级互连网络的三要素 （ 参量 ） 是 交换单元, 拓扑
结构, 控制方式 。
2,单级互连网络的三种类型是 立方体, PM2I,混洗交换
互连网络 。
3,在多级互连网络中, 交换开关的三种控制方式是 级控制,
单元控制, 部分级控制 。
4,从单机向多机发展的三条途径是 时间重叠, 资源重复,
资源共享 。
5,两大类多机系统是指 多处理机系统 和 多计算机系统 。
6,在互连网络中所用的四功能交换单元的四功能是 直通,
交换, 下播, 上播 。
7,多机系统的两类耦合是 松耦合 和 紧耦合 。
8,SIMD互连网络是 （ B） 网络 。
A,连接多个计算机的 B,连接多个处理机的
C,混洗互连 D,多级互连
9,多机系统 （ C ） 。
A,即多计算机系统 B,即多处理机系统
C,包括多处理机系统 D,多用户系统
10.利用 SIMD互连网络, 可实现广播式通信, 因此 （ B ） 。
A,可用双功能交换单元实现
B,必须用四功能交换单元实现
C,必须用单级互连网络实现
D,要用移数网络实现
11,立方体互连网络 （ D ） 。
A,多个部件排成立方体
B,0#可和 5#部件直接通信
C,1#不能和 3#部件直接通信
D,应具有 cube0,cube1,cube2
12,阵列式多处理机系统 （ B ） 。
A,具有多个相同的排成阵列结构的 CPU
B,具有多个相同的排成阵列结构的处理机
C,具有多个不同的排成阵列结构的处理机
D,最适合完成对累加和求解
13,并行式多处理机系统 （ C ） 。
A,具有多个相同的 CPU B,具有多个不同的 CPU
C,具有多个相同的处理机 D,具有多个不同的处理机
14,多级混洗交换互连网络 （ B ） 。
A,是 PM2I的逆网络 B,是多级立方体的逆网络
C,完全与多级立方体相同 D,完全与 PM2I相同
15,利用 SIMD互连网络, 实现 8个部件之间点对点通信,
可用 （ C ） 。
A,单级 B,两级 C,三级 D,四功能交换单元
16,并行处理机与流水线处理机相比，通用性 ( )，灵活性
( )。 D
A．好 差 B．差 好 C．好 好 D．差 差
17,有 16个处理器组成的交换网络，其输入与输出之间的
一种对应关系如下,
0123456789ABCDEF
32107654BA98FEDC
它是实现的 ( A )交换。
A,4组 4元交换 B,2组 8元交换
C,1组 16元交换 D,8组 2元交换
18,并行处理机获得并行性的方式采用的是 ( B )。
A,时间重叠 B．资源重复 C,资源共享 D,都不是
19,有 8个处理单元互连成的并行处理机，要求按
(0,5),(1,4),(2,7),(3,6)配对通信。
实现此功能的互连函数的一般表达式。
A,f(x2 x1 x0)= x2 x0 x1 B,f(x2 x1 x0)= x2 x1 x0
C,f(x2 x1 x0)= x1 x0 x2 D,f(x2 x1 x0)= x2 x1 x0
20,紧耦合多处理机系统是指处理机之间通过 ( )
相互通讯。
A,共享主存 B．消息传递系统
C,I／ 0通道 D．脱机 I／ O设备
