并行程序设计导论第二章习题

并⾏程序设计导论第⼆章习题2.1当讨论浮点数加法时，我们简单那地假设每个功能单元都花费相同的时间。如果每个取命令与存命令都花费2纳秒，其余的每个操作耗费1纳秒。a在上述假设下，每个浮点数加法要耗费多少时间？b⾮流⽔线1000对浮点数的加法要耗费多少时间？c流⽔线1000对浮点数加法要耗费多少时间？d如果操作数/结果存储在不同级的内存层级上，那么取命令与存命令所要耗费的时间可能会差别⾮常⼤。假设从⼀级缓存上去数据/指令要耗费2纳秒，从⼆级缓存上取数据/指令要耗费5纳秒，从主存取数据/指令要耗费50纳秒。当执⾏某条指令，取其中⼀个操作数时，发⽣了⼀次⼀级缓存失效，那么流⽔线会发⽣什么情况？如果⼜发⽣⼆级缓存失效，⼜会怎样？解答：a对照第17页的图，⾃⾏画⼀下就出来了，9纳秒b因为1000对要串⾏执⾏，所以9*1000=9000纳秒c这个可以画⼀下图，可能更有助与明⽩为什么这么算。1000+(9-1)=1008纳秒(感谢sinat_26845549同学的提醒)这⾥确实是计算错误了。这⾥根据17页的提⽰【引⽤】有些延迟（例如等待操作数）会造成流⽔线的阻塞。这⾥可以画图，得出⼀个函数表达式：f(n)=2n+7。这⾥的n就是浮点数加法对的数量。所以，这⾥的答案应为f(1000)=2007nsd①因为指令会逐层查询，所以在⼀级缓存失效的时候，会去⼆级缓存中找，这样这次指令查找的时间为2+5=7纳秒。②假设这⾥的告诉缓存只有两级，这次指令查找的时间为2+5+50=57ns对于整个流⽔线来说，只要这两次失效不在最后执⾏的⼏个任务上发⽣，那么对于整体的执⾏时间不会有影响。这个可以从第18页图中看出来。2.2请解释在CPU硬件⾥实现的⼀个队列，怎么使⽤可以提⾼直达⾼速缓存(write-throughcache)的性能。解答：因为⾼速缓存的速度要⽐主存块很多，且写直达有⼀个特性就是，当CPU想Cache写数据时，⾼速缓存⾏会⽴即写⼊主存中。2.3回顾之前⼀个从缓存读取⼆维数组的⽰例。请问⼀个更⼤矩阵和⼀个更⼤的缓存是如何影响两队嵌套循环的性能的？如果MAX=8，缓存可以存储4个缓存⾏，情况⼜会是怎样的？在第⼀对嵌套循环中对A的读操作，会导致发⽣多少次失效？第⼆对嵌套循环中的失效次数⼜是多少？解答：①当矩阵增⼤时，第⼀个嵌套循环的缺失次数要增加。当缓存增⼤时，第⼀个嵌套循环的缺失次数会减少。第⼆个嵌套循环在矩阵增⼤的情况下缺失次数会增多，当缓存达到⼀定程度的时候，才会出现缺失次数减少的情况。②这⾥假设每个缓存⾏可以存4个元素。第⼀个循环⼀⾏有两次缺失的发⽣，所以2*8=16次第⼆个循环⼀列有⼋次缺失的发⽣，所以8*8=64次2.4在表2-2中，虚拟地址由12位⾃⼰偏移量和20位的虚拟页号组成。如果⼀个程序运⾏的系统上拥有这样页⼤⼩和虚拟空间，这个程序有多少页？解答：页的数量=2^20=1048576=1024k2.5在冯·诺依曼系统中加⼊缓存的虚拟内存改变了它作为SISD系统的类型吗？如果加⼊流⽔线呢？多发射或硬件多线程呢？解答：①这⾥没有改变SISD的类型，这⾥只是对与数据的存储做了⼀定的处理，⽽没有对指令和数据的数量进⾏变动。②当加⼊流⽔线是属于指令级别的并⾏，所以当加⼊流⽔线时，系统的类型变为MISD。③添加多发射和硬件多线程也是⼀样的，依旧是数据指令级别的并⾏，所以系统还是MISD。2.6假设⼀个向量处理器的内存系统需要⽤10个周期从内存载⼊⼀个64位的字。为了使⼀个载⼊流的平均载⼊时间为⼀个周期载⼊⼀个字，需要多少个内存体(memorybank)?解答：那这⾥就需要10个了。因为这⾥需要在⼀个周期内将64位的字进⾏载⼊，所以使⽤10个刚好能在⼀个周期内完成读取。当字的各个部分分布在不同的内存体中时，那么在装⼊/存储连续数据时能⼏乎⽆延迟的访问，这样就能保证平均载⼊时间为⼀个周期的要求了。2.7请讨论GPU与向量处理器执⾏以下代码时的不同之处：sum=0.0;for(i=0;i<n;i++){y[i]+=a*x[i];sum+=z[i]*z[i];}解答：①因为向量处理器是单指令多数据的处理⽅式，所以对于上⾯的代码其可能会分为两个指令来执⾏。下⾯分解⼀下上⾯的代码，其中每⼀个循环代表着⼀个向量指令。sum=0.0;for(i=0;i<n;i++){//loop1y[i]+=a*x[i];}for(i=0;i<n;i++){//loop2sum+=z[i]*z[i];}通过这两指令来完成。②⽽GPU的处理⽅式就不⼤⼀样了，虽然书中没有提任何有关GPU计算的⽅式。不过就根据本⼈接触到的异构计算，GPU应该会这样做：sum=0.0//hostside//createabufferforsum(hostside)int_sum[n]={0};//the1stGPUprocessor(deviceside){y[0]+=a*x[0];sum[0]+=z[0]*z[0];}//the2edGPUprocessor(deviceside){y[1]+=a*x[1];sum[1]+=z[1]*z[1];}...//thenthGPUprocessor(deviceside){y[n-1]+=a*x[n-1];sum[n-1]+=z[n-1]*z[1];}//hostsum=sum[0]+sum[1]+...+sum[n-1];//(hostside)这样就可以看出两者的差别了吧。GPU是将每个计算分解成⼀个任务，让⼀个GPU处理器来完成，所以这⾥GPU的⽅式类似与SIMD，但也如书中所写，GPU不是纯粹的SIMD系统。2.8如果硬件多线程处理器拥有⼤缓存，并且运⾏多个线程，请解释为何改处理器的性能会下降。解答：这⾥和⼤缓存的关系并不⼤，重要的影响是来⾃于多个线程。因为在硬件多线程处理器中，当前任务需要等待数据从内存中读出，那么它可以通过执⾏其他线程⽽不是继续当前线程来发掘并⾏性。所以就需要⽀持线程间的快速切换，当切换速度过慢且线程的数量过多的情况下，性能⾃然会下降。2.9在关于并⾏硬件的讨论中，⽤Flynn分类发来识别三种并⾏系统：SISD、SIMD和MIMD。我们讨论系统中没有多指令单指令流单数据系统，或称为MISD系统。那么，MISD系统是如何⼯作的呢？请举例说明。解答：从名字上就能看出来，对于单个数据，进⾏不同的指令操作。⽐如，处理器取到了⼀个数据，在同⼀时间对这个数据进⾏乘和减的操作。这样的系统没有存在的意义，其功能完全可以由SIMD或MIMD进⾏替换。2.10假设⼀个程序需要运⾏10^12条指令来解决⼀个特定的问题，⼀个单处理器系统可以在10^6秒(⼤约11.6天)内完成。所以，⼀个单处理器系统平均每秒运⾏10^6条指令。现在假设程序已经实现并⾏化，可以在分布式内存系统上运⾏。该并⾏程序使⽤p个处理器，每个处理器执⾏(10^12)/p条指令并必须发送10^9(p-1)条消息。执⾏该程序时，不会有额外的开销，即每个处理器执⾏完所有的指令并发送完所有的消息之后，程序就完成了，⽽不会有由诸如等待消息等事件所产⽣的延迟。那么：a假设发送⼀条消息需要耗费10^-9秒。如果使⽤1000个处理器，每个处理器的速度和单个处理器运⾏串⾏程序的速度⼀样，那么该程序的运⾏需要多少时间？b假设发送⼀条消息耗费10^-3秒。如果使⽤1000个处理器，那么改程序的运⾏需要多少时间？解答：这⾥每个核上的总⼯作时间为：指令+发送消息=(10^12)/p/T指令+10^9(p-1)/T消息①根据上⾯⽅程可得，(10^12)/1000/(10^6)+10^9(1000-1)/10^9=1999s。②(10^12)/1000/(10^6)+10^9(1000-1)/10^3=999001000s=1.0547年2.11请写出不同的分布式内存互连形式的总连路数的表达式。解答：分布式内存互连⽹络通常分成两种：直接链接与间接互连。因为间接链接没有固定的表达式，所以这⾥只罗列出直接连接的表达式：环状直连（2p），环⾯⽹格（3p），等分宽度（2p^(1/2)），全相连⽹络（(p^2)/2+p/2）,超⽴⽅体（4*log(p)）【以2为底的log】。2.12a除了没有循环链接(“wraparound”link)，平⾯⽹格（planarmesh）和⼆维环⾯⽹格(toroidalmesh)是相似的。请问⼀个平⾯⽹格的等分宽度是多少？b三维⽹格与平⾯⽹格是相似的，除了三维⽹格拥有深度这个特性外。请问⼀个三维⽹格的等分宽度是多少？解答：这个等分宽度的确是没有怎么看懂。只能根据推断来做了。a这个不太清楚怎么去求，因为当平⾯内有奇数个核就不太清楚应该怎么去求了。b感觉应该是（1+log(p)）【以2为底的log】2.13a.请画出⼀个思维超⽴⽅体结构b.请⽤超⽴⽅体的归纳定义来解释为何超⽴⽅体的等分宽度为p/2解答：a.这个可以在⽹上找⼀下图，百度⼀下挺多的。这⾥我上传两幅图。b.这个就省略了吧，真的不知为何2.14为了定义间接⽹络的等分宽度，我们将处理器分为两组，每组拥有⼀半数量的处理器。然后，在⽹络的任意处移除链接，使两组之间不再链接。移除的最⼩连路数就是该⽹络的等分宽度。当我们对链路计数时，如果图中⽤的是单向链接，则两条单向链接算作⼀条链路。请说明⼀个8x8的交叉开关的等分宽度⼩于等于8，并说明⼀个拥有8个处理器的omega⽹络的等分宽度⼩于或等于4。解答：这是⼀道证明题，⾃⼰对这块的理解还差很多，这⾥也就先略过吧。2.15a.假定⼀个共享内存系统使⽤监听⼀致性协议和写回缓存。并假设0号核的缓存⾥有变量x，并执⾏赋值命令x=5。1号核的缓存⾥没有变量x。当0号核更新x后，1号核开始尝试执⾏y=x。y被赋值是多少？为什么？b.假设上⾯的共享内存系统使⽤的基于⽬录的协议，则y的值将是多少？为什么？c.你能否为前两部分中所发现的问题提出解决⽅案？解答：a.因为x在更新前，1号核并没有x这个变量。所以，在1号核的cache中，x变量的副本是已经被⼴播更新了的。这⾥y的值是5。b.与监听⼀致性协议不同的是，基于⽬录的Cache⼀致性协议是可以直接访问另⼀核的内存的。所以，在1号核要对y赋值时，会去0号核的内存中获取x变量的值。这⾥y依旧是5。c.以上两种⼀致性解决办法都有其⾃⾝的缺点，这些缺点在书中第29页中也提到了。所以，有了两者结合的解决⽅案——“基于⽬录的Cache⼀致性协议”。2.16a.假定⼀个串⾏程序的运⾏时间为T(串⾏)=n^2，运⾏时间单位为毫秒。并⾏程序的运⾏时间为T(并⾏)=(n^2)/p+log(p)【以2为底】。对于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(串⾏)增长的快，随着问题规模的增加，并⾏效率将降低。解答：a.这⾥n是问题规模，⽽p则是加速⽐。当p选定时，问题规模越⼤，实际加速⽐越靠近p；效率也会有所上升，并趋近于1。b.这⾥使⽤公式来证明的⽐较好。我们知道效率的公式是E=T(串⾏)/(pxT(并⾏))。带⼊题⽬中的并⾏表达式，得E=T(串⾏)/(pxT(串⾏)/p+T(开销))，这个⽅程看着还是不直观，对等号两边求倒得1/E=1+pxT(开销)/T(串⾏)，在这个等式中，当p固定，开销时间与效率成反⽐，串⾏时间与效率成正⽐。这就解释了上⾯两个情况。2.17如果⼀个并⾏程序所获得的加速⽐可以超过p(进程或线程的个数)，则我们有时称该并⾏程序拥有超线性加速⽐(superlinearspeedup)。然⽽，许多作者并不能够克服“资源限制”的程序职位是拥有超线性加速⽐。例如，当⼀个程序运⾏在⼀个单处理器系统上时，它必须使⽤⼆级存储，当它运⾏在⼀个⼤的分布式内存系统上时，它可以讲所有数据都放置到主存上。请给出另外⼀个例⼦，说明程序是如何克服资源限制，并获得⼤于p的加速⽐的。解答：⾃⼰的理解就是在缓存上不存在“未命中”的情况，加速了数据的载⼊速度，从⽽超除了应有的加速⽐。这⾥引⽤和的解释。摘取关键部分，对其他内容有兴趣的可以直接去百科上查看。超线性加速⽐有⼏种可能的成因，如现代计算机的存储层次不同所带来的“⾼速缓存效应”；具体来说，较之顺序计算，在并⾏计算中，不仅参与计算的处理器数量更多，不同处理器的⾼速缓存也集合使⽤。⽽有鉴于此，集合的缓存便⾜以提供计算所需的存储量，算法执⾏时便不必使⽤速度较慢的内存，因⽽存储器读些时间便能⼤幅降低，这便对实际计算产⽣了额外的加速效果。2.19假定T(串⾏)=n,T(并⾏)=n/p+log(p)【以2为底】，时间单位为毫秒。如果以倍率k增加p，那么为了保持效率值恒定，需要如何增加n？请给出公式。如果我们将进程数从8加倍到16，则n的增加⼜是多少？该并⾏程序是可扩展的吗？解答：以下log都是以2为底的。1）这⾥需要效率相等，所以我们可以将加倍和没加倍之前的效率放在等号两边。就有n/[p(n/p+log(p))]=n’/[kp(n’/kp+log(kp))],计算可得n’/n=klog(kp)/log(p)=klog(k)/log(p)+k2）可以通过与上⼀⼩题相同的⽅式来计算。我算得结果是n’/n=8/33）这⾥需要重温⼀下“可扩展”的定义了。【引⽤】“⼀个并⾏程序，如果问题的规模与进程/线程数都以⼀定的倍率增加，⽽效率保持⼀个常数值，那么该并⾏程序就是可扩展的。”所以本题的程序是可扩展的。2.20⼀个可以获得线性加速⽐的程序是强可扩展吗？请解释解答：是的。根据加速⽐的计算公式S=T(串⾏)/(T(串⾏)/p+log(p))，当获得线性加速⽐时，S=p，则这⾥分母部分中对数的那部分就完全多余了；可以写成，S=T(串⾏)/(T(串⾏)/p)，这样的话加速⽐与问题规模就没有关系了，所以这⾥问题规模就可以认为是⼀个常数，且这个常数不随着p的变化⽽变化，所以这样的程序是强可扩展的程序。2.21Bob有个程序，相对两组数据进⾏计时，input_data1和input_data2。为了在程序中加⼊计时函数前得到⼀些想法，他⽤两组数据和UNIX的shell命令time，运⾏了程序：$time./bobs_prog<input_data1real0m0.001suser0m0.001ssys0m0.000s$time./bobs_prog<input_data2real1m1.234suser1m0.001ssys0m0.111sBob⽤的时间函数的精度为毫秒。Bob应该使⽤第⼀组数据和时间函数对他的程序计时吗?如果使⽤第⼆组数据呢？请分别解释使⽤和不使⽤的原因。解答：不建议使⽤第⼀组数据⽤来计时。根据题⽬可以看出来data1明显要⽐data2的数据规模⼩很多，这样的话，毫秒级的计时对于data1来说就不够⽤了，⽽使⽤data2来计时就很容易看出程序在运⾏时所消耗的时间，以及系统中是否有其他任务在CPU上运⾏。有关于time命令的解析，⼤家可以使⽤mantime或中查看。2.22正如我们在习题2.21中所看到的，UNIX的shell命令time报告⽤户时间、系统时间，以及“实际”时间或全部耗费的时间。假设Bob定义了⼀下这些可被C程序调⽤的函数：doubleutime(void)doublestime(void)doublertime(void)第⼀个函数返回的是从程序开始执⾏⽤户时间所消耗的秒数。第⼆个返回的是系统时间秒数，第三个是总时间秒数。⼤致上，⽤户时间主要消耗在不需要操作系统执⾏的⽤户代码和数据库函数上，如sin和cos函数。系统时间耗费在那些需要操作系统执⾏的函数上，如printf和scanf函数。a.这三个函数值的数学关系是怎么样的？假定程序包含如下代码：u=doubleutime(void)s=doublestime(void)r=doublertime(void)请写出u、s和r之间关系的表达式(可以假定忽略函数调⽤的时间花费)b.在Bob的系统上，任何使⽤，如果⼀个MPI进程在等待消息，则它花费的时间不计⼊utime和stime，⽽计⼊rtime。请解释Bob是如何根据这些条件来