五、加速比的概念
加速比的常规定义
加速比概念的延伸
六、非线性流水线的概念
非线性流水线的预约表
延迟禁止表
初始冲突向量
状态转移图:调度方案, 平均延迟
七, 指令级高级并行超级处理机
超标量处理机
超长指令字处理机
超流水线处理机
处理机并行的度
第六章 多机系统
§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) 有如下两个矩阵
635756
1598
710
aaa
aaa
aaa
A

…………


?
635756
1598
710
bbb
bbb
bbb
B

…………


?
635756
1598
710
ccc
ccc
ccc
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实现的连接名称 。
入端号
G2G1 G0
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 15
连接关系名称
0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 直通或恒等
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 15 12 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 13 12 11 10 9 8 二组八元
1 0 0 0 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 2.8 ⊕ 1.16
1 1 1 1 15 14 13 12 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 3C 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设备