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