并行计算导论第二章习题

2.1当讨论浮点数加法时，我们简单地假设每个功能单元都花费相同的时间。如果每个取命令与存命令都耗费2纳秒，其余的每个操作耗费1纳秒。a.在上述假设下，每个浮点数加法要耗费多少时间？b.非流水线1000对浮点数的加法要耗费多少时间？c.流水线1000对浮点数加法要耗费多少时间？d.如果操作数/结果存储在不同级的内存层级上，那么取命令与存命令所要耗费的时间可能会差别非常大。假设从一级缓存上取数据/指令要耗费2纳秒，从二级缓存上取数据/指令要耗费5纳秒，从主存取数据/指令要耗费50纳秒。当执行某条指令，取其中一个操作数时，发生了一次一级缓存失效，那么流水线会发生什么情况？如果又发生二级缓存失效，又会怎样？2.2请解释在CPU硬件里实现的一个队列，怎么使用可以提高写直达高速缓存（write-throughcache）的性能。2.3回顾之前一个从缓存读取二维数组的示例。请问一个更大矩阵和一个更大的缓存是如何影响两对嵌套循环的性能的？如果MAX=8，缓存可以存储4个缓存行，情况又会是怎样的？在第一对嵌套循环中对A的读操作，会导致发生多少次失效？第二对嵌套循环中的失效次数又是多少？2.4在表22中，虚拟地址由12位字节偏移量和20位的虚拟页号组成。如果一个程序运行的系统上拥有这样的页大小和虚拟地址空间，这个程序有多少页？2.5在冯·诺依曼系统中加入缓存和虚拟内存改变了它作为SISD系统的类型吗？如果加入流水线呢？多发射或硬件多线程呢？2.6假设一个向量处理器的内存系统需要用10个周期从内存载入一个64位的字。为了使一个载入流的平均载入时间为一个周期载入一个字，需要多少个内存体（memorybank）？2.7请讨论GPU与向量处理器执行以下代码时的不同之处：2.8如果硬件多线程处理器拥有大缓存，并且运行多个线程，请解释为何该处理器的性能会下降。2.9在关于并行硬件的讨论中，用Flynn分类法来识别三种并行系统：SISD、SIMD和MIMD。我们讨论的系统中没有多指令流单数据流系统，或者称为MISD系统。那么，MISD系统是如何工作的呢？请举例说明。2.10假设一个程序需要运行1012条指令来解决一个特定问题，一个单处理器系统可以在106秒（大约11.6天）内完成。所以，一个单处理器系统平均每秒运行106条指令。现在假设程序已经实现并行化，可以在分布式内存系统上运行。该并行程序使用p个处理器，每个处理器执行1012/p条指令并必须发送109(p-1)条消息。执行该程序时，不会有额外的开销，即每个处理器执行完所有的指令并发送完所有的消息之后，程序就完成了，而不会有由诸如等待消息等事件所产生的延迟。那么，a.假设发送一条消息需要耗费10-9秒。如果程序使用1000个处理器，每个处理器的速度和单个处理器运行串行程序的速度一样，那么该程序的运行需要多少时间？b.假设发送一条消息需要耗费10-3秒。如果程序使用1000个处理器，那么该程序的运行需要多少时间？2.11请写出不同的分布式内存互连形式的总链路数的表达式。2.12a.除了没有循环链接（“wraparound”link），平面网格（planarmesh）和二维环面网格(toroidalmesh)是相似的。请问一个平面网格的等分宽度是多少？b.三维网格与平面网格是相似的，除了三维网格拥有深度这个特性外。请问一个三维网格的等分宽度是多少？2.13a.请画出一个四维超立方体结构。b.请用超立方体的归纳定义来解释为何超立方体的等分宽度为p/2。2.14为了定义间接网络的等分宽度，我们将处理器分为两组，每组拥有一半数量的处理器。然后，在网络的任意处移除链接，使两组之间不再连接。移除的最小链路数就是该网络的等分宽度。当我们对链路计数时，如果图中用的是单向链接，则两条单向链接算作一条链路。请说明一个8×8的交叉开关矩阵的等分宽度小于或等于8，并说明一个拥有8个处理器的omega网络的等分宽度小于或等于4。2.15a.假定一个共享内存系统使用监听缓存一致性协议和写回缓存。并且假设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、…、128等不同情况下运行该程序。当p增加、n保持恒定时，加速比和效率的情况分别如何？当p保持恒定而n增加呢？b.假设T并行＝T串行/p+T开销，我们固定p的大小，并增加问题的规模。请解释如果T开销比T串行增长得慢，随着问题规模的增加，并行效率也将增加。请解释如果T开销比T串行增长得快，随着问题规模的增加，并行效率将降低。2.17如果一个并行程序所获得的加速比可以超过p（进程或线程的个数），则我们有时称该并行程序拥有超线性加速比（superlinearspeedup）。然而，许多作者并不将能够克服“资源限制”的程序视为是拥有超线性加速比。例如，当一个程序运行在一个单处理器系统上时，它必须使用二级存储，当它运行在一个大的分布式内存系统上时，它可以将所有数据都放置到主存上。请给出另外一个例子，说明程序是如何克服资源限制，并获得大于p的加速比的。2.18请观察你在计算机科学导论课上编写的三个程序。这些程序中有哪些部分本来就是串行的？当问题规模增加时，串行部分工作所占的比例会减少吗？或者保持大致相同？2.19假定T串行＝n，T串行=n/p+log2(p)，时间单位为毫秒。如果以倍率k增加p，那么为了保持效率值的恒定，需要如何增加n？请给出公式。如果我们将进程数从8加倍到16，则n的增加又是多少？该并行程序是可扩展的吗？2.20一个可以获得线性加速比的程序是强可扩展的吗？请解释。2.21Bob有个程序，想对两组数据进行计时，input_data1和input_data2。为了在程序中加入计时函数前得到一些想法，他用两组数据和UNIX的shell命令time，运行了程序：Bob用的时间函数的精度为毫秒。Bob应该使用第一组数据和时间函数对他的程序进行计时吗？如果使用第二组数据呢？请分别解释使用和不使用的原因。2.22正如我们在习题2.21中所看到的，UNIX的shell命令time报告用户时间、系统时间，以及“实际”时间或全部耗费的时间。假设Bob定义了以下这些可以被C程序调用的函数：第一个函数返回的是从程序开始执行用户时间所耗费的秒数。第二个返回的是系统时间秒数，第三个是总时间秒数。大致上，用户时间主要耗费在不需要操作系统执行的用户代码和库函数上，如sin和cos函数。系统时间耗费在那些需要操作系统执行的函数上，如printf和scanf函数。a.这三个时间函数值的数学关系是什么样的？假定程序包含如下代码：请写出u、s和r之间关系的表达式（可以假定忽略函数调用的时间花费）。b.在Bob的系统上，任何时候，如果一个MPI进程在等待消息，则它花费的时间不计入utime和stime，而计入rtime。请解释Bob是如何根据这些条件来确定一个MPI进程是否在等待消息上耗费了过多时间。c.Bob提供给了Sally他的计时函数。然而，Sally发现在她的系统上，一个MPI进程在等待消息上的时间耗费是计入用户时间的。那么，Sally可以用Bob的函数去判断一个MPI进程是否在等待消息上耗费了过多时间吗？请解释。2.23在我们应用Foster方法来构建直方图的过程中，我们实质上是用data数组的元素来识别聚合任务的。一个很明显的替代方法是，使用bin_counts数组的元素来识别聚合任务，所以一个聚合任务会由bin_counts[b]的增加，和返回b的Find_bin函数的调用所组成。请解释为何这样的聚合可能存在问题。2.24如果你在第1章还没有完成，那么请试着编写树形结构的全局求和的伪代码，其作用是对loc_bin_cts数组的元素进行求和。请先考虑在共享内存的情况下该如何实现。接着考虑分布式内存的情况。在共享内存的情况下，哪些变量是共享的，哪些是私有的？