计算机组成与结构课后习题
问答题
1、解释下列术语
共享存储多处理机 分布存储多处理机 SMP S2MP MPP 机群系统 虚拟共享存储器
2、处理机在结构、程序并行性、算法、进程同步、资源分配和调度上与并行处理机有什么差别？其根本原因是什么？
3、多处理机有哪些基本特点？发展这种系统的主要目的有哪些？多处理机着重解决哪些技本问题？
4、画出多处理机两种不同结构的框图。从哪些途径可以减少多处理机访问主存的冲突？
5、设16个处理机编号分别为0、1、…、15，采用单级互连网络。当互连函数分别为：
(1) Cube3
(2) PM2+3
(3) PM2-0
(4) Shuffle
(5) Shuffle(Shuffle) 时，第13号处理机各与哪一个处理机相连？
6、有编号为0、1、2、…、31共32个处理机，分别计算下列互连函数。（E为交换函数，S为混洗函数，B为蝶式函数，PM2I为移数函数。自变量为10进制数表示的处理机编号）
(1) E
2
(12)
(2) S(8)
(3) B(9)
(4) PM2I+3(28)
(5) E0(S(4))
(6) S(E0(18))
(7) 用E0和S构成混洗交换网（每步只能使用E0或S一次），网络直径是多少？从5号处理机发送数据到7号处理机，最短路径需要经过几步？列出经过的处理机编号
(8) 采用移数函数构成互连网，网络直径是多少？结点度是多少？与2号处理机距离最远的是几号处理机？
7、试在含一个PE的SISD机和在含n个PE的且连接成一线性环的SIMD机上计算下列求内积的表达式：
假定完成每次ADD操作需2个单位时间，完成每次MULTIPLY操作需4个单位时间，沿双向环在相邻PE间移数需1个单位时间。
(1)SISD计算机上计算s的时间是多少？
(2)SIMD计算机上计算s的时间是多少？
(3)用SIMD机计算s相对于SISD机计算的加速比是多少？
8、试确定在下列4种计算机系统中，计算下列表达式所用的时间。
其中，加法需用30ns，乘法需用50ns。在SIMD和MIMD计算机中，数据由一个PE（处理单元）传送到另一个PE需要10ns，而在SISD计算机中数据传送时间可忽略不计。在SIMD计算机中PE间以线性环连接（以单向方式传送数据），而在MIMD计算机中，PE间以全互连方式连接。
(1)具有一个通用PE的SISD计算机系统。
(2)具有一个加法器和一个乘法器的多功能部件的SISD计算机系统。
(3)具有8个PE的SIMD计算机系统。
(4)具有8个CPU的MIMD计算机系统。
9、下面由六条指令组成的代码段需运行64次才能计算向量算术表达式：
D(I) = A(I) + B(I) x C(I)，其中0≤I≤63。
Load R1,B(I) /R1←Memory(α+I)/
Load R2,C(I) /R2←Memory(β+I)/
Multiply R1,R2 /R1←(R1) x (R2)/
Load R3,A(I) /R3←Memory(γ+I)/
Add R3,R1 /R3←(R3)+(R1)/
Store D(I),R3 /Memory(θ+I)←(R3)/
这里R1、R2和R3为CPU的寄存器，(R1)是R1的内容，α、β、γ和θ分别是数组B(I)、C(I)、A(I)和D(I)的起始存储地址。假设在一台SIMD机中，不论单处理机还是单个PE，每次取数或存数需4个时钟周期，加法需2个周期，乘法需8个周期。 a) 计算在一台SISD单处理机计算机上依次重复执行上述代码段64次所需的CPU周期数，忽略所有其它延迟时间。 b) 假设用一台有64个PE的SIMD机，以6条同步向量指令对64组向量数据执行上述向量操作，所用的时钟速率与前面一样。计算SIMD机的总执行时间，忽略指令广播及其它延迟。 c) SIMD计算机与SISD计算机相比，其加速比为多少？
10、a为一个计算机系统中n台处理机可以同时执行的程序代码的百分比，其余代码必须用单台处理机顺序执行。每台处理机的执行速率为x MIPS，并假设所有处理机的处理能力相同。 （a） 试用参数n、a、x推导出系统专门执行该程序时的有效MIPS速率表达式。
（b） 假设n=16，x=4 MIPS，要求得到系统的性能为40MIPS，试求a值。