并行计算导论第二章习题

《并行计算导论第二章习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2.1当讨论浮点数加法时，我们简单地假设每个功能单元都花费相同的时间。如果每个取命令与存命令都耗费2纳秒，其余的每个操作耗费1纳秒。a.在上述假设下，每个浮点数加法要耗费多少时间？b.非流水线1000对浮点数的加法要耗费多少时间？c.流水线1000对浮点数加法要耗费多少时间？d.如果操作数/结果存储在不同级的内存层级上，那么取命令与存命令所要耗费的时间可能会差别非常大。假设从一级缓存上取数据/指令要耗费2纳秒，从二级缓存上取数据/指令要耗费5纳秒，从主存取数据/指令要耗费50纳秒。当执行某条指令，取其中一个操作数时，发生了一次一级缓存失效，那么流水

2、线会发生什么情况？如果又发生二级缓存失效，又会怎样？2.2请解释在CPU硬件里实现的一个队列，怎么使用可以提高写直达高速缓存（write-throughcache）的性能。2.3回顾之前一个从缓存读取二维数组的示例。请问一个更大矩阵和一个更大的缓存是如何影响两对嵌套循环的性能的？如果MAX=8，缓存可以存储4个缓存行，情况又会是怎样的？在第一对嵌套循环中对A的读操作，会导致发生多少次失效？第二对嵌套循环中的失效次数又是多少？2.4在表22中，虚拟地址由12位字节偏移量和20位的虚拟页号组成。如果一个程序运行的系统上拥有这样的页大小和虚拟地址空间，

3、这个程序有多少页？2.5在冯·诺依曼系统中加入缓存和虚拟内存改变了它作为SISD系统的类型吗？如果加入流水线呢？多发射或硬件多线程呢？2.6假设一个向量处理器的内存系统需要用10个周期从内存载入一个64位的字。为了使一个载入流的平均载入时间为一个周期载入一个字，需要多少个内存体（memorybank）？2.7请讨论GPU与向量处理器执行以下代码时的不同之处： 2.8如果硬件多线程处理器拥有大缓存，并且运行多个线程，请解释为何该处理器的性能会下降。2.9在关于并行硬件的讨论中，用Flynn分类法来识别三种并行系统：SISD、SIMD和MIMD。我们讨

4、论的系统中没有多指令流单数据流系统，或者称为MISD系统。那么，MISD系统是如何工作的呢？请举例说明。2.10假设一个程序需要运行1012条指令来解决一个特定问题，一个单处理器系统可以在106秒（大约11.6天）内完成。所以，一个单处理器系统平均每秒运行106条指令。现在假设程序已经实现并行化，可以在分布式内存系统上运行。该并行程序使用p个处理器，每个处理器执行1012/p条指令并必须发送109(p-1)条消息。执行该程序时，不会有额外的开销，即每个处理器执行完所有的指令并发送完所有的消息之后，程序就完成了，而不会有由诸如等待消息等事件所产生的延

5、迟。那么，a.假设发送一条消息需要耗费10-9秒。如果程序使用1000个处理器，每个处理器的速度和单个处理器运行串行程序的速度一样，那么该程序的运行需要多少时间？b.假设发送一条消息需要耗费10-3秒。如果程序使用1000个处理器，那么该程序的运行需要多少时间？2.11请写出不同的分布式内存互连形式的总链路数的表达式。2.12a.除了没有循环链接（“wraparound”link），平面网格（planarmesh）和二维环面网格(toroidalmesh)是相似的。请问一个平面网格的等分宽度是多少？b.三维网格与平面网格是相似的，除了三维网格拥有深

6、度这个特性外。请问一个三维网格的等分宽度是多少？2.13a.请画出一个四维超立方体结构。b.请用超立方体的归纳定义来解释为何超立方体的等分宽度为p/2。2.14为了定义间接网络的等分宽度，我们将处理器分为两组，每组拥有一半数量的处理器。然后，在网络的任意处移除链接，使两组之间不再连接。移除的最小链路数就是该网络的等分宽度。当我们对链路计数时，如果图中用的是单向链接，则两条单向链接算作一条链路。请说明一个8×8的交叉开关矩阵的等分宽度小于或等于8，并说明一个拥有8个处理器的omega网络的等分宽度小于或等于4。2.15a.假定一个共享内存系统使用监听

7、缓存一致性协议和写回缓存。并且假设0号核的缓存里有变量x，并执行赋值命令x=5。1号核的缓存里没有变量x。当0号核更新了x后，1号核开始尝试执行y=x。y被赋的值是多少？为什么？b.假定上面的共享内存系统使用的是基于目录的协议，则y的值将是多少？为什么？c.你能否为前两部分中所发现的问题提出解决方案？2.16a.假定一个串行程序的运行时间为T串行＝n2，运行时间的单位为毫秒。并行程序的运行时间为T并行=n2/p+log2(p)。对于n和p的不同值，请写一个程序并找出这个程序的加速比和效率。在n=10、20、40、…、320和p=1、2、4、…、12

8、8等不同情况下运行该程序。当p增加、n保持恒定时，加速比和效率的情况分别如何？当p保持恒定而n增加呢？b.假设T并行＝T串