发布时间 : 星期日 文章（自考02325李学干版）计算机系统结构课后习题更新完毕开始阅读1a42c41b48d7c1c708a145a6
第七章 多处理机
1.多处理机在结构、程序并行性、算法、进程同步、资源分配和调试上与并行处理机有什么差别？
答： 多处理机与并行处理机的主要差别是并行性的等级不同。 （1）结构灵活性。多处理机制结构灵活性高于并行处理机。 （2）程序并行性。并行处理机是操作级并行，并行性仅存在于指令内部，识别比较容易，由程序员掌握程序并行性的开发;多处理是指令、任务、作业并行，并行性主要存在于指令外部，另外还存在于指令内部，识别比较困难，必须利用多种途径开发程序的并行性。
（3）并行任务派生。并行处理机工作能否并行工作由指令决定，多处理机必须有专门指令指明程序能否并行执行，派生的任务数是动态变化的。 （4）进程同步。并行处理机的进程同步是自然的，而多处理机必须采取同步措施。
（5）资源分配和任务调度。多处理机的资源分配和任务调度比并行处理机复杂得多。
2.多处理机有哪些基本特点？发展这种系统的主要目的可能有哪些？多处理着重解决哪些技术问题？ 答： ○多处理机的基本特点：
多处理机具有两台以上的处理机,在操作系统控制下通过共享的主存或输入/输出子系统或高速通讯网络进行通讯.结构上多个处理机用多个指令部件分别控制,通过机间互连网络通讯;算法上不只限于处理向量数组,还要实现更多通用算法中的并行;系统管理上要更多地依靠软件手段,有效解决资源分配和管理,特别是任务分配,处理机调度,进程的同步和通讯等问题.
○使用多处理机的目的:
一是用多台处理进行多任务处理协同求解一个大而复杂的问题来提高速度,二是依靠冗余的处理机及其重组来提高系统的可靠性,适应性和可用性.
○多处理着重要解决的技术问题:
（1）硬件结构上，如何解决好处理机、存储器模块及I/O子系统间的互连。
（2）如何最大限度开发系统的并行性，以实现多处理要各级的全面并行。
（3）如何选择任务和子任务的大小，即任务的粒度，使并行度高，辅助开销小。
（4）如何协调好多处理机中各并行执行任务和进程间的同步问题。 （5）如何将任务分配到多处理机上，解决好处理机调度、任务调度、任务调度和资源分配，防止死锁。
（6）一旦某个处理发生故障，如何对系统进行重新组织，而不使其瘫痪。
（7）多处理机机数增多后，如何能给编程者提供良好的编程环境，减轻程序的复杂性。
3.分别画出4*9的一级交叉开关以及用两级2×3的交叉开关组成的4×9的Delta网络，比较一下交叉开关设备量的多少？ 解答：
4*9的一级交叉开关如下图所示：
两级2×3的交叉开关组成的4×9的Delta网络如下图所示：
2^2*3^3有Delta网络由5个2*3的交叉开关组成，其交叉开关的结点数由一级网络的36个减少到现在Delta网络中的2*3*5=30个。 剖析： 第一级有2个2*3的交叉开关，第2级有3个2*3的交叉开关，级间采用混洗拓扑。
4.说明4＊4交叉开关组成的两级16*16交叉开关网络虽节省了设备，但它是一个阻塞式网络。 答：
16*16交叉开关网络需要256个开关结点，每个结点中选1的多路裁决和选择电路。采用4×4的交叉开关构成的二级交叉开关网络，共需要16×8=128个开关结点，每个结点只需要4中选1的多路裁决和选择电路，节省了设备。但它是一个阻塞式网络。因为第1级每4个输入端中只能有一个连到第2级的一个输入端，而第2级的这个输入端本可以对应4个输出端的某一个。这就意味着，当第1级4个输入端中的某一个连到了最终的某个输出端时，第1级同组内其它3个输入端由于有路径冲突，就不能同时将信息传送到第2级输出相应的另外3个输出端上，而采用16×16的一级交叉开关就不存在这种问题。
5.由霍纳法则给定的表达式如下：E=a(b+c(d+e(f+gh))) 利用减少树高的办法来加速运算，要求 (1)画出树形流程图;
(2)确定Tp、P、Sp、Ep诸值。 解答：
(1)对于原式，单处理机串行运算树形流程图如左下图所示，多处理机并行运算树形流程图如右下图所示。 17
(2)P台处理机运算的级数Tp=4。 所需处理机数目P=3。
加速比Sp=顺序运算的级数T1/P台处理机运算的级数Tp=7/4。 效率Ep=加速比Sp/所需处理机数目P=7/12。
6、求A1、A2 ... ... A8的累加和，有如下程序： S1 A1=A1+A2 S2 A3=A3+A4 S3 A5=A5+A6 S4 A7=A7+A8 S5 A1=A1+A3 S6 A5=A5+A7 S7 A1=A1+A5
（1）写出用FORK、JOIN语句表示其并行任务的派生和汇合关系的程序，以假想使此程序能在多处理机上运行。
（2）画出该程序在有3台处理机制系统上运行的时间关系示意图。 （3）画出该程序在有2台处理机制系统上运行的时间关系示意图。 解答：
(1)用FORK、JOIN语句表示其并行任务的派生和汇合关系的程序如下。 FORK 20 FORK 30 FORK 40 10 A1=A1+A2 JOIN 4 GOTO 80 20 A3=A3+A4 JOIN 4 GOTO 80 30 A5=A5+A6
JOIN 4 GOTO 80 40 A7=A7+A8 JOIN 4 80 FORK 60 50 A1=A1+A3 JOIN 2
GOTO 70 60 A5=A5+A7
JOIN 2 70 A1=A1+A5
(2)在有3台处理机制多处理机系统上运行的资源时间图如下图所示。假设标号为50和60的两个并发进程中，标号为60的进程最后完成。
(3)在有2台处理机制多处理机系统上运行的资源时间图如下图所示。假设标号为50和60的两个并发进程中，标号为50的进程最后完成。
剖析：
GOTO 70语句的问题关键是70语句是在50语句还是60语句所在CPU上执行的。也就是说50语句和60语句谁先执行完。
18
7、若有如下程序： V=U/B W=A*U X=W-V Y=W*U Z=X/Y
试用FORK、JOIN语句改写成可在多处理机上并行执行的程序。假设现有两台处理机，且除法速度最慢，加、减法速度最快，请画出该程序运行时的资源时间图。 解答：
用FORK、JOIN语句改写成可在多处理机上并行执行的程序如下： S1 U=A+B FORK S3 S2 V=U/B JOIN 2 GOTO S4' S3 W=A*U JOIN 2 S4' FORK S5 S4 X=W-V JOIN 2 GOTO S6 S5 Y=W*U JOIN 2 S6 Z=X/Y
该程序在有2台处理机的多处理机系统上运行时的资源时间图如下所示：
8.分别确定下列各计算机系统中，计算点积S=(8)∑(i=1)ai*bi所需的时间(尽可能给出时空图示意)： (1)通用PE的串行SISD系统;
(2)具有一个加法器和乘法器的多功能并行流水SISD系统; (3)有8个处理器的SIMD系统; (4)有8个处理器的MIMD系统。
设访存取指和取数的时间可以忽略不计；加与乘分别需要2拍和4拍；在SIMD和MIMD系统中处理器(机)之间每进行一次数据传送的时间为1拍，而在SISD的串行或流水系统中都可忽略；在SIMD系统中PE之间采用线性环形互连拓扑，即每个PE与其左右两个相邻的PE直接相连，而在MIMD中每个PE都可以和其它PE有直接的通路。
解答:
(1)利用通用PE的串行SISD系统计算点积所需时间为46拍，时空图如下图所示：
(2)利用具有一个加法器和乘法器的多功能并行流水SISD系统计算点积所需时间为15拍，时空图如下图所示：
(3)利用有8个处理器的SIMD系统计算点积所需时间为14拍，时空图如下图所示：
(4)利用有8个处理器的MIMD系统计算点积所需时间为14拍，时空图如下图所示：
19
第八章 其它计算机结构
1、简述脉动阵列结构的特点。
答： （1）结构简单，规整，模块化强，可扩充性好；
（2）处理单元间数据通信距离短，规则，使数据流和控制流的设计，同步
控制均简单规整；
（3）脉动阵列机中各处理单元同时运算，并行性极高，可通过流水获得很
高的吞吐率；
（4）输入数据被多个处理单元重复使用，减轻阵列与外界 I/O通信量，降低系统对主存和I/O系统频宽的要求。 （5）脉动阵列结构的构形与特
定任务和算法密切相关，具有专用性，限制了应用范围。
2、什么叫控制驱动、数据驱动、需求驱动？
答： 控制流驱动:即指令的执行是在PC(程序计数器)的控制下，按照事先
指定的序列进行的,指令的执行顺序隐含在控制流中。
9.设程序有T个任务，在A、B两台处理机组成的多处理机上运行。每个 数据流驱动:即指令的执行是按照数据相关和资源可用性确定的序列进行任务在A处理机上执行的时间为E，在B处理机上执行的时间为2E，不考的，指令的执行基本上是无序的。只要一条指令所需的操作数全部就绪,就可以虑机间通讯时间，问如何分配任务，可使系统总执行时间最短？总执行时间最短为多少？ 解：
设为A处理机分配I个任务，为B处理机分配T-I个任务,则系统总
被激发并执行。
需求驱动:即指令的执行是按照数据需求确定的序列进行的。
3、什么叫大规模并行处理机MPP?什么叫机群系统？
执行时间最短为IE=2(T-I)E。解得：I=2T/3。所以，总执行时间最短为答： MPP是大规模并行处理机，指用数百万个高性能，低成本的RISC微2TE/3。
10.简述多处理机操作系统3种不同类型的构形,列出每种构形有优点和缺点以及设计中的问题. 答: 类构型 型 工作负荷固定，从处主管理程序只在一台指定硬件结构简对主机的可靠性要求理机的能从的处理上运行 型 单，控制简单 高，灵活性差 力明显低于主处理机 控制功能分散到多台处适应分布处各理机，共同完成对整个理的模块化自系统的控制。每台处理结构，对主机独机都有一个独立的管理依赖性小，可立程序(操作系统的内核)靠性高，系统型 在运行。要求管理程序效率较高 必须是可再入的。 集中了主从浮管理程序在处理机间浮型和各自独动动 型 立型的优点，处理机系且灵活性高 统
设计最困难 统，同构多处理机系荷的平衡比较困难 紧耦合多人为干预，处理机间负输入输出结构变换需要统 大了开销。实现复杂，处理机系格会增加共享冲突，加松耦合多
用表格，但一些共享表
尽管每台处理机都有专优点 缺点 适用场合 处理器通过互联网络互连，组成的SIMD或MIMD系统。
机群系统是将多个高性能工作站或高档微型计算机使用高速通信网络加以
互连组成系统。
4、用结构有向图形式画出求解 x=square root (a+b)*d/e-e/d 的数据
流程序图，当a=4、b=8时，表示出该数据流程序图的执行过程。
20