[网络协议]02325《计算机系统结构》自考大题：第 6、7、8 章

复习总目录

??02325《计算机系统结构》自考复习重点目录

6. 阵列处理机

1. 单级互连网络

历史考题：2020.10 (PM2I)、2017.04 (PM2I)

题目描述：单级互连网络的互连函数，单元连接。
??

课后习题?6-4?6-5

??实现 16 个处理单元的单级立方体互连网络。
（1）写出所有各种单级立方体互连网络函数的一般式；
（2）3 号处理单元用单级立方体互连网络可将数据直接传送到哪些处理单元上？
（3）单级立方体互连网络换成单级 PM2I 网络的前两问结果。

解：
（1）函数一般式：
$\begin{array}{l}\mathrm{C}\mathrm{u}\mathrm{b}{\mathrm{e}}_0({\mathrm{b}}_3{\mathrm{b}}_2{\mathrm{b}}_1{\mathrm{b}}_0)={\mathrm{b}}_3{\mathrm{b}}_2{\mathrm{b}}_1{\overline{\mathrm{b}}}_0\\ \mathrm{C}\mathrm{u}\mathrm{b}{\mathrm{e}}_1({\mathrm{b}}_3{\mathrm{b}}_2{\mathrm{b}}_1{\mathrm{b}}_0)={\mathrm{b}}_3{\mathrm{b}}_2{\overline{\mathrm{b}}}_1{\mathrm{b}}_0\\ \mathrm{C}\mathrm{u}\mathrm{b}{\mathrm{e}}_2({\mathrm{b}}_3{\mathrm{b}}_2{\mathrm{b}}_1{\mathrm{b}}_0)={\mathrm{b}}_3{\overline{\mathrm{b}}}_2{\mathrm{b}}_1{\mathrm{b}}_0\\ \mathrm{C}\mathrm{u}\mathrm{b}{\mathrm{e}}_3({\mathrm{b}}_3{\mathrm{b}}_2{\mathrm{b}}_1{\mathrm{b}}_0)={\overline{\mathrm{b}}}_3{\mathrm{b}}_2{\mathrm{b}}_1{\mathrm{b}}_0\end{array}$

（2）1、2、7、11 号。

（3）函数一般式：
$\begin{array}{l}\mathrm{P}\mathrm{M}{2}_{+0}(j)=j+1\mathrm{m}\mathrm{o}\mathrm{d}16\\ \mathrm{P}\mathrm{M}{2}_{?0}(j)=j?1\mathrm{m}\mathrm{o}\mathrm{d}16\\ \mathrm{P}\mathrm{M}{2}_{+1}(j)=j+2\mathrm{m}\mathrm{o}\mathrm{d}16\\ \mathrm{P}\mathrm{M}{2}_{?1}(j)=j?2\mathrm{m}\mathrm{o}\mathrm{d}16\\ \mathrm{P}\mathrm{M}{2}_{+2}(j)=j+4\mathrm{m}\mathrm{o}\mathrm{d}16\\ \mathrm{P}\mathrm{M}{2}_{?2}(j)=j?4\mathrm{m}\mathrm{o}\mathrm{d}16\\ \mathrm{P}\mathrm{M}{2}_{\pm 3}(j)=j\pm 8\mathrm{m}\mathrm{o}\mathrm{d}16\end{array}$
?1、2、4、5、7、11、15 号。

互连网络概念：
??处理单元之间需要传送数据，但是当处理单元很多的时候不可能每个单元都两两直接连接，成本太高，就要用互连网络的方式，不同的互连网络就对应不同互连函数，代表不同的连接模式。不同网络的互连函数如下表所示。
（1）立方体单级网络（Cube）
??连接结构类似立方体：4 个处理单元用二维立方体（正方形）连接，每个单元和另外 2 个单元连接；8 个处理单元用三维立方体（正方体）连接，每个单元和另外 3 个单元连接；以此类推。
??如本题，16 个单元用 4 个二进制位表示，每个单元和另外 4 个单元连接。3 号(0011) 所连接的单元为 2(0010)、1(0001)、7(0111)、11(1011) 。
（2）PM2I 单级网络
??PM2I 的含义是 $\mathrm{P}\mathrm{l}\mathrm{u}\mathrm{s}?\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{u}\mathrm{s}{2}^i$（加减 $2^i$），对应着它的互连函数，代表 $j$ 号处理单元可以直接连接哪些单元号。
??如本题， $i$ 取值范围就是 0 到 3 对应 4 位，$N$ 为 16 对应处理单元个数，mod 代表取余。$i$ 取到 3 的时候两个结果是一样的，所以写互连函数的时候是 $2\mathrm{l}\mathrm{o}{\mathrm{g}}_{2}N?1$ 个。对于 3 号：
$3\pm 1=2,4$
$3\pm 2=1,5$
$3\pm 4=?1,7\to 15,7$
$3\pm 8=?5,11\to 11,11$
（3）混洗交换和蝶形基本不考，简单记下互连函数即可。

2. 多级立方体网络

历史考题：2021.04、2018.04、2017.10、2016.10

题目描述：互连函数、网络拓扑结构图、控制开关状态。
??

课后习题?6-6

??阵列有 0~7 共 8 个处理单元互连，要求按 (0,5)、(1,4)、(2,7)、(3,6) 配对通信。
（1）写出实现此功能的互连函数的一般式；
（2）画出用三级立方体网络实现互连函数的互连网络拓扑结构图，并标出各控制开关的状态。

解：
（1）$\mathrm{C}\mathrm{u}\mathrm{b}\mathrm{e}({\mathrm{b}}_2{\mathrm{b}}_1{\mathrm{b}}_0)={\overline{\mathrm{b}}}_2{\mathrm{b}}_1{\overline{\mathrm{b}}}_0$
??把配对通信的二进制位表示写出来就能看出来（只要算一对就行，保险起见都算一算）：
$(0,5)\to (000,101)$
$(1,4)\to (001,100)$
$(2,7)\to (010,111)$
$(3,6)\to (011,110)$

（2）

拓扑结构图画法：
??此图分为两个部分，底部的交换、直连、交换是各控制开关的状态，需要根据题目来确定，其余部分为多级立方体互连网络的结构，这部分是固定的。

??图中 A~L 的矩形框为控制单元，每个控制单元 2 个输入 2 个输出，可以实现的控制方式有 4 种，上播下播通常不考：
（1）直连：输入 (x,y) 输出 (x,y)；
（2）交换：输入 (x,y) 输出 (y,x)；
（3）上播：输入 (x,y) 输出 (x,x)；
（4）下播：输入 (x,y) 输出 (y,y)；

??对于多级立方体网络，每一列控制单元都是二功能交换单元，对应一个等级 $i$，并对应 ${\mathrm{C}\mathrm{u}\mathrm{b}\mathrm{e}}_i$ 互连函数。
??以第 1 列，第 0 级为例，控制单元利用 ${\mathrm{C}\mathrm{u}\mathrm{b}\mathrm{e}}_0$ 实现直连或交换两个功能，对于 ${\mathrm{C}\mathrm{u}\mathrm{b}\mathrm{e}}_0$ 来说 0(000) 对应 1(001)、2(010) 对应 3(011)、4(100) 对应 5(101)、6(110) 对应 7(111)。
??以第 2 列，第 1 级为例，对于 ${\mathrm{C}\mathrm{u}\mathrm{b}\mathrm{e}}_1$ 来说 0(000) 对应 2(010)、1(001) 对应 3(011)、4(100) 对应 6(110)、5(101) 对应 7(111)。
??图中每个控制单元输入输出的数字是一样的，而每一对数字都是可以用对应等级的互连函数实现连接的，如此一来图中每个单元上的数字都可以先写出，然后把相同的数字连接起来就行了。
??这里的多级立方体网络是采用的级控制，即每一级（列）所有的控制开关只能处于一种状态，要么直连要么交换。题目中控制开关的状态可以由两种方法确定：
（1）根据第一问的互连函数，0、2 位要取反，对应 0、2 级交换，1 级直连；
（2）根据网络拓扑结构图，要想让 0 输入和 5 相连：0 从 A0 输入交换从 A1 输出，从 F1 输入直连从 F1 输出，从 J1 输入交换从 J5 输出，最终连接 5。

课后习题?6-10

??并行处理机有 16 个处理单元，要实现相当于先 8 组 2 元交换，然后是 1 组 16 元交换，再次是 4 组 4 元交换的交换函数功能。
（1）写出实现此函数最终等效的功能，各处理器间所实现的互连函数的一般式；
（2）画出实现此互连函数的四级立方体互连网络拓扑结构图，标出各级交换开关的状态。

解：
??这里主要搞懂几组几元交换的意思，得到如 6-6 中的配对通信，就很容易了。如 8 组 2 元交换代表 16 个处理单元分成 8 组，每组 2 个单元，每组的单元反向排列。

| 0  1 |  2  3 |  4  5 |  6  7 |  8  9 | 10 11 | 12 13 | 14 15 |		输入
| 1  0 |  3  2 |  5  4 |  7  6 |  9  8 | 11 10 | 13 12 | 15 14 |		8 组  2 元交换
|14 15   12 13   10 11    8  9    6  7    4  5    2  3    0  1 |		1 组 16 元交换
|13 12   15 14 |  9  8   11 10 |  5  4    7  6 |  1  0    3  2 |		4 组  4 元交换

??0(0000) 对应 13(1101)，可得到互连函数 $\mathrm{C}\mathrm{u}\mathrm{b}\mathrm{e}({\mathrm{b}}_3{\mathrm{b}}_2{\mathrm{b}}_1{\mathrm{b}}_0)={\overline{\mathrm{b}}}_3{\overline{\mathrm{b}}}_2{\mathrm{b}}_1{\overline{\mathrm{b}}}_0$，拓扑结构图按同样的画法，先确定每一级的数字对，标上数字后对应连接。交换开关状态直接安装互连函数确定，0、2、3 级为交换，1 级为直连。

3. 并行存储器无冲突访问

历史考题：2019.10

题目描述：无冲突访问数组元素分布、并行存储器分体数。
??

课后习题?6-14

??在集中式主存的阵列机中，处理单元数为 4，为了使 $4\times 4$ 的二维数组 A 的各元素 $a_{ij}(i=0～3,j=0～3)$ 在行、列、主 / 次对角线上均能实现无冲突访问，请填出数组各元素在存储器分体（分体号从 0 开始）中的分布情况。假设 $a_{00}$ 已放在分体号为 3。体内地址（从 $i+0$ 开始）为 $i+0$ 的位置。

解：
分体数 $M=5=2^{2P}+1$
$P=1$
数组中同一列上两个相邻行的元素其地址错开的体号距离 ${\delta }_1=2^P=2$
数组中同一行中两个相邻列的元素其地址错开的体号距离 ${\delta }_2=1$
数组各元素在存储器分体中的分布情况如下表：

解释：
??无冲突访问就是在访问数组的行、列、主 / 次对角线的元素时没有冲突。需要访问的数据存放在不同的分体中时访问没有冲突，但是多个数据在同一分体中就会产生冲突。假设如下表存储数据，可以看出访问数组每一行、主 / 次对角线的元素没有冲突，但是访问列时每个元素都在一个分体中就会产生冲突，无法并行。

??题目的目的就是要设计分体的数量和数组元素的存放方式，使得实现无冲突访问。解题步骤为：
（1）确定分体数，分体数为大于 4(数组的行列数、处理单元数) 的质数，也就是 5；
（2）将分体数改写为 $2^{2P}+{\delta }_2=2^{2\times 1}+1$ 的形式；
（3）${\delta }_1=2^P=2$，代表同一列元素的间隔，如 $a_{00}$ 存在 3，$a_{10}$ 要存在 5，因为分体号是 $0～4$，5 就对应到 0；
（4）${\delta }_2=1$，代表同一行元素的间隔，如 $a_{00}$ 存在 3，$a_{01}$ 要存在 4。

7. 多处理机

1. 霍纳法则

历史考题：2019.10、2019.04、2018.10、2017.04、2015.04

题目描述：画树形流程图，计算级数 $T_P$、机数 $P$、加速比 $S_P$、效率 $E_P$。
??

课后习题?7-6

??由霍纳法则给定的表达式如下：$E=a(b+c(d+e(f+gh)))$，利用减少树高的办法来加速运算，要求：
（1）画出树形流程图；
（2）确定 $T_P$、$P$、$S_P$、$E_P$ 的值。

解：
（1）

（2）$T_P=4,P=3,S_P=7/4,E_P=7/12$

解释：
??原式 $E=a(b+c(d+e(f+gh)))$ 只能从内向外依次计算，一共 7 步，不能并行，也就是只能单处理机处理，此时的树高（级数）为 $T_1=7$。
??将式子改写，通用方法是先完全展开，然后尽可能两两成一对并且提公因式：

$\begin{array}{rl}E& =a(b+c(d+e(f+gh)))\\ & =ab+acd+acef+acegh\\ & =(ab+acd)+(acef+acegh)\\ & =a(b+cd)+ace(f+gh)\\ & =[a(b+cd)]+[(ace)(f+gh)]\end{array}$

??然后按公式画树形图即可，个人感觉从上往下画比较好，顶部为加法，展开两个分支，然后在逐步画各个子项的计算，这样比较容易对齐树的层级。
??注意点：有些情况画法是不唯一的，例如某一项为 $ab(c+d)$，此时可以 $ab$ 和 $c+d$ 并行再相乘分两步，也可以先算 $c+d$ 再依次乘上 $a$ 和 $b$ 分三步。此时需要根据题目的情况来决定，有时按并行的两步来计算并不能减少树高，反而会增加机数（因为只一个分支不一定影响整个树高）。
??级数 $T_P$ ：树高，树含有运算符的层级数量；
??机数 $P$：有多少台处理机在进行并行运算，看每一层有多少个运算符，取最大值；
??加速比 $S_P=T_1/T_P$：单处理机的级数和当前并行加速后的级数的比值；
??效率 $E_P=S_P/P$：加速比除以机数。

2. FORK、JOIN 语句

历史考题：2021.10、2020.10、2020.04、2016.04、2015.10

题目描述：画树形流程图，计算级数 $T_P$、机数 $P$、加速比 $S_P$、效率 $E_P$。
??

课后习题?7-8

??若有下述程序：
??$\mathrm{U}=\mathrm{A}+\mathrm{B}$
??$\mathrm{V}=\mathrm{U}/\mathrm{B}$
??$\mathrm{W}=\mathrm{A}?\mathrm{U}$
??$\mathrm{X}=\mathrm{W}?\mathrm{V}$
??$\mathrm{Y}=\mathrm{W}?\mathrm{U}$
??$\mathrm{Z}=\mathrm{X}/\mathrm{Y}$
??试用 FORK、JOIN 语句将其改写成可在多处理机上并行执行的程序。假设现有两台处理机，且除法速度最慢，加、减法速度最快，请画出该程序运行时的资源时间图。

解：
（1）改写后的程序为：

							| 语法解释:
10	U = A + B				| 执行语句左边的编号通常就按 10 20 30... 依次增大, 没有严格的要求
	FORK	30				| FORK	30 就代表下面一条语句和 30 号语句并行
20	V = U / B				|
	JOIN 	2				| JOIN	2 就代表有 2 条语句并行
	GOTO	40				| GOTO	40 是因为 20 运行完接下来要运行 40
30	W = A * U				|
	JOIN	2				| 30 下面不用写 GOTO	 40 是因为按顺序它运行完本来就是运行 40
40	FORK	60				| 这里的 FORK 编号是因为前面有 GOTO 要跳到这里来, 而第一条按顺序运行
50	X = W - V				| 没有别的语句要用到它的编号, 就省略了。
	JOIN	2				|
	GOTO	70				| 如果有 2 条以上的语句要并行就是多写几行 FORK, 同时 JOIN 改成对应的数量
60	Y = W * U				| 例如 20 30 40 都并行:
	JOIN	2				| FORK	30
70	Z = X / Y				| FORK	40

??题目给出的程序每一行就是一条指令，通过观察可以分析程序的并行性，得到程序的运行步骤：
（1）① $\mathrm{U}=\mathrm{A}+\mathrm{B}$ 执行
（2）② $\mathrm{V}=\mathrm{U}/\mathrm{B}$ 和 ③ $\mathrm{W}=\mathrm{A}?\mathrm{U}$ 可并行
（3）④ $\mathrm{X}=\mathrm{W}?\mathrm{V}$ 和 ⑤ $\mathrm{Y}=\mathrm{W}?\mathrm{U}$ 可并行
（4）⑥ $\mathrm{Z}=\mathrm{X}/\mathrm{Y}$ 执行

（2）资源时间图

??优化了一下答案的图，很多题目中只说加减法最快，除法最慢，这里直接自己规定加减法为 4，乘法 5，除法 6，FORK、JOIN、GOTO 都是 1。部分题目也会这样规定，定量画出来更直观。
??画图流程和注意事项：
（1）10 号语句，加法占 4 个时间
（2）紧接着 FORK 30，后面按顺序运行 20，并且上面并行 30；
（3）20 和 30 运行完都是接上 JOIN 2 ，JOIN 2 是个关键，它会判断 2 条并行指令是否都运行完，如果没有当前的指令就断开了要等全都运行完，如果已经都运行完了就按当前指令往下运行，如果还有指令没开始运行，就会运行未运行指令。
??有点绕，下面举几个例子：
??这道题里面，30 是乘法，20 是除法，所以 30 后面的 JOIN 2 会发现 20 还没运行完就停住了不会往下运行 40，而 20 的 JOIN 2 发现都运行完了就会进入 GOTO 40；假如是 20 先运行完那么就不会进入 GOTO，而是 30 运行完后自然按顺序运行 40。后面也是如此，因为 50 结束的比 60 快，所以 50 后面的 GOTO 70 就被截断了不运行，等 60 运行完接上 70。
??有的情况是 JOIN 4 是 4 条语句并发，假设是 (10,20,30,40)，但是只有 2 个处理机，那么就是先并行 10 和 20，谁先运行完后面紧跟 30，以此类推。
（4）还有个注意点是 FORK 相关的，假设现在是 3 条语句并发 (10,20,30)，在 3 个处理机上运行，那么运行 10 之前就有 2 个 FORK 语句：FORK 20 和 FORK 30，画图的时候当 FORK 20 一运行完，CPU2 就可以开始执行 20 了，然后 FORK 30 运行完再执行 30 和 10，参考本题的虚线。

8. 数据流机和归约机

??不考大题。

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖