并行处理机和多处理机.doc

并行处理机和多处理机1. 设a为一个计算机系统中n台处理机可以同时执行的程序代码的百分比，其余代码必须用单处理机顺序执行。每台处理机的执行效率为xMIPS,并假设所有处理机的处理能力相同。那么当n=16,x=4MIPS的情况下，a为多少的时候系统的性能能够达到40MIPS?A.0.84B.0.88C.0.92D.0.96【答案】D2. 设a为一个计算机系统中n台处理机可以同时执行的程序代码的百分比，其余代码必须用单处理机顺序执行。每台处理机的执行效率为xMIPS,并假设所有处理机的处理能力相同。那么当n=16,a=0.92的情况下，x为多少的时候系统的性能能够达到40MIPS?A. 4MIPSB. 4.5MIPSC. 5MIPSD. 5.5MIPS【答案】D3. 假设一台4处理机带有共享存储器的计算机来执行一个混和程序。此多处理机有4种运行方式。与1,2,3,4四台处理机处于活动状态相对应。设为i台处理机用于执行上述程序的时间百分数。已知；R1=4MIPS，R2=8MIPS，R311MIPS，R4=15MIPS，试问上述混合程序的调和均值执行时间T为多少A. 0.25MIPSB. 0.375MIPSC. 0.5MIPSD. 以上都不对【答案】D4. 假定有一个处理机台数为32的共享存储器多处理机系统。假设典型处理机每条执行执行时间对全局存储器进行访问的平均次数为1.6。共享存储器的平均存储时间为使用本地存储器的单处理机的速率为2MIPS速率，问这个多处理机系统的有效MIPSA.15.24B.14.6C.13.5D.以上均不对 【答案】A5. 在有个节点的三维网格中，求个数据相加的和，假设所有的数据已经被平均分配到了各个节点中，加法运算时间忽略不计，数据传递操作一次需要单位时间，问最小时间开销是多少？An/2BnC3n/2D2n【答案】C6. 一台向量计算机只能以下述两种方式中的一种运行：向量方式，执行速度是10MFLOPS；另一种是标量方式，执行速度Rs为1MFLOPS。设a是该计算机的典型程序代码中可向量化的百分比。若要使Ra达到7.5MFLOPS，问向量化百分比a应有多大（Ra使平均执行速度）ABCD【答案】C7. 设a为一个计算机系统中n台处理机可以同时执行的程序代码的百分比，其余代码必须用单处理机顺序执行。而单个节点机的处理效率是4MIPS,那么在a=0.8的条件下，要让系统的效率达到20MIPS,则至少需要多少台节点机？A.8B.16C.32D.以上均错误【答案】D8. 设a为一个计算机系统中n台处理机可以同时执行的程序代码的百分比，其余代码必须用单处理机顺序执行。而单个节点机的处理效率是4MIPS,那么在a=0.8的条件下，要让系统的效率达到10MIPS,则至少需要多少台节点机？A.4B.8C.16D.20【答案】C9. 假定有一个处理机台数为p的共享存储器多处理机系统。设m为典型处理机每条执行执行时间对全局存储器进行访问的平均次数。设t为共享存储器的平均存储时间，x为使用本地存储器的单处理机MIPS速率，再假定在多处理机上执行n条指令。现在假设p=32,m=0.4,t=1s,要让多处理机的有效性能达到56MIPS，需要每台处理机的MIPS效率是多少？A.2B.4C.5.83D.40【答案】B10. 设有一个4个处理器的SIMD系统，假设在系统中访存取指和取数的时间可以忽略不计；加法与乘法分别需要2拍和4拍；在SIMD系统中处理器（机）之间每进行一次数据传送的时间为1拍；在SIMD系统中，PE之间采用线性环形互连拓扑，即每个PE与其左右两个相邻的PE直接相连。求利用此系统计算表达式所需的节拍数。A. 23B. 12C. 11D. 10【答案】C11. 设计一种采用加、乘和数据寻径操作的算法，计算表达式。假设加法和乘法分别需要2个和4个单位时间，从存储器取指令、取数据、译码的时间忽略不计，所有的指令和数据已经装入有关的PE。现有一台串行计算机，有一个加法器，一个乘法器，问最短多少单位时间计算出s？A. 192nsB. 130nsC. 128nsD. 以上结果都不对【答案】B12. 设有一个4个处理器的MIMD系统，假设在系统中访存取指和取数的时间可以忽略不计；加法与乘法分别需要2拍和4拍；在MIMD系统中处理器（机）之间每进行一次数据传送的时间为1拍；在MIMD系统中，每个PE都可以和其它PE有直接的的通路。求利用此系统计算表达式所需的节拍数。A. 23B. 12C. 11D. 10【答案】D13. 试确定在具有8个PE的MIMD计算机系统中，计算下列表达式所用时间其中，加法需用30ns，乘法需用50ns。，数据由一个PE（计算单元）传送到另一个PE需要10ns，在MIMD计算机中PE间以全互连方式连接A. 250nsB. 210nsC. 200nsD. 180ns【答案】B14. 设计一种采用加、乘和数据寻径操作的算法，计算表达式。假设加法和乘法分别需要2个和4个单位时间，从存储器取指令、取数据、译码的时间忽略不计，所有的指令和数据已经装入有关的PE。现有一台8个PE的SIMD计算机，8个PE连成双向环结构，每个PE可以用一个单位时间把数据直接送给它的相邻PE。每个PE可以在不同时刻执行加法或乘法。求最短求出s的需要多少单位时间。A. 70nsB. 64nsC. 62nsD. 50ns【答案】D15. 什么是集中式共享多处理机？什么是分布式共享多处理机【答案】集中式共享多处理机：通过大容量的cache和总线互联使各处理机共享个单独的集中式存储器的多处理机。分布式共享多处理机：采用非集中式，存储器分布到各个处理机上的多处理机16. 简SIMD计算机的分布式存储器与共享存储器的异同。【答案】SIMD计算机的分布式存储器与共享存储器的相同点都存在互联网络。不同点式在共享内存方案中，共享的多体并行存储器通过对准网络与各处理单元相连。在分布内存方案中，每个处理单元有自己的本地存储器，处理单元有自己的本地存储器，处理单元之间的数据通过数据寻径网络完成。17. 试分析与比较SIMD计算机与向量计算机的相同与不同【答案】SIMD计算机和向量计算机的相同点是两种计算机都能对大量数据进行向量处理，特别适用于高速数值计算。不同点是SIMD计算机获得高处理速度主要原因是采用资源重复的并行措施，多个处理单元并行工作，向量计算机依靠的是多功能流水线部件时间重叠提高速度；另一区别是SIMD计算机有它的互联网络。18. 何谓SMP？它的主要特点是什么？【答案】SMP成为共享存储型多处理机，也成为对称型多处理机。19. 何谓机群系统？它的主要特点是什么？【答案】机群系统是利用高速通用网络将一组高性能工作站或高档PC机，按某种结构连接起来，并再并行程序设计以及可视化人机交互集成开发环境支持下，统一调度，协调处理，实现高效并行处理的系统。特点：1. 系统开发周期短2. 用户投资风险小3. 系统价格低4. 节约系统资源5. 系统扩展性好6. 用户编程方便20. 试在含一个PE的SISD机和在含n个PE且连接成一线性环的SIMD机上计算下列求内积的表达式：其中n=2k假设完成每次ADD操作需要2个单元时间，完成每次MULTIPLY操作需要4个单位时间，沿双向环在相邻PE间移数需1个单位时间(1) SISD计算机上计算s需要多少时间(2) SIMD计算机上计算s需要多少时间(3) SIMD机计算s相对于SISD计算的加速比是多少？【答案】(1) 4n+2(n-1)(2)(3)21. 如果一台SIMD计算机和一台流水线处理机具有相同的计算性能，对构成它们的主要部件分别有什么要求？【答案】一台具有n个处理单元的SIMD计算机与一台具有一条n级流水线并且时钟周期为前者1/n的流水线处理机的计算性能相当，两者均是每个时钟周期产生n个计算结果。但是，SIMD计算机需要n倍的硬件（n个处理单元），而流水线处理机中流水线部件的时钟速率要求比前者快n倍，同时还需要存储器的带宽也是前者的n倍。22. 今有K对向量，其中第i对由行向量Ri和列向量Ci组成，每个维数为N =2n,可按下式计算第i对向量的内积：下面是完成IPi（i = 1，2，K）的算法。1. 忽略初始化、下标修正和测试等所需的时间，试计算在单处理机上实现上述算法总共需多少时间，并表达成K和N的函数，假定完成乘法与加法需用相同的单位时间。2. 为加速上述计算，可采用SIMD机来发掘计算中的并行性，试求出下列两种不同的情况下的计算时间。i. 用P=N个处理单元PE逐对地计算每对Ri、Ci的IPi。（假设PE间的数据传输不花时间）ii. 将一对向量分配给每个PE，由此PE来计算其内积。在这种情况下P=K【答案】1. 计算一对向量需要做N次乘法，N次加法，共需2N个单位时间，所以计算K对向量的内积需要2KN个单位时间。2. (i)每个IPI经过一个乘法时间算出，经过n次加法求得最后的结果。所以需要K(1n)个单位时间(ii)每个IPI经过N个乘法时间算出，再经过N次加法求得每个IPI，所以共需要2N个单位时间23. 假定有一个处理机台数为p的共享存储器多处理机系统。设m为典型处理机每条执行执行时间对全局存储器进行访问的平均次数。设t为共享存储器的平均存储时间，x为使用本地存储器的单处理机MIPS速率，再假定在多处理机上执行n条指令。请根据以上参数，确定多处理机的有效MIPS速率。【答案】px/(1+mtx)24. 设有一个向量，要计算其累加和。在SISD计算机种可以用FORTRAN语言表示为：S=0.0DO 10 I=0,1510 S=S+A(I)这是一个串行程序。在SISD计算机上，它要用16次加法时间。如果在阵列机上采用的递归相加算法，则只需要次加法时间就够了。首先，原始数据A(I)，存放在16个PEM的a单元中，请写出在阵列处理机上用成对递归相加算法求和的步骤。解：1. 将16个PEM编号，分别为P0, P1, , P15，其a地址中分别存有A0, A1, , A152. 将全部PE的a单元的内容向左传送1个步距3. 令PE0, PE2, PE4, , PE14保持活动，执行加运算，运算结果存于a单元中4. 将全部PE的a单元的内容向左传送2个步距5. 令PE0, PE4, PE8, PE12保持活动，执行加运算，运算结果存于a单元中6. 将全部PE的a单元的内容向左传送4个步距7. 令PE0, PE8保持活动，执行加运算，运算结果存于a单元中8. 将全部PE的a单元的内容向左传送8个步距9. 令PE0保持活动，执行加运算，运算结果存于a单元中则共进行4次加法运算。25. 假设一台4处理机带有共享存储器的计算机来执行一个混和程序。此多处理机有4种运行方式。与1,2,3,4四台处理机处于活动状态相对应。设为i台处理机用于执行上述程序的时间百分数。而且。可以分别用R1,R2,R3,R4表示执行速度使之与分布相对应。试问上述混合程序的调和均值执行时间T为多少。用和Ri推导出多处理机的调和均值执行速率R的表达式，同时用R给出调和均值执行时间T的表达式。另外，假设利用一个智能编译器来提高上述混和程序的并行优化度，混和程序的新的分布为；R1=4MIPS，R2=8MIPS，R311MIPS，R4=15MIPS，求执行同一程序的调和均值的执行时间。【答案】调和均值执行速率R为，利用上述的公式，可以计算出R9.62，调和均值执行时间为T0.10426. 一台向量计算机只能以下述两种方式中的一种运行：向量方式，执行速度是Rv=10MFLOPS；另一种是标量方式，执行速度Rs为1MFLOPS。设a是该计算机的典型程序代码中可向量化的百分比。(1) 推导出该计算机平均执行速度Ra的公式(2) 画出以a为横坐标，Ra为纵坐标的曲线，a的范围为(0,1)(3) 要使Ra达到6MFLOPS，问向量化百分比a应多大(4) 假设Rs2MFLOPS，a=0.7，要使Ra达到9MFLOPS，问Rv应多大？【答案】(1) Ra=Rv*a+Rs*(1-a)(2) 曲线略(3) a=5/9(4) Rv=12MFLOPS27. 试在下述假定条件下，估算总线连接多处理机系统的有效MIPS速率。系统有16台处理机，每台皆有一个板上私用的高速缓存，高速缓存链接到公共总线上。全局共享存储器也链接到总线上，私用高速缓存和共享存储器构成二层的存取层次结构。如果假定高速缓存的命中率是100%，则每台处理机的速率是10MIPS，平均每条指令需要访问存储器0.2次，假设读与写访问的概率相等。作为粗略的近似，忽略所有其他开销，只考虑由共享存储器存取造成的损失。高速缓存把维持0.95的命中率作为目标。高速缓存存取在读命中时用20ns，在采用写回方案的写命中时需要60ns，而采用写直达方案时需要400ns，当高速缓存块被替换时，页面重写概率为0.1，高速缓存与共享存储器之间通过总线的平均块传送时间是400ns。（a）分别求写直达和写回高速缓存的每条指令的有效存储器存取时间（b）计算每台处理的有效MIPS速度。求出16台处理机系统有效MIPS的上限。【答案】（a）写直达 230ns 写回 62ns（b）每台处理机的有效MIPS速度:6.85(写通过时); 8.90(写回时)16台处理机系统有效MIPS的上限:109.6(写通过时);142.3(写回时)28. 下面由六条指令组成的代码段需运行64次才能计算向量算术表达式：D(I) = A(I) + B(I) x C(I)，其中0I63。Load R1,B(I)/R1Memory(+I)/Load R2,C(I)/R2Memory(+I)/Multiply R1,R2/R1(R1) x (R2)/Load R3,A(I)/R3Memory(+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个周期。(1) 计算在一台SISD单处理机计算机上依次重复执行上述代码段64次所需的CPU周期数，忽略所有其它延迟时间。(2) 假设用一台有64个PE的SIMD机，以6条同步向量指令对64组向量数据执行上述向量操作，所用的时钟速率与前面一样。计算SIMD机的总执行时间，忽略指令广播及其它延迟。(3) SIMD计算机与SISD计算机相比，其加速比为多少？【答案】(1) 该程序段中每条指令所需的周期数如下所示：Load R1,B(I)4Load R2,C(I)4Multiply R1,R28Load R3,A(I)4Add R3,R12Store D(I),R34运行一遍这六条指令，共需要（忽略其它延迟时间）44842426个周期。(2) 在一台SISD单处理计算机上依次重复执行上述代码段64遍所需的CPU周期数为2664 = 1664在一台有64个PE的SIMD机，以6条同步向量指令直接对64组向量数据执行上述向量操作，那么只需要执行一遍，所需CPU周期数为26。SIMD计算机和SISD计算机相比，加速比 为1664/26 = 64。29. 假设有一个可扩展的多处理机结构，它有P个处理器节点和共享分布存储器。设R为每个处