《并行分布式试卷1》由会员分享，可在线阅读，更多相关《并行分布式试卷1（6页珍藏版）》请在金锄头文库上搜索。
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.假定A 和B 都已加载到4x 4处理器阵列上，试图示Cannon矩阵乘法的具体过 4x44x4程。2.已知A二-6， 试用 DNS 方法， 逐步求出矩阵乘积c cC =1112= ?oc c21 22Qq( x)3.欲求解Ax=b，则构造二次函数q(x)二1 xt Ax - xTb，试证明=0是Ax=b2dx的解。4. 假定bwika , 0 j n -1，以n=8为例，推导FFT递归计算公式。jkk = 05. 参照下图，对于一个8点的蝶式网络，假定：相应的处理器p(r, i)中已保存了倍数矩阵元素 Wexp(r,i
3、)，0 i 7，1 r 3。输入序列 A = (2, i,1 - i,0,1, i,0,0)。r3d30W 4W 6W 0a7r2r0r1W 3W 4W 6W 5W 2试按下述SIMD-BF模型上算法，计算出d和d 之值。 r,id31d32d33d34d35d36W 7d37SIMD-BF模型上的FFT算法 输入：A = (aa )0n -1输出： d 和 dr,ir, jBegin(1) for i=0 to n-1 par-dod = a0,iiendfor(2) for r=1 to log n dofor所有仅第r位不同且i在第r位为零的每对(i,j) par-do(2.1) d=
4、d+ W exp(r,i)dr ,ir-1,ir-1,j(2.2) d= d+ W exp(r,j)dr, jr-1,ir-1,jendforendforEnd并行分布式试卷 2姓名 学号 分数一、 填空选择题（20 分）1. 对于高性能计算的需要是广泛的，比如在, _,等领 域中应用广泛。2. 在并行系统中，系统互联网络有，和三 类。3. 近代常见的五种并行计算机体系结构模型包括,， ， ，4. 常用的并行计算模型有 _5中国工程院院士金怡濂研究员被授予 2002 年度国家最高科学技术奖。由 他担任总设计师主持研制的并行计算机系统为 系列。A. 曙光 B 神威 C. 银河 D 以上都不 对6
5、关于加速比，下面的论述不对的是A. 严格的线性加速比是难以达到的；B. 在某些算法或程序中，可能出现超线性加速现象；C. 通信密集类的应用问题，加速比往往不是很高D. 加速比仅由算法决定，与应用问题的规模无关二、 简答题（20 分）1何谓 SMP 结构？简述该结构的特性。2试推导 Gustafson 定律。 3何谓并行计算的可扩放性？有哪三种典型的扩放性度量方法？4.何谓PRAM模型？简述该模型的优缺点。5请举例说明并行算法的三种一般设计方法（策略）。三、 综合题(60 分)1. 试画出基于 Batcher 比较器的双调序列(8，6，4，2，0，1，3，5)的双调归并 排序网络，并在标出每个
6、Batcher 比较器的输入和输出数据。2. 使用指针跳跃技术求出下面森林的根，给出求解过程。83.给出环上一到多(one-to-all)的CT选路算法描述，并在下图中画出选路步骤。根据单一信包的通讯时间t(CT)二t + mt + lt ,试推导环上的通讯时one -to-oneswh间 t (CT)。one-to-allCi)4.先写出矩阵乘法A x B 的Fox算法形式描述，然后分析Fox算法在p个nxnnxn处理器组成的超立方上、使用CT选路的运行时间(注：p-超立方上的t(CT) = (t + mt )log p )。one-to-allsw5.离散富里叶变换b二* a o kj，0 j n -1。对于n=8，试完成下面的蝶式jkk =0计算图中的列1到列3的相应标记，并求出b3和b6。0126.
