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