8.6 试在含一个PE的SISD机和在含m个PE且连接成一线性环的SIMD机上计算下列求内积的表达式。
假定完成每次ADD操作需2个单元时间，完成每次MULTIPLY操作需4个单位时间，沿双向环在相邻PE间移数需1个单位时间。
(a) SISD计算机上计算s的时间是多少？
(b) SIMD计算机上计算s的时间是多少？
(c) 用SIMD机计算s相对于用SISD机计算的加速比是多少？

8.7 今有K对向量，其中第i对由行向量Ri和列向量Ci组成，每个的维数为N=2n。可按下式计算第i对向量的内积：
下面是完成IP[i](I=1,2, …, K)的算法
(a) 忽略初始化、下标修正和测试等所需的时间，试计算在单处理机上实现上述算法总共需多少时间，并表达成K和N的函数，假定完成乘法与加法需用相同的单位时间。
(b) 为加速上述计算，可采用SIMD机来发掘计算中的并行性，试求出下列两种不同情况上的计算时间。
(i) 用P＝N个处理单元PE逐对地计算每对Ri、Ci的IP[i]。
(ii)将一对向量分配给每个PE，由此PE来计算其内积。这种情况下PE数P＝K。

8.8 一台向量计算机只能以下述两种方式中的一种运行：一种是向量方式，执行速度Rv为 10Mflops；另一种是标量方式，执行速度Rs为1Mflops。设a是该计算机的典型程序代码中可向量化部分的百分比。
(a) 推导出该计算机平均执行速度Ra的公式。
(b) 画出以a为横坐标，Ra为纵坐标的曲线，a的范围为(0，1)。
(c) 要使Ra达到7.5Mflops，问向量化百分比a应多大？
(d) 假设Rs=1Mflops，a=0.7 ，要使Ra达到2Mflops，问Rv应为多大？

8.9 设计一种采用加、乘和数据寻径操作的算法，分别在下面两种计算机系统上用最短的时间来计算表达式s=A1×B1＋A2×B2＋…A32×B32。假设加法和乘法分别需要两个和四个单位时间，从存储器取指令、取数据、译码的时间忽略不计，所有的指令和数据已装入有关的PE。试确定下列每种情况的最小计算时间。
(a) 一台串行计算机，处理机中有一个加法器和乘法器，同一时刻只有其中一个可以使用。这种单处理机系统不需要数据寻径操作。
(b) 一台有8个PE(PE0, PE1, …PE7)的SIMD计算机，8个PE连成双向环结构。每个PE用一个单位时间可以把数据直接送给它的相邻PE。操作数Ai和Bj最初存放在PEi (mod 8 )中，其中i=1, 2, …,32。每个PE可在不同时刻执行加法或乘法。

8.10 A＝(aij)，B=(bij)为64×64的矩阵。有一台由64个带本地存储器的PE组成的SIMD机器，64个互连成8×8的两维双向链路的环网结构。试设计一种矩阵乘算法，使之在这种机器上执行的时间最短。
(a) 画出矩阵元素aij和bij在PE存储器上的初始化分配情况。
(b) 确定完成矩阵乘法所需要的SIMD指令。假设每个PE在每个周期可以执行一次乘法，或一次加法，或一次移数（把数据移给它四个相邻之一）操作。在把数据传给相邻PE之前，应该首先对本地数据进行乘法和加法操作。SIMD移数操作可以在循环连接的环网上向东、或向西、或向南、或向北进行。
(c) 估算矩阵乘法总共需要多少个SIMD指令周期，这包括所有的运算和数据寻径操作时间在内。最后乘积C＝A×B＝(Cij)在各个PE的存储器中没有拷贝。
(d)假设开始时允许数据拷贝，即同一数据元素装入多个PE的存储器。试设计一种新的算法，以进一减少SIMD执行时间。这时必须将通过数据广播指令或数据寻径(移数)指令进行原始数据拷贝的时间考虑在内，而且每个结果元素cij只放在每个PE的存储器中。

8.11 多处理机在结构、程序并行性、算法、进程同步、资源分配和调度上与并行处理机有什么差别？其根本原因是什么？

8.12 多处理机有哪些基本特点？发展这种系统的主要目的有哪些？多处理机着重解决哪些技本问题？

8.13 画出多处理机两种不同结构的框图。从哪些途径可以减少多处理机访问主存的冲突？

8.14 分析并行处理机、单处理机流水方式、多处理和单处理机"分析""执行"一次重叠方式这4种系统，分别属何种指令流/数据流系统？表现出何种并行性？能达到何种并行性等级？各遵循何种并行性途径发展而来？影响系统吞吐率和效率提高的主要问题是什么？如进行向量运算C＝A＋B，向量长度较长时，它们连同单处理机顺序方式相比，比较在吞吐率、设备量、设备利用率方面的优劣。

8.15 假设有两个处理器,处理器甲的速度是乙的两倍, 参考性能模型公式8.1, 请问如何分配任务以达到最优性能?

8.16 本题的目的在于设计一个与实际程序相符的性能模型。参考程序6.1,最内部的一对循环更新矩阵内的一个矩形区域,而外层循环重复该操作n次。回答下列问题(忽略进程同步和计数的开销,只考虑数据通信开销):
(a) 分配此矩阵,使每一行由一个处理器处理,请确定这种算法中必定要进行的处理器之间数据传送情况。如果无广播机制,那么此算法中要进行多少次数据传输?并与串行计算机与多处理器的计算机相比较。
(b) 如果所设计的体系结构支持单周期的广播机制,此种机制能使一个处理器在一个周期内向所有的接收处理器发送一个消息。在此前提下重复((a)。
(c) 已知N=10 ,R/C=1, 在具有广播机制的系统中, 如何向处理器分配任务以取得最优效果。

8.17 重复题8.16,条件改为矩阵的每一列存储于一个处理器中,与每一行存储于一个处理器的方案进行比较并讨论存储格式对任务最优分配的影响。

8.18 解决多处理机系统中的多Cache一致性问题可采用哪些方法？叙述它们的优缺点。

8.19 何谓大规模并行处理机？它的主要特点是什么？

8.20 何谓SMP？它的主要特点是什么？

8.21 何谓机群系统？它的主要特点是什么？

8.22 何谓虚拟共享存储器？叙述它的优点和实现方法。

8.23 试确定在下列4种计算机系统中，计算下列表达式所用时间。

其中，加法需用30ns，乘法需用50ns。在SIMD和MIMD计算机中，数据由一个PE（处理单元）传送到另一个PE需要10ns，而在SISD计算机中数据传送时间可忽略不计。在SIMD计算机中PE间以线性环方式互连（以单向方式传送数据），而在MIMD计算机中，PE间以全互连方式连接。
(a) 具有一个通用PE的SISD计算机系统；
(b) 具有一个加法器和一个乘法器的多功能部件的SISD计算机系统；
(c) 具有8个PE的SIMD计算机系统；
(d) 具有8个PE的MIMD计算机系统。

8.24分别确定在下列各计算机系统中，计算点积 所需的时间:
(a) 通用PE的串行SISD系统；
(b) 具有一个加法器和乘法器的多功能并行流水SISD系统；
(c) 有8个处理器的SIMD系统；
(d) 有8个处理机的MIMD系统。
设访存取指和取数的时间可以忽略不计；加与乘分别需要2拍和4拍；在SIMD和MIMD系统中处理器（机）之间每进行一次数据传送的时间为1拍，而在SISD的串行或流水系统中都可忽略；在SIMD系统中，PE之间采用线性环形互连拓扑，即每个PE与其左右两个相邻的PE直接相连，而在MIMD中每个PE都可以和其它PE有直接的的通路。