并行计算_陈国良_测验习题1

1并行分布式试卷1姓名____________________学号____________________分数_____________一．填空（每空1分，共30分）1．在并行机系统中，常用的静态互联网络有_____________，_______________，______________________，______________________，___________________等。2．在并行机系统中，常用的动态互联网络有___________________________________，_____________________________________和______________________________。3．近代并行计算机体系结构模型包括________________，___________________，_______________________，__________________，_____________________等。4．常用的并行存储访问模型（又叫并行存储结构）包括_______________________，________________________________，_____________________________等。5．常用的并行程序设计模型有___________________，__________________，____________________________等。6．大型稀疏线性方程常用迭代解法有____________________，__________________，_________________________，__________________________等。7．常用的并行计算（或算法）模型有___________________，____________________，________________________，______________________等。8．我国自行研制的并行计算机三大系列是___________________________，_____________________________，_____________________________。二．简要回答（每题5分，共20分）1．试述并行算法基本的设计技术。2．何谓X-Y选路算法何E-cube选路算法（可以例明之）?3．何谓Amdahle和Gustfson加速定律及其推导过程？4．何谓等效率、等速度和平均延迟可扩放性度量标准？并推导他们之间的等效性。2三．综合题（每题10分，共50分）1．假定44A和44B都已加载到44处理器阵列上，试图示Cannon矩阵乘法的具体过程。2．已知4331A，8765B，试用DNS方法，逐步求出矩阵乘积?22211211ccccC。3．欲求解Ax=b，则构造二次函数bxAxxxqTT21)(，试证明0)(xxq是Ax=b的解。4．假定10nkkjkjawb，10nj，以n=8为例，推导FFT递归计算公式。5．参照下图，对于一个8点的蝶式网络，假定：①相应的处理器p(r,i)中已保存了倍数矩阵元素),exp(irw，70i，31r。②输入序列)0,0,,1,0,1,,2(iiiA。试按下述SIMD-BF模型上算法，计算出ird,和jrd,之值。SIMD-BF模型上的FFT算法输入：),...,(10naaA输出：ird,和jrd,Begin(1)fori=0ton-1par-doω0ω0ω0ω0ω4ω4ω4ω4ω0ω0ω4ω4ω2ω2ω6ω6ω0ω4ω2ω6ω1ω5ω3ω7a0a1a2a3a4a5a6a7d30d31d32d33d34d35d36d37r0r1r2r33iiad,0endfor(2)forr=1tonlogdofor所有仅第r位不同且i在第r位为零的每对(i,j)par-do(2.1)jriririrddd,1),exp(,1,(2.2)jrjrirjrddd,1),exp(,1,endforendforEnd4并行分布式试卷2姓名____________________学号____________________分数_____________一、填空选择题(20分)1.对于高性能计算的需要是广泛的，比如在_____________，_______________，______________________，______________________等领域中应用广泛。2.在并行系统中，系统互联网络有___________________________________，_______________________________和______________________________三类。3.近代常见的五种并行计算机体系结构模型包括________________，___________________，_______________________，__________________，_____________________。4.常用的并行计算模型有___________________，__________________，____________________________，_________________等。5．中国工程院院士金怡濂研究员被授予2002年度国家最高科学技术奖。由他担任总设计师主持研制的并行计算机系统为_________系列。A.曙光B神威C.银河D以上都不对6．关于加速比，下面的论述不对的是_________A.严格的线性加速比是难以达到的；B.在某些算法或程序中，可能出现超线性加速现象；C.通信密集类的应用问题，加速比往往不是很高D.加速比仅由算法决定，与应用问题的规模无关二、简答题（20分）1．何谓SMP结构？简述该结构的特性。2．试推导Gustafson定律。3．何谓并行计算的可扩放性？有哪三种典型的扩放性度量方法？4．何谓PRAM模型？简述该模型的优缺点。5．请举例说明并行算法的三种一般设计方法（策略）。5三、综合题（60分）1.试画出基于Batcher比较器的双调序列(8，6，4，2，0，1，3，5)的双调归并排序网络，并在标出每个Batcher比较器的输入和输出数据。2.使用指针跳跃技术求出下面森林的根，给出求解过程。3.给出环上一到多(one-to-all)的CT选路算法描述，并在下图中画出选路步骤。根据单一信包的通讯时间hwsonetooneltmttCTt)(，试推导环上的通讯时间)(CTtalltoone。4.先写出矩阵乘法nnnnBA的Fox算法形式描述，然后分析Fox算法在p个处理器组成的超立方上、使用CT选路的运行时间(注：p-超立方上的pmttCTtwsalltoonelog)()()。5.离散富里叶变换10nkkjkjab，10nj。对于n=8，试完成下面的蝶式计算图中的列1到列3的相应标记，并求出b3和b6。7654012312635478101112139a0a1a2a3a4a5a6a7列2列3列1列0