并行分布式试卷

1、姓名 学号 分数填空（每空1分，共30分）1.在并行机系统中，常用的静态互联网络有等。2.在并行机系统中，常用的动态互联网络有3.近代并行计算机体系结构模型包括等。4.常用的并行存储访问模型（又叫并行存储结构）包括等。5.常用的并行程序设计模型有等。6.大型稀疏线性方程常用迭代解法有等。7.常用的并行计算（或算法）模型有.等。8.我国自行研制的并行计算机三大系列是简要回答（每题5分，共20分）试述并行算法基本的设计技术。何谓X-Y选路算法何E-cube选路算法（可以例明之）？何谓Amdahle和Gustfson加速定律及其推导过程？何谓等效率、等速度和平均延迟可扩放性度量标准？并推导他们之间的

2、等效性。综合题(每题10分，共50分)1.2.3.假定A*和B*都已加载到4 x 4处理器阵列上，试图示Cannon矩阵乘法的具体过 程。r 1 3 5 - 6已知A = 3 4，B =78，试用DNS方法，逐步求出矩阵乘积 TOC o 1-5 h z cc HYPERLINK l bookmark20 o Current Document C = c 11c12=L 2122欲求解Ax=b，则构造二次函数q(x) = i xtAx- xTb，试证明磬打=0是Ax=b2OX的解。假定b =t1心七，0 j n 1，以n=8为例，推导FFT递归计算公式。k=0参照下图，对于一个8点的蝶式网络，假

3、定：相应的处理器p(r, i)中已保存了倍r3W 4W 6W 0气r2r0r1W 3W 6W 4W 5W 2试按下述SIMD-BF模型上算法,计算出吃和d之值。d30d31d32d33d34d35d36W 7d37数矩阵元素 wexp(5，0 i 7，1 r 3。输入序列 A = (2, i,1 i,0,1, i,0,0)。SIMD-BF模型上的FFT算法输入：A = (%,.,a J输出：d和d ,Begin(1) for i=0 to n-1 par-dod = aendfor(2) for r=1 to log n dofor所有仅第r位不同且i在第r位为零的每对(i,j) par-do

4、d = d. +3 exp(r,i)dd= d +3 exp(r,j)dr, jr-1,ir-1, jendforendforEnd姓名 学号 分数一、填空选择题（20分）对于高性能计算的需要是广泛的，比如在, _，等领域中应用广泛。在并行系统中，系统互联网络有，和 三类。近代常见的五种并行计算机体系结构模型包括， ， ，常用的并行计算模型有 ， ，中国工程院院士金怡濂研究员被授予2002年度国家最高科学技术奖。由他担任总设计师主持研制的并行计算机系统为 系列。曙光B神威C.银河D以上都不对关于加速比，下面的论述不对的是严格的线性加速比是难以达到的；在某些算法或程序中，可能出现超线性加速现象；

5、通信密集类的应用问题，加速比往往不是很高加速比仅由算法决定，与应用问题的规模无关二、简答题（20分）何谓SMP结构？简述该结构的特性。试推导Gustafson定律。何谓并行计算的可扩放性？有哪三种典型的扩放性度量方法？何谓PRAM模型？简述该模型的优缺点。请举例说明并行算法的三种一般设计方法（策略）。三、综合题(60分)试画出基于Batcher比较器的双调序列(8, 6, 4, 2, 0, 1, 3, 5)的双调归并 排序网络，并在标出每个Batcher比较器的输入和输出数据。使用指针跳跃技术求出下面森林的根，给出求解过程。给出环上一到多(one-to-all)的CT选路算法描述，并在下图中画出选路步骤。根据单一信包的通讯时间t(CT) = t + mt + lt，试推导环上的通讯时one -to-onesw h TOC o 1-5 h z 间 t(CT)。one-to-all(1)先写出矩阵乘法七 x B的Fox算法形式描述，然后分析Fox算法在p个处理器组成的超立方上、使用CT选路的运行时间(注：p-超立方上的tii (CT) = (t