搜索
第一章并行计算机系统及其结构模型习题例题：1.查阅资料，找出一个并行计算的典型应用，详细描述该应用在并行化方面成功和失败之处以及遇到的困难：（从下列方面考虑：该应用是针对什么科学或者工程上的具体问题设计的；对于要解决的问题，该应用实际效果怎样，模拟结果和物理结果进行比较的结果如何；该应用的运行在什么并行计算平台上；（比如分布式或共享内存，向量机）这个应用使用那种开发工具开发的；该应用的实际工作性能怎样，和运行平台最佳性能相比较；该应用的可扩展性如何？如果不好，你认为它的扩展性的瓶颈在何处？）2.一个nN2=个节点的洗牌交换网络如图所示。试问：此节点度=？网络直径=？和网络对剖宽度=？45672301N=8的洗牌交换网络3.一个kkN2)1(+=个节点的蝶形网络如图所示。试问：此网节点度=？网络直径=？和网络对剖宽度=？行0行1行2行3k=3的蝶型网络4.参照图，试解释为什么：①当I／O处理器将一个新的数据X’写回主存而绕过采用WT策略的高速缓存时会造成高速缓存和主存间的不一致；②当直接从主存输出数据而绕过高速缓存采用WB策略时也会造成不一致。5.将一种互连网络中的结点映射到另一种网络的过程叫做嵌入（Embedding）。研究嵌入是很重要的，因为设计在某一特定网络连接的并行机上的算法，如果实际运行在另一种与之不同的互连网络的并行机上时，我们要重新分析其通信（即选路）时间。试问：①如何将一个环形网络嵌入到带环绕的二维网孔中去？②被嵌入到带环绕的二维网孔上的原设计的算法其选路时间有何变化？第二章当代并行计算机系统介绍习题例题：1.请尽可能访问以下有关高性能并行计算的网址：IEEE/CSParaScope()，world-wideparallelcomputingsitesHighPerformanceComputingLists()TheLanguageList()enumerateprogramminglanguagesTOP500()World'sTOP500mostpowerfulcomputingsites(atNetlib，UniversityofTennessee)Myrinet()DSMbibliography(~rasit/dsmbiblio.html)BerkeleyActiveMessagepage()TheCrayResearchsystempage()SGI/CrayOrigin2000()CrayT3E()PetaFLOPSwebsite()NASAHPCCProgram()CrayT3E()IBMSP()IntelParagon()KaiLi(~li/)SP2atMHPCC()MPIStandardsite()MITParallelandDistributedOperatingSystemsGroup().NationalCenterforSupercomputerApplicationsatUIUC(NCSA)()CornellTheoryCenter(CTC)()ArgonneNatlLaboratory，Mathematics&ComputerScienceDiv.()ArmyResearchLab()LawrenceLivermoreNationalLaboratory()LosAlamosNatlLaboratory(LANL)AdvancedComputingLaboratory().MauiHighPerformanceComputingCenter(MHPCC)()SanDiegoSupercomputerCenter()SandiaNationalLaboratories()MassivelyParallelComp.Res.Lab.ParallelProcessinginJapan()CrayResearch()IBMHigh-PerformanceComputing()ParaSoftCorporation()2.对于一个100Mb时钟频率的总线连接的SMP系统，假定总线宽度为8个字节，为传输16个字节的数据，那么总线带宽可达多少，3.试解释系统带宽与系统互连对剖宽度之间的关系，并举一例说明之。4.试比较下列5种并行结构的不同点：①PVP；②SMP；③MPP；④COW；⑤DSM5.试举一例说明：如何在SIMD机器上实现MIMD并行应用?如何在SIMD模型上实现MPMD并行应用?第三章并行计算性能评测习题例题：1.使用40MHZ主频的标量处理器执行一个典型测试程序，其所执行的指令数及所需的周期数如表所示。试计算执行该程序的有效CPI、MIPS速率及总的CPU执行时间。指令类型指令数时钟周期数整数算术45,0001数据传送32,0002浮点15,0002控制转移8,00022.根据表所给出的数据：①分别计算BerkeleyNow、IntelParagon和CrayC90的性能/价格比；②你能由此得出什么结论吗？三种机器求解某应用常微分方程时的运行一览表机器系统处理器数计算时间（s）通信时间（s）I/O时间（s）总时间（s）价格（s）CrayC901674162730IntelParagon2561224104610Now+Ethernet256(RS6000)4233404030273404NOW+ATM+PIO+AM256(RS6000)48102153.一个p个处理器上的并行程序的加速比是p-1,根据Amdahl定律，串行分量为多少？4.在Amdahl定律的假设条件下，对于一个固定问题，随着使用的处理器数目p的增加，是否可以达到常数效率？为什么？5.若对于一个固定问题，随着使用的处理器数目p增加，效率为常数，根据Amdahl定律串行分量s（可以表示成p的函数）为多少？6.对于一个具有良好可扩放性的并行算法，任务的规模（或是任务的个数）会不会随着问题的规模的增加而增加？为什么？7.对于一个在给定并行体系结构上解决给定问题的并行算法，若下面的条件变化时，并行效率是增加还是减少？若其他的独立参数是固定的。处理器数目增加问题规模增加通讯带宽增加通讯延迟增加处理器的计算速度增加通讯步之间的计算量增加通讯端口增加，每个处理器可以同时通讯第四章并行算法的设计基础习题例题：1.试证明Brent定理：令W(n)是某并行算法A在运行时间T(n)内所执行的运算数量，则A使用p台处理器可在t(n)＝O(W(n)／p+T(n))时间内执行完毕。2.假定Pi（1≤i≤n）开始时存有数据di1ijjd=∑,所谓累加求和指用来代替Pi中的原始值di输入：P。算法PRAM-EREW上累加求和算法i中保存有di输出：P,l≤i≤niijjld=∑中的内容为beginforj=0tologn–1dofori=2j(i)P+1tonpar-doi=d(ii)di-(2^i)i=di+dendfori-(2^j)endforend(1)试用n=8为例，按照上述算法逐步计算出累加和。(2)分析算法时间复杂度。3.在APRAM模型上设计算法时，应尽量使各处理器内的局部计算时间和读写时间大致与同步时间B相当。当在APRAM上计算M个数的和时，可以借用B叉树求和的办法。假定有j个处理器计算n个数的和，此时每个处理器上分配n/p个数，各处理器先求出自身的局和；然后从共享存储器中读取它的B个孩子的局和，累加后置入指定的共享存储单元SM中；最后根处理器所计算的和即为全和。算法如下：算法APRAM上求和算法输入：n个待求和的数输出：总和在共享存储单元SM中Begin(1)各处理器求n/p个数的局和,并将其写入SM中(2)Barrier(3)fork=[logB3.1forallP(p(B–1)+1)]–2downto0doiifP,0≤i≤p–1,doiP在第k级theniendif计算其B各孩子的局和并与其自身局和相加,然后将结果写入SM中endfor3.2barrierendforEnd(1)试用APRAM模型之参数，写出算法的时间复杂度函数表达式。(2)试解释Barrier语句的作用。4.在给定时间t内，尽可能多的计算输入值的和也是一个求和问题，如果在logP模型上求此问题时，要是tL+2·0，则在一个单处理机上即可最快地完成；要是tL+2·0时，则根处理器应在t-1时间完成局和的接收工作，然后用一个单位的时间完成加运算而得最终的全和。而根的远程子节点应在（t－1）－(L+2·0）时刻开始发送数据，其兄妹子节点应依次在（t－1）－(L+2·0+g)，（t－1）－(L+2·0+2g)，···时刻开始发送数据。图示出了t=28，p=8，L=5，o=2，g=4的logP模型上的通信（即发送/接收）调度树。试分析此通信调度树的工作原理和图中节点中的数值是如何计算的？628101418484P0P1P2P3P4P5P6P7图1.50t=28，p=8，L=5，o=2，g=4的通信调度树5.欲在8个处理器的BSP模型上，计算两个N阶向量内积：①试画出各超级步的计算过程（假定N=8）；②并分析其时间复杂度。第五章并行算法的一般设计策略习题例题：1、令n是待排序的元素数，p＝2d是d维超立方中处理器的数目。假定开始随机选定主元x，并将其播送给所有其他处理器，每个处理器按索接收到的x，对其n/p个元素按照≤x和＞x进行