并行分布式试卷1 姓名 分数 填空(每空1分,共30分) 1.在并行机系统中,常用的静态互联网络有 2.在并行机系统中,常用的动态互联网络有 和 3.近代并行计算机体系结构模型包括 等 4.常用的并行存储访问模型(又叫并行存储结构)包括 5.常用的并行程序设计模型有 6.大型稀疏线性方程常用迭代解法有 7.常用的并行计算(或算法)模型有 等 8.我国自行研制的并行计算机三大系列是 二.简要回答(每题5分,共20分) 1.试述并行算法基本的设计技术 2.何谓XY选路算法何E-cube选路算法(可以例明之)? 3.何谓 Amdahl和 Gustfson加速定律及其推导过程? 4.何谓等效率、等速度和平均延迟可扩放性度量标准?并推导他们之间的等效性
1 并行分布式试卷 1 姓名____________________ 学号____________________ 分数_____________ 一. 填空(每空 1 分,共 30 分) 1. 在并行机系统中,常用的静态互联网络有__ ___________,__ _____________, ______________________,______________________,___________________等。 2. 在并行机系统中,常用的动态互联网络有___________________________________, _____________________________________和______________________________。 3. 近代并行计算机体系结构模型包括_______ _________,___________________, _______________________,____________ ______,_____________________等。 4. 常用的并行存储访问模型(又叫并行存储结构)包括_______________________, ________________________________,_____________________________等。 5. 常用的并行程序设计模型有____________ _______,__ _ _______________, ____________________________等。 6. 大型稀疏线性方程常用迭代解法有____________________,_ _________________, _________________________,__________________________等。 7. 常用的并行计算(或算法)模型有___________________,___ _________________, ________________________,______________________等。 8. 我 国 自 行 研 制 的 并 行 计 算 机 三 大 系 列 是 ___________________________ , _____________________________,_____________________________。 二. 简要回答(每题 5 分,共 20 分) 1. 试述并行算法基本的设计技术。 2. 何谓 X-Y 选路算法何 E-cube 选路算法(可以例明之)? 3. 何谓 Amdahle 和 Gustfson 加速定律及其推导过程? 4. 何谓等效率、等速度和平均延迟可扩放性度量标准?并推导他们之间的等效性
三.综合题(每题10分,共50分) 1.假定A4×4和B×4都已加载到4×4处理器阵列上,试图示 Cannon矩阵乘法的具体过 程 2.已知A=13 试用DNS方法,逐步求出矩阵乘积 34 78 C 3.欲求解Ax=b,则构造二次函数q(x)=xAx-x2b,试证明(x)20是Ax=b 的解。 4.假定b=∑v/a,0≤j≤n-1,以n8为例,推导Fr递归计算公式 5.参照下图,对于一个8点的蝶式网络,假定:①相应的处理器p(r,1)中已保存了倍 数矩阵元素呷),0≤i≤7,1≤r≤3。②输入序列A=(2,1-i,0,1,i0,0)。 试按下述SIMD-BF模型上算法,计算出d;和d,;之值 SIMD-BF模型上的FFT算法 输入:A=(a0…,an-1) 输出:d,1和d Begin (1) for i=0 to n-1 par-do 2
2 三.综合题(每题 10 分,共 50 分) 1. 假定 A44 和 B44 都已加载到 4 4 处理器阵列上,试图示 Cannon 矩阵乘法的具体过 程。 2. 已知 = 3 4 1 3 A , − − = 7 8 5 6 B ,试 用 DNS 方法 ,逐 步求 出矩 阵乘积 ? 21 22 11 12 = = c c c c C 。 3. 欲求解 Ax=b,则构造二次函数 q x x Ax x b T T = − 2 1 ( ) ,试证明 0 ( ) = x q x 是 Ax=b 的解。 4. 假定 − = = 1 0 n k k jk bj w a ,0 j n −1 ,以 n=8 为例,推导 FFT 递归计算公式。 5. 参照下图,对于一个 8 点的蝶式网络,假定:① 相应的处理器 p(r, i)中已保存了倍 数矩阵元素 exp(r,i) w ,0 i 7,1 r 3。② 输入序列 A = (2,i,1− i,0,1,i,0,0) 。 试按下述 SIMD-BF 模型上算法,计算出 r i d , 和 r j d , 之值。 SIMD-BF 模型上的 FFT 算法 输入: ( ,..., ) A = a0 an−1 输出: r i d , 和 r j d , Begin (1) for i=0 to n-1 par-do ω0 ω0 ω0 ω0 ω4 ω4 ω4 ω4 ω0 ω0 ω4 ω4 ω2 ω2 ω6 ω6 ω 0 ω 4 ω 2 ω 6 ω 1 ω 5 ω 3 ω 7 a0 a1 a2 a3 a4 a5 a6 a7 d30 d31 d32 d33 d34 d35 d36 d37 r0 r1 r2 r3
endor (2) for rl to log n de for所有仅第r位不同且i在第r位为零的每对(iJj)par-do (2.1)d=d d (22)d,=d-1+ d endor
3 d0,i = ai endfor (2) for r=1 to log n do for 所有仅第 r 位不同且 i 在第 r 位为零的每对(i,j) par-do (2.1) r j r i dr i dr i d 1, exp( , ) , = −1, + − (2.2) r j r j dr j dr i d 1, exp( , ) , = −1, + − endfor endfor End
并行分布式试卷2 姓名_ 分数 填空选择题(20分) 1.对于高性能计算的需要是广泛的,比如在 等领 域中应用广泛 2.在并行系统中,系统互联网络有 和 类 3.近代常见的五种并行计算机体系结构模型包括 4.常用的并行计算模型有 等 5.中国工程院院士金怡濂研究员被授予2002年度国家最高科学技术奖。由 他担任总设计师主持研制的并行计算机系统为 系列 A.曙光 B神威 C.银河 D以上都不 6.关于加速比,下面的论述不对的是 A.严格的线性加速比是难以达到的 B.在某些算法或程序中,可能出现超线性加速现象 C.通信密集类的应用问题,加速比往往不是很高 D.加速比仅由算法决定,与应用问题的规模无关 二、简答题(20分) 何谓SMP结构?简述该结构的特性 2.试推导 Gustafson定律。 3.何谓并行计算的可扩放性?有哪三种典型的扩放性度量方法? 4.何谓PRAM模型?简述该模型的优缺点。 5.请举例说明并行算法的三种一般设计方法(策略)
4 并行分布式试卷 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.请举例说明并行算法的三种一般设计方法(策略)
三、综合题(60分) 1.试画出基于 Batcher比较器的双调序列8,6,4,2,0,1,3,5)的双调归并 排序网络,并在标出每个 Batcher比较器的输入和输出数据 2.使用指针跳跃技术求出下面森林的根,给出求解过程。 10 6 3.给出环上一到多(one-to-al的CT选路算法描述,并在下图中画出选路步骤 根据单一信包的通讯时间to(CT)=1n+mn+ln,试推导环上的通讯时 间 t(CT)。 (①(2③ 4.先写出矩阵乘法A-Bmn的Fox算法形式描述,然后分析Fox算法在p个 处理器组成的超立方上、使用CT选路的运行时间(注:p-超立方上的 fone-toall (CT)=(t, +mt e )log p )o 5.离散富里叶变换b=∑a20,0≤j≤n-1。对于n=8,试完成下面的蝶式 计算图中的列1到列3的相应标记,并求出b3和b6 列0 列1 列2
5 三、 综合题(60 分) 1. 试画出基于 Batcher 比较器的双调序列(8,6,4,2,0,1,3,5)的双调归并 排序网络,并在标出每个 Batcher 比较器的输入和输出数据。 2. 使用指针跳跃技术求出下面森林的根,给出求解过程。 3. 给出环上一到多(one-to-all)的 CT 选路算法描述,并在下图中画出选路步骤。 根据单一信包的通讯时间 one to one s w h t CT = t + mt + lt − − ( ) ,试推导环上的通讯时 间 t (CT) one−to−all 。 4. 先写出矩阵乘法 Ann Bnn 的 Fox 算法形式描述,然后分析 Fox 算法在 p 个 处理器组成的超立方上、使用 CT 选路的运行时间(注:p-超立方上的 t one−to−all(CT) = (t s + mtw )log p )。 5. 离散富里叶变换 − = = 1 0 n k kj bj ak ,0 j n −1 。对于 n=8,试完成下面的蝶式 计算图中的列 1 到列 3 的相应标记,并求出 b3 和 b6。 7 6 5 4 0 1 2 3 1 2 6 3 4 5 7 8 10 11 12 13 9 a0 a1 a2 a3 a4 a5 a6 a7 列0 列 1 列2 列 3